Quadratic speedup for unstructured search via amplitude amplification
Searching N unsorted items one by one takes about N/2 checks. Grover's algorithm finds the target in about √N.
Click "Apply Oracle" and watch the target's amplitude flip below zero. Notice that every probability stays exactly the same.
Imagine searching an unsorted database of N items for one specific entry. Classically, you must check items one by one — on average N/2 checks. Grover's algorithm finds it in just ~√N steps, a quadratic speedup that applies to any search problem.
The magic is amplitude amplification: start in uniform superposition, then repeatedly apply an oracle (which marks the target) followed by a diffusion operator (which amplifies marked amplitudes). After ~π/4·√N iterations, measuring gives the target with near certainty.
The oracle is a black box that recognizes the target: it flips the amplitude of |target⟩ from positive to negative while leaving all other states unchanged. Crucially, this doesn't change any probabilities — every state still has probability 1/N. The sign flip is invisible to measurement but creates a phase difference that enables constructive interference.
Click "Iterate →" to rotate the state toward the target, or "Jump to Optimal". Keep iterating past the peak and you overshoot.
Each Grover iteration consists of: (1) oracle marks the target, then (2) the diffusion operator "reflects about the mean". Geometrically, this is a rotation by angle θ = 2·arcsin(1/√N) toward the target state |w⟩. After ~π/4·√N rotations, the state vector points almost directly at |w⟩, giving near-100% probability of measuring the target. Go past the optimal point and you overshoot!
Why √N? Each iteration rotates by θ ≈ 2/√N radians. To reach π/2 (100% probability), you need π/(2θ) ≈ π√N/4 ≈ O(√N) iterations.
Overshooting: Too many iterations rotate past the target. The probability oscillates! You must know approximately when to stop (or use fixed-point variants).
Geometric picture — The algorithm is a rotation in 2D: the |target⟩ and |non-target⟩ plane. Each iteration rotates by 2·arcsin(1/√N).
Step through the circuit: Hadamards, then oracle and diffusion in turn. Watch the target bar grow while the others shrink.
Step through the complete algorithm: (1) initialize with Hadamards to create uniform superposition, then repeat: (2) apply the oracle Uf to flip the target, (3) apply the diffusion operator D = 2|s⟩⟨s| − I to amplify. After the optimal number of iterations, measure. Watch the target amplitude grow while non-target amplitudes shrink — constructive vs destructive interference in action.
Click "Start Race!" to pit a one-by-one classical search against Grover. For 256 items it is about 128 steps against about 12.
Watch a classical and quantum search race head-to-head. The classical algorithm checks items one by one (O(N) steps). Grover's algorithm uses O(√N) quantum iterations. For N = 256 items, classical needs ~128 steps but quantum needs only ~12. For a million items: ~500,000 vs ~785. The advantage grows with the database size.
Universal applicability — Any problem reducible to "search" benefits: optimization, SAT solving, cryptographic attacks
Spot a mistake or have an idea?