Grover's Search Algorithm

Find a needle in a haystack in √N steps instead of N - amplitude amplification in action

Worked example — Grover's Search Algorithm

Current iteration	0 (Superposition)
Target probability	12.50%
Classical (1/N)	12.50%
Iteration	0 / 2 · Superposition

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

why √N and not faster? 🖖

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.

how the answer gets amplified 🖖

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.

four items, one shot, certainty 🖖

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.

Problem solved in full

Two iterations to find a marked item among 8 5 steps
Grover's algorithm finds a marked item among 8 in two iterations. Work out where the two comes from — and what happens if you run a third.
1. Before anything runs, the state is a uniform superposition: every item equally likely, so the marked one carries 1/8 of the probability. That is the same as a classical random guess, and the panel prints both to make the point.
  
  $N = 8 : uniform superposition gives P = \frac{1}{8} = 12.50%$
2. Each Grover iteration is a rotation by a fixed angle in a two-dimensional plane spanned by the marked state and everything else. The angle comes from the amplitude, and for N = 8 it is about 20.7°.
  
  $sin θ = \frac{1}{N} ⟹ θ = 20.7 0^{\circ}; P_{k} = sin^{2} ((2 k + 1) θ)$
3. So the probability is not a curve that climbs and levels off — it is a sine squared, and it climbs steeply: 12.5%, then 78.1%, then 94.5%.
  
  $k = 1 : 78.12%; k = 2 : 94.53%; k = 3 : 33.01%$
4. The optimal stopping point is the rotation that lands nearest 90°, which is π/4 times the square root of N. For eight items that is 2.22, and you cannot do a fractional iteration, so it is 2.
  
  $k_{opt} = ⌊ \frac{π}{4} N ⌋ = ⌊ 2.221 ⌋ = 2$
5. Run a third and the rotation overshoots. The probability falls to 33.0% — worse than after one iteration, and heading back toward the starting point.
  
  $classical \sim \frac{N}{2} = 4 queries vs O (N) = 2$
Answer

The tool prints 12.50% for both the starting superposition and the classical 1-in-N, and stops the automatic run at 2, though the step and skip-to-end controls carry it to 5. More iterations make it worse, because amplitude amplification is a rotation and rotations come back round. That is also why Grover's speed-up is only quadratic and not exponential — you need about √N rotations to reach 90°, so 8 items take 2 and a million take 785. Useful, and nothing like the exponential advantage the phrase 'quantum search' suggests.

$P_{k} = sin^{2} ((2 k + 1) θ) ROTATES : past k_{opt} it falls again$

References (1)

The algorithm this tool steps through: L. K. Grover, "A fast quantum mechanical algorithm for database search." Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–219, 1996.

By the 42Math team · Updated 2026-07-29

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

N = 4 - N=4 items — only 1 Grover iteration needed to find target
N = 8 - N=8 items — ~2 iterations optimal, classic demo size
N = 16 - N=16 items — 3 iterations optimal, O(√N) visible
N = 32 - N=32 items — ~4 iterations, shows quadratic advantage