Grover’s Algorithm

We are now in a good place to discuss our first quantum algorithms and subroutines. Let’s begin with Grover’s search algorithm and the amplitude amplification trick.

You have likely heard that one of the many advantages a quantum computer has over a classical computer is its superior speed searching databases. Grover’s algorithm demonstrates this capability. This algorithm can speed up an unstructured search problem quadratically, but its uses extend beyond that; it can serve as a general trick or subroutine to obtain quadratic run time improvements for a variety of other algorithms. This is called the amplitude amplification trick. But before we start the simulations, let’s look at the unstructured search problem.

The Oracle

How will the list items be provided to the quantum computer? A common way to encode such a list is in terms of a function \(f\) which returns \(f(x) = 0\) for all unmarked items \(x\) and \(f(w) = 1\) for the winner. To use a quantum computer for this problem, we must provide the items in superposition to this function, so we encode the function into a unitary matrix called an oracle. First we choose a binary encoding of the items \(x, w \in \{0,1\}^n\) so that \(N = 2^n\); now we can represent it in terms of qubits on a quantum computer. Then we define the oracle matrix \(U_f\) to act on any of the simple, standard basis states \(| x \rangle\) by
\(U_f | x \rangle = (-1)^{f(x)}  |  x \rangle.\)

We see that if \(x\) is an unmarked item, the oracle does nothing to the state. However, when we apply the oracle to the basis state \(| w \rangle\), it maps \(U_f | w \rangle = -| w \rangle\). Geometrically, this unitary matrix corresponds to a reflection about the origin for the marked item in an \(N = 2^n\) dimensional vector space.

Amplitude amplification

So how does the algorithm work? Before looking at the list of items, we have no idea where the marked item is. Therefore, any guess of its location is as good as any other, which can be expressed in terms of a quantum state called a uniform superposition:

\(|s \rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N -1} | x \rangle.\)

If at this point we were to measure in the standard basis \(\{ | x \rangle \}\), this superposition would collapse, according to the fifth quantum law, to any one of the basis states with the same probability of \(\frac{1}{N} = \frac{1}{2^n}\). Our chances of guessing the right value \(w\) is therefore \(1\) in \(2^n\), as could be expected. Hence, on average we would need to try about \(N = 2^n\) times to guess the correct item.

Enter the procedure called amplitude amplification, which is how a quantum computer significantly enhances this probability. This procedure stretches out (amplifies) the amplitude of the marked item, which shrinks the other items’ amplitude, so that measuring the final state will return the right item with near-certainty.

This algorithm has a nice geometrical interpretation in terms of two reflections, which generate a rotation in a two-dimensional plane. The only two special states we need to consider are the winner \(| w \rangle\) and the uniform superposition \(| s \rangle\). These two vectors span a two-dimensional plane in the vector space \(\mathbb{C}^N.\) They are not quite perpendicular because \(| w \rangle\) occurs in the superposition with amplitude \(N^{-1/2}\) as well. We can, however, introduce an additional state \(|s'\rangle\) that is in the span of these two vectors, which is perpendicular to \(| w \rangle\) and is obtained from \(|s \rangle\) by removing \(| w \rangle\) and rescaling.

step 0 The amplitude amplification procedure starts out in the uniform superposition \(| s \rangle\).  (The uniform superposition is easily constructed from \(| s \rangle = H^{\otimes n} | 0 \rangle^n\), as was shown in a previous section.) At \(t = 0\) the initial state is \(| \psi_0 \rangle =   |s \rangle\).
The left graphic corresponds to the two-dimensional plane spanned by \(|w\rangle, |s\rangle\). The right graphic is a bar graph of the amplitudes of the state \(| \psi_t \rangle\) for the case \(N = 2^2 = 4\). The average amplitude is indicated by a dashed line.
step 1 We apply the oracle reflection \(U_f\) to the state \(U_f | \psi_t \rangle =  | \psi_{t'} \rangle\).

Geometrically this corresponds to a reflection of the state \(|\psi_t\rangle\) about \(-|w\rangle\). This transformation means that the amplitude in front of the \(|w\rangle\) state becomes negative, which in turn means that the average amplitude has been lowered.

step 2 We now apply an additional reflection \(U_s\) about the state \(|s\rangle\). In the bra-ket notation this reflection is written \(U_s = 2|s\rangle\langle s| - \mathbb{1}\). This transformation maps the state to \(U_s | \psi_{t'} \rangle\) and completes the transformation \(|\psi_{t+1}\rangle = U_s U_f | \psi_t \rangle\).

Two reflections always correspond to a rotation. The transformation \(U_s U_f\) rotates the initial state \(|s\rangle\) closer towards the winner \(|w\rangle\). The action of the reflection \(U_s\) in the amplitude bar diagram can be understood as a reflection about the average amplitude. Since the average amplitude has been lowered by the first reflection, this transformation boosts the negative amplitude of \(|w\rangle\) to roughly three times its original value, while it decreases the other amplitudes. We then go to step 1 to repeat the application. This procedure will be repeated several times to zero in on the winner.

After \(t\) steps the state will have transformed to
\(| \psi_t \rangle = (U_s U_f)^t  | \psi_0 \rangle.\)
How many times do we need to apply the rotation? It turns out that roughly \(\sqrt{N}\) rotations suffice. This becomes clear when looking at the amplitudes of the state \(| \psi_t \rangle\). We can see that the amplitude of \(| w \rangle\) grows linearly with the number of applications \(\sim t N^{-1/2}\). However, since we are dealing with amplitudes and not probabilities, the vector space’s dimension enters as a square root. Therefore it is the amplitude, and not just the probability, that is being amplified in this procedure.

Example circuits

Let us now examine a simple example. The smallest circuit for which this can be implemented involves 2 qubits, i.e. \(N = 2^2\), which means there are four possible oracles \(U_f\), one for each choice of the winner. The first part of this example creates the uniform superposition. The second part tags the state with \(U_f\), which is made from a control-Z gate, made from a CNOT (as described in the last section). The final part of the circuit performs \(U_s\).

Grover N=2 A=00
Open in composer

Grover N=2 A=01
Open in composer

Grover N=2 A=10
Open in composer

Grover N=2 A=11
Open in composer