Grover’s Algorithm
Quantum Algorithms, Quantum Computation, Qubit, Grover’s Algorithm
\(\require{cancel}\)
Basic Elements of Quantum Algorithms
The most basic element of a QC is a quantum bit, qubit for short, which is a two-level quantum system. It spans a two-dimensional Hilbert space denoted as \(H_2\). \(H_2\) is equipped with a fixed basis \((|0\rangle,|1\rangle)\), a so-called computational basis. States \(|0\rangle\) and \(|1\rangle\) are called the basis states. A general state of a single quantum bit is a vector that can be written as: \[\begin{equation} c_0|0\rangle+c_1|1\rangle, \label{eq:qubit} \end{equation}\] where \(|c_0|^2+|c_1|^2=1\)
We can extend this definition to multiple qubits: for example, a system of two qubits describes a four-dimensional Hilbert space \(H_4=H_2\otimes H_2\) having an orthonormal basis \((|00\rangle, |01\rangle,|10\rangle,|11\rangle)\). A state of a two-qubit system is a unit-length vector \[\begin{equation} c_0|00\rangle+c_1|01\rangle+c_2|10\rangle+c_3|11\rangle, \label{eq:twoqubit} \end{equation}\] with \(|c_0|^2+|c_1|^2+|c_2|^2+|c_3|^2=1\).
One of the most important gates in QC is the Hadamard gate, denoted by \(H\), and it is defined as follows:
\[\begin{equation} H|{\mathbf x}\rangle\,\,= \frac{1}{\sqrt{2}} \sum_{{\mathbf y}}(-1)^{{\mathbf x.y}}|{\mathbf y}\rangle \label{eq:hadamarddef} \end{equation}\]
Applying \(H\) to the computational basis we get
\[\begin{eqnarray} H|0\rangle&=&\frac{1}{\sqrt[]{2}}(|0\rangle\,+\,|1\rangle),\nonumber\\ H|1\rangle&=&\frac{1}{\sqrt[]{2}}(|0\rangle\,-\,|1\rangle). \label{eq:hadamarddef2} \end{eqnarray}\] The Hadamard gate basically creates superpositions out of pure states, and it can also be written in matrix form as follows: \[\begin{equation} H=\frac{1}{\sqrt[]{2}}\left( \begin{array}{cc} 1 & 1\\ 1 & -1\\ \end{array} \right). \label{eq:hadamard} \end{equation}\]
Using Hadamard transformations along with phase shift operations, one can implement the quantum Fourier transform (QFT), which is basically the classical discrete Fourier transform applied to the quantum state vector:
\[\begin{equation} QFT |x\rangle\, =\frac{1}{\sqrt{N}}\sum_{y=1}^{N-1}e^\frac{-2\pi i x.y}{N}|y\rangle \label{eq:qft2} \end{equation}\]
This transformation is a key element in many quantum algorithms, including Shor’s factorization algorithm.
Grover’s Algorithm
Grover’s search algorithm enables a QC to find a specific item in an unsorted database of \(N\) entries using \(\mathcal{O}(\sqrt{N})\) operations whereas a classical algorithm would require \(\mathcal{O}(N)\) operations.
Consider a database with \(N\) entries, one of which is the target entry. The goal is to find the index of that particular entry with the least number of queries. The database can be treated as a black box, which is usually referred to as an oracle, that calculates a simple function:
\[\begin{eqnarray} f(x)=\begin{cases} 1 & x =w \\ 0 & x \neq w, \end{cases} \label{eq:groveroracle} \end{eqnarray}\] where \(w\) is the entry we are trying to locate. We are going to feed a state \(|x\rangle |q\rangle\) into the oracle where \(x\) represents the index we are querying and \(q\) is an ancillary bit which will be used by the oracle to return the query result. If we hit the index of the special entry, i.e. \(x=w\), the oracle will flip the ancillary bit, otherwise it will return the same value1. So mathematically, what the oracle is doing is the following transformation:
\[\begin{eqnarray} |x\rangle |q\rangle \rightarrow |x\rangle| f(x)\oplus q\rangle. \label{eq:groveroraclef} \end{eqnarray}\]
Here are the steps of the algorithm:
- Prepare a uniform superposition of numbers \(0\) to \(N-1\): \(|s\rangle=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle\),
- Append the ancillary bit \(|q\rangle=(|0\rangle -|1\rangle)/\sqrt{2}\),
- Feed this input to the oracle,
- Apply the Grover diffusion operator \(2 |s\rangle \langle s| -I\),
- Return to Step 3 and repeat \(\sqrt{N}\) times,
- Measure the output.
Note that we are feeding in all of the possible indices at once, so the special index \(w\) is indeed fed into the oracle. However, it is just one of the \(N\) states appearing in the input. With no clever algorithm, the output will also be in a superposition of \(N\) states. It will collapse into one of them when a measurement is done. The probability of this state being the correct one is just \(1/N\), just like in the classical case. A QC’s ability to process all inputs at once is not useful unless you can sift through the output using a good algorithm. To understand how Grover’s algorithm enhances the chances of getting the correct output, let’s take a look at what the oracle returns for that particular input: \(x=w\) and \(|q\rangle=(|0\rangle -|1\rangle)/\sqrt{2}\). Using Eq. \(\ref{eq:groveroraclef}\), we get:
\[\begin{eqnarray} |w\rangle|q\rangle=|w\rangle \frac{|0\rangle -|1\rangle)}{\sqrt{2}} \rightarrow |w\rangle\frac{| 1\oplus 0\rangle- |1 \oplus 1\rangle}{\sqrt{2}} =|w\rangle \frac{|1\rangle-|0\rangle}{\sqrt{2}} = -|w\rangle|q\rangle, \label{eq:groveroraclefstar} \end{eqnarray}\] which is simply the negative of the input value. One can repeat the same calculation and show that when \(x\neq w\), the oracle output is equal to its input. Based on these two observations, we can define the effect of the oracle in the operator form:
\[\begin{eqnarray} U_w= I -|w\rangle \langle w|, \label{eq:groveroracleop} \end{eqnarray}\] which is easy to understand: if the object it operates on has \(|w\rangle\) content, then the sign on that component will be flipped. Let’s apply the oracle operation \(U_w\) to the uniform superposition \(|s\rangle\):
\[\begin{eqnarray} U_w|s\rangle&= (I -|w\rangle \langle w|)|s\rangle =|s\rangle -\frac{2}{\sqrt{N}}|w\rangle. \label{eq:groveroracleopons} \end{eqnarray}\]
The diffusion operation, \(U_s=2 |s\rangle \langle s| -I\) will act on the state in Eq. \(\ref{eq:groveroracleopons}\) to yield
\[\begin{eqnarray} U_s U_w|s\rangle&=&(2 |s\rangle \langle s| -I)(|s\rangle -\frac{2}{\sqrt{N}}|w\rangle)=\frac{N-4}{N}|s\rangle +\frac{2}{\sqrt{N}}|w\rangle, \label{eq:afterdiffusion} \end{eqnarray}\] which shows the ingenuity of the algorithm: the amplitude of the state \(|w\rangle\) increased from \(1/\sqrt{N}\) to \(\frac{2}{\sqrt{N}}\) in one iteration. In fact, if \(N=4\), the amplitude becomes \(1\), which means that Grover’s algorithm can locate the special entry out of four in a single iteration with 100% probability. For larger \(N\), you need to keep iterating \(U_s U_w\) operations \(\sqrt{N}\) times to enhance the amplitude of \(|w\rangle\). At each step of the iteration, you are moving the output state closer to the state represented by \(|w\rangle\). The operations can be visualized as rotations in Hilbert space of quantum states as illustrated below.
1 You may ask why we simply do not return \(1\) or \(0\) depending on \(x=w\). This is because all the operations in QC have to be reversible. If the oracle overwrote \(|q\rangle\) with \(0\) or \(1\), the previous information on \(|q\rangle\) would not be recoverable. This is also the reason why there is no quantum \(AND\) gate: one cannot uniquely recover the inputs of the \(AND\) gate from its output.