Chapter 21 — Key Takeaways (Grover's Algorithm)

The famous one. §21.4's over-rotation and §21.5's wrong-$M$ failure are what break implementations.

No promise — and that is the point

Chapter 20's algorithms all needed special structure. Grover needs none: any predicate, any input.

$$\text{classical } \mathcal{O}(N) \;\longrightarrow\; \text{quantum } \mathcal{O}(\sqrt N)$$

Quadratic, not exponential — and provably optimal. No quantum algorithm beats $\Omega(\sqrt N)$ for unstructured search. Aaronson–Ambainis: exponential speedups require promise structure, so the quadratic bound is the price of generality, not a weakness.

Two reflections = a rotation

$$O_f|x\rangle = (-1)^{f(x)}|x\rangle \qquad D = 2|s\rangle\langle s| - I = H^{\otimes n}\big(2|0\rangle\langle 0| - I\big)H^{\otimes n}$$

def diffuser(n):
    qc.h(range(n)); qc.x(range(n))
    qc.h(n-1); qc.append(MCXGate(n-1), ...); qc.h(n-1)    # multi-controlled Z
    qc.x(range(n)); qc.h(range(n))

⚛️ The diffuser is itself a phase oracle — marking $|0\dots0\rangle$, conjugated into the Hadamard basis. A product of two reflections is a rotation, which explains the iteration count, the over-rotation, and every failure below. It also means the diffuser costs what the oracle costs.

★ The exact success probability

$$P(k) = \sin^2\!\big((2k+1)\theta\big), \qquad \sin\theta = \sqrt{M/N}$$

Verified against simulation to $10^{-15}$:

     k   measured   sin²((2k+1)θ)       diff
     0   0.062500        0.062500   4.16e-17
     3   0.961319        0.961319   9.77e-15
     6   0.020381        0.020381   1.53e-16

$$k_{\text{opt}} = \left\lfloor \frac{\pi}{4}\sqrt{N/M} \right\rfloor$$

Not probability 1 — $k$ is an integer, so $(2k+1)\theta$ lands near $\pi/2$. At $N{=}16,M{=}1$: $k{=}3$, $P = 0.9613$. High probability, and repeat if unlucky.

★★ Over-rotation

     k   P(marked)
     0      0.0625     <- uniform, 1/16
     3      0.9613     <- OPTIMAL
     4      0.5817
     5      0.1255
     6      0.0204     <- WORSE THAN DOING NOTHING

Six iterations gives 2.1% of optimal — below the 0.0625 you started with.

⚠️ Every classical intuition about iteration is wrong here. More iterations is not "more thorough." There is no "close enough" improving with effort. It does not converge — it oscillates. Compute $k$ in advance and stop.

Later peaks exist at $(2k+1)\theta = \pi/2 + m\pi$:

   m=0: ideal k = 2.608  -> k=3,  P = 0.9613   (3 iterations)
   m=1: ideal k = 8.825  -> k=9,  P = 0.9922   (9 iterations)
   m=2: ideal k = 15.041 -> k=15, P = 0.9996   (15 iterations)

$k{=}9$ genuinely beats $k{=}3$ at 3× the cost. Use the first peak.

★★ You must know $M$, and guessing wrong gives ZERO

   M   M/N     k_opt   P(k_opt)
   1  0.062        3     0.9613
   2  0.125        2     0.9453
   4  0.250        1     1.0000     <- more solutions, FEWER iterations
   8  0.500        1     0.5000     <- Grover CANNOT HELP

At $M/N = 1/2$: $\theta = \pi/4$, so $(2k+1)\theta = \pi/2$ needs $k = 0.5$ — no integer lands on the peak.

The catastrophic case

   assumed M=1, k=3:   P(any marked) = 0.0000
   true M=3,    k=1:   P(any marked) = 0.9492

   M=3, N=16, θ = 0.447832
     k=1: (2k+1)θ = 0.4276π   sin² = 0.949219
     k=3: (2k+1)θ = 0.9978π   sin² = 0.000046     <- rotated onto the UNMARKED axis

🐛 The symptom is diagnostic:

Failure	Symptom
wrong $M$	no successes at all, uniform over non-solutions
broken oracle	a different single answer dominates
over-rotation	low but nonzero, and a smaller $k$ does better

A broken oracle marks something; a wrong $M$ marks nothing. The check: run $k=1$ and $k=2$. If a small $k$ works, the oracle is fine and $M$ is wrong.

Fix: estimate $M$ first (quantum counting = phase estimation on the Grover operator, also $\mathcal{O}(\sqrt N)$), or use exponential search — try $k = 1, 2, 4, 8,\dots$ and verify classically.

★ What it costs

     n         N       iterations   T/oracle   T/diffuser        TOTAL T
     8       256               12         47           47          1,128
    12     4,096               50         79           79          7,900
    16    65,536              201        111          111         44,622
    20 1,048,576              804        143          143        229,944

Through Chapter 15's estimator:

   n=16 (N=65,536):  44,622 T  ->  278,010 physical qubits, 0.30 s

Classical brute force at n=20: under a second on one core.

$$c_q\sqrt N < c_c N \iff \sqrt N > c_q/c_c \approx 10^{9}\text{–}10^{12} \implies N > 10^{18}$$

A quintillion. Such problems exist — a 128-bit key space is $2^{128}$, $\sqrt N = 2^{64}$ — which is why Grover's practical significance is cryptographic.

★★ Grover does not search a database

The oracle is a CIRCUIT. Real data must be encoded into it, touching all $N$ items first:

$$\underbrace{\mathcal{O}(N)}_{\text{build oracle}} + \underbrace{\mathcal{O}(\sqrt N)}_{\text{search}} = \mathcal{O}(N)$$

Criterion: Grover helps when $|\text{oracle}| \ll N$, not when $|\text{oracle}| \sim N$.

QRAM does not rescue it: it does not exist, building it is $\mathcal{O}(N)$, and it must stay coherent for all $\sqrt N$ iterations.

And check the problem is actually unstructured — a B-tree gives $\mathcal{O}(\log N) \ll \mathcal{O}(\sqrt N)$. Grover is optimal for unstructured search, and almost nothing real is unstructured.

🔬 The cryptographic case, carefully

Rely on: Grover takes symmetric key strength from $2^k$ to $2^{k/2}$. AES-128 → ~64 bits, AES-256 → ~128. Sound, and the standard argument for doubling key lengths.

Qualifications: - Parallelizes poorly — $p$ machines give $\sqrt p$, where classical brute force gives $p$. - One enormous coherent computation — $2^{64}$ iterations with AES inside each. - It does not break AES the way Shor breaks RSA (Ch. 15 CS1: ~25M qubits, and RSA falls outright).

Use AES-256; worry about Shor.

Common pitfalls

• Running more iterations "to be thorough."
• Hard-coding $M = 1$ because the test case had one solution.
• Diagnosing "returns nothing" as a broken oracle.
• Chasing the second peak for 0.03 more probability at 3× cost.
• Believing "searches a database."
• Applying Grover to structured data that an index handles better.
• Forgetting the diffuser costs as much as the oracle.

Project piece added this chapter

vqelab/grover.py — phase_oracle, diffuser, grover_circuit, success_probability (the analytic reference), optimal_iterations, can_succeed (detects the $M/N = 1/2$ failure), GroverResult with over_rotated and marked_count_looks_wrong, estimate_marked_count, and grover_cost (oracle and diffuser, every iteration). 15 tests pass, including test_running_longer_becomes_worse_than_doing_nothing and test_a_wrong_marked_count_gives_essentially_zero.