Quantum Cookbook

Part V · Chapter 28

Grover's Algorithm

Read ~24 min Prerequisites Ch. 22–23 Tools amplitude-amplification widget, code cell Live
Basic

Search an unsorted list of N items for one marked item, with no structure to exploit — classically, there's no better strategy than checking items one by one, ~N/2 checks on average. Grover's algorithm does it in roughly √N queries. This is a real, hard, generically useful problem — not engineered to showcase a gap like Ch. 26's promise-based one — and the speedup, while not exponential, is genuinely useful and provably optimal.

The two ingredients

One Grover iteration is two steps applied in sequence:

  1. The oracle — exactly Ch. 23's phase oracle, flipping the sign of the marked item only.
  2. The diffusion operator — reflects every amplitude about their average value. (|0⟩ Hadamard transform, flip the sign of everything except |0⟩, Hadamard transform back — three steps that together perform exactly this reflection.)
Fig. 28.1 — one Grover iterationoracle, then diffusion, repeated
|s⟩ Oracle Diffusion × (√N times)
Repeat this whole block ≈ π/4·√N times — not more, not fewer. Fig. 28.2 will show you exactly why the count matters this precisely.
Intermediate
Fig. 28.2 — adjust N, the marked item, and the iteration countwatch it overshoot if you go too far

Geometric picture

P(marked) after each iteration so far

Each iteration rotates the state vector by a fixed angle toward |marked⟩ — keep dragging the iteration slider past the optimum and watch P(marked) come back down. More iterations is not always better; this is the chapter's central, easy-to-miss subtlety.
Advanced

Why √N is provably the best possible

Unlike Ch. 26's exponential gap, Grover's quadratic speedup isn't just the best anyone has found — it's been proven optimal: no quantum algorithm, of any design, can solve unstructured search in fewer than roughly √N oracle queries (the BBBT lower bound, 1997). This makes Grover's algorithm a rare case where you know, with mathematical certainty, that you're not leaving easy speedup on the table. It generalizes directly too: with t marked items out of N, the optimal iteration count becomes ≈(π/4)√(N/t) — search gets easier the more targets there are, exactly as you'd expect.

Fig. 28.3 — code, runs in your browser
Watch the probability climb toward the optimal iteration, then fall back down for the extra 3 iterations past it — the same overshoot Fig. 28.2 shows interactively.
Check your understanding

What two operations make up one Grover iteration?

The phase oracle (flips the sign of the marked item) and the diffusion operator (reflects every amplitude about their average).

Check your understanding

Roughly how many iterations does Grover's algorithm need for N items, and how does that compare to classical search?

≈(π/4)√N — a quadratic speedup over the classical ~N/2 average checks.

Check your understanding

What happens if you run more iterations than the optimal count?

P(marked) decreases again — the state vector keeps rotating past the marked item rather than stopping there. More iterations is not always better.

Check your understanding

Is Grover's √N speedup the best anyone has found so far, or is it provably optimal?

Provably optimal — the BBHT lower bound proves no quantum algorithm can solve unstructured search faster than roughly √N queries, for any algorithm design whatsoever.

Check your understanding

How does the optimal iteration count change if there are t marked items instead of 1, out of N total?

It becomes ≈(π/4)√(N/t) — fewer iterations are needed as the number of targets increases, since each iteration amplifies a larger combined target probability.

Review queue

Scroll back to a chapter's quiz cards to review them once they're due — a full cross-chapter queue view is a planned upgrade.