Skip to content

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:

  1. Show that Grover's iteration is a rotation by \(2\theta\) in a two-dimensional plane.
  2. Derive \(\Pr[\text{success}] = \sin^2\big((2k+1)\theta\big)\) and the optimal \(k\).
  3. Prove the \(\frac{\pi}{4}\sqrt{N}\) formula and analyse over-rotation.
  4. State the BBBV optimality theorem and explain why \(\Theta(\sqrt N)\) cannot be beaten.
  5. Generalise to amplitude amplification and quantum counting.

22.2 The Two-Dimensional Picture

Grover's algorithm never leaves the plane spanned by

\[ |w\rangle \quad\text{and}\quad |w^\perp\rangle = \frac{1}{\sqrt{N-M}}\sum_{x \text{ unmarked}}|x\rangle . \]

(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

\[ |\psi\rangle = \sin\theta\,|w_{\text{all}}\rangle + \cos\theta\,|w^\perp\rangle \]

Matching amplitudes with \(|\psi\rangle = \frac{1}{\sqrt N}\sum_x|x\rangle\):

\[ \sin\theta = \sqrt{\frac{M}{N}}, \qquad \cos\theta = \sqrt{\frac{N-M}{N}} \]
\[ \boxed{\ \theta = \arcsin\sqrt{\frac{M}{N}}\ } \]

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.

\[ \alpha \ \xrightarrow{O_f}\ -\alpha \ \xrightarrow{D}\ \alpha + 2\theta \]
\[ \boxed{\ G = D\,O_f \text{ is a rotation by } +2\theta \text{ toward } |w_{\text{all}}\rangle\ } \]

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\):

\[ \boxed{\ G^{k}|\psi\rangle = \sin\big((2k+1)\theta\big)\,|w_{\text{all}}\rangle + \cos\big((2k+1)\theta\big)\,|w^\perp\rangle\ } \]
\[ \boxed{\ \Pr[\text{success after } k \text{ iterations}] = \sin^2\big((2k+1)\theta\big)\ } \]

Matrix form

In the ordered basis \(\{|w^\perp\rangle, |w_{\text{all}}\rangle\}\):

\[ G = \begin{pmatrix}\cos2\theta & -\sin2\theta\\ \sin2\theta & \cos2\theta\end{pmatrix} \]

— 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\)):

\[ k = \frac{\pi}{4\theta} - \frac12 . \]

Since \(k\) must be an integer, take

\[ \boxed{\ k_{\text{opt}} = \left\lfloor \frac{\pi}{4\theta}\right\rfloor, \qquad \theta = \arcsin\sqrt{M/N}\ } \]

Large-\(N\) approximation. For \(M \ll N\), \(\theta\approx\sqrt{M/N}\), so

\[ k_{\text{opt}} \approx \frac{\pi}{4}\sqrt{\frac{N}{M}} \qquad\text{and for } M=1: \qquad k_{\text{opt}} \approx \frac{\pi}{4}\sqrt N \approx 0.785\sqrt N . \]

Residual error. The rounding leaves an angular error of at most \(\theta\), so

\[ \Pr[\text{failure}] \le \sin^2\theta = \frac{M}{N} \ \longrightarrow\ 0 \ \text{as } N\to\infty . \]

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.

\[ \sin\theta = \frac12 \ \Longrightarrow\ \frac{M}{N} = \frac14 . \]

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:

\[ \sum_{x} \sum_{t=1}^{T}\big\| \Pi_x|\psi_t\rangle \big\|^2 = T \]

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:

\[ \big\| |\psi_T^{(0)}\rangle - |\psi_T^{(x^*)}\rangle \big\| \le 2\sqrt{\frac{T^2}{N}} . \]

To distinguish the two cases with constant probability, this must be \(\Omega(1)\), forcing

\[ T = \Omega(\sqrt N) . \qquad\blacksquare \]

Consequences.

  1. 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.
  2. 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.
  3. 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

\[ Q = -\mathcal{A}\,S_0\,\mathcal{A}^{-1}\,S_\chi \]

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

\[ O\!\left(\frac{1}{\sqrt p}\right) \ \text{repetitions suffice, versus } O\!\left(\frac1p\right) \ \text{classically.} \]

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

\[ M = N\sin^2\theta . \]

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.

\[ \sin\theta = \sqrt{\tfrac{1}{1024}} = \tfrac{1}{32} = 0.03125 \ \Longrightarrow\ \theta = 0.031255\ \mathrm{rad} = 1.7908° \]
\[ k_{\text{opt}} = \left\lfloor\frac{\pi}{4\theta}\right\rfloor = \left\lfloor\frac{0.785398}{0.031255}\right\rfloor = \lfloor 25.128\rfloor = \mathbf{25} \]

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×.

Estimate the resources to find a 128-bit AES key by Grover search. Comment on the security implication.

Solution.

\(N = 2^{128}\), \(M=1\).

\[ k_{\text{opt}} \approx \frac{\pi}{4}\sqrt{2^{128}} = \frac{\pi}{4}\times 2^{64} = 0.7854\times 1.8447\times10^{19} = \mathbf{1.449\times10^{19}} \ \text{iterations} \]

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

\[ \approx 1.449\times10^{19}\times 2\times10^{4} = \mathbf{2.9\times10^{23}} \ \text{gates}. \]

At an optimistic \(10^{9}\) logical gates per second:

\[ t = 2.9\times10^{14}\ \mathrm{s} \approx \mathbf{9\ \text{million years}} . \]

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.

\[ \sin\theta = \frac14 \Rightarrow \theta = 0.25268\ \mathrm{rad} = 14.478° \]

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
\[ k_{\text{opt}} = \left\lfloor\frac{\pi}{4\times0.25268}\right\rfloor = \lfloor3.108\rfloor = \mathbf{3} \]

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\).

\[ \Pr[w] = 0.6875^2 = 0.47266 \ \checkmark \]

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\):

\[ 0.99^{R} \le 0.01 \ \Longrightarrow\ R \ge \frac{\ln0.01}{\ln0.99} = \frac{-4.605}{-0.01005} = 458.2 \]
\[ R_{\text{classical}} = \mathbf{459} \ \text{runs of } \mathcal{A} . \]

Amplitude amplification. \(\sin\theta = \sqrt{p} = 0.1\), so \(\theta = 0.10017\) rad.

\[ k_{\text{opt}} = \left\lfloor\frac{\pi}{4\theta}\right\rfloor = \left\lfloor\frac{0.7854}{0.10017}\right\rfloor = \lfloor7.84\rfloor = \mathbf{7} \]
\[ \Pr = \sin^2(15\times0.10017) = \sin^2(1.5026) = 0.99534 = \mathbf{99.5\%} \]

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

\[ (1-\eta)^{k} \approx e^{-\eta k} = \exp\!\left(-\eta\frac{\pi}{4}\sqrt N\right) . \]

Require this to stay above, say, \(\frac12\):

\[ \eta\frac{\pi}{4}\sqrt N \le \ln 2 = 0.693 \]
\[ \sqrt N \le \frac{0.693 \times 4}{\pi \times 10^{-4}} = \frac{2.772}{3.1416\times10^{-4}} = 8824 \]
\[ N \le 7.8\times10^{7} \approx 2^{26} . \]

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

  1. Compute \(\theta\) and \(k_{\text{opt}}\) for \(N = 10^{6}\), \(M=1\). [Ans: \(\theta\approx0.001\) rad, \(k=785\)]
  2. For \(N=64\), \(M=4\): find \(k_{\text{opt}}\) and the success probability. [Ans: \(\theta=30°\), \(k=1\), \(\Pr=1\)]
  3. Show that \(\Pr[\text{success}]=0\) when \((2k+1)\theta = \pi\).
  4. Verify that \(G\) has eigenvalues \(e^{\pm2i\theta}\).
  5. For \(p = 0.25\), how many amplitude-amplification rounds reach certainty? [Ans: 1]
  6. Explain why \(\sqrt P\) machines give only \(\sqrt P\) speed-up in parallel Grover.
  7. 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.