Interference

The popular picture says a quantum computer tries every answer at once. It does not, and the way to see why is to compare it with a coin. Flip a fair coin and you get heads or tails with equal odds. Flip it again and you are still at equal odds: randomness only ever blurs. Scott Aaronson’s blog carries the same warning in its banner, that quantum computers will not solve hard problems instantly by trying all solutions in parallel.

A qubit behaves differently because its two outcomes carry amplitudes, and amplitudes are added before they are squared into probabilities. The Hadamard gate H turns |0⟩ into an equal mix of |0⟩ and |1⟩ with amplitude 1/√2 each, so a measurement now gives 50/50, the same as the coin. Apply H again and there are two paths to each outcome. Both paths to |0⟩ contribute +½, which sum to 1. The paths to |1⟩ contribute +½ and −½, which sum to 0. The wrong answer has cancelled, and |0⟩ now comes out every time.

Put a phase gate between the two Hadamards and the cancellation can be dialled. With a phase φ in the middle, the amplitude for |0⟩ is (1 + e^{iφ})/2, so the chance of |0⟩ is cos²(φ/2). At φ = 0 it is 1, at φ = π/2 it is ½, and at φ = π it is 0, so every shot gives |1⟩. The path diagram shows the same sum as arrows: the two arrows to each outcome, added head to tail, in the phase colours.

Now the myth. Put three qubits through a Hadamard each and they hold eight amplitudes of equal size, one per three-bit string. Measuring gives exactly one string, chosen at random with equal odds, so nothing has been tried “in parallel” in a way you can read out. What an algorithm does is arrange its gates so that the amplitude of wrong answers cancels and the right one is left large. Aaronson’s post on Shor’s algorithm explains period finding and the Fourier transform with clocks, which is this cancellation at work.

The next page, Grover’s search, is this effect repeated: each step moves amplitude from the wrong answers towards the right one.

Grover’s search →