Grover's Algorithm
Grover's Algorithm
Set the search-space size, the target state and the number of iterations, and see the oracle, the diffusion operator and the measurement distribution, comparing the theoretical probability $\sin^2((2k+1)\theta)$ with the shot results.
Experiment steps
- Choose the number of qubits (2 to 8) and the target state.
- Leave the number of iterations at the optimal value or change it manually.
- Track the target amplitude after each iteration in the chart.
- Increase the iterations beyond the optimum and notice the drop in probability (over-rotation).
The optimal number is about $\frac{\pi}{4}\sqrt{N}$. The theoretical complexity is $O(\sqrt N)$ queries, but the classical simulation itself costs $O(2^n)$ memory and time, so there is no real speed-up on your computer.
Ready-made scenarios
Each scenario opens the simulator with specific settings; the simulator loads only when the scenario is opened.
Grover Search over 8 Items
With $N=8$ and one marked item ($|101\rangle$) the optimal number of iterations is 2 and the success probability is $\sin^2(5\theta)\approx0.945$.
Goal: Verify the success-probability formula and that an optimal number of iterations exists.
- Choose $n=3$ and the marked item 5 (i.e. 101).
- Run with the optimal number of iterations.
- Change the number of iterations to 1, then 3.
- Compare the curve with the theoretical formula.
Theory predicts, with two iterations, $P(101)=0.9453$, with the rest spread equally over the other seven items (about $0.0078$ each). With one iteration $0.781$, and with three $0.330$.
Concepts this experiment explains
References
- Lov K. Grover (1996). A fast quantum mechanical algorithm for database search. Proc. 28th ACM STOC, pp. 212–219 doi:10.1145/237814.237866
- Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp (1998). Tight Bounds on Quantum Searching. Fortschritte der Physik 46(4-5):493–505 doi:10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
