Grover Search on Two Qubits
One Grover iteration over 4 items with |11⟩ marked yields P(11) = 1 exactly.
Goal
Watch amplitude amplification in the smallest possible example.
Approximate duration: 5 minutes
Steps
- Load the grover2 example.
- Follow the amplitudes after H, then after the oracle, then after the diffuser.
- Run 1000 shots.
- Modify the oracle to mark another item (add X before and after CZ).
Theory predicts the amplitudes $(\tfrac12,\tfrac12,\tfrac12,-\tfrac12)$ after the oracle, and exactly $P(11)=1$ after the diffuser; all thousand shots will give 11.
In a space of $N=4$ items with one marked item, $\sin\theta=\sqrt{1/4}$, i.e. $\theta=30^\circ$, and the success probability after $k$ iterations is $\sin^2((2k+1)\theta)$. With $k=1$: $\sin^2 90^\circ=1$.
The circuit: H on both qubits, then the phase oracle $CZ$, which flips the sign of $|11\rangle$, then the Diffuser $H^{\otimes2}X^{\otimes2}\,CZ\,X^{\otimes2}H^{\otimes2}$, which reflects the amplitudes about their mean. This is Amplitude Amplification, not “trying all possibilities in parallel” and then reading them out.
Test your understanding
The quiz needs JavaScript.
Related topics
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
- Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.
