Step through Grover's quantum search algorithm on a 16-item register. Watch amplitude amplification boost the target item's probability in O(√N) iterations versus O(N) classically.
Grover's algorithm uses two operations per iteration: an oracle that flips the sign of the target amplitude, and a diffusion operator that reflects amplitudes about their mean. After ~√N iterations, the target probability approaches 1.
Select a target item in the 16-element register. Step through iterations and watch the amplitude histogram. The target bar grows while others shrink. Compare quantum O(√N) = 3 iterations with classical O(N) = 16.
Grover's algorithm provides a provably optimal quadratic speedup for unstructured search — no quantum algorithm can do better. For a database of 1 million items, it finds the answer in ~1000 queries instead of 500,000.
This simulation walks through Grover's quantum search algorithm on a register of N = 16 basis states. The system begins in a uniform superposition with every amplitude equal to 1/√16. Each iteration applies an oracle that flips the sign of the marked target's amplitude, then a diffusion operator that reflects all amplitudes about their mean (D = 2|s⟩⟨s| − I). Together these perform a rotation that steadily concentrates probability onto the target.
You choose the target item from the 16-element drop-down, then use Step to advance one Grover iteration, Auto to run iterations automatically, and Reset to return to the uniform state. The amplitude histogram shows the target bar growing while the others shrink, peaking after about π/4·√N ≈ 3 iterations. This quadratic O(√N) speedup underpins faster brute-force search, cryptanalysis and database lookup tasks on quantum hardware.
What does this simulation show?
It visualises Grover's algorithm searching an unstructured register of N = 16 items for a single marked target. The amplitude of every item is drawn as a bar, and you watch the target's bar grow toward near-certainty as you apply successive Grover iterations.
How does Grover's algorithm work?
Each iteration combines two steps. The oracle flips the sign of the target amplitude, marking it; the diffusion operator then reflects all amplitudes about their average. This "inversion about the mean" raises the target while lowering the rest, rotating the state vector toward the solution.
What do the controls do?
The target drop-down selects which of the 16 items (shown as |0000⟩ to |1111⟩) is the marked solution. Step performs one oracle-plus-diffusion iteration, Auto runs iterations every 0.9 seconds, and Reset restores the uniform 1/√16 superposition with zero iterations.
The optimal count is roughly π/4·√N. For N = 16 that rounds to 3 iterations, at which the target probability is near its maximum. The info bar displays this as "π/4·√16 ≈ 3".
Classically, searching an unsorted list of N items needs about N/2 comparisons on average (8 for N = 16). Grover finds the target in only O(√N) iterations, a quadratic speedup. For a million items that is roughly 1,000 queries instead of 500,000.
Grover iterations are a rotation, so they overshoot. After the optimal point the target probability falls again as the state rotates past the solution. The simulation labels this "over-rotation", showing that more iterations is not always better.
It is the unitary D = 2|s⟩⟨s| − I, where |s⟩ is the uniform superposition. In practice it reflects each amplitude about the average of all amplitudes, which amplifies any value the oracle pushed below the mean, namely the marked target.
The amplitude arithmetic is exact for an idealised, noise-free quantum computer with real amplitudes, which is all Grover's algorithm requires. It omits real-world effects such as decoherence, gate errors and measurement collapse, so it is a faithful mathematical model rather than a hardware emulation.
The algorithm begins by placing the register in a uniform superposition, typically via Hadamard gates, so every item has amplitude 1/√N = 1/4 and probability 1/16 (6.25%). This equal starting point reflects having no prior knowledge of where the target lies.
No. For unstructured search the O(√N) scaling is provably optimal; no quantum algorithm can find a marked item with fewer oracle queries. This optimality, proven by Bennett, Bernstein, Brassard and Vazirani, makes Grover a benchmark for quantum search.
Grover-style amplitude amplification speeds up brute-force tasks: searching unstructured databases, inverting functions, solving constraint and SAT problems, and attacking symmetric cryptography (halving effective key strength), which is why post-quantum guidance recommends larger key sizes.