25. Grover's Algorithm
25.1Unstructured search
The problem: given a boolean predicate P on N = 2ⁿ items with the promise that M items satisfy it, find one — with P available only as a black box. "Unstructured" is the operative word: no ordering, no gradient, no locality to exploit; the only operation is "test item x". This is the right model for inverting hash functions, for search spaces where checking is cheap but constructing is impossible, and as the worst-case backbone for constraint satisfaction. It is deliberately the most pessimistic model of search — which is what makes the quadratic speedup credible: if you cannot beat √N here, no cleverness was assumed anywhere.
25.2Classical complexity
Classically, testing items one at a time needs, on average, N/2 queries to find a marked item (N in the worst case), and no classical algorithm does better — for unstructured search the birthday-style tricks do not apply because the answers are independent bits. Grover (1996) needs Θ(√N) quantum queries, and Bennett–Bernstein–Brassard–Vazirani (1997) proved that is optimal: no quantum algorithm beats the quadratic factor for black-box search. Two consequences worth internalizing: the speedup is quadratic, never exponential — a 128-bit key loses to Grover like a 64-bit key to classical brute force — and NP-complete problems inherit only this quadratic improvement (Part VIII).
25.3The oracle
The black box enters as a phase oracle: O|x⟩ = (−1)^{P(x)}|x⟩ — flip the sign of marked states, leave the rest. Realizing it from a classical circuit for P is mechanical: compute P(x) into an ancilla and uncompute, with the ancilla prepared in |−⟩ so the CNOTs kick back phases (21.2). That construction costs one application of the predicate circuit per oracle call — and this is Grover's hidden constant: for a hard predicate (a full SAT instance, say) the oracle is the size of the whole problem, evaluated once per iteration, √N times. Budget it before believing any "Grover solves X" claim.
25.4Phase inversion
The oracle is a reflection. For M = 1 it is O = I − 2|w⟩⟨w|: geometrically, every amplitude component along |w⟩ flips sign while the orthogonal complement is untouched — a mirror through the plane orthogonal to the marked state. For M marked items it is I − 2·Σ_w|w⟩⟨w|. Reflections are unitary and their composition is a rotation — the fact the whole algorithm rides on. A useful sanity check: the oracle alone does nothing measurable (a global-sign-visible operation applied to a real superposition changes only phases), which is exactly why a second operation is needed before anything can be read out.
25.5The diffusion operator
The second reflection is D = 2|s⟩⟨s| − I, where |s⟩ is the uniform superposition — inversion about the mean: every amplitude aᵢ becomes 2μ − aᵢ (μ = average amplitude), so below-average amplitudes (marked items, just sign-flipped) end up further above the mean. Implementation: D = H^{⊗n}·(2|0⟩⟨0| − I)·H^{⊗n}, and the middle piece is a phase flip on |0…0⟩ built from X gates and a multi-controlled Z with the ancilla trick — O(n) gates. One Grover iteration is G = D·O: reflect about |w⟩'s orthogonal complement, then about |s⟩.
one iteration G = D·O:
|x> ──O───H^⊗n───●───H^⊗n── O: flip sign of marked |w>
Z middle: phase flip on |0…0>25.6Amplitude amplification
Grover generalizes beyond uniform starts: given any preparation A with A|0⟩ = |ψ⟩ succeeding (having overlap √p with good states) with probability p, the operator Q = (2|ψ⟩⟨ψ| − I)·A·O·A† amplifies success to ≈ 1 in O(1/√p) applications — versus O(1/p) classical repetitions. This is amplitude amplification (Brassard–Høyer–Mosca–Tapp), and it converts any probabilistic algorithm's success probability into a quadratic gain: Monte Carlo estimation becomes amplitude estimation (QPE on Q, 24.7), backtracking search gets walk-based speedups. When M is unknown, QPE on G doubles as a counter — quantum counting — and BBHT's randomized schedules replace the fixed iteration count. Grover is the name; amplitude amplification is the technology.
25.7Geometric interpretation
Everything above happens in a plane. Write the state as a component on the marked subspace and one on the rest: |ψ⟩ = sin(θ)|w⟩ + cos(θ)|r⟩ with sinθ = √(M/N). The starting uniform state sits at angle θ; each Grover iteration rotates by exactly 2θ toward |w⟩; success probability after k iterations is sin²((2k+1)θ).
state plane spanned by |r> (unmarked) and |w> (marked):
start: |s> = cosθ·|r> + sinθ·|w> angle θ above |r>
each G: rotate by 2θ toward |w>
after k: angle (2k+1)θ, P(success) = sin²((2k+1)θ)
stop at k ≈ π/(4θ): angle ≈ π/2 → all amplitude on |w>Search as a rotation problem: the oracle tilts, the diffusion turns, and you stop when the rotation has swept the amplitude onto the answer. Overshooting keeps rotating — past π/2 the success probability falls again.
25.8The optimal iteration count
Set (2k+1)θ ≈ π/2: the optimum is k* ≈ π/(4θ) − 1/2 ≈ (π/4)·√(N/M) iterations for M ≪ N. For N = 16, M = 1: θ = arcsin(1/4) ≈ 0.2527, so k* ≈ 2.6 — three iterations give sin²(7θ) ≈ 96%. Past the optimum the sine keeps oscillating: 4 iterations drop to ≈ 58%, 5 to ≈ 13%. Two boundary facts: if M = N/2, θ = π/4 and there is no speedup at all (one iteration, 50% — you could have guessed); and the √(N/M) scaling means knowing M matters, hence quantum counting or BBHT schedules when it is unknown. Grover is a precise timing problem, not an iterative refinement.
import numpy as np
n, N = 4, 16
w = 0b1010 # marked item
s = np.ones(N, dtype=complex) / np.sqrt(N) # uniform start
O = np.eye(N); O[w, w] = -1 # oracle: phase inversion
D = 2 * np.outer(s, s) - np.eye(N) # diffusion: inversion about mean
for k in range(6):
print(f"k={k} P(find)={abs(s[w])**2:.3f}")
s = D @ O @ s25.9Noise sensitivity
Count the exposure: one iteration costs the oracle plus O(n) gates; √N iterations means roughly 4n·√N gate applications total. At a physical error rate p per gate, the failure budget 4n·√N·p must stay well below 1. For n = 20 (N ≈ 10⁶): 4·20·1024·10⁻³ ≈ 82 — five orders of magnitude over budget at p = 10⁻³. The quadratic speedup hurts twice: more iterations means more accumulated noise, and the narrow sin² peak means angle errors (over/under-rotation from imperfect gates) shift the optimum. This is why Grover on today's hardware is a 3-to-6-qubit demonstration, and why the fault-tolerant crossover is a genuine engineering milestone, not a formality.
25.10Practical implementation
Rules of thumb from the people who run this. First, exploit classical structure before reaching for Grover — real SAT solvers beat √(2ⁿ) on real instances; Grover is the worst-case guarantee, not the average-case winner. Second, when you do run it, the oracle dominates: co-design the predicate circuit with the diffusion (cancel adjacent H layers, merge rotations, 46.8). Third, prefer amplitude-amplification framings with known p — they compose into larger algorithms. Fourth, if M is unknown, count first (24.7). Fifth, for composability use fixed-point search (Yoder–Low–Chuang), which cannot overshoot, at a modest constant-factor cost. Hardware demonstrations today: a handful of qubits, meaningful as system benchmarks — not as search.