Grover's Search

You have a phone book with a million entries, shuffled into random order. You know the number you want; you need the name.

The ordinary way, you check entries one at a time. On average, half a million checks.

Grover's method finds it in about 785.

One round, two moves

Mark it. The black box puts a minus sign on the entry you want. Nothing visible has changed yet — the odds are all still identical.

Fold everything about the average. Work out the average of all the amplitudes and reflect every one across it. The marked entry, sitting below the average because it went negative, gets thrown well above it. Everything else drops a little.

Repeat. Each round nudges the right answer up a bit more, and the wrong answers down.

You have to know when to stop

This is the part that surprises everyone.

Grover is a rotation, and rotations keep going. Do about (π/4)√N rounds and the right answer is nearly certain. Keep going and it rotates straight past — the odds start coming back down.

Run it twice as long as you should and you are worse off than when you started.

Where it helps, and where it does not

Grover needs nothing but a way to check a candidate, so it applies almost everywhere: puzzles, password cracking, database lookups.

Two things take the shine off.

First, this is the ceiling, not the floor. Four researchers proved in the 1990s that no quantum method can ever do unstructured search faster than this. There is no better version coming.

Second, square-rooting a million gives you a thousand — which is lovely, but the overhead of running a real error-corrected quantum computer can swallow the whole gain. Current estimates suggest Grover only beats an ordinary machine on problems so large that neither one finishes.