Code example: Grover's algorithm

Backends

This example is written for the emulator backend. Spin-2 has only two qubits and does not support this example. The starmon-5 backend can be used to execute this example, however, since it does not support the Toffoli gate, the code needs to be rewritten into two-qubit and single-qubit operations.

What does it do?

In mathematical terms, Grover's algorithm L. K. Grover, Phys. Rev. Lett. 79, 325-328 (1997) solves the problem of an unstructured search. It is a quantum algorithm for finding the input value $x_0$ of an Oracle function $f(x)$ with $f(x_0)=1$ and $f(x) = 0$ for all other values of $x$. The strength of the algorithm is that when the Oracle function has $N$ possible input values, the algorithm only requires $\mathcal{O}(\sqrt{N})$ evaluations of the Oracle, while the best classical algorithm needs $\mathcal{O}(N)$ evaluations.

What is the use?

An example of such a problem is finding a specific card in a shuffled deck of N cards. Classically this can only be done by searching the deck of cards one by one, in which case you will need $N$ steps (i.e. $N$ evaluations of the Oracle representing the inspection of cards). Grover's algorithm requires only $\mathcal{O}(\sqrt{N})$ evaluations of the Oracle. The caveat however is that the probability of finding the right answer is not 100%, as will become clearer from the steps in the algorithm. Other examples where Grover's algorithm or similar methods are used are for instance minimization problems.

How does it work?

First, we have to define input states. Without loss of generality we will assume that the input states are integers between 0 and $2^n$ where $n$ is an integer. The $2^n$ integer states will be encoded by the states $\vert 0 \rangle$ and $\vert 1 \rangle$ of $n$ qubits.

Secondly, we have to define an Oracle function for our example, i.e. a function that returns 'zero' for all possible input states, except one input state. We require an Oracle function $f(x)$ that can be encoded in an operator (series of quantum gates) $O$ and that acts as $O \vert x\rangle = (-1)^{f(x)} \vert x\rangle .$ This means that the Oracle negates the probability amplitude of the input state $\vert x\rangle$ if and only if $f(x)=1$.

Examination of the code

Let's look at a concrete example. Let's say our Oracle is a function that returns a 1 (true) only for an input value of the decimal number 6 and 0 (false) for all other possible inputs between 0 and 7. The decimal number 6 is equal to the value 110 in binary representation. We can now try and see how many Oracle calls are needed to find the input value for which the function returns True.

The algorithm (see code below) consists of the following steps:

1. Initialization of the qubits in the $|0\rangle$ state and creation of a uniform superposition of all basis inputs
2. Execution of the Oracle
3. Application of Grover's diffusion operator (inversion about the mean)
4. Repetitions of step 2 and 3
5. Final measurement

In this example 2 repetitions will achieve a high probability of success as will be shown below.

The Oracle operator can be defined in our case by the following circuit. It is not difficult to see that this circuit negates the amplitude probability of the input if and only if the input is 110.

The Oracle function is followed by Grover's diffusion operator (also called amplitude purification) which calculates the mean probability amplitude $\mu$ of all states and inverts the probability amplitudes around this mean. This actually amplifies the probability amplitude of the target state. Repeated steps of calling the Oracle and the diffusion operator amplifies the probability amplitude further. Combining all elements, we arrive at the following algorithm, where the sub circuit called Grover, consists of the Oracle followed by the diffusion operator and is called twice:

Examination of the results

Various resources on the web provide a detailed explanation of Grover's algorithm. To understand just a bit of what is happening let's look at the code, but first start with only one iteration. You can try this yourself by creating a new project, copying the code above to the editor and by changing the number of iterations to 1 in line 8.

When we execute this code, with one iteration only, on the QX single Node emulator (1024 shots) we get the following result (or something quite similar, due to the inherent probabilistic behavior of the code). You may have to scroll to the right to get a clear view on the full histogram. Remember that the input value we were looking for has value 110 (binary representation of the decimal number 6).

The histogram shows that even after 1 iteration there is a reasonable amount of success of finding this value, in this case around 77%, to find the correct entry.

If we now run the code again with two iterations we get the following result. We see that the probability of success has already increased to 95%! For a database of size $N=2^n$ the optimal number of rotations is $r=\pi \sqrt{N}/4$. In our case $N=2^3=8$, so the optimal number is $2.22$, rounded to $2$.

For three iterations, the success probability will decrease again. You can try this yourself by modifying the number of iterations to 3.

Note that the number of iterations in Grover's algorithm is critical. If you make too many iterations the probability of success decreases again.

Want to know more?

To learn more about oracles and Grover's algorithm check out Grover's algorithm on QuTube.

You can also visit Grover's algorithm on Wikipedia and this in-depth lecture by David Deutsch. Or check out this quantiki page or this site.