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.

Suppose you are given a large list of \(N\) items. Among these items there is one item with a unique property that we wish to locate; we will call this one the winner \(w\). Think of each item in the list as a box of a particular color. Say all items in the list are gray except the winner \(w\), which is pink.

To find the pink box – the *marked item* – using classical
computation, one would have to check on average \(N/2\) of these boxes,
and in the worst case, all \(N\) of them. On a quantum computer,
however, we can find the marked item in roughly \(\sqrt{N}\) steps with
Grover’s amplitude amplification trick. It was proven (even before
Grover’s algorithm was discovered!) that this speedup is in fact the
most we can hope for [Bennett,
1997]. A quadratic speedup is
indeed a substantial time-saver for finding marked items in long lists.
Additionally, the algorithm does not use the list’s internal structure,
which makes it *generic;* this is why it immediately provides a
quadratic quantum speed-up for many classical problems.

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.

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.

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.

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.

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.

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\).