Learn · 04
Grover's search, step by step
Picture a lock with sixteen possible codes, from 0000 to 1111. An ordinary computer finds the right code by trying them one at a time: about eight tries on average, sixteen at worst.
A quantum computer can put four qubits into an even superposition of all sixteen codes. Each code has amplitude 0.25, so measuring right away gives each one a 6.25% chance. Grover’s algorithm raises the right code’s chance to about 96% using two operations, repeated.
The test. The quantum version of trying the lock is a gate that flips the sign of the right code’s amplitude and leaves every other code alone. It works on the whole blend in one go, but it doesn’t say which code is right. After the test, the right code’s amplitude is −0.25 and the rest are 0.25. Every code still has a 6.25% chance of being measured, because squaring hides the sign. The answer is marked, but invisibly.
The reflection. The second operation moves every amplitude to the opposite side of the average of all sixteen, keeping the same distance. If an amplitude is 0.1 above the average, it ends up 0.1 below it.
Here is the first round in numbers:
- After the test, fifteen codes are at 0.25 and the right one is at −0.25. The average is (15 × 0.25 − 0.25) ÷ 16 = 0.22.
- Each wrong code is 0.03 above the average, so the reflection moves it to 0.03 below: 0.19.
- The right code is 0.47 below the average, so the reflection moves it to 0.47 above: 0.69.
The right code’s chance has gone from 6% to 47% (0.69 × 0.69). The wrong codes each dropped from 6.25% to about 3.5%.
That’s why only the right answer grows, and it’s interference at work. The test makes the right code the only amplitude far from the average. The reflection moves each amplitude by twice its distance from the average, so the right code moves a long way and the others barely move. The next round starts from the new amplitudes and does the same again.
In the simulation, each column is one code. Dots above the line are positive amplitude and rings below it are negative. The right code is labelled, but the algorithm never sees the label. It only has the test. Round runs one test and one reflection. Measure reads the four qubits.
Three rounds take the chance to 96%. A fourth drops it to 58%, because the reflection keeps pushing the right code’s amplitude past the top and back down. The best number of rounds can be worked out from the number of codes beforehand, so the algorithm knows when to stop.
For sixteen codes, three rounds instead of about eight tries is a small saving. It grows with size. A six-digit lock has a million codes. Trying them one at a time takes about 500,000 tries on average. Grover’s algorithm takes about 785 rounds. If each try and each round took one second, that’s six days against thirteen minutes. In general the rounds grow with the square root of the number of codes: a hundred times more codes needs ten times more rounds.
In practice, each round on today’s quantum hardware is much slower and less reliable than one check on an ordinary processor, which manages billions per second. For any search a current quantum computer can hold, an ordinary computer finishes first. The square-root saving only pays off on searches far larger than today’s machines can run.