Implementing Grover’s Algorithm in Qiskit

One advantage a quantum computer is supposed to have over classical computers is superior searching speeds. For instance, let’s say you had a library full of books and on one page of one such book, there is a big red X. After a while, you realize that you want to find this specific page but instead of trying to look for it yourself, you decide to use a computer.

If you were using a classical computer, it would have to systematically look through each book and with in each book, look at each page until it finds the X. But, if you were using a quantum computer, it would be able to look through each book at the same time, or perhaps even each page at the same time.

As you can see, a quantum computer is exponentially faster.

But, how would a quantum computer actually be able to do this? One way is by using Grover’s Algorithm.

Grover’s Algorithm was developed to solve the following problem. Say you had an unstructured list with N = 2^n elements, and you want to find the element w (the “winning” element). Like before, the classical computer could take anywhere between 1 query of the list (if it happens to get the winning element on the first try) or 2^n queries (if it takes all the way to the end to get the right one).

What grover’s algorithm could do is choose w in at most sqrt(N) queries.

A nice thing about Grover’s Algorithm is that it doesn’t depend on the list’s internal structure — i.e., the way it works is not influenced by the nature of the list. This means that it is generic and therefor, can be generalized to speeding up the run time of other operations quadratically (because of the square root).

How does the algorithm work?

1. Initialize 2^n qubits to the state |0>.
2. Create an equal superposition of all possible states, |s> by applying Hadamard gates to each qubit.
3. Pass it through the quantum oracle — i.e. the function of interest.
4. Pass it through the “Grover diffuser” — basically another function, which we will explain below.
5. Keep repeating step 2 and 3.

Why does the algorithm work?

Before we begin our search, all guesses are equally good and so the “goodness” of all the searches is an equal superposition of all possibilities. Since we have 2^n items in the list, if we were to measure the quantum state, it would collapse to either one of the bases with equal probability and so the probability of guessing the winning state on the first try is 1/(2^n).

What we want to do is increase the probability that we choose the winning state and decrease the probability that we choose anything else. This is done using amplification: the process of stretching the amplitude of the winning state and and shrinking that of the others so that we are more likely to choose the winning one.

This is done in two steps. First off, the oracle keeps the phase of all the states we are not looking for positive and changes the phase of the one we are looking for to a negative. The average of all these amplitudes is then brought down because of the negative one, and so it is less than the amplitudes of all the other list items.

Then, the Grover diffuser reflects these states over said average. This makes the amplitude of w much higher than the average and the other amplitudes much smaller. So, now the probability of choosing the winning state is much higher than that of the other states.

After several repetitions of the oracle and Grover diffuser, the probability of choosing the winning state will converge to 100% because its amplitude will keep getting higher and higher. However in most cases, it will never quite reach that because the other items will still have a small amplitude associated with them.

And it turns out that it converges after about sqrt(N) steps.

For a more detailed version of the mathematical explantation, check out: https://www.youtube.com/watch?v=iJX794qJIpY&list=PLOFEBzvs-VvrXTMy5Y2IqmSaUjfnhvBHR&index=6

How can we implement this in qiskit?

The version of Grover’s algorithm that we are going to implement here is concerns a list of the computational basis states with 2 qubits. In particular, we are going to be looking for w = |11>.

It turns out that in this case, the quantum oracle will look like

which is actually the same as the controlled-Z gate. This makes construction pretty easy later on. So now, our circuit needs to look something like

Now, this turns out to be a pretty special example because we can actually make the probability of choosing the winning state exactly 100% (rather than somewhere quire close to it).

Like always, the first step is to import everything we need.

Then, we define the circuit to take 2 qubits.

Then, we define a function which adds Hadamard gates to all such qubits.

And apply it to our circuit to get

Then, we add in the diffuser and oracle from above.

And, we can run it through a simulator and find that every time, we choose the winning state!

If we were to simulate this algorithm on a real device, we wouldn’t expect to get such a perfect result — some of the time, we’d end up getting one of the other computational bases due to decoherence — qubits not behaving as they are supposed to due to error.