Grover's Search & Amplitude Amplification
Finding a needle in √N steps by rotating amplitude.
Searching unsorted items classically takes about looks. Grover's algorithm takes about , by alternating two reflections that together rotate the state toward the answer. The same rotation, amplitude amplification, speeds up a huge range of other algorithms.
What you’ll learn
- Write the oracle and the diffusion as reflections and show that diffusion is inversion about the mean.
- Derive the success probability with and the optimal number of iterations.
- Build the diffusion from Hadamards, gates and a multi-controlled , and run the 2-qubit circuit.
- Handle several or unknown numbers of marked items, and generalize to amplitude amplification.
- Explain the limits: quadratic optimality, oracle cost, data loading and overheads.
Search as a query problem
Let with , and call marked if . Suppose items are marked. With no structure to exploit, a classical algorithm needs queries to find one; for , about on average.
Quantumly, one query gives the phase oracle through phase kickback (see Oracles & Phase Kickback: Deutsch–Jozsa), and the uniform superposition is one layer of Hadamards away:
Write for the mean amplitude.
Projecting onto replaces every amplitude by the mean.
Each amplitude is reflected about the mean: . The marked amplitude, just negated by the oracle, sits far below the mean, so it lands far above it.
Two reflections make a rotation
Everything happens in a plane. Define the normalized good and bad states
Then with , and both and map the plane to itself.
In the plane, the oracle is the reflection about the axis .
The diffusion is the reflection about the axis , which makes the angle with .
Two reflections whose axes meet at angle compose to a rotation by . The start state sits at angle ; each iteration adds .
After iterations the angle is .
Measuring then yields a marked item with probability (uniformly random among the marked ones).
Choose so that :
Then , so . Overshooting is costly: is periodic in and returns near zero after about iterations.
items, one of them marked. What is ?
Show the answer
25 iterations
, so and , with success probability . Classical search needs about queries on average.
The circuit
The diffusion is cheap to build. Since ,
and , which flips only the sign of , equals : the multi-controlled flips the sign of , and the layers relabel it as . This implements ; the global sign is invisible. A costs elementary gates with ancillas, so each iteration costs one query plus gates, and the diffusion never depends on which item is marked.
Why does a single iteration succeed with certainty for , ?
- Because , so and exactly
- Because two qubits decohere too slowly for errors to matter
- Because the diffusion operator is the identity for
- It doesn't: the success probability is
Show the answer
A. Because , so and exactly
with . Then and : one rotation lands exactly on . For larger the angle generally does not hit exactly.
Many marked items, and amplitude amplification
With marked items the same analysis holds with : about iterations. But large holds a surprise.
with marked items. What is the success probability after one Grover iteration?
- , unchanged
Show the answer
B. , unchanged
, so and : the rotation by carries the state from to , the mirror-image angle. With it is worse: and . When , just guess at random.
Unknown . Using the wrong count is dangerous. Run the schedule when items are marked and you rotate by about twice the right angle, ending near . Boyer, Brassard, Høyer and Tapp (1998) fix this with exponential search: pick uniformly from , run, check the result with one query, and on failure multiply by a constant . The expected number of queries is without knowing . Alternatively, estimate first by quantum counting.
What Grover does, and does not, buy you
- Optimal. No quantum algorithm searches an unstructured space with fewer than queries (Bennett, Bernstein, Brassard & Vazirani 1997; Boyer et al. 1998). Quadratic is the end of the road.
- NP problems. Brute-force SAT over variables drops from about to oracle calls, each a polynomial-size circuit evaluating the formula. Still exponential. Classical solvers exploit structure that plain Grover ignores, though quadratic speedups of some structured heuristics, such as backtracking, are known (Montanaro 2018).
- Data loading. "Database search" is a metaphor. If the items are classical records, the oracle needs them in quantum-accessible memory (QRAM); without it, each query costs gates and the speedup is gone.
- Depth and overhead. The iterations run one after another, and machines in parallel achieve only time . On error-corrected hardware every logical gate is slow, and analyses suggest quadratic speedups pay off only at very large problem sizes (Babbush et al. 2021).
Key takeaways
- The oracle and the diffusion are reflections; their product rotates by in , with .
- ; gives success at least , and overshooting hurts.
- Diffusion is : each iteration costs one query plus gates.
- Unknown : use exponential search or counting. Any checkable algorithm with success probability can be amplified in rounds.
- The speedup is quadratic and optimal; its practical value depends on oracle cost, data loading and error-correction overhead.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
After the oracle, amplitudes are . What does produce?
Show the answer
C.
The mean is , and sends and .
You plan iterations for one marked item, but items are actually marked ( large). Roughly what success probability do you get?
- Close to
- Close to , as planned
- About
- About
Show the answer
A. Close to
Now , twice as large, so after iterations the angle is : the state is back near . This is why unknown needs exponential search or counting.
An algorithm succeeds with probability , and success can be checked. With amplitude amplification, about how many rounds (each using and once) are needed for near-certain success?
- On the order of
- On the order of
- Just
- On the order of
Show the answer
D. On the order of
, so and : rounds give . Classical repetition needs about tries for comparable success: versus .
Grover's algorithm on SAT with variables and a single satisfying assignment needs about how many oracle calls?
- About
- About
- About
- About
Show the answer
B. About
The search space has assignments, so . A quadratic improvement on brute force, but still exponential in .
Which statement about one Grover iteration on qubits is correct?
- It uses one query and further gates, and the diffusion does not depend on which item is marked
- The diffusion must be redesigned for every marked item
- It needs about gates, because it acts on all amplitudes
- It needs no query: the diffusion alone finds the marked item
Show the answer
A. It uses one query and further gates, and the diffusion does not depend on which item is marked
uses Hadamards, gates and one ( gates with ancillas). Only the oracle knows the marked item.
Go deeper
- The Geometry of Grover & Optimal Iterations · Two reflections make a rotation.
- Optimality: the BBBV Lower Bound · Why no quantum algorithm beats √N for unstructured search.
- Amplitude Estimation & Quantum Counting · Quadratic speedups for Monte Carlo.
Further reading
- L. K. Grover, "A fast quantum mechanical algorithm for database search", Proc. 28th ACM STOC, 212–219 (1996).
- M. Boyer, G. Brassard, P. Høyer & A. Tapp, "Tight bounds on quantum searching", Fortschritte der Physik 46, 493–505 (1998).
- G. Brassard, P. Høyer, M. Mosca & A. Tapp, "Quantum amplitude amplification and estimation", Contemporary Mathematics 305, 53–74 (2002); arXiv:quant-ph/0005055.
- M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, ch. 6 (Cambridge, 10th anniv. ed., 2010).