Search and Amplitude Amplification

Fix the problem precisely. We are given a function $f:\{0,1{\}}^n\to \{0,1\}$ as a black box — an oracle — that returns 1 on some hidden set of $M$ “solutions” and 0 on the other $N-M$ inputs, where $N=2^n$. We may only query it: hand it an $x$ and learn $f(x)$. There is no structure to exploit — no periodicity, no monotonicity, nothing but yes/no answers. How many queries to find a solution?

Classically the answer is stark. With no structure, every unqueried input is equally likely to be the needle, so you can do no better than try them one by one: $\approx N/2$ queries on average (the expectation is exactly $(N+1)/2$ for a single needle), $N$ in the worst case. The question of this chapter is whether a quantum machine, allowed to query the oracle in superposition, can do better — and if so, how much.

The quantum query model was set up in Chapter 6. The key device is the phase-flip oracle: rather than write the answer into an output register, it marks a solution by flipping the sign of its amplitude,

This is the phase-kickback trick of Chapter 6: a controlled operation with an output qubit prepared in $|-⟩$ deposits the answer as a phase on the input. One query of $O_f$ touches all $N$ amplitudes at once. That is the raw material; the art is turning an invisible phase into a visible probability.

A phase flip alone accomplishes nothing measurable: the marked amplitude is now $-1/\sqrt{N}$ instead of $+1/\sqrt{N}$, but its magnitude — and so its measurement probability — is unchanged. Grover's insight is to follow the oracle with a second operation that converts that sign difference into a difference in magnitude: the diffusion operator, an inversion about the mean.

Start in the uniform superposition $|s⟩=H^{\otimes n}|0⟩=\frac{1}{\sqrt{N}}{\sum }_x|x⟩$. The diffusion operator is the reflection

whose action on any state is wonderfully concrete: if $\bar{a}$ is the mean of the amplitudes, then $D$ sends each amplitude $a\mapsto 2\bar{a}-a$ — it reflects every amplitude through the average. After the oracle has pushed the marked amplitude below zero, the mean dips slightly; reflecting the lone negative amplitude about that mean sends it well above the crowd, while the many positive amplitudes each shrink a little. One Grover iteration is $G=D{O}_f$: oracle, then diffusion.

Why a rotation? Because the whole dance happens in a two-dimensional plane. Let $|\beta ⟩$ be the (normalized) uniform superposition of the $M$ solutions and $|\alpha ⟩$ the uniform superposition of the $N-M$ non-solutions. The start state is $|s⟩=\cos \theta |\alpha ⟩+\sin \theta |\beta ⟩$ with

a small angle when solutions are rare. The oracle $O_f$ is a reflection about $|\alpha ⟩$ (it flips the $|\beta ⟩$ component); the diffusion $D$ is a reflection about $|s⟩$. The composition of two reflections is a rotation by twice the angle between their axes — here a rotation by $2\theta$ that carries the state toward $|\beta ⟩$. After $k$ iterations the state sits at angle $(2k+1)\theta$, so the probability of measuring a solution is

This is the master law of the chapter, and the Lab referees the simulator against it at a tolerance of order $10^{-13}$ (the achieved deviation is read live in the panel). To make $(2k+1)\theta \approx \pi /2$ — the top of the sine — we want

which for a single solution is the famous $\frac{\pi }{4}\sqrt{N}$. Here is the trap that (8.4) makes vivid: the success probability is oscillatory. Run past $k_{\text{opt}}$ and the state rotates beyond the solution axis; the probability falls again, all the way back to nearly zero near $k\approx \pi /2\theta$. More iterations are not better. A quantum searcher must stop at exactly the right time, which is why knowing $M$ (or estimating it) matters. Drive the amplitudes yourself. The explorer below holds a real array of $N$ amplitudes and does exactly what the lab does — flip the sign of the marked one, then send every amplitude to $2\bar{a}-a$ — so what you see is the mechanism running, not a plot of (8.4). You can stop it half-way through an iteration to catch the marked amplitude below the axis and the mean (gold dashed) dipping with it:

Notice how flat the marked bar starts — at $k=0$ it is just $1/\sqrt{N}$, the same as every other — and how steeply it climbs, then falls. The closed form (8.4) is never used to draw the bars, so the explorer can be compared against it, and it prints that comparison for the state on screen; the Lab does the same at every $k$ of every $N$ in its sweep, at machine precision.

Grover's trick does not depend on the start being the uniform superposition. Suppose any quantum subroutine $A$ (a state-prep circuit, with no measurements) produces

so that a plain measurement finds a “good” outcome with probability $a^2$, perhaps small. (A phase convention hides in (8.6): we take $a=⟨\text{good}|A|0⟩$ to be real and $\ge 0$, absorbing any phase into $|\text{good}⟩$ — automatically true for the lab's construction, where $A$ is a product of real $R_y$ rotations.) The amplitude amplification operator replaces Grover's two reflections with the analogous pair,

a reflection across the complement of the good subspace — $I-2P_{\text{good}}$ flips the sign of the good component and fixes everything orthogonal to it, exactly as the oracle of §8.2 reflected across $|\alpha ⟩$ by flipping $|\beta ⟩$ — followed by a reflection about the prepared state $A|0⟩$. Exactly as before, this rotates by $2\theta$ in the two-dimensional $\{|\text{good}⟩,|\text{bad}⟩\}$ plane, so after $k$ steps the good-outcome probability is ${\sin }^2((2k+1)\theta )$ again, reaching near 1 after

steps — a quadratic improvement over the $O(1/a^2)$ repetitions a classical “prepare, measure, retry” loop would need. Grover's algorithm is the special case $A=H^{\otimes n}$, where $A(2|0⟩⟨0|-I)A^{†}=2|s⟩⟨s|-I$ is exactly the diffusion operator. The Lab builds a deliberately biased $A$ — a product of $R_y$ rotations whose success amplitude $a$ is a few percent, printed live in the panel — and boosts it to near-certainty, verifying the same sin² law to the same machine-precision standard as Grover's own. This generalization is what makes Grover a building block: wrap it around any subroutine whose successes you can recognize, and you square the number of tries.

Could a cleverer quantum algorithm beat $\sqrt{N}$? No — and this is provable. The BBBV theorem (Bennett, Bernstein, Brassard, and Vazirani) shows that any quantum algorithm that finds a marked item among $N$ using an unstructured oracle with bounded error — succeeding with probability at least, say, $2/3$ on every instance — must make at least

queries. The idea of the proof is a “hybrid” argument: each query can only nudge the state a little, and it takes $\Omega (\sqrt{N})$ such nudges before the algorithm's behaviour can depend appreciably on which item is marked. Grover meets this bound, so it is optimal: the quadratic speedup is the exact ceiling for unstructured search.

This deserves an honest scorecard. Grover's advantage is quadratic, not exponential. A million-item search drops from $\sim 5\times 10^5$ queries to $\sim 800$ — genuinely useful, but a far cry from the exponential collapse Shor gives factoring. And it comes with fine print: you need a real quantum oracle for $f$ (building one can cost as much as the search it saves), you need to know roughly how many solutions there are (to avoid over-rotating), and the whole run must stay coherent. The lesson to carry forward is that quantum speedups are problem-specific: exponential when there is structure to exploit (Chapter 7 and, next, simulation), quadratic and provably no more for pure unstructured search.

The same quadratic flavour appears in a different guise, one that has become a general-purpose algorithmic primitive: the quantum walk. Consider a walker on a line. A classical random walker flips a coin at each step and moves left or right; after $t$ steps its position is spread over a Gaussian of width $\sigma \sim \sqrt{t}$ — the familiar diffusive scaling of Brownian motion.

A quantum walker carries a “coin” qubit. Each step applies a Hadamard to the coin — putting it in superposition of left and right — and then a conditional shift that moves the left-amplitude left and the right-amplitude right. Because the amplitudes interfere rather than average, the distribution does not pile up in the middle; it races outward in two ballistic fronts, and the spread grows linearly,

That is again a quadratic separation — the quantum walker covers in $t$ steps what the classical walker needs $t^2$ to reach. The Lab evolves both walkers — the quantum one as amplitudes with a coin, the classical one as an exact probability distribution updated by $p_{t+1}(x)=\frac{1}{2}{p}_t(x-1)+\frac{1}{2}{p}_t(x+1)$ — and fits the exponent of $\sigma (t)$ from each evolved dataset: it comes out $\approx 1$ for the quantum walk and $\approx \frac{1}{2}$ for the classical one, refereed. Discrete- and continuous-time quantum walks underlie a whole family of algorithms — element distinctness, spatial search, and, in a sense, even Grover — where the walk's fast spreading is exactly what accelerates the search.

A fresh state-vector simulator — the same flat array of $2^n$ amplitudes from Chapter 2 — carries the whole chapter. The oracle is a sign flip on the marked indices; the diffusion is one pass computing the mean and reflecting through it:

1impl State {
2// …
3    /// THE ORACLE. Mark solutions by a phase flip: |x> -> -|x> for x in
4    /// `marked`, and leave every other basis state alone. This is I - 2·P_good.
5    fn oracle(&mut self, marked: &[usize]) {
6        for &m in marked {
7            self.amps[m] = -self.amps[m];
8        }
9    }
10
11    /// THE DIFFUSION OPERATOR 2|s><s| - I: inversion about the mean amplitude.
12    /// Reflecting every amplitude through the average sends a -> 2·mean - a.
13    fn diffuse(&mut self) {
14        let dim = self.dim();
15        let mean: C = self.amps.iter().sum::<C>() / (dim as f64);
16        for a in self.amps.iter_mut() {
17            *a = 2.0 * mean - *a;
18        }
19    }
20
21    /// Total probability sitting on the marked set — the success probability.
22    fn success(&self, marked: &[usize]) -> f64 {
23        marked.iter().map(|&m| self.amps[m].norm_sqr()).sum()
24    }
25}

The headline referee never trusts the simulator on its own word: it computes the geometry independently — $\theta$ from $\sqrt{M/N}$, the success probability from ${\sin }^2((2k+1)\theta )$, and the optimal $k$ from $\pi /4\theta$ — and demands agreement at every step of every $n$ in the sweep, at a tolerance of $5\times 10^{-13}$ (the deviation the run actually achieves is in the panel):

1/// The half-angle θ of the search: sinθ = √(M/N).
2fn grover_theta(m: usize, n_dim: usize) -> f64 {
3    (m as f64 / n_dim as f64).sqrt().asin()
4}
5
6/// Success probability after k iterations, sin²((2k+1)θ).
7fn grover_law(k: usize, theta: f64) -> f64 {
8    let s = ((2 * k + 1) as f64 * theta).sin();
9    s * s
10}
11
12/// The optimal integer iteration count, round(π/(4θ) − 1/2).
13fn k_optimal(theta: f64) -> usize {
14    let x = PI / (4.0 * theta) - 0.5;
15    x.round().max(0.0) as usize
16}
17// …
18    let mut worst_law: f64 = 0.0;
19    for n in 2..=12 {
20        let big_n = 1usize << n;
21        let marked = vec![(0x2b_usize.wrapping_mul(n)) % big_n]; // an arbitrary target
22        let theta = grover_theta(1, big_n);
23        let k_max = 2 * k_optimal(theta) + 2;
24        let mut s = State::zero(n);
25        s.hadamard_all();
26        for k in 0..=k_max {
27            let dev = (s.success(&marked) - grover_law(k, theta)).abs();
28            worst_law = worst_law.max(dev);
29            s.oracle(&marked);
30            s.diffuse();
31        }
32    }
33    assert!(worst_law.is_finite());
34    referees.push(Referee {
35        name: "Grover P(k) = sin²((2k+1)θ), n=2..12".into(),
36        value: worst_law,
37        tol: 5e-13,
38        pass: worst_law < 5e-13,
39    });

That check grades a probability, and along Grover's own orbit every amplitude stays real — so a diffusion that mishandled the imaginary part of an amplitude would sail straight through it. That is not hypothetical: replacing the mean by the mean of the real parts alone leaves every other referee in this lab passing. A second referee therefore grades the mechanism of §8.2 directly, as an operator identity: the simulator's two in-place passes against an explicit dense $(2|s⟩⟨s|-I)(I-2P_{\text{good}})$ matrix, applied to a deliberately lopsided state with unequal magnitudes and phases. It is the check that catches a dropped factor of 2 in $a\mapsto 2\bar{a}-a$:

1// =====================================================================
2    // Referee 2: the mechanism itself, as an operator identity. The simulator
3    // never builds a matrix — oracle() flips signs in place and diffuse() makes
4    // one O(N) pass computing the mean — so here the SAME single iteration is
5    // recomputed a second, independent way: the dense matrix
6    //   G_ij = (2/N − δ_ij) · (−1)^{f(j)}
7    // read straight off G = (2|s><s| − I)(I − 2P_good), applied by an explicit
8    // matrix-vector product. It is run on a deliberately lopsided state (unequal
9    // magnitudes AND phases, two marked items), because along the symmetric
10    // Grover orbit a wrong mean or a dropped factor of 2 can hide.
11    // =====================================================================
12    let mech_n = 6usize;
13    let mech_dim = 1usize << mech_n;
14    let mech_marked = vec![9usize, 44usize];
15    let mut mech = State::zero(mech_n);
16// …
17    let mut mech_sim = mech.clone();
18    mech_sim.oracle(&mech_marked); // path A: the two in-place passes
19    mech_sim.diffuse();
20    let mut mech_mat = vec![c(0.0, 0.0); mech_dim]; // path B: the dense matrix
21    for i in 0..mech_dim {
22        let mut acc = c(0.0, 0.0);
23        for j in 0..mech_dim {
24            let sign = if mech_marked.contains(&j) { -1.0 } else { 1.0 };
25            let refl = 2.0 / mech_dim as f64 - if i == j { 1.0 } else { 0.0 };
26            acc += refl * sign * mech.amps[j];
27        }
28        mech_mat[i] = acc;
29    }
30    let mech_dev = mech_sim
31        .amps
32        .iter()
33        .zip(mech_mat.iter())
34        .map(|(a, b)| (a - b).norm())
35        .fold(0.0f64, f64::max);
36    assert!(mech_dev.is_finite());
37    referees.push(Referee {
38        name: "Iteration = (2|s><s|−I)(I−2P) matrix, max |Δa|".into(),
39        value: mech_dev,
40        tol: 2e-16,   // roundoff-tight: the two paths agree to ~1e-16
41        pass: mech_dev < 2e-16,
42    });

The quantum walk is its own small engine: a coin Hadamard and a conditional shift, iterated, with the position spread measured at each step and its growth exponent fit by least squares. The line is sized so that nothing is ever shifted off its ends — and that, too, is refereed rather than asserted, by measuring the walker's total probability at every step:

1/// σ(t) of the quantum walker's position for t = 0..=steps, together with the
2/// total probability at each step. The line holds 2·steps+1 sites, which is
3/// exactly wide enough that no amplitude is ever shifted off either end during
4/// the run: the two ballistic fronts reach the outermost sites only at t =
5/// steps. Returning the totals lets a referee CHECK that containment rather
6/// than take it on trust.
7fn quantum_walk_sigma(steps: usize) -> (Vec<f64>, Vec<f64>) {
8// …
9    for _ in 0..steps {
10        // Coin: Hadamard mixing the two coin components at each position.
11        let mut b0 = vec![c(0.0, 0.0); width];
12        let mut b1 = vec![c(0.0, 0.0); width];
13        for p in 0..width {
14            b0[p] = inv * (amp0[p] + amp1[p]);
15            b1[p] = inv * (amp0[p] - amp1[p]);
16        }
17        // Shift: coin-0 moves left (p-1), coin-1 moves right (p+1).
18        let mut n0 = vec![c(0.0, 0.0); width];
19        let mut n1 = vec![c(0.0, 0.0); width];
20        for p in 0..width {
21            if p >= 1 {
22                n0[p - 1] = b0[p];
23            }
24            if p + 1 < width {
25                n1[p + 1] = b1[p];
26            }
27        }
28        amp0 = n0;
29        amp1 = n1;
30        sigmas.push(position_sigma(&amp0, &amp1, start));
31        totals.push(walk_total(&amp0, &amp1));
32    }
33    (sigmas, totals)
34}

Every referee writes its verdict to JSON, and the panel below reads the whole scoreboard live — the count, the achieved values, and the tolerances are all whatever the last run produced, not numbers typed into this page. The Grover law holds across the whole $n$ sweep; the diffusion matches its matrix definition to floating-point roundoff; the numeric peak lands on the predicted $k_{\text{opt}}$ exactly; the multi-solution case obeys the same law with $\sin \theta =\sqrt{M/N}$; amplitude amplification boosts a biased subroutine to near-certainty on schedule; and the two evolved walkers separate cleanly into a slope-1 (ballistic) and a slope-½ (diffusive) line — both slopes fit from the data, neither asserted.

Run it yourself with cargo run --release in Rust-QML/ch08-grover. Grover and Shor are the two celebrities of quantum algorithms, and between them they mark the boundary of the honest scorecard: quadratic where there is no structure, exponential where there is. The next chapter turns to the problem that started the field — and where the exponential advantage is least in doubt.