by Thomas Fernandes
In a previous post I tried to explain most of quantum physics using the analogy of a spinning wheel. The blur of the spinning as a wave function, the stopped spoke as a particle. Now I want to see if the same wheel can explain quantum computing. To understand what makes a quantum computer different, it helps to start with the classical one.
A classical computer runs on bits, each one either 1 or 0, on or off. In wheel terms bits are levers, either up or down, fully committed to a single state. These levers are arranged into logical gates. AND only rises if both inputs are up. OR rises if either is up. NOT flips whatever it receives. String enough gates together in clever ways and you can compute almost anything.
Your processor contains billions of transistors doing the flipping for you, each one a tiny electrically controlled lever. Computing speed is limited by how fast a switch can be flipped, which is gated by how fast an electron can travel across the transistor. Smaller transistors mean shorter distances and faster switching, which is why chip manufacturers spent decades shrinking them down to a few nanometers.
A quantum bit, a qubit, is more like our wheel than a lever. While spinning it holds all positions in superposition, not restricted to 0 or 1 but everything in between simultaneously. When stopped it resolves to one answer. Define the upper half of the wheel as 1 and the lower as 0, and an even spin gives you 50/50 odds. You can bias those odds by adjusting what portion of the 360 degrees counts as 1 and which counts as 0. If you ever read about quantum gates, this is what they do, they set the qubit’s wave function in a controlled way before measurement. Get the wheel spinning if you will.
A quantum computer does not compute by flipping switches sequentially since all switch states are true at the same time. The infinitely fast wheel is both 0 and 1 all the time. So, the steps in quantum computing are not computation steps in the classical sense. They are steps necessary to stop the wheel on the correct solution. The difference becomes clearer with a specific example.
Say you want to find the correct combination of a four-digit lock, there are 10 000 possibilities. You can represent them in 14 bits, each either up or down, which give 2 options for each of the 14 bits 214 =16 384, enough to contain all code combinations. Now a classical computer would test them one by one. 00000000000000, does this combination open the lock? No? Does 00000000000001? It checks each candidate against the correct answer the way a search function checks each word in a document against the word you typed. For the lock you can get lucky on the first try or unlucky and get it on the 10 000th try. On average it takes 5 000 attempts.
Now scale up. A modern encryption key is not 14 bits but something closer to 128, giving 2 to the power of 128 possible values. A classical computer checking a billion combinations per second would take longer than the age of the universe to check all combinations. This is why encryption works. Checking your code is fast, finding the correct one in a haystack is not.
Which is why it is a classic example of a quantum computing application known as the Grover algorithm. Since in quantum computing all states exist simultaneously in superposition, the correct answer is already in there. You don’t need to search; you only need to check. The challenge is now completely different.
Instead of 14 bits, use 14 qubits so 14 wheels. Set all wheels spinning simultaneously. While spinning each wheel is in superposition. The system holds all 10 000 possible combinations at once. You can imagine that, by spinning, each wheel will get through 1 and 0 impossibly fast and all combinations will be tested instantly. If you measure now, that is, if you stop the wheels, all you will get is a random combination. What you need is to make sure that when you stop, only the correct answer emerges. This is what the Grover algorithm is for.
First all wheels are entangled. That is, they interact with each other, which we represent by connections at the axles. Initially those connections are loose and each wheel rotates freely. To check the correct answer, quantum computing uses “oracles”, which are mechanisms that recognize the correct combination when it appears during the spinning, the way a lock recognizes the right key.
In this case, when the correct combination comes around, the oracle applies a (conceptual) rubber band, connecting all fourteen wheels together at that moment. The band is elastic and light. The wheels continue spinning but now with a slight restoring force drawing the system back toward the correct answer whenever it drifts away.
At each subsequent pass through the correct position, they get another band that further constrains the system. Two bands make the oscillation tighter. Four bands tighter still. To stop all 14 wheels in the correct position requires 157 bands so 157 steps. To be compared to the 5 000 average computation steps in classic computing.
Now scale up here as well for the 128 bits of encryption. More wheels, more inertia as a system, more passes for the bands to stabilize. But instead of doubling the possibilities, each new wheel only multiplies the inertia by . So now the 128 bits can be solved in a few hundred years. Still very long but immensely shorter than the age of the universe. This square root scaling is the signature of Grover’s algorithm and why it is more efficient. I explore it a bit more at the end for those who want to go deeper.
Grover’s algorithm represents the most direct application of quantum computing. It does not try to understand the problem or uncover any structure. Instead, it leverages the particularities of quantum superposition to explore all possible solutions. The use case of a random code is one of systematic search where computations are inefficient. But most of real life has patterns and even codes are not chosen randomly: a third of four-digit codes can be found by testing only 61 combinations. Usually, algorithms are designed to reduce computing time by cleverly exploiting patterns instead of checking every option one by one.
If you want all the prime numbers up to 1 000 000, one naïve strategy would be to take each number in turn and test whether it is divisible by any smaller number. A search similar to the one we mentioned that can be very, very long. Instead of asking Is this number divisible? is this one? and this one? You can also start from the opposite direction. If 2 is prime, then every multiple of 2 (4, 6, 8, 10, …) cannot be prime and you eliminate all multiples in one sweep. Then move to 3 and eliminate 6, 9, 12, 15, and so on. Continue this process upward. Rather than testing each number individually, you remove entire patterns at once. What remains at the end are exactly the primes. So what use is quantum computing in this most common scenario of patterns to exploit?
Well, those patterns still need to be computed and if they usually save a lot of time, sometimes the pattern is just too long to compute to be useful. To see why, imagine a 12-hour clock. If you move forward two hours at a time from 12, you land on 2, 4, 6, 8, 10, and back to 12 in six steps; if you move three hours at a time, you land on 3, 6, 9, 12 in four steps. In both cases, the number of steps, which we can call the period, gives you a usable clue to find the factors of 12, here the step times the period gives you 12. But classically this pattern is useless since to find the period, you’d have to compute every step one by one, which already requires knowing the factors in the first place. You only get a shortcut if the periodicity comes “for free”. Or via quantum computing.
Specifically, Shor’s algorithm factors large numbers into their prime components. The pattern to exploit would be, like the clock, to use the repeating period to reach a number much larger than 12 to find the factors. Because the period is even longer to find than the solution and the problem has no shortcuts, it is used as an encryption method. Quantum computing, however, can find the periodicity very fast.
Imagine encoding your function in many wheels spinning at slightly different speeds. Most of the time their spokes point in different directions. But at one specific moment in the cycle all the spokes align simultaneously. The time between those alignments is the period and this rhythm is visible within a few measurements unlike Grover, which needed you to stop all the wheels in the correct position. Once you have the period, a classical computer finishes the job in no time using a simple mathematical relation that converts the period into the factors you were looking for. In Shor’s algorithm, the quantum part finds the period and the classical part computes the solution.
This is a conceptual explanation of how it works. Wikipedia has once again the full mathematical description, but it becomes more complicated to follow unless you are already familiar with many mathematical concepts.
The important point is that quantum does not simply compute faster in a traditional sense. For example, if you wanted to compute 10 different outcomes, quantum computing would be slower than traditional since it naturally resolves randomly. So, you are not guaranteed to explore all options in 10 steps, like throwing a dice until you have seen all faces. If the reason you want to explore the 10 outcomes is to find the correct one, quantum computing can be useful since it holds all combinations at once. You still need to find a way to remove all unwanted outcomes, however, which is the “computing” time of quantum computers. This can not only be used to find the correct option out of many but also to find patterns to exploit.
There is one more application of quantum computing worth mentioning, and in some ways, it is the most natural one. Rather than engineering interference to compute, you build a quantum system that behaves like a quantum phenomenon you want to study.
In most cases the property of material to our eyes is encoded in the pointer states discussed last time. We do not need to worry about quantum aspects or entanglement at that scale since they are so diluted by decoherence. At small scales quantum states can be computed by systematically exploring all combinations. However, for larger systems we face an exponential wall. Two possible states for 50 electrons yields 250, roughly eleven days to solve for a top computer, long but not unusable. The real problem runs deeper.
Electrons are not binary. Like the wheel that can be anywhere between 0 and 1, each electron exists in a superposition of states with continuous amplitudes. Describing the full quantum state means tracking not just which combinations are possible but how much of each combination is present simultaneously, and how all those combinations interfere with each other. The mathematical object encoding all of this has 2100 entries. That is incomputable.
A quantum computer sidesteps this entirely by being the molecule rather than describing it. Build a 50-qubit network whose couplings mirror the electron interactions of the target material and let it evolve. Since it obeys the same physical laws, you observe the same properties emerging naturally. You are not solving an equation. You are running an equivalent physical system and reading off what it does.
What comes out is not a mathematical solution; only the simulation of the system without the underlying math. The math exists only in the physical state of the qubits. What you get instead are the same pointer states you would measure on the real material such as bond energies, magnetic ordering or conductivity. The power is not in replacing understanding but in accessing materials that cannot be synthesized or are too unstable to study, reaction transition states that last only nanoseconds or properties of hypothetical materials optimized for a target behavior before anyone attempts to make them.
This is where many researchers believe the first genuinely useful quantum advantage will appear. Not in breaking encryption, which can be addressed through longer keys or alternative methods, but in understanding the quantum behavior of matter itself. Which in turn could help design higher-temperature superconductors among other things.
As of now, no interesting computation has been done using quantum computers. The obstacle is isolation from the environment. Every stray interaction acts like a tennis ball hitting a spinning wheel, nudging it off course. Engineers can compensate by spreading each computation across multiple wheels, to obtain a clear signal despite perturbation. But redundancy is not free and too many qubits spent on error correction means not enough remaining for computation. To be usable we will need to make wheels less easily disturbed by the tennis balls the universe keeps throwing.
Grover in more detail:
For those who want to look deeper under the hood, here is the same mechanism in quantum terms. In quantum computing, to represent possible states, people actually use Bloch spheres, almost like a wheel but with the additional dimension to encode something our wheels keep silent: phase. Phase describes if you are in sync or not. Two waves of the same amplitude in sync will have their peaks rise twice as high, and their troughs fall twice as low. But if they are out of sync (if one reaches its peak exactly when the other reaches its trough) they interfere destructively, each canceling the other out.
With that in mind, going back to our 14 qubits, all possible combinations exist in superposition within the entangled 14 qubits in sync. The oracle first tags the correct answer by inverting its phase, flipping it from in sync to out of sync with everything else. Each subsequent step is then designed so that all the in-sync amplitudes cancel each other out through destructive interference while the out-of-sync correct answer survives and grows. This is the repetitive damping by the rubber bands. The more phases you have to cancel (more wheels you have to stop) the more steps you need. This is the mathematical foundation that leads to the scaling and the 157 steps for our lock combination. Again Wikipedia has all the equations if you are so inclined.
***
You can find my other essays at Librotium. Fair warning, none of them are about quantum physics. You have a criticism of advice and an exploration of human monogamy and polygamy.
Enjoying the content on 3QD? Help keep us going by donating now.