Grover's Search Algorithm

Amplitude amplification provides quadratic speedup for unstructured database search. Watch the marked state probability grow as sin²((2k+1)θ) while unmarked states decrease.

Qubits n (N = 2ⁿ items)6
Marked items M1
Current iteration k0
Algorithm: Initialize |s⟩ = H⊗ⁿ|0⟩ (uniform superposition). Repeat k times: Oracle O_f flips phase of marked states; Diffusion D = 2|s⟩⟨s|−I reflects about average.
Amplitude after k iterations: Marked: sin((2k+1)θ)/√M, where sin(θ) = √(M/N).
Success probability: P_k = M·sin²((2k+1)θ)/N
Optimal: k* = ⌊(π/4)√(N/M)⌋, P* ≈ 1 for M ≪ N.
Classical: O(N/M) queries. Grover: O(√(N/M)) — quadratic speedup.