Quantum Parallelism and Its Limits

The most repeated myth in quantum computing goes: "n qubits hold 2^n values simultaneously, so a quantum computer tries all answers in parallel." Half of that sentence is true and half is the myth. Let's be precise.

A qubit is a two-level quantum system whose state is a pair of amplitudes — numbers (possibly negative or complex) attached to the values 0 and 1; squaring an amplitude's magnitude gives the probability of reading that value. A superposition is any state where more than one amplitude is nonzero (plain-words intro: superposition). For n qubits, the state is a list of 2^n amplitudes, one per n-bit string. That part is true: describing 3 qubits takes 8 numbers, and describing 50 qubits takes 2^50 ≈ 1.1 quadrillion numbers.

Here is the catch: a measurement — the only way to get data out — returns one n-bit string, chosen at random with those squared-magnitude probabilities, and the superposition is gone afterward. If you build a uniform superposition and immediately measure, you have constructed an expensive random number generator — something a classical machine does trivially. The 2^n amplitudes are real, but they are not a readable array. "Tries everything at once" confuses storing a description with delivering answers.

Worked example 1 — computing the distribution by hand. The Hadamard gate H sends |0> to (|0> + |1>)/√2, i.e. amplitude 1/√2 ≈ 0.7071 on each value (background: Hadamard and superposition).

1. Each of the 3 qubits independently gets amplitudes (0.7071, 0.7071).
2. The amplitude of any specific 3-bit string is the product of one factor per qubit: 0.7071 × 0.7071 × 0.7071 = 1/√8 ≈ 0.35355.
3. The probability of that string is the square: 0.35355² = 1/8 = 0.125.
4. Check: 8 strings × 0.125 = 1.000 — probabilities sum to one. ✔
5. Expected count at 1000 shots: 1000 × 0.125 = 125 per string, give or take shot noise.

The same construction on n qubits gives 2^n amplitudes of 1/√(2^n) each. At n = 10 that is 1,024 amplitudes; at n = 50, about 1.1 × 10^15; at n = 300, more than the estimated number of atoms in the observable universe. This is why classical simulation of general circuits hits a wall (see simulation limits) — and it is still not, by itself, a speedup.

Three hard facts stand between the 2^n amplitudes and you:

• Sampling, not reading. One shot yields one string. Measurement is destructive: after it, the register holds only the measured string (details: measurement).
• Repetition gives statistics, slowly. Re-preparing and re-measuring estimates probabilities, never signs or phases directly, and estimating all 2^n of them takes a number of runs that grows exponentially with n. Reconstructing a full state this way is called tomography, and its cost is the point: it erases any exponential advantage.
• Holevo's bound (proved theory, 1973): no matter how cleverly you encode, one measurement of n qubits can convey at most n classical bits of information. A 300-qubit state may need 2^300 numbers to describe, yet a readout hands you at most 300 bits.

So quantum parallelism is real as state-space arithmetic and useless as direct readout. Every working quantum algorithm respects this: it never tries to read the list. It reshapes the list first.

Interference means amplitudes add like signed numbers: same sign reinforces, opposite signs cancel. It is the only lever a quantum algorithm has over what the measurement will show.

Worked example 2 — one qubit, step by step. H maps the amplitude pair (a₀, a₁) to ((a₀+a₁)/√2, (a₀−a₁)/√2). Start at |0>, i.e. (1, 0):

1. First H: ((1+0)/√2, (1−0)/√2) = (0.7071, 0.7071). A fair-coin superposition.
2. Second H: new amplitude of 0 is (0.7071 + 0.7071)/√2 = 1.4142/1.4142 = 1. New amplitude of 1 is (0.7071 − 0.7071)/√2 = 0/1.4142 = 0.
3. The two paths leading to |1> — "was 0, flipped" and "was 1, stayed" — carry equal and opposite amplitude and annihilate. The paths to |0> reinforce. Probability of 0: 1² = 1, exactly.

A classical random process can never do step 3: probabilities are non-negative and cannot cancel. Signs (more generally, phases — see amplitudes and phase and the interference chapter) are the resource that separates quantum from classical computation.

Put the two halves together and the design problem of this whole course appears:

• You can touch all 2^n strings with amplitude in one circuit — including one oracle query made in superposition.
• You cannot read the results out; you get one sample.
• Therefore a quantum algorithm must arrange gates so that paths to wrong answers interfere destructively and paths to right answers interfere constructively — moving probability onto strings that reveal the answer before the measurement.

Every algorithm ahead is a different way of pulling that off: Deutsch–Jozsa gets certainty in one query, Bernstein–Vazirani reads a whole hidden string at once, and Grover ratchets probability onto a marked item step by step. When someone says a quantum computer "tries everything at once," the accurate correction is: it interferes everything at once — and that is harder to exploit, and more interesting.

Both circuits here use only single-qubit H gates — the easy part of real hardware; using an archetype figure of 0.05% error per single-qubit gate (illustrative, not a vendor number), six gates barely dent the result. Readout dominates: at an archetype 1% error per qubit read, three qubits all read correctly with probability 0.99³ ≈ 0.970, so expect roughly 97% clean shots.

One honest subtlety: a flat histogram is weak evidence by itself, because fully decohered (noise-scrambled) qubits also produce a flat histogram. It is the second experiment — H twice returning deterministically to 000 — that certifies real superposition and coherent interference, which is why patterns like it appear inside hardware benchmarking suites. Compare devices' measured error rates on readout fidelity and coherence times, or browse the QPU index and try both circuits in the Lab.