Grover's Quantum Search
Grover's algorithm is a genuine quantum speedup: it finds a marked item among N in about pi/4 * sqrt(N) steps instead of the classical N/2. Here a dense state-vector simulator runs over 4 qubits (16 basis states), marking |0101> = index 5. Every probability below is a real amplitude-amplification measurement computed live at build time by OnlyCSharp.PhysicsAndAstronomy.Physics.QuantumComputing.Algorithms.GroverSearch.
Setup
- qubits n = 4 -> 16 basis states
- marked state = |0101> = index 5
- classical baseline (uniform random guess) = 1/16 = 6.25%
- theoretical optimum = floor(pi/4 * sqrt(16)) = 3 iteration(s)
Amplitude amplification curve
| Grover iterations | P(marked = |0101>) |
|---|---|
| 0 | 6.25% |
| 1 | 47.27% |
| 2 | 90.84% |
| 3 (peak) | 96.13% |
| 4 | 58.17% |
Verdict
Optimal among iterations 0-4: 3 iteration(s) -> P = 96.13%. This matches the theoretical pi/4 * sqrt(N) optimum - real amplitude amplification, not a scripted number. The marked state jumps from the 6.25% classical baseline to 96.13%.