Grover’s algorithm: quantum search
Lesson 11 of 23 in the course “Quantum”. Free, with animations and a quiz.
The box problem
You have N closed boxes and a gift in one of them. No hints: open, look, close. On average you’ll open half the boxes, in the worst case all of them. The quantum version: we have an “oracle”, a circuit that says whether a box is the right one. In 1996 Lov Grover of Bell Labs showed how to find the gift in about √N questions. For a million boxes that’s about 800 questions instead of half a million.
How it works: mark and reflect
First, H gates give every box the same amplitude. Step 1: the oracle puts a minus on the right box’s amplitude, the marking step from our recipe. Step 2: “reflection about the mean.” The mean dropped slightly because of the minus, and every amplitude is flipped around it. The ordinary boxes get a bit lower, while the negative one jumps way up. Repeat “mark + reflect”, and the right box grows each time.
The key is stopping in time
A non-obvious detail: Grover isn’t “the longer, the better.” The right box’s amplitude grows like a rotating arrow. For 64 boxes the chance is nearly 100% after about 6 steps, and if you keep going, the arrow overshoots and the chance starts to fall. So the number of steps is computed in advance: about π/4 · √N. If you don’t know how many gifts there are, there are clever variants of the algorithm, but that’s detail.
Grover and encryption
Guessing a cipher key is exactly searching for one box among a huge number. AES-128 has 2 to the power 128 options. Grover takes the square root, leaving 2 to the power 64 steps, so “128-bit” security becomes “64-bit.” In practice even that is a lot: Grover’s steps run strictly one after another, and you can’t spread them over thousands of machines as easily as ordinary brute force. But the cure is simple and already in use: AES-256 still holds 128 bits after Grover.
The speed limit
Maybe someone will invent an even faster search? No: in 1997 four researchers, Bennett, Bernstein, Brassard and Vazirani, proved that for “blind” search √N is the limit for any quantum computer. This leads to an important conclusion. Many hard problems, like the optimal delivery route, essentially boil down to brute force. A quantum computer can speed them up at most to the square root, not make them instant. Nobody has found an exponential speedup for such problems.
Where Grover is really useful
It sounds like “quantum Google”, but for searching an ordinary database Grover is nearly useless. To query the oracle, the data first has to be loaded into quantum memory, which already takes on the order of N steps and eats the whole gain. The real value is where the “boxes” aren’t stored but computed by a formula: guessing keys, checking solutions, a subroutine inside more complex algorithms. And all of it will need large error-corrected computers.
Check yourself
- Roughly how many Grover steps for 10,000 options?
Correct answer: About 80. √10,000 = 100, and π/4 · 100 ≈ 79. A quadratic speedup, not an instant one. - A friend ran three times more Grover steps than needed, “to be safe.” What happens?
Correct answer: The chance drops: the arrow overshoots the answer. Grover is a rotation. Past the optimum, the right box’s amplitude shrinks again. - Should AES-256 be replaced urgently because of Grover?
Correct answer: No: after Grover it still has 128 bits of security. Grover halves the bit strength, and 128 bits is considered safe. That’s why AES-256 is recommended for the long term.
← The “tries everything at once” myth Shor’s algorithm and RSA →