Quantum Computing 101 (no math)

The word “quantum” is derived from Latin, originally meaning “how much”. It refers to the smallest possible, indivisible unit of the universe, which we call particles. Quantum computing leverages properties of particles to perform computations.

We already use particles to do computations - take the transistor, or the physical realization of a bit. When electrons flow through the transistor, we call it a “1” state; otherwise, the transistor is in the “0” state (it's really the voltage difference, but flow is reasonable for learning). However, electron flow is not a property of the electrons themselves in the same sense that electron spin is, which is either up or down. For example, electrons are either flowing through a transistor or not flowing at a given moment, while an electron’s spin can be both up and down simultaneously. That seemingly strange behavior is governed by the laws of quantum mechanics.

Quantum mechanics describes three strange behaviors present in particles and not notably observed in larger systems of millions of particles, so they are unfamiliar to us humans. I call these three behaviors the ‘superpowers’ of quantum computing. - superposition, interference, and entanglement.

To understand these three superpowers, and how they provide an advantage in quantum computing, we need to adjust the way we think about bits. First, let’s choose a different physical realization of a bit. Take a particle (and an axis to define up and down); if its spin is up, call it 1, and if it’s down, call it 0. Great! Something very interesting just happened. Since we redefined our bit from being electron flow in transistors to simply electron spin, our new bit now is governed by the laws of quantum mechanics. We’ll call this a qubit. The most important thing is instead of thinking of our qubit as a 0 or a 1, we now think of our qubit as a probability distribution of being either 0 or 1 upon measurement. Personally, it is most intuitive to envision a histogram whenever probability distribution is mentioned. This distribution is very important - if we measure the spin, it will always be either up or down, but until we do, the possible outcomes of our measurement are governed by this probability distribution. If we have multiple qubits, we can think of them collectively as one probability distribution for all the possible combinations of 0s and 1s we can observe. We’re ready to explore the three superpowers of quantum computing.

If I flip a coin and conceal the result, we can also think of the coin as a probability distribution - 50% chance of heads, and 50% chance of tails. When I reveal the result, the state of the coin is revealed, but it was already in that state before I revealed. However, in quantum mechanics, before we reveal (measure) the particle’s spin, it is both up AND down. This is useful for computations - if we apply a function onto the qubit, treating its distribution as the input, then the function operates on all the branches of the probability distribution and the outputs will follow that same distribution. For example, let’s say our function outputs “apple” if the input bit is 0, and “banana” if it’s 1. If our qubit’s probability distribution has nonzero probability for both 0 and 1, then it is in superposition, and applying our function changes the probability distribution from 0s and 1s to either measuring either apple or banana. So, we can do many evaluations of a function in parallel, but upon measurement, we will only see ONE output of the function, according to that probability distribution. It may seem pointless to have done many computations but only having access to one of them, and you can’t even choose which one you get to measure (it's a probability). Luckily, the second superpower can partially save us.

There’s something we haven’t mentioned - the probability distribution for qubits is actually described by complex numbers. To convert from complex numbers to probabilities, you take the norm squared. Consequently, two different 'complex distributions' can lead to the same probability distributions. As strange as that may seem, this quantum mechanical property is what allows for interference - qubit probability distributions can be updated in interesting, nonclassical ways. In other words, interference allows you to selectively spike the probabilities of measuring computations you were interested in, while decreasing probabilities of those you weren’t. This is the very essence of most quantum algorithms - perform many computations in parallel, then maximize the probability of measuring the ‘important’ computations. You may not know what the important computations were unless you compare them to the rest, and interference is exactly what lets you manipulate the probabilities accordingly.

Entanglement is the property where the outcome sampled from a qubit’s probability distribution will instantaneously affect the probability distribution of another qubit. To entangle two particles, they usually need to interact physically, but they can stay entangled no matter how far apart they are.

These are the superpowers of quantum computing. Superposition and interference allow for parallel computation and ability to bias the measurement outcome to certain results. Entanglement allows for information to be correlated across qubits which also turns out to be very useful in algorithms.

To conclude with an example, imagine needing to search 1000 doors and only one has money in it. Your friend Mike has superpowers and can instantly check all the doors at once (superposition). However, if you ask him which door it was, he will only tell you what was behind one door at random. However, you can influence Mike (interference) and give him a higher probability of telling you which door had the money. Entanglement would be having multiple friends with such superpowers, and depending on what one friend said, it would bias the answers of the other friends.