ExperimentIntermediateEstablished concept Runs in the browser

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

  1. Choose the number of qubits (2 to 8) and the target state.
  2. Leave the number of iterations at the optimal value or change it manually.
  3. Track the target amplitude after each iteration in the chart.
  4. Increase the iterations beyond the optimum and notice the drop in probability (over-rotation).
Loading the simulator…
What theory predicts and what you observe

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.

  1. Choose $n=3$ and the marked item 5 (i.e. 101).
  2. Run with the optimal number of iterations.
  3. Change the number of iterations to 1, then 3.
  4. Compare the curve with the theoretical formula.
Loading the simulator…

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

  1. Lov K. Grover (1996). A fast quantum mechanical algorithm for database search. Proc. 28th ACM STOC, pp. 212–219 doi:10.1145/237814.237866
  2. 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

Local experiment results come from an exact classical state-vector simulation running in your browser, and computation server results come from Qiskit and PennyLane simulators; neither is equivalent to running on a real quantum computer. Memory doubles with each qubit ($2^n$ amplitudes), so the number of qubits is limited to 16 in the browser.