Grover Search

Grover's algorithm finds a marked item among N candidates using about (π/4)·√N oracle calls instead of the classical average of N/2, by repeatedly reflecting amplitudes so that probability piles up on the marked item. On 2 qubits a single iteration succeeds with probability exactly 1, and you can run that circuit — and a 3-qubit version with success probability exactly 25/32 — below.

What problem does Grover's algorithm actually solve?

Unstructured search: you have N candidate answers and a yes/no test, and nothing about the structure of the problem tells you where to look. Classically you test candidates one at a time — on average N/2 tests, worst case N.

In the quantum query model (introduced in what is a quantum algorithm), the test is packaged as an oracle: a quantum circuit that recognizes the answer without telling you where it is. It flips something — here, the sign of an amplitude — exactly when its input is the marked item. Grover's algorithm finds the marked item using about (π/4)·√N oracle calls. For a million candidates that is roughly 785 calls instead of an average of 500,000.

Two honest framings before we start. First, this is a proved speedup in query count — a theorem, not a conjecture — but query count is not wall-clock time; the next chapter does that accounting and it is sobering. Second, the popular description "the database is searched in superposition" 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 trivial — measurement then samples one random string. The entire cleverness of Grover is what happens between the oracle calls.