Skip to main content
Logo image

Quantum Computing: A gentle introduction for Liberal Arts Institutions

Levi Goldberg, Shun Suzuki, Javier Orduz

Section 3.2 Grover’s Algorithm

Classical search algorithms are fundamental techniques used in computer science to locate a specific item within a collection of items. Common approaches include linear search, where each item is checked sequentially until the target is found, and binary search, which efficiently narrows down the search range in a sorted array by repeatedly dividing it in half. These methods are crucial in various applications, from database retrieval to optimization problems, as they determine how quickly and efficiently data can be accessed and processed. However, classical search often requires significant time and resources, especially with large datasets. Quantum computing has the potential to revolutionize search algorithms through methods like Grover’s algorithm, which can search an unsorted database quadratically faster than classical algorithms, offering a profound improvement in speed and efficiency for large-scale search problems.
To implement Grover’s algorithm, we need unitary matrix, written as \(U_f\text{.}\) This matrix works as a black box as following
\begin{gather} \ket{x,y} \stackrel{U_f}{\rightarrow} \ket{x, y\oplus f(x)}\tag{3.2.1} \end{gather}
The XOR operartion is
\begin{equation*} \boldsymbol{x}\oplus \boldsymbol{y} = x_1\oplus y_1, x_2\oplus y_2, x_3\oplus y_3, \ldots, x_n\oplus y_n. \end{equation*}
diffusion gate is an operator given by
\begin{gather} O = - I + 2\ket{\phi}\bra{\phi}\tag{3.2.2} \end{gather}
Household transform is is a linear algebra technique often used to construct quantum operations that reflect a quantum state about a certain axis or state, which is a crucial step in many quantum algorithms, including Grover’s algorithm. By applying a series of these transformations, one can systematically manipulate and amplify the amplitude of the desired state while diminishing the amplitudes of the undesired ones, ultimately leading to a more efficient search process. This method contributes to the algorithm’s overall quadratic speedup compared to classical search methods.
Now, we implement Grover’s algorithm for the following example
We prose a random vector \(x\text{,}\) and try to find the expected factor
1. Consider you have the following data
\begin{gather} \boldsymbol{x}^T=(x_1,x_2,x_3,x_4,x_5)=(19,12,3,10,1)\label{eq:randomVector_a}\tag{3.2.3} \end{gather}
Figure 3.2.2. Representation of \(x_i\)values
2. Calculate the average
\begin{gather} \overline{x}=\sum_i^N\frac{x_i}{N} = \frac{19+12+3+10+1}{5} = \frac{45}{5} = 9\tag{3.2.4} \end{gather}
3. Invert each element aorund the average by defining \(\overline{x} - x_i = \delta_i\)
\begin{align} \overline{x}&-&x_i & =&\delta\\ 9&-&19 &=&-10\\ 9&-&12 &=&3\\ 9&-&3 &=&6\\ 9&-&10 &=&-1\\ 9&-&1 &=&8 \tag{3.2.5} \end{align}
We calculate the units away, \(δ\) , from the average,\(x\) , for each \(xi\)
4.a define \(2x-x_i =x^\prime_i\) and calculate
\begin{align} 2\overline{x}& -& x_i& =& x_i^\prime\\ 18 & - & 19 & = & -1\\ 18& -&12 &=&6\\ 18& -&3 &=&15\\ 18& -&10 &=&8\\ 18& -&1 &=&17 \tag{3.2.6} \end{align}
The inversion about the average calculates the units away, \(δ\text{,}\) from the average, \(x\text{,}\) for each \(x_i\) .
4.b Plot the data
\begin{align} \begin{pmatrix} x_1^\prime&x_2^\prime&x_3^\prime&x_4^\prime&x_2^\prime \end{pmatrix} = \begin{pmatrix} -1& 6& 15& 8 &17 \end{pmatrix}\tag{3.2.7} \end{align}
Figure 3.2.3. Representation of \(x^\prime_i\)values
The last operation,\(-x_i +2\overline{x}=x_i^\prime\) has the following representation in terms of matrices,
\begin{gather} (- I + 2 A) \boldsymbol{x} = \boldsymbol{x}^\prime\tag{3.2.8} \end{gather}
where \(\overline{x} \to A \boldsymbol{x},\) where
\begin{align} A = \frac{1}{5} \begin{pmatrix} 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1 \end{pmatrix}\tag{3.2.9} \end{align}
is the matrix for the average. It means \(\boldsymbol{\overline{x}} = A\boldsymbol{x}\text{.}\) As follows,
\begin{align} \boldsymbol{\overline{x}} = A \boldsymbol{x}= \frac{1}{5} \begin{pmatrix} 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1 \end{pmatrix} \begin{pmatrix} 19\\12\\3\\10\\1 \end{pmatrix} = \begin{pmatrix} 9\\9\\9\\9\\9 \end{pmatrix}\tag{3.2.10} \end{align}
This is a state where each amplitude is the average of all the amplitudes.
5. Invert amplitudes about the average.
\begin{align} (-I+2A)\boldsymbol{x}&=&\boldsymbol{x}^\prime\\ \left[- \begin{pmatrix} 1&0&0&0&0\\ 0&1&0&0&0\\ 0&0&1&0&0\\ 0&0&0&1&0\\ 0&0&0&0&1 \end{pmatrix} + \frac{2}{5} \begin{pmatrix} 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ \end{pmatrix} \right] \begin{pmatrix} 19\\12\\3\\10\\1 \end{pmatrix} &=&\\ % \frac{1}{5} \begin{pmatrix} -3&2&2&2&2\\ 2&-3&2&2&2\\ 2&2&-3&2&2\\ 2&2&2&-3&2\\ 2&2&2&2&-3\\ \end{pmatrix} \begin{pmatrix} 19\\12\\3\\10\\1 \end{pmatrix} &=& \begin{pmatrix} -1\\ 6\\ 15\\ 8\\17\\ \end{pmatrix}\tag{3.2.11} \end{align}
The item (4).b and eq. (3.1.11) show same results, the second report implies linear algebra operations.
This example emphasizes on invert amplitudes about the mean; however, Grover’s algorithm requires phase inversion. The following example explains the step.
Consider the information from the example 3.1.1. We have the same vector.
\begin{gather} \boldsymbol{x}^T=(x_1,x_2,x_3,x_4,x_5)=(19,12,3,10,1)\label{eq:randomVector_b}\tag{3.2.12} \end{gather}
To apply the phase inversion about the average, which requires the function,
\begin{equation*} %f(x), f:\{0,1\}^n \to \{0,1\} \end{equation*}
and
\begin{align} f(x)= \begin{cases} 1& \text{if } x=w\\ 0&\text{else if} \end{cases}\tag{3.2.13} \end{align}
which is usually shown such as
\begin{gather} \ket{x} \stackrel{U_f}{\rightarrow} (-1)^{f(x)}\ket{x}\tag{3.2.14} \end{gather}
where \(U_f\)is an oracle. This oracle shifts the phase of the solution, and highlights the solutions to the search problem.
We will take the vector
\begin{align} \boldsymbol{\overline{x}}^T= \begin{pmatrix} 9&9&9&9&9 \end{pmatrix}\tag{3.2.15} \end{align}
And suppose we are looking for the second input, it meansx=x_2=w\(\) is the winner, it is oul goal. \(\boldsymbol{\overline{x}}^T=\begin{pmatrix} 9&-9&9&9&9 \end{pmatrix}.\)
Now we apply
Figure 3.2.5. Representation of the \(\overline{x}_i\) values. The horizontal line is the new average\(\frac{9-9+9+9+9}{5} = 5.4\)
and calculate
\begin{align} (-I+2A)\boldsymbol{x}&=&\boldsymbol{x}^\prime\\ \frac{1}{5} \begin{pmatrix} -3&2&2&2&2\\ 2&-3&2&2&2\\ 2&2&-3&2&2\\ 2&2&2&-3&2\\ 2&2&2&2&-3\\ \end{pmatrix} \begin{pmatrix} 9\\-9\\9\\9\\9 \end{pmatrix} &=&\begin{pmatrix} 9\\ 99\\ 9\\ 9\\9\\ \end{pmatrix}\tag{3.2.16} \end{align}
Figure 3.2.6. Representation of the \(\overline{x}_i\) values. The horizontal line is the new average\(\frac{9-99+9+9+9}{5} = 12.6\)
and calculate
\begin{align} (-I+2A)\boldsymbol{x}&=&\boldsymbol{x}^\prime\\ \frac{1}{5} \begin{pmatrix} -3&2&2&2&2\\ 2&-3&2&2&2\\ 2&2&-3&2&2\\ 2&2&2&-3&2\\ 2&2&2&2&-3\\ \end{pmatrix} \begin{pmatrix} 9\\-99\\9\\9\\9 \end{pmatrix} &=&\begin{pmatrix} -171\\ 369\\ -171\\ -171\\-171\\ \end{pmatrix}\tag{3.2.17} \end{align}
We can see how the amplitude for the second element increases.
We showed how this search algorithm works, and it is clear that we will get the second element in the list as the most probable output.
This part shows the Grover’s algorithm in bracket notation.
This algorithm enables this search method to be speed up to\(\mathcal{O}(\sqrt{N})\) operations. With this algorithm "searching an unsorted database" with \(N=2^n\) elements in \(\mathcal{O}(\sqrt{N})\) time. Classical algorithm needs on average \(N/2 =\mathcal{O}(\sqrt{N})\) time. The goal is find \(w\text{,}\) given an oracle \(U_f\) with
\begin{equation*} f:\{0,1\}^n \to \{0,1\} \end{equation*}
\begin{align} f(x)= \begin{cases} 1& \text{if } x=w\\ 0&\text{else if} \end{cases}\tag{3.2.18} \end{align}
and
\begin{align} f_0(x)= \begin{cases} 0& \text{if } x=0000\\ 1&\text{else} \end{cases}\tag{3.2.19} \end{align}
where the phase oracle is
\begin{gather} U_f\ket{x} = (-1)^{f(x)}\ket{x}\tag{3.2.20} \end{gather}
where
\begin{align} U_f: \begin{cases} \ket{w} \to -\ket{w} &\\ \ket{x} \to \ket{x} & \forall x\neq w \end{cases}\tag{3.2.21} \end{align}
then
\begin{gather} U_f = 1 - 2 \ket{w}\bra{w}\tag{3.2.22} \end{gather}
and
\begin{align} {U_f}_0: \begin{cases} \ket{0} \to \ket{0}^{\otimes n} &\\ \ket{x} \to -\ket{x} & \forall x\neq 00...000 \end{cases}\tag{3.2.23} \end{align}
then
\begin{gather} {U_f}_0 = 2 (\ket{0}\bra{0})^{\otimes n} - I \tag{3.2.24} \end{gather}
the Grover’s iteration
\begin{gather} G=(2|\psi\rangle\langle\psi|-I) O\tag{3.2.25} \end{gather}
The algorithm is shown below
Figure 3.2.7. The process of Grover’s algorithm
Here is another explanation
\(\textbf{Claim:}\) \(y=w\)
\(\textbf{Proof:}\) Define a superposition state
\begin{gather} \ket{\psi_1} = H^{\otimes n}\ket{0}^{\otimes n} = 2^{-\frac{n}{2}}\sum_{x\in \{0,1\}}^{2^n-1}\ket{x}\tag{3.2.26} \end{gather}
and (note the dashed line in the circuit)
\begin{align} V = H^{\otimes n} {U_f}_0H^{\otimes n} &= H^{\otimes n}\big( 2 \ket{0}\bra{0}^{\otimes n} - I \big) H^{\otimes n}\\= & 2 H^{\otimes n}\ket{0}\bra{0}^{\otimes n}H^{\otimes n} - H^{\otimes n}IH^{\otimes n}\\ &= 2 \ket{\psi_1}\bra{\psi_1} - I\tag{3.2.27} \end{align}
where we used eq.(3.1.24) and eq.(3.1.26)
\(\textbf{Process:}\) This algorithm carries out the operation \((V U_f)^r\) on the state \(\ket{\psi_1}\)
The representation of the Grover’s algorithm using circuits is shown in fig(3.1.8.)
Figure 3.2.8. Quantum circuit for the Grover algorithm
<Prev^TopNext>