8.94: Grover's Quantum Search Algorithm

D. Candela described a Grover search algorithm in the August (2015) issue of the American Journal of Physics. Chris Monroe's group recently published an experimental implementation of the same algorithm in Nature Communications 8, 1918 (2017). The Grover search is implemented for N = 3 using the three qubit quantum circuit shown below. The search algorithm (blue) runs an integer number of times closest to \( \frac{\pi}{4} \sqrt{2^N}\). The closest integer for N = 3 is 2. The Appendix provides a demonstration of the implementation of the J operator shown at the far right below.

\[ \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 \]

There are 8 items in the data base and the oracle, O, identifies the correct query with a minus sign. In other words, a search of the data base should return the result |110>. The J and Hadamard matrices required are shown below.

\[ \begin{matrix} H = \frac{1}{ \sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \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{GroverSearch = HHH J HHH O} \end{matrix} \nonumber \]

Initial Hadamard gates on the circuit wires feed the Grover search algorithm a superposition of all possible queries yielding a superposition of answers, but with the correct answer highly weighted as shown below.

\[ \begin{matrix} \Psi = \frac{1}{4} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} & \text{GroverSearch}^3 \Psi = \begin{pmatrix} -0.088 \\ -0.088 \\ -0.088 \\ -0.088 \\ -0.088 \\ -0.088 \\ 0.972 \\ -0.088 \end{pmatrix} & \text{This state is close to the correct result:} & \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{matrix} \nonumber \]

The probability of a successful search after two cycles of the circuit is \(0.972^2 = 94.5 \%\). For a classical search it would require on average 4 (8/2) queries.

It is easy to extend the algorithm to N = 4 by adding a row to the circuit above. In this example the search of the data base should return the result |1010>.

\[ \begin{matrix} O = \begin{pmatrix} 1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &1 &0 &0& 0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &0 & 0 \\ 0& 0 &0& 0 &0 &0 &0 &0 &0 &0 &-1 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0& 0 &0 &0 &0 &0 &1 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 \\ 0 &0 &0 &0 &0& 0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 \\ 0 &0 &0 &0 & 0& 0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 \end{pmatrix} & J' = \begin{pmatrix} -1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &1 &0 &0& 0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &0 & 0 \\ 0& 0 &0& 0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0& 0 &0 &0 &0 &0 &1 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 \\ 0 &0 &0 &0 &0& 0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 \\ 0 &0 &0 &0 & 0& 0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 \\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 \end{pmatrix} \\ \text{HHHH = kronecker(H, kronecker(H, kronecker(H, H)))} & \text{GroverSearch = HHHH J' HHHH O} ~ \frac{ \pi}{4} \sqrt{2^4} = 3.142 \end{matrix} \nonumber \]

\[ \begin{matrix} \Psi = \frac{1}{4} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} & \text{GroverSearch}^3 \Psi = \begin{pmatrix} 0.051 \\ 0.051 \\ 0.051 \\ 0.051 \\ 0.051 \\ 0.051 \\ 0.051 \\ 0.051 \\ 0.051 \\ 0.051 \\ -0.98 \\ 0.051 \\ 0.051 \\ 0.051 \\ 0.051 \\ 0.051 \end{pmatrix} & \text{This state is close to the correct result:} & \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{matrix} \nonumber \]

The probability of a successful search after two cycles of the circuit is \((-0.98)^2 = 96.0 \%\). For a classical search it would require on average 8 (16/2) queries.

Appendix

The following calculation demonstrates the identity on the right side of Grover search circuit. X is the NOT operator and CCZ is the controlled-controlled Z gate.

\[ \begin{matrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} & \text{XXX = kronecker(X, kronecker(X, X))} & \text{CCZ} = \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} \end{matrix} \nonumber \]

\[ \begin{matrix} \text{XXX CCZ XXX} = \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{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} \end{matrix} \nonumber \]