You are reading without signing in. Sign in or continue as guest to take quizzes and climb the ranks.
Grover's search
Amplitude amplification: find a marked item in √N steps, and why you must stop at the right time.
- 01Describe one Grover iteration as two reflections.
- 02Compute the optimal number of iterations for N = 4 and N = 1024.
- 03Explain 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 gates (drag a box around them, then press Duplicate in the small toolbar that appears) 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 |
2 questions · one try each counts
Grover's advantage is…
Sign in to answer and climb the ranks; you will come back to this lesson.
What happens if you run 2·k_opt iterations?
Sign in to answer and climb the ranks; you will come back to this lesson.