algorithmsLab
13 min read
Grover's Algorithm
The full circuit, oracle plus diffusion operator, worked exactly for a 2-qubit (4-item) search.
Suggested before this lesson
Last lesson covered the geometry: the oracle and the diffusion operator each reflect the state about a different axis, and together they rotate it toward the marked answer. This lesson builds both as real gates and runs the whole thing on the smallest nontrivial case, searching 4 items, where you'll get to watch the rotation land exactly on the right answer.
For a single marked item , the oracle just needs to flip the sign of that one basis state's amplitude and leave every other basis state alone. When (both qubits marked), that's precisely what already does: flip sign exactly when both qubits read 1.
reflects about the uniform superposition . The standard construction sandwiches a "flip sign of everything except " step between two layers of : turn back into with , flip every state's sign except (equivalently, up to an unobservable global phase, flip the sign of only ), then undo the s. Flipping the sign of specifically is on every qubit (remaps ), then the same used above (now catching the remapped ), then again to undo the remap:
Search 2 qubits (4 possible items) for . With , ; one Grover iteration lands the state at , giving : a single iteration finds the answer with certainty, no other outcome is even possible. This exact-success case only happens at ; larger needs iterations and lands close to, but not exactly at, probability 1.
Circuit
h
cz
x
Step through the circuit: after gate 12 of 12
13 / 13
Measurement Probabilities
0.0%
0.0%
0.0%
100.0%
Exact State
| Basis state | Re | Im | Probability |
|---|---|---|---|
| 0 | 0 | ||
| 0 | 0 | ||
| 0 | 0 | ||
| -1.000 | 0 |
Live preview of the circuit detected in your code
This lesson's oracle only marks , because that's exactly what flips the sign of. To mark a different target, say , sandwich the same between gates on whichever qubits should read 0 in the target (here, qubit 0): on qubit 0 remaps , catches it, undoes the remap, exactly the same trick the diffusion operator's own construction already used above to target instead of .
Switch to 16 before the quiz below: watch how many iterations it actually takes to peak, and how the peak probability compares to the case above.
N =
State in the (|s'⟩, |ω⟩) plane
1
47.3%
Each iteration rotates the state by toward . Slide up past and watch the success probability peak, then fall again, overshoot is real in Grover's algorithm, unlike classical search. Try a bigger : the starting angle shrinks, so more iterations are needed, but the achievable peak probability stays close to 1.
Python
Python