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



The operation U_s = 2|s\rangle\langle s| - \mathbb{1} can also be written as U_s = |s\rangle\langle s| - \left(\mathbb{1} - |s\rangle\langle s|\right) 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 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 focus 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 two qubits, that is,  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 image5

Open in IBM Quantum Composer

Grover N=2 A=01 image6

Open in IBM Quantum Composer

Grover N=2 A=10 image7

Open in IBM Quantum Composer

Grover N=2 A=11 image8

Open in IBM Quantum Composer