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 