Part IV. Protocols and Algorithms · Chapter 30
Grover and Amplitude Amplification
Grover's algorithm is the most honest speedup in this book: a real, provable quadratic gain for unstructured search, with an iteration count you must tune and an overshoot that punishes greed.
In this chapter 9 sections
Reader question. How does amplitude amplification rotate probability toward marked states, and what resource assumptions govern the quadratic gain?
Two reflections rotate the state within the plane spanned by marked and unmarked components by a fixed angle; about iterations maximize success when M is known, but oracle, state-preparation, verification, and fault-tolerant costs determine end-to-end value.
- This chapter does not describe Grover as reading every candidate or promise a quadratic wall-clock speedup in every workload.
- It does not ignore unknown solution count, overshooting, or reversible oracle cost.
Compress N amplitudes into a two-dimensional plane
Define marked and unmarked normalized components.
Grover's algorithm searches items for marked ones, where "marked" means an oracle recognizes a solution. Classically you check items one by one: about queries. Grover needs only about ; a quadratic speedup, provable and, in the oracle model, provably optimal.
The mechanism is two reflections that compose into one rotation. First, the oracle marks solutions by flipping their phase. Second, the diffusion operator reflects every amplitude about the mean. In the two-dimensional plane spanned by "the marked direction" and "the uniform unmarked direction," those two reflections add up to a rotation by a small fixed angle. Each iteration turns the state a little closer to the marked state; and, crucially, keeps turning past it if you let it. The right number of iterations is approximately:
Too few iterations under-amplify. Too many overshoot and hand you a wrong answer with confidence.
Evidence boundary. Grover search uses amplitude amplification to achieve oracle queries for M marked items. [Lov K. Grover] [Michael A. Nielsen]
The oracle reflects marked phase
Show the first geometric operation.
The marking oracle acts as I-2 Pi_good, negating the good subspace and leaving its magnitude unchanged. This reflection is useful only relative to a prepared starting state and a second reflection. Counting it as a unit-cost query is a black-box abstraction; compiling a real predicate must include its reversible arithmetic, ancillas, and uncomputation.
Evidence boundary. Amplitude amplification is a rotation produced by two reflections in a two-dimensional invariant subspace. [John Watrous] [John Preskill]
Diffusion reflects about the prepared state
Derive the second operation.
The oracle uses the same phase-kickback discipline as the previous chapters:
A marked gets a minus sign; everything else is untouched. Diffusion then maps each amplitude to , which is reflection about the average. Neither step alone does anything impressive; a sign flip is unmeasurable, and reflection about the mean without the flip is the identity. Alternated, they rotate.
The iteration formula above is an estimate derived from that geometry, not a license to run the loop forever. If is unknown, practical variants estimate it or use randomized schedules; the core point stands: amplitude amplification has a clock, and the algorithm must know when to stop.
Evidence boundary. Query improvement does not automatically include oracle construction, state preparation, verification, or hardware overhead. [Ethan Bernstein] [National Academies of Sciences]
Notation contract: N search states, M marked, sin²θ=M/N, iteration k, success sin²((2k+1)θ); oracle query separated from gate cost.
Four items complete one exact rotation
Calculate every amplitude with one marked item.
With one marked item among four, sin(theta)=1/2 and theta=pi/6. The uniform state starts at angle theta from the bad axis. One Grover iterate rotates by 2theta, reaching 3theta=pi/2 and success probability one. The statevector fixture exposes both reflections so the exact result cannot be mistaken for generic monotonic amplification.
Stop before the probability turns back
Relate angle, M, and iteration count.
Grover is a reusable subroutine pattern:
- prepare a uniform superposition over candidates;
- mark good states by phase;
- reflect about the starting state (diffusion);
- repeat a tuned number of times;
- measure;
- verify the candidate classically.
The last step is easy to forget and essential: the algorithm returns a candidate with high probability, not a certificate. Amplitude amplification generalizes beyond search; it boosts any subroutine that produces a good outcome with known probability; which is why it shows up inside counting, optimization, and Monte Carlo speedups.
In code, treat oracle and diffusion as separately testable components. First verify the oracle flips the marked branch and leaves the rest unchanged. Then verify diffusion implements the reflection. Finally, sweep the iteration count and confirm the curve rises and falls as predicted. That sweep catches the most common Grover bug: a circuit that performs the sign flip but never actually amplifies.
Price preparation, oracle, and verification
Build the end-to-end quadratic-gain condition.
The O(sqrt(N/M)) query count excludes constructing the searchable superposition, implementing the predicate, routing its gates, repeating after failure, and checking a candidate. If preparation or verification costs Theta(N), the composed workflow remains linear. Resource estimates must also address unknown M, because over-rotation can reduce success after the optimum.
Amplitude-amplification explorer
| Field | Reader-visible record |
|---|---|
| Format | Exact/numerical simulator with iteration curve and resource calculator |
| Verification | Tests N=4 exact amplitudes, general sin²((2k+1)θ) probabilities, overshoot, and break-even under supplied cost functions. |
| Availability | Published companion and deterministic command |
Two-qubit Grover trace is the executable companion used by this page.
cd labs && python -m unittest tests.test_companion_models.CompanionModelTests.test_one_grover_iteration_finds_one_of_four -vExecutable reference fixture
Run with Python 3.11 or later. The final assertion is the chapter-level pass condition for this small instance.
def grover4(marked, apply_oracle=True):
if marked not in range(4) or type(apply_oracle) is not bool:
raise ValueError("marked must be a four-item index")
amplitudes = [0.5] * 4
if apply_oracle:
amplitudes[marked] *= -1
mean = sum(amplitudes) / 4
result = [2 * mean - amplitude for amplitude in amplitudes]
return {"amplitudes": result, "success": result[marked] ** 2,
"normalized": abs(sum(value * value for value in result) - 1.0) < 1e-12}
marked_two = grover4(2)
marked_zero = grover4(0)
missing_oracle = grover4(2, False)
invalid_rejected = False
try:
grover4(4)
except ValueError:
invalid_rejected = True
assert marked_two["normalized"] and marked_two["success"] == 1.0
assert marked_zero["amplitudes"] == [1.0, 0.0, 0.0, 0.0]
assert missing_oracle["success"] == 0.25 and invalid_rejected
print(f"PASS: 30 Grover marked2={marked_two['success']:.2f} marked0={marked_zero['success']:.2f} no_oracle={missing_oracle['success']:.2f}")Scope boundary
- This chapter does not describe Grover as reading every candidate or promise a quadratic wall-clock speedup in every workload.
- It does not ignore unknown solution count, overshooting, or reversible oracle cost.
Depth commitment. One two-plane proof, one N=4 trace, one N=8 table, and one cost calculator.
Practice problem
For N=8 and M=2, derive θ, compute success probability for k=0,1,2,3, and choose the best integer iteration.
- Deliverable
- Angle derivation, probability table, circuit iteration count, and overshoot explanation.
- Pass condition
- The explorer evaluates the analytic formula and statevector simulation and requires agreement for every k.
Verification record
Expected solution form. Geometric derivation plus statevector and formula comparison.
Model answer. sin^2(theta)=M/N=1/4, so theta=pi/6. The success probabilities sin^2((2k+1)theta) for k=0,1,2,3 are 1/4, 1, 1/4, and 1/4; one iteration is the unique best choice in this range.
Model result and check. CI checks exact/float probabilities and the selected maximum.
Acceptance test. The explorer evaluates the analytic formula and statevector simulation and requires agreement for every k.
Companion work
Artifacts for this chapter
These entries resolve to checked-in local source. Commands are reproduced exactly from the chapter manifest, and source-embedded fixtures are exported as direct downloads.
Reproduce or test
cd labs && python -m unittest tests.test_companion_models.CompanionModelTests.test_one_grover_iteration_finds_one_of_four -v
Provenance
Sources and review
- Lov K. Grover. A fast quantum mechanical algorithm for database search. Proceedings of STOC. 1996primary paper
- Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press. 2010textbook
- John Watrous. The Theory of Quantum Information. Cambridge University Press / University of Waterloo. 2018textbook
- John Preskill. Lecture Notes for Physics 219: Quantum Computation. California Institute of Technology. 2018graduate lecture notes
- Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on Computing. 1997primary paper
- National Academies of Sciences, Engineering, and Medicine. Quantum Computing: Progress and Prospects. National Academies Press. 2019consensus study report
The load-bearing claims in the chapter are mapped inline to this registered source set. A citation supports only the bounded claim beside it.