Marin Ivezic
Ten qubits in equal superposition carry 1,024 amplitudes at the same time. The number is correct, and it feeds the most repeated claim in quantum computing: that a quantum computer tries every possible answer at once and returns the right one.
The first half of that claim is defensible. The second half is false, and correcting it takes about two pages.
We teach the distinction in the first hours of our technology programs, because almost every later confusion about quantum speedups traces back to it. Three ideas are usually collapsed into one. Superposition is a state. Quantum parallelism is what a circuit does to that state. Interference decides which parts of the result survive to the measurement. Keep the three apart and you can say precisely what a quantum computer does and does not do.
Superposition is a state, not a computation
A classical bit is 0 or 1. A qubit can be in a combination of both, described by an amplitude attached to |0⟩ and another attached to |1⟩. Amplitudes are complex numbers, and the fact that they are complex is what separates a quantum computer from a coin flip.
Registers scale the same way. Three qubits can hold an equal superposition of all eight basis states, from |000⟩ to |111⟩. Ten qubits hold 1,024. Fifty hold more than a quadrillion, and the register is in all of them simultaneously, with one amplitude for each.
Then we measure, and the arrangement ends. Measurement returns a single basis state, chosen at random, with probability equal to the squared magnitude of that state’s amplitude. Everything else is discarded. Prepare fifty qubits in an equal superposition, measure them, and you have an expensive random number generator.
Superposition on its own therefore computes nothing. It holds possibilities, and it hands back exactly one of them when we look.
What parallelism actually buys
Suppose we have a circuit that computes some function f. Feed that circuit a superposition of all 2^n possible inputs, and one pass produces a superposition of all the pairs (x, f(x)). Every input, one operation. David Deutsch described this in his 1985 paper on the universal quantum computer and gave it the name quantum parallelism.
Now measure the result. You get one pair, and you do not choose which one. A classical computer could have produced that same pair by evaluating f once on a random input, at a fraction of the cost in hardware, cooling, and error correction.
So quantum parallelism, used naively, buys nothing. The speedups come entirely from what happens between the parallel evaluation and the measurement.
Why cancellation is the real mechanism
Classical randomized algorithms also cover enormous numbers of possibilities at once. A random process over n bits holds a probability distribution across 2^n outcomes, and nobody calls it exponentially fast. The difference is cancellation. Probabilities are non-negative, so they only accumulate. Amplitudes are complex, so two computational paths arriving at the same wrong answer can arrive with opposite signs and destroy each other.
Designing a quantum algorithm therefore means arranging the interference so that the paths leading to wrong answers cancel and the paths leading to the right answer reinforce. Nothing else in the machine produces a speedup.
Deutsch’s algorithm, one query instead of two
One line of notation follows, and it is the only one in this article.
Take a function f with one bit in and one bit out. Four such functions exist. Two are constant, meaning f(0) = f(1), and two are balanced, meaning f(0) ≠ f(1). We want to know which kind we have, and we don’t care about the individual output values. Classically that costs two queries. You have to look at both outputs and compare them.
The quantum version costs one. Put the input qubit into an equal superposition and prepare the output qubit in the state (|0⟩ − |1⟩)/√2. Run the circuit once. Each branch of the superposition picks up a phase of −1 exactly when f(x) = 1, so the input register becomes (−1)^f(0)|0⟩ + (−1)^f(1)|1⟩, up to normalization.
If f is constant, the two terms share a sign and the branches remain in phase. A final Hadamard gate makes them reinforce at |0⟩. If f is balanced, the signs differ, the branches are out of phase, and the same gate sends the register to |1⟩. One measurement returns the answer with certainty.
We never learn f(0). We never learn f(1). We learn a relation between them, and that relation is the only thing the interference leaves standing. Every known quantum speedup works this way: the algorithm reports a global property of the function, and the individual values cancel before anyone looks.
Deutsch and Richard Jozsa generalized the construction in 1992 to n input bits, given a promise that f is either constant or balanced. A deterministic classical algorithm needs 2^(n−1) + 1 queries in the worst case, and the quantum version still needs one. Allow a classical algorithm to answer correctly with high probability instead of certainty, and a handful of random queries will do. The exponential separation is real and it holds specifically against deterministic classical algorithms.
Shor and Grover follow the same rule
Shor’s 1994 algorithm converts factoring into period-finding. It evaluates modular exponentiation across a superposition of exponents, which is the parallel step, and then applies a quantum Fourier transform. The transform makes amplitudes reinforce at values related to the period of the function and cancel almost everywhere else. Measurement returns a value tied to the period, and classical number theory recovers the factors from there. The parallel step only prepares the state. The Fourier transform produces the answer.
Grover’s 1996 search algorithm begins with an equal superposition over N candidates and repeats a cycle of oracle marking and diffusion roughly (π/4)√N times, raising the amplitude of the marked item and reducing the rest. The gain is quadratic rather than exponential. In 1997, Bennett, Bernstein, Brassard and Vazirani proved a matching lower bound, so no quantum algorithm searches an unstructured space in fewer than order √N queries. The quadratic gain is a ceiling, not a starting point.
Where the misconception costs money
Once the three ideas are separated, evaluating a quantum claim becomes concrete. State-space size is not evidence of anything. The useful questions are narrower:
- Which algorithm, named, with a citation?
- What produces the interference, and has anyone shown it works for this problem class rather than a related one?
- What do the constant factors and the error-correction overhead do to the advantage on hardware that exists?
Most advantage claims we see in the market fail at the second question, and they fail quietly. The pitch describes an exponentially large state space, then moves to a business outcome, and no algorithm is named in between.
The same discipline applies to security planning. Grover’s quadratic gain against symmetric keys is often quoted as halving effective key strength, and the practical picture is less favourable to the attacker than that, since Grover parallelizes poorly and the iteration depth is enormous.
What to carry into the next conversation
Superposition gives a quantum computer many states. Parallelism applies one operation to all of them. Interference determines what survives the measurement, and interference has to be designed problem by problem. No general method exists for finding it, which is why the list of algorithms with proven quantum advantage is still short after four decades.
We build that sequence into the foundations of Quantum Academy’s technology certification programs, ahead of any hardware or vendor material, so that candidates read algorithm papers and roadmaps with the right question in hand. You can see the current programs and their prerequisites at quantumacademy.com/.