Grover search
30 min
The problem
Among N items one is marked, and the only way to tell is to ask an oracle about one item at a time. Classically you check about N/2 items on average, and N − 1 in the worst case.
One Grover iteration
- Start in an equal superposition of all N items.
- The oracle flips the sign of the marked item’s amplitude.
- The diffusion step reflects every amplitude about the mean, which grows the marked amplitude and shrinks the others.
About (π/4)√N iterations bring the marked item close to probability 1. More iterations overshoot and lower it again, so the count matters.
The lab
With two qubits there are N = 4 items, and one iteration finds the marked one with certainty. cz a, b is the oracle for item 11: it flips the sign of |11⟩ only. The diffusion is h, x on both qubits, cz, then x and h again. Our run read ma = 1, mb = 1 on all 1,000 shots.
In perspective
The speed-up is quadratic, about √N oracle calls instead of about N. It holds for any unstructured search, and it is one of the few quantum speed-ups with a proof of optimality.
HiQ lab 1
Grover search over four items
Mark item 11 with a cz, then reflect every amplitude about the mean. With four items one round is enough.
// Grover search over four items (two qubits) for the marked item 11.// With four items, one oracle call and one diffusion find it with certainty.program groverqubits a, bbits ma, mb// Uniform superposition over 00, 01, 10, 11.h ah b// Oracle: flip the sign of 11.cz a, b// Diffusion: reflect every amplitude about the mean.h ah bx ax bcz a, bx ax bh ah bmeasure a -> mameasure b -> mb- What you should see
- ma = 1, mb = 1 on every shot: the marked item, found with certainty.
- What we measured
- ma = 1, mb = 1 on all 1,000 shots. QCOS checked this program and ran it on a Softquantus Cloud simulator, 1,000 shots, 13 November 2026.
Check it yourself
Save the program as grover.qcos, set QCOS_API_KEY to a key from your workspace on the Softquantus Research Platform, and ask QCOS to check it. Change a line, check again, and see what the checker says.
pip install softqcossoftqcos lang check grover.qcos