8.96: Grover's Search Algorithm- Four-Card Monte

Last updated
Save as PDF

Page ID: 149255

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Grover's search algorithm is great at playing four-card monte. As the following quantum circuit shows it can determine which card is the queen in one pass.

\[ \begin{matrix} |0 \rangle & H & \triangleright & \lceil & ~ & \rceil & H & \lceil & ~ & \rceil & H & \triangleright & \text{Measure} & ~ & \lceil & ~ & \rceil & ~ & X & \cdot & X \\ ~ & ~ & ~ & | & \text{Oracle} & | & ~ & | & J & | & ~ & ~ & ~ & \text{where} & | & J & | & = & ~ & | \\ |0 \rangle & H & \triangleright & \lfloor & ~ & \rfloor & H & \lfloor & ~ & \rfloor & H & \triangleright & \text{Measure} & ~ & \lfloor & ~ & \rfloor & ~ & X & \fbox{Z} & X \end{matrix} \nonumber \]

The following matrix operators are required to construct the circuit. Giving |10> a negative phase in the Oracle designates it as the queen. The Appendix shows the calculation of J as shown on the right side above.

\[ \begin{matrix} H = \frac{1}{ \sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} & \text{HH = kronecker(H, H)} & \text{Oracle} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} & J = \begin{pmatrix} -1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \end{matrix} \nonumber \]

Operating on the input state, which creates a superposition of all queries, enables the algorithm to identify which card is the queen in one operation of the circuit.

\[ \begin{matrix} \text{GroverSearch = HH J HH Oracle HH} & \text{GroverSearch} \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ -1 \\ 0 \end{pmatrix} = - |10 \rangle \end{matrix} \nonumber \]

Now the operation of the algorithm is carried out in stages to show the importance of constructive and destructive interference in quantum computers.

\[ \begin{matrix} \text{Step 1} & \text{HH} \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0.5 \\ 0.5 \\ 0.5 \\ 0.5 \end{pmatrix} = \frac{1}{2} \left[ |00 \rangle + |01 \rangle + |10 \rangle + |11 \rangle \right] \\ \text{Step 2} & \text{Oracle} \begin{pmatrix} 0.5 \\ 0.5 \\ 0.5 \\ 0.5 \end{pmatrix} = \begin{pmatrix} 0.5 \\ 0.5 \\ -0.5 \\ 0.5 \end{pmatrix} = \frac{1}{2} \left[ |00 \rangle + |01 \rangle - |10 \rangle + |11 \rangle \right] \\ \text{Step 3} & \text{HH} \begin{pmatrix} 0.5 \\ 0.5 \\ -0.5 \\ 0.5 \end{pmatrix} = \begin{pmatrix} 0.5 \\ -0.5 \\ 0.5 \\ 0.5 \end{pmatrix} = \frac{1}{2} \left[ |00 \rangle - |01 \rangle + |10 \rangle + |11 \rangle \right] \\ \text{Step 4} & \text{J} \begin{pmatrix} 0.5 \\ -0.5 \\ 0.5 \\ 0.5 \end{pmatrix} = \begin{pmatrix} -0.5 \\ -0.5 \\ 0.5 \\ 0.5 \end{pmatrix} = \frac{1}{2} \left[ - |00 \rangle - |01 \rangle + |10 \rangle + |11 \rangle \right] \\ \text{Step 5} & \text{HH} \begin{pmatrix} -0.5 \\ -0.5 \\ 0.5 \\ 0.5 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ -1 \\ 0 \end{pmatrix} = - |10 \rangle \end{matrix} \nonumber \]

Appendix

\[ \begin{matrix} \lceil & ~ & \rceil & ~ & X & \cdot & X \\ | & J & | & = & ~ & | \\ \lfloor & ~ & \rfloor & ~ & X & \fbox{Z} & X \end{matrix} \nonumber \]

\[ \begin{matrix} J = \begin{pmatrix} -1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} & X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} & \text{CZ} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 \end{pmatrix} & \text{kronecker(X, X) CZ kronecker(X, X)} = \begin{pmatrix} -1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \end{matrix} \nonumber \]