Chapter 21: Grover's Algorithm

"Running it longer makes it worse. That is not a bug — it is what a rotation does."

Overview

Grover's algorithm is the one everybody has heard of, and it is the first algorithm in Part IV with no promise. Chapter 20's four algorithms all required the input to have a special structure; Grover requires nothing. Give it any predicate and it finds the inputs satisfying it in $\mathcal{O}(\sqrt N)$ queries where classical search needs $\mathcal{O}(N)$.

That generality is what makes it famous, and the price is that the speedup is only quadratic.

The algorithm is a rotation, and everything surprising about it follows from that. Measured on $N = 16$ with one marked state:

   iterations   P(marked)
            0      0.0625        <- uniform, 1/16
            1      0.4727
            2      0.9084
            3      0.9613        <- optimal
            4      0.5817
            5      0.1255
            6      0.0204        <- WORSE than doing nothing

Six iterations is worse than zero. Not degraded — actively worse than the uniform superposition you started from. Rotating past the target keeps rotating.

And a subtler failure that is easy to hit in practice. If you assume one marked state and there are actually three:

   assumed M=1, ran 3 iterations:   P(any marked) = 0.0000
   true M=3,    ran 1 iteration:    P(any marked) = 0.9492

Exactly zero. The amplitude rotated precisely onto the unmarked subspace, and §21.4 shows the arithmetic that makes it exact rather than merely small.

Then §21.6 prices it. A 20-bit Grover search costs 229,944 T gates; the classical alternative is about one second on one core.

In this chapter, you will learn to:

• Build the oracle and diffuser, and see the diffuser is itself an oracle.
• Derive the iteration count and verify $P(k) = \sin^2\!\big((2k+1)\theta\big)$.
• Demonstrate over-rotation.
• Handle multiple marked states, and what happens when you guess wrong.
• Price a Grover search honestly.
• Explain why it does not search a database.

Learning Paths

How to read this chapter by track. - 🔰 Beginner — §21.2 and §21.3. The rotation picture explains everything else. - 🔬 Researcher — §21.4 and §21.6; the iteration-count sensitivity is under-appreciated. - 🤖 Quantum ML — §21.5's amplitude amplification generalizes well beyond search. - 🏗️ Quantum Engineer — §21.6; the T-count accounting decides whether this is ever worth running. - 🔐 Security — all of it. Grover halves symmetric key strength, and §21.7 says what that means.

21.1 The Problem, and What Makes It Different

Unstructured search. Given a predicate $f: \{0,1\}^n \to \{0,1\}$ and no other information, find an $x$ with $f(x) = 1$.

No promise. Chapter 20's algorithms needed $f$ to be constant-or-balanced, or linear, or two-to-one. Grover needs nothing at all. That is a genuine and important difference — it is why Grover applies to real problems and Deutsch–Jozsa does not.

Classically: $\mathcal{O}(N)$ queries, $N = 2^n$. You check inputs until one works, and with no structure to exploit there is nothing better.

Grover: $\mathcal{O}(\sqrt N)$.

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

Quadratic, not exponential — and Chapter 20 §20.5 hinted at why that is not an accident. Aaronson and Ambainis proved that exponential speedups require promise structure; for a total function like unstructured search, the gap can be at most polynomial. Grover is optimal: no quantum algorithm does unstructured search in fewer than $\Omega(\sqrt N)$ queries.

So the quadratic speedup is not a weakness of the algorithm. It is the best that is possible, and the price of dropping the promise.

The lower bound, and what "optimal" is actually claiming

"Grover is optimal" gets repeated a lot, usually without the qualification that makes it meaningful. The theorem is BBBV — Bennett, Bernstein, Brassard and Vazirani, 1997 — and its shape is worth following, because the assumption it needs is the same assumption §21.7 will attack.

The setup. Run any quantum algorithm that makes $T$ oracle queries, on the oracle $f_0$ that marks nothing. At each query $t$, the register is in some state, and it has some amplitude on each basis element $x$. Define

$$q_x = \sum_{t=1}^{T} \big|\alpha_x^{(t)}\big|^2$$

— the total amplitude weight the algorithm ever puts on the index $x$ at query time. Since each query happens on a normalized state, $\sum_x |\alpha_x^{(t)}|^2 = 1$, and therefore

$$\sum_{x} q_x = T$$

The averaging step. $N$ indices sharing a total of $T$ means some index $x_0$ has $q_{x_0} \le T/N$. There is always an index the algorithm barely looks at, and the algorithm does not get to choose which one, because it has not been told where the marked state is.

The hybrid step. Now switch to the oracle $f_{x_0}$ that marks exactly that index. The two runs differ only in a phase applied at each query, weighted by the amplitude on $x_0$. Summing the per-query perturbations and applying Cauchy–Schwarz bounds the distance between the two final states by something on the order of

$$\sqrt{T \cdot q_{x_0}} \;\le\; \sqrt{T^2/N} \;=\; \frac{T}{\sqrt N}$$

The conclusion. To answer differently on $f_0$ and $f_{x_0}$ — which is what "finding the marked state" requires — the final states must be distinguishable, so that distance must be $\Omega(1)$. That forces

$$T = \Omega(\sqrt N)$$

No quantum algorithm does unstructured search in $o(\sqrt N)$ queries, and Grover matches the bound to within the constant. It is one of the few places in this book where an algorithm is not merely the best known but provably the best there is.

📐 Math Aside — what the proof assumes, and why it is the whole story.

The argument above never opens the oracle. It treats $O_f$ as a unitary the algorithm may apply and nothing else — no reading the gate list, no noticing that the circuit has a repeated subexpression, no exploiting the structure of $f$.

That is the assumption, and it is doing all the work. Chapter 19 §19.7 called this out as the third gap in query complexity: the classical $\mathcal{O}(N)$ lower bound also holds only for query-only algorithms. Both bounds — the classical $N$ and the quantum $\sqrt N$ — are statements about an algorithm that is forbidden to look at the problem.

Real solvers look at the problem. A SAT solver reads the clause list and propagates. A database reads the index. Neither is a query-only algorithm, and neither is bound by $\mathcal{O}(N)$.

So the honest statement of Grover's optimality is: among algorithms that treat the predicate as a black box, $\sqrt N$ is the floor and Grover reaches it. The theorem is true, tight, and restricted to a model that most real problems escape. Case Study 2's B-tree escapes it by an exponential.

This is also why the quadratic ceiling is not a defect to be engineered around. Aaronson and Ambainis's result — that exponential speedups require promise structure — and BBBV are the same observation from two directions. Structure buys you exponentials. Generality costs you everything above a square root.

21.2 The Two Ingredients

The oracle marks the solutions by flipping their phase — Chapter 19's phase oracle, unchanged:

$$O_f|x\rangle = (-1)^{f(x)}|x\rangle$$

The diffuser reflects every amplitude about the mean:

$$D = 2|s\rangle\langle s| - I, \qquad |s\rangle = \frac{1}{\sqrt N}\sum_x |x\rangle$$

def diffuser(n):
    qc = QuantumCircuit(n)
    qc.h(range(n)); qc.x(range(n))
    qc.h(n - 1)
    qc.append(MCXGate(n - 1), list(range(n - 1)) + [n - 1])   # multi-controlled Z
    qc.h(n - 1)
    qc.x(range(n)); qc.h(range(n))
    return qc

⚛️ The Physics Underneath — the diffuser is an oracle in disguise.

Read the code inside-out. The H-sandwiched MCX is a multi-controlled $Z$ — a phase oracle that marks the all-ones state. The X layers convert it to marking $|0\dots0\rangle$ instead. The outer H layers conjugate the whole thing into the Hadamard basis.

$$D = H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n}$$

So Grover is two reflections: one about the solutions, one about the uniform superposition. And a product of two reflections is a rotation — by twice the angle between the mirrors. That single geometric fact explains the iteration count, the over-rotation, and every failure mode in this chapter.

It also means the diffuser costs roughly what the oracle costs (§21.6): both are multi-controlled operations on $n$ qubits.

One Grover iteration is $G = D \cdot O_f$.

Inversion about the mean, worked by hand

The rotation picture in §21.3 is the right way to understand Grover. But there is a second description — inversion about the mean — that is the right way to see it, because it can be done with a pocket calculator and it reproduces the simulator's numbers exactly.

$D = 2|s\rangle\langle s| - I$ acting on a state with amplitudes $a_x$ gives

$$a_x \;\longmapsto\; 2\bar a - a_x, \qquad \bar a = \frac{1}{N}\sum_x a_x$$

Every amplitude is reflected through the mean. Amplitudes below the mean go above it; amplitudes above go below. The oracle's only job is to push one amplitude below the mean so the reflection throws it up.

At $N = 16$ with one marked state, every amplitude starts at $1/4$. The oracle flips the marked one to $-1/4$, dragging the mean down to $\bar a = (15 \cdot \tfrac14 - \tfrac14)/16 = 0.21875$, and the reflection sends the marked amplitude to $2(0.21875) + 0.25 = 0.6875$. Squaring: 0.4726562 — which is the $k=1$ row of §21.3's table, to every digit.

Carrying that arithmetic forward and checking each row against Statevector:

     k   a_marked   a_unmarked        mean    a_marked²    simulator
     0   0.2500000    0.2500000           -    0.0625000    0.0625000
     1   0.6875000    0.1875000   0.2187500    0.4726562    0.4726562
     2   0.9531250    0.0781250   0.1328125    0.9084473    0.9084473
     3   0.9804688   -0.0507812   0.0136719    0.9613190    0.9613190
     4   0.7626953   -0.1669922  -0.1088867    0.5817041    0.5817041
     5   0.3542480   -0.2414551  -0.2042236    0.1254917    0.1254917
     6  -0.1427612   -0.2555542  -0.2485046    0.0203808    0.0203808

Two columns in that table explain over-rotation completely, and neither is the probability column.

The unmarked amplitude goes negative at $k = 3$. Up to that point the diffuser has been draining the unmarked states to feed the marked one. At $k = 3$ it overshoots: the unmarked amplitudes cross zero and start growing in the negative direction. Nothing is broken — the marked state has simply taken all the amplitude there was to take, and the machinery does not stop.

The mean goes negative at $k = 4$. Once $\bar a < 0$, "inversion about the mean" is reflecting about a negative value, and the reflection that used to lift the marked amplitude now pushes it down. That is the exact iteration at which the probability first falls: 0.9613 to 0.5817.

And at $k = 6$ the marked amplitude itself is negative — $-0.1428$, smaller in magnitude than the $-0.2556$ sitting on each of the fifteen unmarked states. The algorithm has not merely lost the answer; it has made the answer the least likely outcome in the register.

📊 What the Numbers Say — a probability is a square, and squares hide the sign.

Every number in §21.3's and §21.4's tables is $|a|^2$, and the squaring destroys exactly the information that makes the behaviour intelligible. $P = 0.0204$ at $k = 6$ looks like decay toward zero. The amplitude $-0.1428$ says something completely different: the state is on the far side, travelling, with a sign that flipped somewhere between $k=5$ and $k=6$.

This is worth a habit. When a probability curve does something you did not predict, look at the amplitudes before you look for a bug — on a simulator they are free. Chapter 11 §11.2's statevector simulator and Chapter 26 §26.2 exist for exactly this, and it is the single fastest way to tell "the algorithm did something wrong" from "the algorithm did what it does."

On hardware you do not get amplitudes, which is one more reason to establish the analytic reference on a simulator first (Chapter 26 §26.8).

21.3 The Rotation, and the Iteration Count

Work in the two-dimensional space spanned by $|\text{marked}\rangle$ and $|\text{unmarked}\rangle$. The uniform superposition starts at angle $\theta$ from the unmarked axis, where

$$\sin\theta = \sqrt{M/N}$$

with $M$ the number of marked states. Each iteration rotates by $2\theta$, so after $k$ iterations the state is at angle $(2k+1)\theta$, and

$$\boxed{\;P(k) = \sin^2\!\big((2k+1)\theta\big)\;}$$

Verified against the simulator, $N = 16$, $M = 1$:

     k   measured   sin²((2k+1)θ)       diff
     0   0.062500        0.062500   4.16e-17
     1   0.472656        0.472656   2.00e-15
     2   0.908447        0.908447   6.55e-15
     3   0.961319        0.961319   9.77e-15
     4   0.581704        0.581704   7.77e-15
     6   0.020381        0.020381   1.53e-16

Agreement to $10^{-15}$ — the formula is not an approximation.

The optimal $k$ puts $(2k+1)\theta$ closest to $\pi/2$:

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

For $N = 16$, $M = 1$ that is 3, giving $P = 0.9613$.

Note it is not 1. Grover is not exact — $(2k+1)\theta$ lands near $\pi/2$, not on it, because $k$ must be an integer. You get a high probability and repeat if unlucky.

Deriving the rotation

The formula was asserted above and verified numerically. Deriving it takes half a page and makes every failure mode in the rest of the chapter obvious in advance.

Step 1: the state never leaves a plane. Define the two normalized vectors

$$|m\rangle = \frac{1}{\sqrt M}\sum_{f(x)=1}|x\rangle, \qquad |u\rangle = \frac{1}{\sqrt{N-M}}\sum_{f(x)=0}|x\rangle$$

They are orthogonal, and the uniform superposition is a combination of them:

$$|s\rangle = \sqrt{\tfrac{M}{N}}\,|m\rangle + \sqrt{\tfrac{N-M}{N}}\,|u\rangle = \sin\theta\,|m\rangle + \cos\theta\,|u\rangle$$

which is where $\sin\theta = \sqrt{M/N}$ comes from — it is not a definition, it is the angle that $|s\rangle$ happens to make with $|u\rangle$. Both $O_f$ and $D$ map this plane to itself: $O_f$ negates $|m\rangle$ and fixes $|u\rangle$, and $D$ is built from $|s\rangle$, which lies in the plane. So a $2^n$-dimensional problem collapses to a two-dimensional one, permanently, and that is the single fact that makes Grover analysable at all.

Step 2: both operators are reflections.

$$O_f = I - 2|m\rangle\langle m| \quad\text{(reflection about } |u\rangle\text{)}$$ $$D = 2|s\rangle\langle s| - I \quad\text{(reflection about } |s\rangle\text{)}$$

Each squares to the identity, which is the algebraic signature of a reflection.

Step 3: two reflections make a rotation. In a plane, reflecting about a line at angle $\alpha$ and then about a line at angle $\beta$ is a rotation by $2(\beta - \alpha)$. Here the mirrors are $|u\rangle$ at angle $0$ and $|s\rangle$ at angle $\theta$, so

$$G = D\,O_f = \text{rotation by } 2\theta$$

Note what is not in that expression: $k$. The rotation angle is the same on every iteration. The operator does not know how far it has come and has no mechanism for slowing down near the target. This is the entire content of §21.4.

Step 4: read off the probability. Starting at angle $\theta$ and rotating by $2\theta$ a total of $k$ times leaves the state at angle $(2k+1)\theta$ from $|u\rangle$. Its component along $|m\rangle$ is $\sin\big((2k+1)\theta\big)$, and measuring gives a marked state with probability

$$P(k) = \sin^2\!\big((2k+1)\theta\big)$$

Nothing was approximated anywhere in that derivation, which is why the simulator agrees to $10^{-15}$ rather than to three digits. The $10^{-15}$ is floating-point arithmetic, not physics.

📐 Math Aside — where $\frac{\pi}{4}\sqrt{N/M}$ comes from, and how bad it is at small $N$.

Setting $(2k+1)\theta = \pi/2$ and solving gives the exact ideal iteration count

$$k_{\text{ideal}} = \frac{1}{2}\left(\frac{\pi}{2\theta} - 1\right)$$

which is not the formula anyone quotes. The familiar $\frac{\pi}{4}\sqrt{N/M}$ comes from two approximations applied on top of it: $\theta \approx \sin\theta = \sqrt{M/N}$ for small $\theta$, and dropping the $-\tfrac12$.

Both errors are largest exactly where the chapter's demonstrations live. At $N=16$, $M=1$:

text N θ exact ideal k (π/4)√N floor P(floor) 16 0.252680 2.6083 3.1416 3 0.961319 64 0.125328 5.7667 6.2832 6 0.996586 256 0.062541 12.0582 12.5664 12 0.999947 1,024 0.031255 24.6286 25.1327 25 0.999461 4,096 0.015626 49.7634 50.2655 50 0.999945 65,536 0.003906 200.5614 201.0619 201 0.999988 1,048,576 0.000977 803.7476 804.2477 804 1.000000

The approximation is off by 0.53 iterations at $N = 16$ — a 20% error — and the gap never shrinks. It is a constant $\approx 0.5$ at every size, because dropping the $-\tfrac12$ is an additive error, not a relative one. What shrinks is its importance: half an iteration out of 2.6 is a fifth of the answer; half an iteration out of 804 is nothing.

The floor rescues it at $N = 16$ by luck. $\lfloor 3.1416 \rfloor = 3$ and the true optimum is also 3, so the two errors happen to cancel. That is worth knowing before you trust the rule on a hand-checked toy example.

Note also that $P(\text{floor})$ is not monotonic in $N$ — $N = 1{,}024$ gives 0.999461, worse than $N = 256$'s 0.999947. Nothing is wrong. The success probability depends on how close $k_{\text{ideal}}$ lands to an integer, which wanders as $N$ grows. A success probability that goes down when the problem gets bigger is not always a bug.

21.4 Over-Rotation

Here is what "it is a rotation" costs you.

   iterations   P(marked)   fraction of optimal
            3      0.9613               100.0%
            4      0.5817                60.5%
            5      0.1255                13.1%
            6      0.0204                 2.1%

Six iterations gives 2% of optimal — and 0.0204 is below the 0.0625 you started with.

Running the algorithm longer does not converge. It oscillates, with period set by $\theta$, and past the first peak you are rotating away from the answer.

⚠️ Common Pitfall — every classical intuition about iteration is wrong here.

More iterations is not "more thorough." There is no "close enough" that improves with effort. The algorithm does not converge to an answer and stay there.

You must compute $k$ in advance and stop. And computing $k$ requires knowing $N$ and $M$ — which brings us to the failure that matters in practice.

The second peak

A subtlety worth knowing, because it looks like a bug in your implementation.

The success probability peaks whenever $(2k+1)\theta = \pi/2 + m\pi$:

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

Later peaks give slightly higher probability, because they happen to land closer to an integer. $k = 9$ genuinely beats $k = 3$ — at three times the cost.

Use the first peak. $\lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor$ is the practical rule, and the extra 0.03 of success probability is never worth 3× the runtime.

Over-rotation is a sinusoid, sampled at integers

$P(k) = \sin^2\!\big((2k+1)\theta\big)$ is a sine wave in $k$, and knowing its period tells you the whole failure in advance. The argument advances by $2\theta$ per iteration and $\sin^2$ has period $\pi$, so

$$k_{\text{period}} = \frac{\pi}{2\theta}$$

At $N = 16$, $M = 1$ that is $\pi / (2 \times 0.2526803) = 6.21654$ iterations. The whole story of the chapter's headline table fits in that one number.

   period in k = π/(2θ)                    6.21654 iterations
   k = 6, as a fraction of one period        96.52%
   (2·6+1)·θ                               3.284843 rad = 1.045598 π
   overshoot past π                        0.143251 rad
   θ itself                                0.252680 rad

So $k = 6$ is not "the algorithm decaying". It is 96.5% of the way around the circle, still short of the start, sitting at an angle 0.1093 radians before the one it began at. That is why $P(6) = 0.0204$ is below $P(0) = 0.0625$ rather than equal to it: it has not got back yet.

Run one more iteration and the probability starts climbing again. The curve is periodic, and the period is not an integer, which is the reason the algorithm cannot simply be run to convergence: an integer number of iterations never returns exactly to any previous point and never settles anywhere.

Two practical consequences.

The safe side of the peak is the low side. Under-shooting by one iteration at $N=16$ costs $0.9613 \to 0.9084$, a loss of 0.053. Over-shooting by one costs $0.9613 \to 0.5817$, a loss of 0.380 — seven times worse. The curve is not symmetric about the integer optimum because the optimum is not at an integer. When $M$ is uncertain, round the iteration count down.

And the fractional period is why $\lfloor\cdot\rfloor$ is the right operator in $\lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor$, not $\text{round}(\cdot)$. Flooring biases you to the cheap side of the peak; rounding sometimes puts you on the expensive one.

📊 What the Numbers Say — 0.0204 is a result, not a failure.

A reader meeting the over-rotation table for the first time usually reads $0.0204$ as the algorithm stopped working. It is worth being precise about what the number is.

The circuit is exact. No noise, no approximation, no truncation — the derivation above has no error term, and §21.3 measured agreement with the closed form to $10^{-15}$. 0.0204 is the correct output of a correctly implemented algorithm given the wrong iteration count.

The right comparison is not to 0.9613. It is to 0.0625, the probability of guessing. A run that scores 0.0204 has done measurable negative work: 804 iterations of a 20-bit search would have cost 229,944 T gates to arrive somewhere worse than the free uniform superposition.

And the sign of the comparison is the diagnostic. $P < 1/N$ can only be produced by rotation past the peak; nothing else in the algorithm can push a marked state below uniform. If you see it on a simulator, your iteration count is wrong and nothing else is. This is the book's theme "compared to what?" in its cheapest form — the baseline is $1/N$, it costs nothing to compute, and without it 0.0204 is just a small number.

📉 Noise Report — noise moves the optimum, and erases the symptom.

Everything above is noiseless. On hardware it changes in two ways, and only one of them is obvious.

Grover at $n = 4$, marked state 1011, transpiled to [cz, rz, sx, x], run on Aer with a depolarizing model — two-qubit error $p_2$, single-qubit error $p_2/10$ — 20,000 shots per cell:

text 2q error k=0 k=1 k=2 k=3 k=4 k=5 k=6 best k 0.000 0.0617 0.4672 0.9085 0.9607 0.5779 0.1261 0.0198 3 0.001 0.0655 0.4549 0.8618 0.8900 0.5248 0.1232 0.0326 3 0.005 0.0655 0.4107 0.6944 0.6498 0.3642 0.1119 0.0633 2 0.010 0.0655 0.3630 0.5370 0.4466 0.2408 0.0977 0.0728 2 0.020 0.0655 0.2856 0.3293 0.2296 0.1278 0.0799 0.0712 2

The $k=3$ circuit as transpiled: 84 cz gates, depth 474.

★ The optimal iteration count moves from 3 to 2 at a two-qubit error rate of 0.005. The analytic optimum stops being the empirical optimum, because each additional iteration buys less rotation than it pays in decoherence. On a noisy device, $\lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor$ is an upper bound on the useful iteration count, not the answer. Chapter 29 §29.2's lesson — that the right circuit depends on the machine — arrives here as an algorithmic parameter rather than a transpiler setting.

And the less obvious half: over-rotation stops being visible. At $p_2 = 0.020$, $k=6$ gives 0.0712 — above the 0.0625 uniform baseline, where the noiseless run gave 0.0198. Depolarizing noise drags every outcome toward $1/N$, and it drags the over-rotated state up toward $1/N$ just as it drags the correct one down.

So §21.4's diagnostic — "$P$ below $1/N$ means you over-rotated" — is a simulator diagnostic and does not survive contact with hardware. The signature it depends on is precisely the thing noise removes. This is Part V's recurring shape arriving early: a measurement that cannot detect the thing being asked about. On hardware, sweep $k$ and take the argmax; do not look for the sub-uniform tell.

21.5 Multiple Marked States, and Guessing Wrong

$M$ appears in the iteration count, so you need to know how many solutions there are before you can search for them. This is the algorithm's most awkward requirement and the one most often skipped.

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

More solutions means fewer iterations — $M = 4$ out of 16 needs only one.

What happens if you guess wrong

Suppose there are three solutions and you assume one:

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

Zero. Not degraded — zero.

The arithmetic, and it is exact:

   M=3, N=16:  θ = arcsin(√(3/16)) = 0.447832

   k=1:  (2k+1)θ = 1.343 rad = 0.4276π   ->  sin² = 0.949219
   k=2:  (2k+1)θ = 2.239 rad = 0.7127π   ->  sin² = 0.615967
   k=3:  (2k+1)θ = 3.135 rad = 0.9978π   ->  sin² = 0.000046

At $k = 3$ the state has rotated through almost exactly $\pi$ — landing on the unmarked axis. The amplitude on every solution is essentially zero, and you measure a non-solution with certainty.

🐛 Debug This — a Grover implementation returning nothing is more likely a wrong $M$ than a wrong oracle.

The symptom is distinctive: not "low success," but no successes at all across many shots, with a distribution that looks uniform over non-solutions.

A broken oracle usually marks the wrong state, so you see a different single answer dominating. A wrong $M$ rotates you onto the orthogonal subspace, so you see nothing.

The check: run with $k = 1$ and $k = 2$. If a small $k$ works and your computed $k$ does not, the oracle is fine and your $M$ is wrong. This costs two runs and immediately distinguishes the two most common failures.

When Grover fails entirely

   M/N     best k    P(best)   P(k=0)
   0.125        6     0.9998    0.1250
   0.250        1     1.0000    0.2500
   0.375        3     0.9902    0.3750
   0.500        4     0.5000    0.5000     <- no improvement possible

At $M/N = 1/2$, Grover cannot help. There, $\theta = \pi/4$, so $(2k+1)\theta = \pi/2$ requires $k = 0.5$ — and no integer number of iterations lands on the peak. You are stuck at the 50% you already had.

This is a fringe case for search, and it matters for the amplitude amplification generalization, where the "marked" fraction is whatever your subroutine's success probability happens to be.

The half-marked case is exact, and stranger than "you miss the peak"

"No integer lands on the peak" undersells what happens at $M/N = 1/2$. Tabulating $P(k)$ there:

   N = 16, M = 8:   θ = 0.7853982 rad = 0.2500 π

     k   (2k+1)θ      sin²
     0    0.2500π  0.500000
     1    0.7500π  0.500000
     2    1.2500π  0.500000
     3    1.7500π  0.500000
     4    2.2500π  0.500000
     5    2.7500π  0.500000
     6    3.2500π  0.500000
     7    3.7500π  0.500000
     8    4.2500π  0.500000

Every iteration count gives exactly 0.5. Not "close to 0.5", not "0.5 on average" — identically 0.5, forever.

The reason is one line. $\theta = \arcsin\sqrt{1/2} = \pi/4$ exactly, so $(2k+1)\theta$ is an odd multiple of $\pi/4$ for every integer $k$, and $\sin^2$ of every odd multiple of $\pi/4$ is $1/2$.

The rotation is happening. The state is moving by $\pi/2$ per iteration, a quarter turn, marching right round the circle — and every stopping point it can reach is equidistant from the two axes. It is not that Grover is weak here; it is that the geometry offers no place to stand.

Why this matters beyond the fringe case. It is the sharpest possible demonstration that Grover's output depends on $M/N$ and only on $M/N$. The algorithm has no other input. A subroutine whose success probability happens to sit at one half is unimprovable by amplitude amplification, and the only fix is to change the subroutine so that it is not one half — which is the sort of advice that sounds like a joke until you have hit it.

Amplitude amplification: the same rotation, on anything

Grover generalizes, and the generalization is used far more often than search is.

Replace $H^{\otimes n}$ with any state-preparation unitary $A$, and replace the diffuser with a reflection about $A|0\rangle$:

$$\mathcal{Q} = \underbrace{A\big(2|0\rangle\langle 0| - I\big)A^{\dagger}}_{\text{reflect about } A|0\rangle} \; \cdot \; \underbrace{O_f}_{\text{reflect about the bad subspace}}$$

Setting $A = H^{\otimes n}$ recovers Grover exactly, since $H^{\otimes n}|0\rangle = |s\rangle$. The derivation in §21.3 never used any property of $H^{\otimes n}$ except that it produced the state the diffuser reflects about, so all of it carries over unchanged with

$$\sin\theta = \sqrt{a}, \qquad a = \big|\langle \text{good}|A|0\rangle\big|^2$$

where $a$ is the success probability of the subroutine $A$ on its own. The uniform-superposition case is just $a = M/N$.

This turns Grover from a search algorithm into a general success-probability booster: given any quantum subroutine that succeeds with probability $a$ and a way to recognize success, you can raise $a$ to near 1 in $\mathcal{O}(1/\sqrt a)$ repetitions instead of the classical $\mathcal{O}(1/a)$.

Working the analytic numbers:

   a (subroutine)     θ      k_opt   P(k_opt)   classical repeats for the same P
           0.500  0.785398       0   0.500000                                  2
           0.250  0.523599       1   1.000000                                  0
           0.100  0.321751       2   0.998560                                 63
           0.050  0.225513       3   0.999939                                190
           0.010  0.100167       7   0.995344                                535
           0.001  0.031628      24   0.999558                              7,721

A subroutine that works one time in ten reaches 0.9986 in two amplitude-amplification iterations. Reaching the same confidence by rerunning it takes 63 attempts. Even counting each iteration as one $A$, one $A^\dagger$ and one oracle call, that is roughly 5 subroutine invocations against 63 — about $12\times$, which is the quadratic showing up at a size small enough to be useful.

And $a = 0.25$ is exact. $\theta = \pi/6$, so one iteration lands on $3 \times \pi/6 = \pi/2$ precisely, and $P = 1$. That is the same arithmetic as $M = 4$ out of $N = 16$ giving 1.0000 in the table above — the only case in this chapter where Grover is deterministic.

Where you will meet this again. Amplitude estimation — running phase estimation (Chapter 22 §22.4) on $\mathcal{Q}$ rather than iterating it — reads off $a$ itself to $\varepsilon$ accuracy in $\mathcal{O}(1/\varepsilon)$ queries where Monte Carlo needs $\mathcal{O}(1/\varepsilon^2)$. That is the same quadratic, and it is the engine behind most quantum proposals in finance and Monte Carlo integration. Quantum counting, the fix for §21.5's unknown $M$, is the same construction pointed at $M$: estimate $a = M/N$, multiply by $N$.

Which is worth pausing on. The remedy for "you must know $M$" is a subroutine that costs $\mathcal{O}(\sqrt N)$ — the same order as the search it protects. It does not change the asymptotics, and it roughly doubles the constant. Every remedy in this book is denominated in the currency of the disease, and this is a clean instance: the fix for a $\sqrt N$ algorithm's missing parameter costs $\sqrt N$.

🧱 Project Checkpoint — vqelab/grover.py: search that refuses to guess.

grover_circuit(n, oracle, iterations) and optimal_iterations(N, M) implementing $\lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor$.

success_probability(k, N, M) returns the analytic $\sin^2((2k+1)\theta)$ — the reference value to compare a run against, in the spirit of Chapter 7 §7.7.

GroverResult carries the measured probability, the predicted probability, the iteration count used, and whether the run was over-rotated — computed by checking whether a smaller $k$ would have done better.

estimate_marked_count(n, oracle) does the thing the algorithm cannot: it runs a short quantum counting sweep to estimate $M$ before committing to an iteration count, so that §21.5's zero-success failure is caught rather than suffered.

grover_cost(n, iterations) applies Chapter 19's Clifford+T accounting to the whole search — oracle and diffuser, every iteration — because §21.6 is the number that decides whether to run it.

Its tests assert: measured probability matches the analytic formula to $10^{-9}$; the optimal $k$ is the argmax over small $k$; over-rotation is detected; and an incorrect $M$ produces a near-zero success probability that the result object flags.

21.6 What It Actually Costs

Chapter 19 §19.7 said query complexity hides the cost of a query. Grover is where that bites hardest, because it makes $\sqrt N$ queries and each iteration contains two multi-controlled operations — the oracle and the diffuser.

Using Chapter 19's favourable accounting (ancillas available, so multi-controlled gates cost linear T count):

     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

A 20-bit search costs about 230,000 T gates. And that assumes the oracle is a single marked state — the cheapest possible predicate. A real constraint checker is much larger.

Through Chapter 15's resource estimator:

   n=8  (N=256):     1,128 T  ->    114,930 physical qubits,  0.01 s
   n=12 (N=4,096):   7,900 T  ->    177,990 physical qubits,  0.05 s
   n=16 (N=65,536): 44,622 T  ->    278,010 physical qubits,  0.30 s

Against classical brute force at $n = 20$: 1,048,576 evaluations of a cheap predicate — well under a second on one core.

🔬 Honest Assessment — where the quadratic speedup actually pays.

The crossover is governed by constants, and the constants are terrible. Grover does $\frac{\pi}{4}\sqrt N$ iterations, each costing thousands of fault-tolerant T gates, against a classical loop costing nanoseconds per iteration. Writing $c_q$ and $c_c$ for the per-iteration costs, quantum wins when

$$c_q \sqrt N < c_c N \qquad\Longleftrightarrow\qquad \sqrt N > c_q / c_c$$

With $c_q/c_c$ realistically in the range $10^{9}$–$10^{12}$ (fault-tolerant T gates against classical clock cycles), that needs $N > 10^{18}$ or worse — a search space of a quintillion, where the quadratic advantage finally overcomes the constant.

Such problems exist. Symmetric-key cryptanalysis is one: a 128-bit key space is $N = 2^{128}$, and $\sqrt N = 2^{64}$ is exactly the regime where the constants stop mattering. That is why Grover's practical significance is in cryptography — see §21.7.

For most search problems it is not close, and the reason is not that Grover is bad. It is that a quadratic speedup with a $10^{9}$ constant needs an enormous $N$ before it means anything, and most real search spaces are not enormous — or, if they are, they have structure a classical solver can exploit.

📐 Math Aside — the cost table in closed form.

The four totals above are not four independent measurements; they are one formula evaluated four times, and having it in closed form lets you price a search without running anything.

Measuring the ancilla-assisted multi-controlled X across sizes:

text n T per MCX CX per MCX T per Grover iteration 4 15 12 30 8 47 36 94 12 79 60 158 16 111 84 222 20 143 108 286

The T column is arithmetic in $n$ — the differences are a flat 32 per step of 4. Fitting:

$$T_{\text{MCX}}(n) = 8n - 17$$

and since one iteration is an oracle plus a diffuser, each an $(n-1)$-controlled operation,

$$\boxed{\;T_{\text{total}} = 2\,(8n - 17)\left\lfloor \frac{\pi}{4}\sqrt{2^n} \right\rfloor\;}$$

Check it against §21.6's table: $2(143)(804) = 229{,}944$ at $n=20$; $2(111)(201) = 44{,}622$ at $n=16$; $2(79)(50) = 7{,}900$; $2(47)(12) = 1{,}128$. All four, exactly.

The shape is the point. The per-iteration cost is linear in $n$ — a factor of five from $n=4$ to $n=20$ — while the iteration count is $\sqrt{2^n}$, a factor of 256 over the same range. So

$$T_{\text{total}} \;\approx\; \frac{\pi}{2}\,(8n-17)\,2^{n/2}$$

grows as $2^{n/2}$ up to a linear correction. Every extra bit of search space multiplies the cost by $\sqrt2 \approx 1.41$; every extra two bits doubles it. That is what a quadratic speedup looks like written as a bill: still exponential in the input length, just with half the exponent.

Extrapolating to the case §21.7 says actually matters — a 128-bit key — gives $2(8\cdot128 - 17)\cdot\frac{\pi}{4}2^{64} \approx 2.9\times10^{22}$ T gates for a single-marked-state oracle, which is the cheapest predicate imaginable and nothing like an AES circuit. This is a prediction from the fitted formula, not a measurement, and it is offered only to show that the exponent, not the constant, is what puts AES out of reach. For scale, Chapter 15 Case Study 1's RSA-2048 estimate runs on about $10^{10}$ T gates.

⚙️ Under the Transpiler — three spare qubits, 151× less depth.

Chapter 19 §19.6 measured a 491× T-count reduction from six ancillas on a single multi-controlled X. The effect on a whole Grover search is larger than that suggests, because the search contains $2k$ of them.

The $n = 4$, $k = 3$ circuit — 40 h, 30 x, 6 mcx as written, depth 171 before synthesis — transpiled four ways at optimization_level=0:

text basis width depth 2q gates total gates Clifford+T, no ancillas 4 23,547 84 29,392 Clifford+T, +3 ancillas 7 156 72 268 IBM basis (cz,rz,sx,x) 4 627 84 864 IBM basis, +3 ancillas 7 528 72 852

Three idle qubits take the Clifford+T circuit from depth 23,547 to 156 — a factor of 151 — and the gate count from 29,392 to 268. Same algorithm, same iteration count, same answer. The transpiler chose an ancilla-based synthesis for the MCXGate the moment it had room, exactly as §19.6 described, and it did so six times.

Now read the two bases against each other, because that comparison is the trap. In the IBM basis the no-ancilla circuit is depth 627 — perfectly reasonable — while in Clifford+T it is 23,547. The difference is not the algorithm. It is that rz is a free continuous rotation in the IBM basis and a Solovay–Kitaev sequence of T gates under fault tolerance. Chapter 19 §19.5 made this point about a single oracle; here it is a factor of 37 in depth on a complete search.

The practical rule: a Grover circuit that looks cheap on a NISQ backend has not been priced. The fault-tolerant number is the one in §21.6, and you only see it if you exclude rz from the basis.

Note also that optimization_level=3 on the width-4 IBM-basis circuit gives depth 343 with the same 84 cz gates. The optimizer halved the depth and removed none of the two-qubit gates, because the two-qubit count is structural: it is what the multi-controlled operations decompose into, and no peephole pass can rewrite an $(n-1)$-controlled X into fewer entangling gates.

💰 Cost and Queue — 90.6% of the machine is a magic-state factory.

§21.6 quoted 278,010 physical qubits for a 16-bit search. Asking Chapter 15's estimator for the breakdown rather than the total says where they go:

text n T total physical algorithm factories % factory factories 8 1,128 114,930 8,450 106,480 92.6% 11 12 7,900 177,990 15,750 162,240 91.2% 12 16 44,622 278,010 26,010 252,000 90.6% 14

Nine tenths of a fault-tolerant Grover machine is not running Grover. It is distilling magic states so that the other tenth can apply a T gate.

Chapter 15 §15.8 measured 93.0% at three T gates and 98.6% at ten; Chapter 15 Case Study 1 measured 3% for RSA-2048 at ten billion T gates, and drew the lesson that "T factories dominate" is a small-circuit statement that does not survive extrapolation. These three numbers place Grover precisely: at 44,622 T gates and 90.6% factories, a 16-bit search is still firmly in the small-circuit regime.

That is a genuinely unflattering result, and it is worth saying why. The factory fraction falls when a long runtime lets a few factories be reused — RSA-2048 spreads its T gates over a day and a half. A 16-bit Grover search runs in 0.30 seconds. It demands its T gates too quickly to amortize the hardware that makes them, so it pays for parallel factories it uses briefly.

Which points at the honest comparison. The 26,010 algorithm qubits are the part doing the search. The other 252,000 are overhead for asking a fault-tolerant machine to do it in a third of a second — to solve a problem that a classical core, at Exercise 21.22's 1 ns per check, finishes in about 66 microseconds. Chapter 39 §39.5's costing exercise found the same shape at the billing layer: the number you want is rarely the number the total reports.

21.7 Grover Does Not Search a Database

The most common description of Grover's algorithm is wrong, and the way it is wrong matters.

"Grover's algorithm searches an unsorted database of $N$ items in $\sqrt N$ steps."

There is no database. Chapter 19 §19.7 stated the gap; here is what it means concretely.

The oracle must be a circuit. Grover queries $O_f$, a unitary you have built out of gates. To search actual data, that data must be encoded in the circuit — which means you have already touched all $N$ items to build it, at cost $\mathcal{O}(N)$, before the search begins.

So the $\sqrt N$ never includes reading the data. For genuine database search the cost is $\mathcal{O}(N)$ to construct plus $\mathcal{O}(\sqrt N)$ to search, and the first term dominates.

What Grover actually does is search a space defined by a predicate you can compute:

• find an input to a hash function producing a given output,
• find a key that decrypts a known plaintext,
• find an assignment satisfying a constraint formula.

In each case the "database" is implicit — $2^n$ candidates that are never enumerated, recognized by a circuit that is small compared to $N$. That is a real and useful capability, and it is not database search.

The QRAM problem is the input problem

The standard rebuttal to the above is QRAM: a hypothetical quantum memory that returns $\sum_x \alpha_x |x\rangle|D_x\rangle$ in one operation, so the oracle could consult the data without the circuit containing it.

It is worth recognizing that this is not a Grover problem. It is Chapter 32 §32.2's input problem, arriving three parts early and wearing different clothes.

The two statements are the same statement:

   Chapter 32 §32.2   loading N classical numbers into amplitudes costs O(N),
                      which is what a quantum ML speedup was supposed to save

   Chapter 21 §21.7   loading N classical records into an oracle costs O(N),
                      which is what a quantum search speedup was supposed to save

In both cases the algorithm's advantage is measured in queries, and getting the data into a state where it can be queried costs more than the queries save. Chapter 32 measured the amplitude-encoding version precisely: $N - \log_2 N - 1$ gates to load $N$ amplitudes. Linear, and no proposal has ever made it sublinear, because it cannot be — writing down $N$ independent numbers takes $N$ operations.

Frameworks will happily build you the loader, which makes the cost easy to measure rather than argue about. PennyLane 0.45.1 ships qml.QROM, a template that loads a table of classical bitstrings into a quantum register. Decomposing it into a two-qubit gate set and counting:

   records N   address qubits   gates   2-qubit+   gates per record
           2                1       3          1               1.50
           4                2      10          2               2.50
           8                3      27          3               3.38
          16                4      71          7               4.44
          32                5     180         20               5.62
          64                6     418         34               6.53
         128                7     959         63               7.49

Gates per record is not constant — it is rising. Doubling $N$ multiplies the gate count by about 2.3, so the loader is not merely linear in $N$, it is slightly superlinear over this range. 128 one-bit records cost 959 gates to load.

Now put that next to what Grover would save on those 128 records. $\lfloor\frac{\pi}{4}\sqrt{128}\rfloor = 8$ iterations against 128 classical checks — a saving of 120 predicate evaluations. Each iteration needs the QROM and its uncomputation, so the loading alone is $8 \times 2 \times 959 \approx 15{,}300$ gates. The data movement costs about 128 times what the search saves, on the most favourable possible reading of "cost".

And this is one-bit records with no error correction, no fault tolerance, and a loader the framework generated for you.

The three objections to QRAM compound, and Case Study 2 works through them. It does not exist; building it is $\mathcal{O}(N)$; and it must remain coherent across all $\sqrt N$ iterations, which means a fault-tolerant memory of $N$ items sitting inside the computation. Any one of those would be sufficient.

⚠️ Common Pitfall — "assume QRAM" is not a modelling simplification.

Papers proposing quantum speedups on classical data frequently open with "we assume access to a QRAM." It reads like the sort of harmless idealization physicists make all the time — assume a frictionless plane, assume a spherical cow.

It is not. The assumption grants exactly the resource whose cost is the thing being claimed as a saving. A frictionless plane does not hand you the energy the experiment is trying to measure.

The test to apply: ask what the result becomes if the QRAM costs $\mathcal{O}(N)$ to build, which is the only cost anyone has ever demonstrated. If the speedup survives, the assumption was harmless. If the speedup evaporates, the assumption was the speedup.

Chapter 32 §32.8's checklist for reading a QML paper has this as its seventh question, and it is the same question here: is the data classical? If it is, someone has to load it, and the loading is the bill.

Where Grover would actually help

Negative results are easier to state than useful criteria, so here is the criterion in a form you can apply to a proposal before spending a week on it. All five have to hold.

1. The candidate space is implicit. You can generate candidates from an index without storing them. $2^n$ bit strings, all keys of length $k$, all assignments to $n$ variables. If someone has to hand you a list, stop.

2. The predicate is a small circuit. "Small" means small compared to $N$, and cheap in T gates, not in gate count — §21.6's accounting is the one that matters. The predicate is evaluated $2\lfloor\frac{\pi}{4}\sqrt N\rfloor$ times, so its cost is multiplied by roughly $\sqrt N$.

3. The space is genuinely unstructured. No sortable key, no prunable branch, no gradient, no locality. This is where almost every candidate dies, and Case Study 2's B-tree is why: a classical algorithm that can exploit structure achieves $\mathcal{O}(\log N)$, which beats $\mathcal{O}(\sqrt N)$ by an exponential. Grover is optimal only among algorithms forbidden to look.

4. $N$ is enormous. §21.6's crossover is $\sqrt N > c_q/c_c \approx 10^9$–$10^{12}$, so $N > 10^{18}$. Not "big data" enormous — cryptographic enormous.

5. You know $M$, or can afford to estimate it. §21.5 is not optional, and the estimator costs $\mathcal{O}(\sqrt N)$ of its own.

The set of problems satisfying all five is small and is dominated by cryptanalysis, which is the honest summary of what Grover is for. It also includes some structured-search subroutines where Grover is used inside a classical algorithm — quantum backtracking and quantum minimum-finding are the usual examples — and those inherit every one of the five conditions plus the fault-tolerance bill.

What is not on the list is anything with the word "database" in it.

🔀 In Another Framework — what the three frameworks give you, verified in this environment.

```text qiskit 2.5.1 qiskit.circuit.library.GroverOperator PRESENT qiskit.algorithms ABSENT qiskit_algorithms (standalone) not installed

pennylane 0.45.1 qml.GroverOperator PRESENT qml.AmplitudeAmplification PRESENT qml.Reflection PRESENT qml.QROM PRESENT

cirq 1.7.0 (no Grover helper of any kind) ```

Qiskit gives you the operator, not the algorithm. GroverOperator(oracle=...) builds $D \cdot O_f$ — one iteration — and you compose it $k$ times yourself. That is the right API, and it is a deliberate improvement on what came before: the iteration count is the parameter that breaks searches (§21.5), so making the caller supply it is a feature.

PennyLane goes furthest. qml.GroverOperator is the diffuser, qml.Reflection generalizes it to reflect about an arbitrary state, and qml.AmplitudeAmplification implements §21.5's generalization directly. The naming is worth noticing — PennyLane treats amplitude amplification as the primitive and Grover as the special case, which is the correct way round.

Cirq has nothing, and that is a defensible position rather than an omission. Grover is twenty lines: Hadamards, a phase oracle, a diffuser, repeat. Chapter 14 §14.7 found Cirq consistently prefers explicit primitives over convenience layers, and a library function whose main risk is being called with the wrong $k$ is a reasonable thing to decline to ship. Chapter 18 §18.5's choosing criteria apply unchanged.

Whichever you use, the iteration count is yours. No framework can compute it for you, because none of them knows $M$.

🗝️ Version Note — qiskit.algorithms.Grover is gone.

Older tutorials use:

python from qiskit.algorithms import Grover, AmplificationProblem # ModuleNotFoundError problem = AmplificationProblem(oracle, is_good_state=...) result = Grover(sampler=sampler).amplify(problem)

qiskit.algorithms is not part of Qiskit any more. Verified against Qiskit 2.5.1 in this environment: the import raises ModuleNotFoundError. The algorithm layer now lives in a standalone qiskit-algorithms package, separately installed and separately versioned — the same split Chapter 7 §7.1 tabulates for qiskit-nature and qiskit-optimization.

What survived inside Qiskit itself is qiskit.circuit.library.GroverOperator, which is a circuit, not an algorithm — it builds one iteration and leaves the loop to you.

The pattern is worth internalizing: Qiskit kept the circuit layer and shed the algorithm layer. If a tutorial imports an algorithm class from qiskit, it predates the split, and the rest of its API usage should be treated with the same suspicion — qiskit.pulse, removed in Qiskit 2.0 (Chapter 31), is the other common casualty.

🧪 Run It — three experiments, all on a simulator, all under a minute.

1. Find the second peak yourself. Run $N = 64$, $M = 1$, and tabulate $P(k)$ for $k = 0 \dots 40$. Confirm the peaks land where $(2k+1)\theta \approx \pi/2 + m\pi$ and that the period is $\pi/(2\theta) = 12.53$ iterations — twice §21.4's 6.22 at $N=16$, because quadrupling $N$ halves $\theta$. Then find the worst $k$ in the first period and check it against the uniform $1/64$.

2. Reproduce the noise result above. Build the $n=4$ circuit, attach a depolarizing model at $p_2 = 0.005$, and sweep $k = 0 \dots 6$. Confirm the argmax moves from 3 to 2. Then raise the error rate until $k=6$ climbs back above $1/16$ — the point at which over-rotation becomes undetectable. This is the most useful hour in the chapter, because it is the failure you will actually meet.

3. Price your own predicate. Take any oracle you have written, transpile it to ["h","s","sdg","t","tdg","x","y","z","cx"] with optimization_level=0, count t plus tdg, and multiply by $2\lfloor\frac{\pi}{4}\sqrt{N}\rfloor$. Then transpile it again with the same width you would actually allocate. §21.6's ⚙️ Under the Transpiler measured a factor of 151 in depth between those two calls, and you should know which one your number came from.

🔬 Honest Assessment — the cryptographic case, stated carefully.

The claim you can rely on: Grover reduces the effort of brute-forcing a symmetric key from $2^{k}$ to about $2^{k/2}$. AES-128 drops to roughly 64 bits of security; AES-256 to roughly 128. This is the standard justification for doubling symmetric key lengths, and it is sound.

The qualifications that matter:

It is not parallelizable the way classical brute force is. Splitting a Grover search across $p$ machines gives $\sqrt{N/p}$ per machine, so you gain only $\sqrt p$ — where classical brute force gains a full factor of $p$. A large classical cluster erodes the advantage substantially.

The circuit is enormous and must run coherently. $2^{64}$ iterations, each with an AES circuit inside it, all inside one fault-tolerant computation. Published estimates put this well beyond anything on any roadmap.

And the timeline is different from Shor's. Chapter 23's factoring breaks RSA outright, and Chapter 15 Case Study 1 priced it at ~25 million qubits. Grover does not break AES — it weakens it by a factor of two in the exponent, which the response of doubling key sizes handles completely.

The practical summary: use AES-256, and worry about Shor.

21.8 Summary

Grover has no promise. Chapter 20's algorithms all required special structure; Grover works on any predicate, which is why it applies to real problems. The price is that the speedup is quadratic — $\mathcal{O}(\sqrt N)$ against $\mathcal{O}(N)$ — and that is provably optimal, not a weakness. Aaronson and Ambainis proved exponential speedups require promise structure.

The algorithm is two reflections, hence a rotation. The oracle reflects about the solutions; the diffuser $D = H^{\otimes n}(2|0\rangle\langle 0| - I)H^{\otimes n}$ reflects about the uniform superposition — and the diffuser is itself a phase oracle, marking $|0\dots0\rangle$, which is why it costs the same order as the oracle.

★ The success probability is exactly $P(k) = \sin^2\!\big((2k+1)\theta\big)$ with $\sin\theta = \sqrt{M/N}$ — verified against simulation to $10^{-15}$. Optimal iterations: $\lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor$, giving $P = 0.9613$ at $N=16$, $M=1$. Not 1 — $k$ must be an integer, so you get a high probability and repeat if unlucky.

★★ Over-rotation is real and severe. At $N=16$: 3 iterations gives 0.9613, 6 gives 0.0204 — 2% of optimal, and below the 0.0625 you started with. Running it longer does not converge; it oscillates. Compute $k$ in advance and stop.

Later peaks exist at $(2k+1)\theta = \pi/2 + m\pi$ — $k=9$ genuinely beats $k=3$ (0.9922 vs 0.9613) at three times the cost. Use the first peak.

★★ You must know $M$, and guessing wrong is catastrophic. With three solutions but $M=1$ assumed, $k=3$ gives $P = 0.0000$ — $(2k+1)\theta = 0.9978\pi$, rotating almost exactly onto the unmarked axis. The symptom is no successes at all, distinct from a broken oracle's wrong-but-consistent answer. Check by running $k=1$ and $k=2$. And at $M/N = 1/2$ Grover cannot help at all.

★ The cost is the thing. A 20-bit search: 229,944 T gates across 804 iterations, each containing an oracle and a diffuser. Through Chapter 15's estimator, a 16-bit search needs 278,010 physical qubits. Classical brute force at 20 bits is under a second on one core. Quantum wins only when $\sqrt N > c_q/c_c \approx 10^{9}$–$10^{12}$, needing $N > 10^{18}$.

★★ Grover does not search a database. The oracle is a circuit, so real data must be encoded into it — touching all $N$ items at cost $\mathcal{O}(N)$ before the $\mathcal{O}(\sqrt N)$ search begins. What it actually searches is a space defined by a predicate you can compute: hash preimages, decryption keys, constraint assignments. The candidates are never enumerated.

Cryptographically, Grover takes symmetric key strength from $2^k$ to $2^{k/2}$ — the standard argument for doubling key lengths. But it parallelizes poorly ($\sqrt p$ from $p$ machines, versus classical $p$), requires an enormous coherent computation, and does not break AES the way Shor breaks RSA. Use AES-256; worry about Shor.

Everything follows from two reflections. $O_f$ reflects about $|u\rangle$, $D$ reflects about $|s\rangle$, both preserve the plane spanned by $|m\rangle$ and $|u\rangle$, and a product of two reflections at angle $\theta$ is a rotation by $2\theta$ — with no $k$ in it, which is why the algorithm cannot slow down near the target. In amplitude terms the same thing reads as inversion about the mean, and the hand arithmetic reproduces every measured probability exactly: the unmarked amplitude goes negative at $k=3$, the mean goes negative at $k=4$ — the first iteration the probability falls — and by $k=6$ the marked amplitude is $-0.1428$, smaller than the $-0.2556$ on each unmarked state. The answer has become the least likely outcome. $P(k)$ is a sinusoid of period $\pi/(2\theta) = 6.22$ iterations, so $k=6$ is 96.5% of the way round, still short of the start, which is exactly why 0.0204 is below 0.0625.

★ And the optimal iteration count moves under noise. With a depolarizing model on the $n=4$ circuit (84 cz gates, depth 474), $k=2$ beats $k=3$ from a two-qubit error rate of 0.005 upward — the analytic optimum stops being the empirical one. Worse, at $p_2 = 0.020$ over-rotation at $k=6$ scores 0.0712, above the uniform 0.0625, because noise drags every outcome toward $1/N$ from both directions. The "below $1/N$" diagnostic is a simulator diagnostic and does not survive hardware.

The T count has a closed form: $T_{\text{total}} = 2(8n-17)\lfloor\frac{\pi}{4}\sqrt{2^n}\rfloor$, which reproduces all four rows of §21.6's table exactly and grows as $2^{n/2}$ up to a linear correction — still exponential in the input length, with half the exponent. Of the 278,010 physical qubits for a 16-bit search, 252,000 (90.6%) are magic-state factories, placing Grover firmly in Chapter 15's small-circuit regime. And three spare qubits take the $n=4$, $k=3$ circuit from depth 23,547 to 156 in Clifford+T — Chapter 19 §19.6's ancilla trade, applied $2k$ times.

★ The QRAM objection is Chapter 32 §32.2's input problem wearing different clothes: loading $N$ classical items into a quantum state costs $\mathcal{O}(N)$, which is exactly what the query speedup was supposed to save. Measured with PennyLane's qml.QROM: 128 one-bit records cost 959 gates to load, and gates-per-record is still rising at that size. A Grover search over those 128 addresses is 8 iterations — so the loading alone costs roughly 128× what the search saves. "Assume QRAM" is not a harmless idealization; it grants precisely the resource whose cost is the claim.

Next: Chapter 22 — the Quantum Fourier Transform and phase estimation. Chapter 19's kickback extracted one bit of phase; the QFT extracts many, which is the machinery Shor's algorithm runs on and the reason the next chapter is the pivot of Part IV.