Quantum Computing · Part B — 05
Amplitude Amplification
Grover’s search is one idea wearing a famous name: take a faint amplitude on the answer you want and rotate it louder, a little each round. Strip away the search story and it’s a general tool — amplitude amplification — that boosts any outcome you can recognize, in about √N steps instead of N.
↩ before you start · keep these handy
·From QI 8c: Grover finds 1 of N in ~√N queries by alternating an oracle and a “diffusion” step.
·From QC 03: the oracle marks the good state by flipping its sign, (−1)f(x), via kickback.
·From QI 0.3: probability = |amplitude|². Boosting an amplitude boosts its odds.
🔑 symbol decoder · every new mark, in plain words
|good⟩the combined direction of all the answers you’re looking for (the marked items).
|bad⟩everything else — all the non-answers, lumped into one direction.
oracle (reflection)flips the sign of |good⟩ — geometrically, a mirror-flip about the |bad⟩ axis.
diffusion“reflect about the average” — a mirror-flip about the starting state. Together with the oracle it rotates.
θ (theta)the small starting angle of the state above |bad⟩: sinθ = √(M/N), with M marked of N.
G (iteration)one oracle + one diffusion = a rotation of the state by 2θ toward |good⟩.
feel
Turning the signal up, one notch at a time
At the start every item is equally likely, so the answer’s amplitude is a whisper: 1/√N. Each Grover round does two flips that, combined, rotate the whole state a fixed angle toward the answer. Do it the right number of times and the answer’s amplitude swings up near 1 — almost a sure thing — after only about √N rounds.
🎵 everyday picture
Imagine a record on a turntable and a needle that nudges it the same small angle every push. The answer sits at the top; you start near the bottom. Each push (one Grover round) turns you a notch toward the top. A few dozen pushes and you’re pointing almost straight up — but keep pushing past that and you sail right over the top and start heading down again. There’s a sweet spot, and overshooting is a real mistake.
recapEach Grover round rotates the state a fixed angle toward the answer; there is a sweet spot, and overshooting hurts.
play
The amplification dial
Set the haystack size N and step through Grover rounds. The vector lives in a plane: |bad⟩ across, |good⟩ up. Watch it rotate toward the answer, watch the success probability climb — and watch it overshoot if you go past the sweet spot.
▸ amplification dial1 marked of N
recapSuccess probability is sin² of the running angle (2k+1)θ; it peaks near √N rounds, then falls if you overshoot.
math
Two reflections make a rotation
The whole search lives in the 2-D plane spanned by |good⟩ and |bad⟩. The state starts at angle θ above |bad⟩, where:
sinθ = √(M/N) · after k rounds: angle = (2k+1)θ
The oracle reflects the state about |bad⟩; diffusion reflects it about the start. A reflection then a reflection is always a rotation — here by 2θ each round. Success probability is just how far up the vector points:
P(success) = sin² ((2k+1)θ)
best k ≈ (π/4)·√(N/M) → √N speed-up
✎ worked example · N = 4, one answer, one round → certainty
1.sinθ = √(1/4) = 1/2, so θ = 30°
2.after k = 1 round: angle = (2·1+1)·30° = 90°
3.P = sin²(90°) = 1 — the answer with 100% certainty
4.classically you’d expect ~2.5 looks; Grover nails it in one. ✓
recapOracle + diffusion = a 2θ rotation; P = sin²((2k+1)θ), best at k ≈ (π/4)√N.
⚠ common misconceptions
“More iterations is always better.” No — it’s a rotation, so it overshoots. Past the sweet spot the success probability falls back toward zero. You must stop at about (π/4)√N.
“Grover is an exponential speed-up like Shor.” It’s quadratic: √N versus N. Huge for big N, but not the exponential leap factoring enjoys.
“The oracle already knows where the answer is.” It only recognizes a correct answer when handed one (flips its sign) — it can’t point to it. Amplitude amplification is what converts “can check” into “can find, fast.”
✓ you can now
✓picture Grover as a rotation in the |good⟩–|bad⟩ plane by 2θ per round
✓compute the success probability sin²((2k+1)θ) and the optimal round count
✓explain why overshooting lowers your odds, and why the speed-up is √N (quadratic)
✓see Grover as the general tool of amplifying any recognizable outcome