# 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.

## Unstructured search¶

Suppose you are given a large list of items. Among these items is one item with a unique property that we wish to locate. We will call this one the winner, . 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 , which is pink.

To find the pink box – the *marked item* – using classical computation,
one would have to check on average of these boxes, and in
the worst case, all of them. On a quantum computer, however,
we can find the marked item in roughly 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.

## 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 , which
returns for all unmarked items and
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 so
that ; now we can represent it in terms of qubits on a
quantum computer. Then we define the oracle matrix to act on
any of the simple, standard basis states
by We see that if
is an unmarked item, the oracle does nothing to the state.
However, when we apply the oracle to the basis state ,
it maps . Geometrically, this
unitary matrix corresponds to a reflection about the origin for the
marked item in an 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*:

If at this point we were to measure in the standard basis , this superposition would collapse to any one of the basis states with the same probability of . Our chances of guessing the right value is therefore in , as could be expected. Hence, on average we would need to try about 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 and the uniform superposition . These two vectors span a two-dimensional plane in the vector space They are not quite perpendicular because occurs in the superposition with amplitude as well. We can, however, introduce an additional state that is in the span of these two vectors, which is perpendicular to , and is obtained from by removing and rescaling.

**Step 0** The amplitude amplification procedure starts out in the
uniform superposition . (The uniform superposition
is easily constructed from
, as was shown in a
previous section.) At the initial state is
.

The left graphic corresponds to the two-dimensional plane spanned by . The right graphic is a bar graph of the amplitudes of the state for the case . The average amplitude is indicated by a dashed line.

**Step 1** We apply the oracle reflection to the
state .

Geometrically this corresponds to a reflection of the state about . This transformation means that the amplitude in front of the state becomes negative, which in turn means that the average amplitude has been lowered.

**Step 2** We now apply an additional reflection about the
state In the
bra-ket
notation this reflection is written
. This transformation maps
the state to and completes the
transformation .

Note

The operation can also be written as showing that it is the projection onto the uniform superposition minus the projection onto its orthogonal complement.

Two reflections always correspond to a rotation. The transformation
rotates the initial state closer
towards the winner . The action of the reflection
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 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 focus in on the winner.

After steps the state will have transformed to How many times do we need to apply the rotation? It turns out that roughly rotations suffice. This becomes clear when looking at the amplitudes of the state . We can see that the amplitude of grows linearly with the number of applications . 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 two qubits, that is, , which means there are four possible oracles , one for each choice of the winner. The first part of this example creates the uniform superposition. The second part tags the state with , 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 .

**Grover N=2 A=00**

**Grover N=2 A=01**

**Grover N=2 A=10**

**Grover N=2 A=11**