Grover's Search Algorithm

Amplitude amplification finds a marked element in an unsorted database of N items in O(√N) steps — a quadratic speedup over classical O(N). Each iteration: oracle phase-flip then diffusion (inversion about mean).

Qubits n (N=2ⁿ items): 4 (N=16)

Target item (marked): 7

Amplitude Bar Chart — All N States

Success Probability vs Iteration

Iteration k

—

Optimal k*

—

P(success)

—

Classical N/4

Algorithm

Init: |ψ⟩ = H^⊗n|0⟩ = (1/√N) Σₓ |x⟩ (uniform superposition)

Oracle Uω: |x⟩ → -|x⟩ if x=ω, else |x⟩ (phase flip)

Diffusion Us: 2|ψ⟩⟨ψ| - I (inversion about mean)

After k iters: P(ω) = sin²((2k+1)·arcsin(1/√N))

Optimal k* = ⌊π√N/4⌋ ≈ π√N/4 (quadratic speedup)