8.95: Grover's Search Algorithm- Implementation for Two Items

Last updated
Save as PDF

Page ID: 149254

\( \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}}\)

Chris Monroe's research group recently published an experimental implementation of the Grover search algorithm in Nature Communications 8, 1918 (2017). In this report the Grover search is implemented for N = 3 using the three qubit quantum circuit shown below. In this particular example it is demonstrated that the search algorithm successfully searches for two items in one operation of the circuit. The lead sentence in the paper states "The Grover search algorithm has four stages: initialization (red), oracle (green), amplification (blue) and measurement (black)."

\[ \begin{matrix} \textcolor{red}{ |0 \rangle} & \textcolor{red}{ \triangleright} & \textcolor{red}{H} & \textcolor{lime}{ \lceil} & ~ & \textcolor{lime}{ \rceil} & \textcolor{blue}{H} & \textcolor{blue}{X} & \textcolor{blue}{ \cdot} & \textcolor{blue}{X} & \textcolor{blue}{H} & \triangleright & \text{Measure} \\ ~ & ~ & ~ & \textcolor{lime}{|} & ~ & \textcolor{lime}{|} & ~ & ~ & \textcolor{blue}{|} \\ \textcolor{red}{ |0 \rangle} & \textcolor{red}{ \triangleright} & \textcolor{red}{H} & \textcolor{lime}{ \lceil} & \textcolor{lime}{ \text{Oracle}} & \textcolor{lime}{ \rceil} & \textcolor{blue}{H} & \textcolor{blue}{X} & \textcolor{blue}{|} & \textcolor{blue}{X} & \textcolor{blue}{H} & \triangleright & \text{Measure} \\ ~ & ~ & ~ & \textcolor{lime}{|} & ~ & \textcolor{lime}{|} & ~ & ~ & \textcolor{blue}{|} \\ \textcolor{red}{ |0 \rangle} & \textcolor{red}{ \triangleright} & \textcolor{red}{H} & \textcolor{lime}{ \lfloor} & ~ & \textcolor{lime}{ \rfloor} & \textcolor{blue}{H} & \textcolor{blue}{X} & \textcolor{blue}{ \fbox{Z}} & \textcolor{blue}{X} & \textcolor{blue}{H} & \triangleright & \text{Measure} \end{matrix} \nonumber \]

The oracle, highlighted below, contains 3(|011>) and 5(|101>).

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

The initial Hadamard gates on the three circuit wires feed the Grover search algorithm (in blue) a superposition of all possible queries yielding a superposition of the correct answers.

\[ \begin{matrix} \text{GroverSearch = HHH XXX CCZ XXX HHH Oracle HHH} & \text{GroverSearch} \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ -0.707 \\ 0 \\ -0.707 \\ 0 \\ 0 \end{pmatrix} = - \frac{1}{ \sqrt{2}} \left[ |011 \rangle + |101 \rangle \right] \end{matrix} \nonumber \]