Amplitude Amplification Lab — Grover search, overshoot and multiple targets

The science

Setup. N = 2n items, M marked. Start in the uniform superposition with every amplitude 1/√N. One Grover iteration = oracle (flip the sign of marked amplitudes) then diffusion (reflect every amplitude about the mean, a → 2⟨a⟩ − a).

Rotation picture. With sinθ = √(M/N) the two reflections compose to a rotation by 2θ in the plane of marked/unmarked states, so P(k) = sin²((2k+1)θ). Best k ≈ π/(4θ) − 1/2 ≈ (π/4)√(N/M). Past that the state rotates away (overshoot).

Cost. Classical unstructured search: about N/(M+1) queries on average. Grover: O(√(N/M)) — a quadratic, not exponential, speed-up, and optimal for unstructured search.

Honest simplifications. Real amplitudes only; the oracle is a free black box; no gate errors or decoherence; the 2n vector is stored classically (a real device would not). Marked positions are placed deterministically. Checks: full vector vs closed form, and a separate 2-amplitude recursion.