Quantum algorithms (Shor, Grover)

Equipment

• Model of the state vector rotating in a 2D plane
• Sliders for size N and iteration count k
• Display of target amplitude/probability per iteration

Procedure

1. Set the problem size

   Drag the "Size N" slider to choose the number of items in the simulated database (e.g. N = 25). Look at the initial state axis: the target amplitude starts at $1/\sqrt{N}$ — small for large N. Compare with classical search, which needs on average $N/2$ trials.

2. Increase the iteration count

   Step the "Iterations" slider and watch the state vector rotate toward the target axis: each Grover iteration adds an angle $2\theta$ with $\sin\theta = 1/\sqrt{N}$. Read the probability of measuring the target after k iterations: $P(k) = \sin^2((2k+1)\theta)$.

3. Find the optimal iteration count

   For each N, scan k for the maximum probability and compare with $k^* \approx \frac{\pi}{4}\sqrt{N}$. Push past the optimum to see the probability fall again — the vector overshoots the target. Try a large N (e.g. 100) and repeat: $k^*$ grows as $\sqrt{N}$, not $N$.

Simulation

Experiment history

Related physicists

Related library topics