Lesson 22: Grover's Algorithm: Geometric Analysis and Optimality¶
22.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Show that Grover's iteration is a rotation by \(2\theta\) in a two-dimensional plane.
- Derive \(\Pr[\text{success}] = \sin^2\big((2k+1)\theta\big)\) and the optimal \(k\).
- Prove the \(\frac{\pi}{4}\sqrt{N}\) formula and analyse over-rotation.
- State the BBBV optimality theorem and explain why \(\Theta(\sqrt N)\) cannot be beaten.
- Generalise to amplitude amplification and quantum counting.
22.2 The Two-Dimensional Picture¶
Grover's algorithm never leaves the plane spanned by
(For \(M\) marked items, replace \(|w\rangle\) by \(|w_{\text{all}}\rangle = \frac{1}{\sqrt M}\sum_{x\text{ marked}}|x\rangle\).)
Both \(O_f\) and \(D\) map this plane to itself, and the initial state lies in it. So the entire algorithm is two-dimensional geometry, no matter how large \(N\) is.
The initial angle¶
Write the starting state as
Matching amplitudes with \(|\psi\rangle = \frac{1}{\sqrt N}\sum_x|x\rangle\):
For \(M=1\) and large \(N\), \(\theta \approx \frac{1}{\sqrt N}\) — a tiny angle. \(|\psi\rangle\) starts almost entirely along \(|w^\perp\rangle\).
22.3 Each Iteration Rotates by 2θ¶
Two reflections make a rotation¶
The oracle \(O_f = I - 2|w_{\text{all}}\rangle\langle w_{\text{all}}|\) is a reflection about the axis \(|w^\perp\rangle\): it negates the \(|w_{\text{all}}\rangle\) component.
If the state is at angle \(\alpha\) from \(|w^\perp\rangle\), after \(O_f\) it is at angle \(-\alpha\).
The diffusion operator \(D = 2|\psi\rangle\langle\psi| - I\) is a reflection about the axis \(|\psi\rangle\), which sits at angle \(\theta\).
If the state is at angle \(-\alpha\), reflecting about the line at angle \(\theta\) takes it to \(2\theta - (-\alpha) = 2\theta + \alpha\).
Composition.
Elementary geometry fact: the composition of two reflections about lines meeting at angle \(\theta\) is a rotation by \(2\theta\). Grover's algorithm is that fact, applied \(k\) times.
The state after k iterations¶
Starting at angle \(\theta\) and rotating \(k\) times by \(2\theta\):
Matrix form¶
In the ordered basis \(\{|w^\perp\rangle, |w_{\text{all}}\rangle\}\):
— literally a rotation matrix. Its eigenvalues are \(e^{\pm2i\theta}\), a fact used by quantum counting (§5).
22.4 The Optimal Number of Iterations¶
We want \((2k+1)\theta = \frac{\pi}{2}\) (pointing exactly at \(|w_{\text{all}}\rangle\)):
Since \(k\) must be an integer, take
Large-\(N\) approximation. For \(M \ll N\), \(\theta\approx\sqrt{M/N}\), so
Residual error. The rounding leaves an angular error of at most \(\theta\), so
For \(N = 2^{20}\), \(M=1\): failure probability under \(10^{-6}\).
Exact cases¶
Grover is exact whenever \(\frac{\pi}{4\theta} - \frac12\) is an integer. The most useful instance is \(\theta = \frac{\pi}{6} = 30°\), i.e.
Then \(k = 1\) and \(\Pr = \sin^2(3\times30°) = \sin^2 90° = 1\). This explains the \(N=4, M=1\) and \(N=16,M=4\) results of L21.
Over-rotation¶
\(\Pr[\text{success}] = \sin^2((2k+1)\theta)\) is periodic, with period \(\frac{\pi}{2\theta}\) in \(k\). Running too long is genuinely harmful: at \((2k+1)\theta = \pi\) the success probability is zero.
The counter-intuitive lesson. Unlike classical iterative algorithms, "run it longer to be safer" is wrong here. Grover must be stopped at a precisely computed moment. If \(M\) is unknown, either estimate it first (quantum counting) or use the BBHT randomised strategy: repeatedly pick \(k\) uniformly from \([0, m)\) and grow \(m\) by a factor of \(6/5\) after each failure — this finds a solution in \(O(\sqrt{N/M})\) expected queries without knowing \(M\).
22.5 Optimality: The BBBV Lower Bound¶
Theorem (Bennett, Bernstein, Brassard, Vazirani, 1997). Any quantum algorithm that solves unstructured search over \(N\) items with bounded error requires \(\Omega(\sqrt N)\) oracle queries.
Proof sketch (the hybrid argument). Run the algorithm with the all-zero oracle (no marked item) and track the total "query magnitude" each index \(x\) receives across \(T\) queries:
since each query step has unit norm. By pigeonhole, some index \(x^*\) receives total magnitude at most \(T/N\). Now switch to the oracle marking \(x^*\). A hybrid argument bounds the change in the final state:
To distinguish the two cases with constant probability, this must be \(\Omega(1)\), forcing
Consequences.
- Grover is optimal, matching the lower bound up to a constant. There is no \(O(\log N)\) or even \(O(N^{1/3})\) quantum search.
- Quantum computers do not solve NP-complete problems efficiently by brute force. A SAT instance with \(n\) variables has \(2^n\) assignments; Grover reduces \(2^n\) to \(2^{n/2}\) — still exponential.
- Speed-ups need structure. Shor's exponential advantage comes from the periodic structure of modular exponentiation. Unstructured problems admit only quadratic gains.
22.6 Amplitude Amplification and Quantum Counting¶
Amplitude amplification (Brassard, Høyer, Mosca, Tapp)¶
Grover generalises far beyond search. Let \(\mathcal{A}\) be any quantum algorithm (not just \(H^{\otimes n}\)) that outputs a "good" answer with probability \(p = \sin^2\theta\). Define
where \(S_\chi\) flips the phase of good states and \(S_0\) flips the phase of everything except \(|0\rangle\). Then \(Q\) rotates by \(2\theta\) exactly as before, and
This is a quadratic speed-up for any randomised algorithm's success probability, and it is the form in which Grover appears inside larger algorithms: Monte Carlo estimation, minimum finding, collision finding, and QAOA warm-starting.
Quantum counting¶
The eigenvalues of \(G\) are \(e^{\pm 2i\theta}\). Applying quantum phase estimation (L19) to \(G\) yields \(\theta\), and hence
Cost: \(O(\sqrt N)\) queries for a constant-factor estimate of \(M\). This solves the "unknown \(M\)" problem and also gives quantum approximate counting — estimating the number of solutions to a constraint problem quadratically faster than classical sampling.
22.7 Solved Problems¶
Problem 1 — Success probability as a function of k¶
For \(N = 1024\), \(M=1\): compute \(\theta\), \(k_{\text{opt}}\), and \(\Pr[\text{success}]\) at \(k = 20, 25, 30, 50\).
Solution.
Now evaluate \(\Pr = \sin^2((2k+1)\theta)\):
| \(k\) | \((2k+1)\theta\) (rad) | degrees | \(\Pr\) |
|---|---|---|---|
| 20 | 1.2815 | 73.4° | 0.9187 |
| 25 | 1.5940 | 91.3° | 0.99946 |
| 30 | 1.9066 | 109.2° | 0.8914 |
| 50 | 3.1568 | 180.9° | 0.00023 |
At \(k=50\) (double the optimum) the algorithm has rotated a full \(180°\) and the success probability has collapsed to essentially zero. This is the clearest demonstration of why over-rotation matters.
Classical comparison: 512 queries expected. Quantum: 25. Speed-up ≈ 20×.
Problem 2 — Grover for AES-128 key search¶
Estimate the resources to find a 128-bit AES key by Grover search. Comment on the security implication.
Solution.
\(N = 2^{128}\), \(M=1\).
Each iteration requires two full AES evaluations (the encryption circuit and its inverse for uncomputation), each roughly \(10^4\) quantum gates. So the total gate count is
At an optimistic \(10^{9}\) logical gates per second:
Parallelisation does not rescue it. Splitting the search across \(P\) quantum machines gives only a \(\sqrt P\) improvement (each machine searches \(N/P\) items in \(\sqrt{N/P}\) steps). To finish in one year you would need \(P \approx (9\times10^{6})^2 = 8\times10^{13}\) machines.
Security implication. AES-128 has an effective post-quantum security level of 64 bits — the standard statement — but the constant factors make even that unreachable in practice. The recommended mitigation is simply AES-256, which under Grover retains 128-bit effective security. NIST's post-quantum guidance formalises this: symmetric algorithms survive by doubling key lengths; public-key algorithms must be replaced entirely.
Problem 3 — Rotation angle and geometry, verified numerically¶
For \(N=16\), \(M=1\): compute \(\theta\) and verify \(\Pr[k]\) for \(k=1,2,3\) using both the geometric formula and the amplitude recursion.
Solution.
Geometric formula.
| \(k\) | \((2k+1)\theta\) | \(\Pr = \sin^2\) |
|---|---|---|
| 0 | 14.478° | 0.0625 |
| 1 | 43.43° | 0.4727 |
| 2 | 72.39° | 0.9084 |
| 3 | 101.34° | 0.9613 |
Amplitude recursion check for \(k=1\). Initial \(\alpha = \frac14 = 0.25\) for all 16 states.
Oracle: \(\alpha_w = -0.25\), others \(+0.25\). Mean: \(\bar\alpha = \frac{15(0.25) - 0.25}{16} = \frac{3.5}{16} = 0.21875\). Diffusion: \(\alpha_w = 2(0.21875) + 0.25 = 0.6875\).
matching the geometric formula exactly. The two pictures — amplitude bookkeeping and plane rotation — are the same thing.
Problem 4 — Amplitude amplification of a weak algorithm¶
A heuristic quantum algorithm \(\mathcal{A}\) finds a valid solution with probability \(p = 0.01\). How many repetitions are needed classically, and how many with amplitude amplification, to reach 99 % success?
Solution.
Classical repetition. Failure per run \(= 0.99\):
Amplitude amplification. \(\sin\theta = \sqrt{p} = 0.1\), so \(\theta = 0.10017\) rad.
7 applications of \(\mathcal{A}\) (plus 7 of \(\mathcal{A}^{-1}\)) versus 459 classically — a \(\approx33\times\) improvement, consistent with \(\sqrt{459/7}\approx 8\) per the quadratic rule (the exact factor depends on the target confidence).
Why this matters more than plain search. Amplitude amplification applies to any subroutine with a checkable output — Monte Carlo integration, optimisation heuristics, sampling — making it one of the few broadly reusable quantum primitives.
Problem 5 — Grover with an imperfect oracle¶
The oracle applies the correct phase with probability \(1-\eta\) and does nothing with probability \(\eta\) (a stochastic gate error). Estimate the largest \(N\) for which Grover still works, given \(\eta = 10^{-4}\).
Solution. The algorithm requires \(k \approx \frac{\pi}{4}\sqrt N\) oracle calls, all of which must succeed for the rotation to accumulate correctly. Ignoring partial recovery, the probability that every call is clean is
Require this to stay above, say, \(\frac12\):
So with a \(10^{-4}\) oracle error rate, Grover works up to roughly 26 qubits' worth of search space — and only if every other gate is perfect too.
Generalisation. Setting \(\eta\frac{\pi}{4}\sqrt N = O(1)\) gives \(N = O(1/\eta^2)\): the largest searchable space scales as the inverse square of the error rate. Getting to a cryptographically relevant \(N = 2^{128}\) would need \(\eta \lesssim 10^{-20}\) — utterly impossible without full fault tolerance.
Conclusion. Grover is a fault-tolerant-era algorithm. NISQ demonstrations are limited to \(N \le 2^{5}\) or so, and its quadratic speed-up is too shallow to pay for error-correction overhead in many practical settings — a point made forcefully by Babbush et al. (2021), who argue that quadratic speed-ups may never yield practical advantage once QEC costs are included.
22.8 Practice Problems¶
- Compute \(\theta\) and \(k_{\text{opt}}\) for \(N = 10^{6}\), \(M=1\). [Ans: \(\theta\approx0.001\) rad, \(k=785\)]
- For \(N=64\), \(M=4\): find \(k_{\text{opt}}\) and the success probability. [Ans: \(\theta=30°\), \(k=1\), \(\Pr=1\)]
- Show that \(\Pr[\text{success}]=0\) when \((2k+1)\theta = \pi\).
- Verify that \(G\) has eigenvalues \(e^{\pm2i\theta}\).
- For \(p = 0.25\), how many amplitude-amplification rounds reach certainty? [Ans: 1]
- Explain why \(\sqrt P\) machines give only \(\sqrt P\) speed-up in parallel Grover.
- State the BBBV theorem and one consequence for NP-complete problems.
22.9 Summary¶
- Grover's iteration \(G = D\,O_f\) is the composition of two reflections, hence a rotation by \(2\theta\) in the \(\mathrm{span}\{|w\rangle,|w^\perp\rangle\}\) plane, with \(\theta = \arcsin\sqrt{M/N}\).
- \(\Pr[\text{success}] = \sin^2\big((2k+1)\theta\big)\); optimal \(k = \lfloor\pi/(4\theta)\rfloor \approx \frac{\pi}{4}\sqrt{N/M}\); residual failure \(\le M/N\).
- The probability oscillates: over-rotation drives it to zero. Use quantum counting or the BBHT strategy when \(M\) is unknown.
- BBBV theorem: \(\Omega(\sqrt N)\) queries are necessary, so Grover is optimal and quantum computers do not brute-force NP-complete problems efficiently.
- Amplitude amplification generalises Grover to any algorithm with success probability \(p\), needing \(O(1/\sqrt p)\) instead of \(O(1/p)\) repetitions.
- Practical reality: AES-128 needs \(1.4\times10^{19}\) iterations (millions of years); Grover requires full fault tolerance, since the searchable space scales only as \(O(1/\eta^2)\) in the error rate.
Next lesson: L23 — Grover applied to cryptography: hash preimage attacks.
Practise now: unit2-algorithms-lab.html → Grover tab: switch to the geometric view to
watch the state vector rotate in the 2-D plane, and slide \(k\) past the optimum to see the
probability curve fall.