Grover Search
Grover's algorithm finds one marked item among N choices. It uses about (π/4)·√N oracle calls, instead of the N/2 tries a normal search needs on average. It works by flipping and reflecting amplitudes over and over, so the chance piles up on the marked item. On 2 qubits, one round succeeds with a chance of exactly 1. You can run that circuit below, plus a 3-qubit version that succeeds with a chance of exactly 25/32.
What problem does Grover's algorithm actually solve?
Grover's algorithm solves unstructured search. You have N possible answers and a yes/no test. Nothing about the problem tells you where to look. Think of a combination lock with no clues. A normal computer tests the choices one at a time. On average that takes N/2 tests. In the worst case it takes N.
In quantum query counting (introduced in what is a quantum algorithm), the test comes as an oracle. Here the oracle is a quantum circuit that can spot the answer without telling you where it is. It flips something when its input is the marked item. In this case it flips the sign of an amplitude. Grover's algorithm finds the marked item with about (π/4)·√N oracle calls. For a million choices that is about 785 calls, instead of 500,000 on average.
Two honest notes before we start.
- This speedup in query count is proved. It is a theorem, not a guess. But query count is not clock time. The next chapter does that math, and the result is sobering.
- People often say "the database is searched in superposition." That misleads. There is no database. The oracle is a function you must build as a circuit. And as we saw in quantum parallelism and its limits, putting all inputs into superposition is easy. Then measuring gives you one random string. All of Grover's cleverness is in what happens between the oracle calls.
- How do you boost the right answer without knowing which one it is?
- Run it: two-qubit Grover, one iterationINTERACTIVE
- Re-aim the oracle at a different itemINTERACTIVE
- What changes with three qubits?
- Run it: three-qubit Grover, one iterationINTERACTIVE
- How many rounds do you need?
- What does Grover look like on real hardware today?
You’ve read the opening of chapter 5. Pro unlocks the other 7 sections — plus every chapter of every course, with circuits you can run right on the page. That’s $11.99 a month, about the price of a coffee, or $99.99 a year (save 30%). The first chapter of every course, and the whole math course, stay free.