You are reading without signing in. Sign in or continue as guest to take quizzes and keep XP.
Grover's search
Amplitude amplification: find a marked item in √N steps, and why you must stop at the right time.
- Describe one Grover iteration as two reflections.
- Compute the optimal number of iterations for N = 4 and N = 1024.
- Explain why too many iterations make things worse.
Picture the state as an arrow in the plane spanned by the marked item and everything else. The oracle reflects it across one axis, the diffusion across the other; two reflections make a rotation by 2θ where sin θ = 1/√N. After about (π/4)√N rotations the arrow points at the marked item. Keep going and it rotates past it: the success probability oscillates.
N = 4: one iteration is exact
The oracle marks |11⟩ with a CZ. For four items one Grover iteration already gives probability 1. Simulate, then duplicate the oracle + diffusion block (select it, Ctrl+D) and see the success drop.
OPENQASM 3.0; include "stdgates.inc"; qubit[2] q; bit[2] c; h q[0]; h q[1]; barrier q; cz q[0], q[1]; barrier q; h q[0]; h q[1]; z q[0]; z q[1]; cz q[0], q[1]; h q[0]; h q[1]; c = measure q;
| N | Classical (average) | Grover iterations |
|---|---|---|
| 4 | 2 | 1 |
| 1 024 | 512 | 25 |
| 1 000 000 | 500 000 | 785 |
Grover's advantage is…
Sign in to answer and earn XP; you will come back to this lesson.
What happens if you run 2·k_opt iterations?
Sign in to answer and earn XP; you will come back to this lesson.
Grover rotates the state toward the marked item by a fixed angle per iteration; stop after about (π/4)√N. Quadratic, optimal, and the template for amplitude amplification everywhere.
Up next: QFT and phase estimation