Quantum-computing simulator
Quantum Search
Grover's algorithm (1996) finds a marked item in an unsorted database of N = 2^n items in only O(sqrt(N)) oracle calls versus O(N) classically. Here it runs on a real dense state-vector simulator over a 4-qubit register - 16 basis states, target |0101>.
How to read it: each iteration rotates the state vector toward the marked state, so P(marked) climbs steeply, peaks at the floor(pi/4*sqrt(N)) optimum (iteration 3, green), then overshoots back down at iteration 4. Every probability is simulated, not scripted.
Amplitude-amplification curve - P(|0101>)
| 0 | 6.25 % | |
| 1 | 47.27 % | |
| 2 | 90.84 % | |
| 3 | 96.13 % | |
| 4 | 58.17 % |
The climb 6.25 -> 47 -> 91 -> 96% then the overshoot back to 58% is the tell-tale sine of amplitude amplification: keep iterating past the optimum and you rotate away from the answer.
Actual program output
Grover's search algorithm -- quantum amplitude amplification demo
n = 4 qubits -> 16 basis states; target |0101> = index 5
Classical baseline (uniform random guess over 16 items): 1/16 = 6.25 %
Theoretical optimal iteration count = floor(pi/4 * sqrt(16)) = 3
iterations | P(marked = |0101>)
------------+---------------------
0 | 6.25 %
1 | 47.27 %
2 | 90.84 %
3 | 96.13 %
4 | 58.17 %
Optimal among iterations 0-4: 3 iteration(s) -> P = 96.13 %
Matches the theoretical pi/4 * sqrt(N) optimum -- real amplitude amplification, not a scripted number.
Learn more: Grover's algorithm and amplitude amplification.