← Computing

Grover's Search Algorithm

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

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

  1. 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.

    |s′⟩ |w⟩ θ = 20.70° 2θ k = 0 12.50% k = 1 78.12% k = 2 94.53% k = 3 33.01%

    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=18=12.50%N=8:\quad \text{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⁡θ=1N ⟹ θ=20.70∘;Pk=sin⁡2((2k+1)θ)\sin\theta=\frac{1}{\sqrt N}\ \Longrightarrow\ \theta=20.70^\circ;\quad P_k=\sin^2\left((2k+1)\theta\right)

    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%k=1:\ 78.12\%;\qquad k=2:\ 94.53\%;\qquad 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.

      kopt=⌊π4N⌋=⌊2.221⌋=2k_{\text{opt}}=\left\lfloor\frac{\pi}{4}\sqrt N\right\rfloor=\left\lfloor2.221\right\rfloor=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 ∼N2=4 queriesvsO ⁣(N)=2\text{classical}\ \sim\frac{N}{2}=4\ \text{queries}\quad\text{vs}\quad O\!\left(\sqrt N\right)=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.

    Pk=sin⁡2((2k+1)θ) ROTATES: past kopt it falls againP_k=\sin^2\left((2k+1)\theta\right)\ \text{ROTATES}:\ \text{past}\ k_{\text{opt}}\ \text{it falls again}
References (1)

· Reviewed against published sources. Corrections welcome.