Grover's Search Algorithm

Grover's algorithm achieves the optimal O(√N) query complexity — the BBBV theorem proves no quantum algorithm can search an unstructured database faster without exploiting additional problem structure. The geometric picture explains why: each iteration rotates the state vector by a fixed angle θ ≈ 2/√N in the two-dimensional plane spanned by the target state and the uniform superposition of all other states. Starting near the equator of that plane, roughly (π/4)√N rotations are needed to swing the vector onto the target axis, which is exactly the O(√N) iteration count you see above. Because θ shrinks as N grows, larger search spaces need proportionally more — but still just √N, not N — iterations to align.

In an equal superposition, every candidate starts with the same tiny amplitude. Each round does two things: an oracle flips the sign of the target's amplitude, then an 'inversion about the mean' reflects all amplitudes around their average — nudging the marked one up and the rest down. Repeat, and the target's probability climbs toward 1. For a list of N = 1,000,000, a classical scan checks 500,000 entries on average; Grover needs only about 1,000.

For N = 4 — a two-qubit search — Grover isn't just fast, it's exact: a single iteration lands on the target with 100% probability. The rotation angle satisfies sin(θ/2) = 1/√N = 1/2, so θ = 60°, and after one step the state has turned exactly (2·1+1)·30° = 90° onto the target axis. It's the rare case where a quantum algorithm gives a guaranteed answer, not just a likely one.