Grover's Algorithm — Quantum Amplitude Amplification

N-item unstructured search. Marked state amplitude grows with each Grover iteration, peaking at π√N/4 steps.

Iteration: 0
Optimal iters: 3
P(marked): 0.0625
Quantum: O(√N)
Classical: O(N)
Classical steps needed: 8
Grover iteration:
1. Oracle: flip phase of |w⟩
2. Diffusion: invert about mean
Amplitude of |w⟩:
sin((2k+1)·arcsin(√(M/N)))
Optimal k:
k* = ⌊π/(4·arcsin(√(M/N)))⌋