Grover's Search Algorithm

Amplitude amplification finds a marked item in O(√N) queries

Controls

Step: 0 / 3 optimal

Algorithm

|ψ₀⟩ = H^n|0⟩ = (1/√N)∑|x⟩
Each Grover iteration:
1. Oracle Oₓ: flip phase of |marked⟩
2. Diffuser D: reflect about mean

After k≈(π/4)√N steps, amplitude of marked item ≈ 1.

Classical search: O(N) queries
Grover: O(√N) queries
For N=10⁶: 1M vs ~785 queries!

Oracle & Diffuser

Oₓ: |x⟩ → (-1)^{f(x)}|x⟩
D = 2|ψ⟩⟨ψ| − I
The Oracle marks the target by phase flip — it doesn't reveal the answer directly.

The Diffuser reflects amplitudes about their average. This is "inversion about the mean."

Together they increase the marked amplitude by ~2/√N per step.