Grover Search

With Deutsch-Jozsa, we saw our first fundamentally quantum algorithm that showed how quantum computers could do something better than classical computers. But it doesn't seem like a particularly useful algorithm. Is there a more useful algorithm that we might be able to run on a quantum computer?

We'll answer this question by looking at Grover Search. This algorithm shows how we can use a quantum computer to search through some list of items exponentially faster than a classical computer would be able to.

Let's start by formally defining the problem.

Suppose we have a list of items we would like to search. Perhaps a list of users in our system and we would like to find the user with a particular email address:

In a classical system, we might solve this problem of lookup using indexes. But this can create overheads in other parts of the system, so it is not uncommon that we might consider consider a linear search.

In a completely unordered list like this, we know that the best we can do is simply scanning over each item until we find our match. This is a linear approach since the amount of time it takes to scan through the list is proportional linearly to the number of items in the list.

This is quite often refered to as the "phone book search" problem. A phone book is an ancient pre-historic device that was used to look up a phone number for a particular person. It was sorted by name so that you could find the person you were looking for quickly. But if you wanted to do the opposite, find the name associated to a particular phone number, the best you could do was simply scan through every entry until you found it.

I hope you're already getting excited thinking about how a quanutm computer could solve this quicker. You should be!

Before we step back into the quantum world, let's translate our problem into some more formal mathematical language.

Let's say our database contains $N$ objects. We will define a function $f$ that takes an index from $0$ to $N-1$ and outputs $1$ if the database item at that index satisfies our condition and $0$ otherwise.

For example, in our above example, if we're looking for the user with email "[email protected]", we have $f(x) = 1$ if the object at index $x$ has that email address. If we treat the "User ID" as the index then in this case: $x = 76291$.

Again, to re-iterate in the mathemtical language, the best a classical computer could do to find $x$ would be to check all values from $0$ to $N-1$ until it finds one that satisfies $f(x) = 1$.

Now let's go back to the quantum world.

To start constructing our quantum algorithm, we're going to introduce something called a phase oracle. It will be define as follows:

So it essentially sticks a negative sign in front of a particular state and leaves all others alone. We call this a phase oracle since adding a negative sign is just multiplying by a global phase $e^{i\pi} = -1$.

We can represent this oracle in outer-product notation:

We can see this works, in the case when $y \neq x$:

We will apply one additional constraint before we construct the algorithm: the database will only have a single entry satisfying the condition i.e. there will only exist a single value of $x$ such that $f(x) = 1$. It's possible to generalise to multiple solutions, but we'll keep it simple for now.

Let's define the solution we're looking for as $\omega$ i.e. $f(\omega)=1$. Grover's search will then run as follows:

1. Prepare $n=\lceil \log_2{N} \rceil$ qubits in the starting state $\ket{0}$. This ensures we have enough bits to represent all the possible indexes in our database.
2. Apply the Hadamard gate to all qubits: $H^{\otimes n}$, to end up in the even superposition: $\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1} \ket{x}$
3. Apply our quantum phase oracle for the solution state: $O_{\omega}$
4. Hadamard gate every qubit: $H^{\otimes n}$
5. Apply an oracle that adds a negative sign to every state apart from the all zero state: $-O_0$
6. Hadamard gate every qubit: $H^{\otimes n}$
7. Go back to step 3 and repeat a specified number of times
8. Measure all the qubits with a high probability to get the solution $\omega$
9. If the solution is incorrect, run again

Ok, that's quite a lot to take in. Before we start looking into how this works, let's look at the circuit representation:

The numbers at the bottom represent the corresponding steps in the algorithm listed above. We've also added a bracket over steps 3-6 labelled $G$. We will refer to this part as the Grover iterator. This will be the part that gets repeated several times.

Analysing this algorithm revolves around finding a nice mathematical representation of this operator. Formally, we can see it's defined as:

In fact, we'll split it up more by defining the Grover diffusion operator $D$:

So $G = DO_{\omega}$

We can simplify $D$:

Since the Hadamard gate is its own inverse, the second term here cancels to $I$

The first bracket in the first term we know is just the even superposition of all possible qubit states: $\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\ket{x}$. We will need this state a lot, so we're going to denote it as $\ket{s}$. The second bracket is just the corresponding bra of this ket: $\bra{s}$. This comes from some maths we haven't discussed yet, but just know that since the two terms in the braket are real (have no imaginary coefficients) the bra can be written this way simply by flipping the ket.

Putting this together we now have:

And thus:

The next step of our journey will be building some geometric intuition for what these operators are really doing.

What we will show now, is that an operator of the form $2\ket{x}\bra{x} - I$ actually represents a geometric reflection.

To see this, imagine we have 2 orthogonal vectors $\ket{x}$ and $\ket{x^{\perp}}$ where, since they are orthogonal, we have $\braket{x|x^{\perp}} = 0$. We define a vector in terms of these two: $\ket{\psi} = a\ket{x} + b\ket{x^{\perp}}$ and then see how our operator behaves on it:

As you can see, the operator flipped the component of $\ket{x^{\perp}}$ and left the component of $\ket{x}$ untouched. Thus this represents a reflection or mirroring around the vector $\ket{x}$.

Now we know this a slight re-arranging of our definition of $G$ tells us so much more:

We can see that $G$ is in fact a reflection around $\ket{\omega}$ followed by a reflection around $\ket{s}$ then negated.

If you remember your rules of geometric transforms well, you will know that 2 reflections always make a rotation. So we can see that our Grover iterator is performing a rotation of our vector every time we apply it.

We'd like to be able to visualise this rotation; to see where it's rotating from and where it's rotating to. The problem is that we have $n = \lceil \log_2{N} \rceil$ qubits and thus $\approx N$ different basis states. This means if we have 1000 items to search through, we have a 1000-dimensional vector space! That's not very easy to visualise...

Luckily we have a handy tool up our sleeve: projection. Just in the same way your eyes right now are projecting the 3D world into a 2D image on your retina, we can project our problem into a more manageable number of dimensions.

Surprisingly, we can project it down into just 2!

Our first vector will simply be the solution we are looking for: $\ket{\omega}$.

The second vector we will choose will be the even superposition of all states we are NOT looking for i.e. an even superposition of all $\ket{x}$ where $f(x) = 0$. Since we specified there will be only one solution in our case, there are $N-1$ such values of $\ket{x}$ so we can write our second vector as:

The choice to label this vector $\ket{s^\prime}$ will become apparent shortly.

It's fairly clear these two vectors are orthogonal, since they don't share any of the same kets. And thus we can plot them in 2D:

Ok, so we've got two basis vectors for our space. Now we need to know where in the space to plot our state vector. Since we've applied all Hadamard gates to the all $\ket{0}$ state, we know that we start in the state $\ket{s}$.

We also know all our state vectors should be of unit length, that's what the normalisation coefficients are for, so we have to determine whether it is closer to $\ket{\omega}$ or $\ket{s^\prime}$. We can do this with the inner-product since we know two orthogonal vectors inner-product to 0 and two parallel vectors to 1:

From these results, it is fairly clear that our initial state vector lies closer to $\ket{s^\prime}$ than $\ket{\omega}$, so let's plot our starting point. We'll denote our starting state as $\phi_0$ as we have done before:

Now to find $\ket{\phi_1}$ we just apply our Grover iterator: $\ket{\phi_1} = G\ket{\phi_0}$. We know, from earlier, that this operation is a reflection around $\ket{\omega}$ followed by a reflection around $\ket{s}$ then negated.

A nice result from 2D geometry is that a negated reflection around a vector is equal to a reflection around a perpendicular vector.

So we could pull the negative sign of the Grover iterator inside to the reflection around $\ket{\omega}$ and make it a reflection around $\ket{s^\prime}$

So our Grover iterator is now a reflection around $\ket{s^\prime}$ followed by a reflection around $\ket{s}$.

So this looks like:

Here, the bottom dotted line represents the first reflection around $\ket{s^\prime}$.

So we can see that the Grover iterator is rotating our state away from the vector of non-solutions, $\ket{s^\prime}$, and towards the solution vector $\ket{\omega}$!

Once we have got near to the solution we can simply measure the state and we will have a high probability of finding the correct solution. The only question is how many times do we have to rotate? i.e. how many times do we have to apply the Grover iterator?

To answer this, we'll have to look at the angles involved in the rotations. We can see this more easily on the following diagram:

We can see clearly some doubling relations between angles here. The green angle, the result after the initial reflection around $\ket{s^\prime}$, is double the red angle and the blue angle, the result after the reflection around $\ket{s}$, is double the green angle. And finally, the yellow angle is clearly half the blue angle.

Putting this all together we see that the angle between $\ket{\phi_0}$ and $\ket{\phi_1}$ is simply double the red angle, the angle between $\ket{s}$ and $\ket{s^\prime}$.

So what is the red angle?

We can use the following geometric result on the inner-product: $\braket{x|y} = \sqrt{\braket{x|x}}\sqrt{\braket{y|y}}\cos{\theta}$. In our case $\ket{s}$ and $\ket{s^\prime}$ are unit vectors, so the length scales can be ignored: $\braket{s|s^\prime} = \cos{\theta}$.

But we already calculated this inner-product earlier it's:

So we have:

Using sin/cos relations:

For small $\theta$ we have $\sin^{-1}{\theta} \approx \theta$ so:

Now remember every application of the Grover iterator rotates by $2\theta$ so after $n$ iterations we are at an angle of $(n+1)2\theta$.

We reach the solution when this angle equals $\pi/2$ which, when subbing into the previous equation, is when $n = \pi/4\theta - 1$.

Subbing now in our approximation of $\theta$:

Wow, that was a lot of work! But we're finally done!

We've shown that we require only $\sim \sqrt{N}$ steps to reach the solution.

Remember a classical algorithm would take $N$ steps, so we've found a significant improvement!