Grover Search

Grover's algorithm is a quantum algorithm for unstructured search. Given a way to check whether a candidate is a solution, it increases the probability of measuring a matching candidate through repeated phase flips and reflections.

For a search space of $N$ candidates with one marked solution, Grover search uses $O(\sqrt{N})$ oracle queries to find it with high probability, compared with $O(N)$ queries for classical unstructured search. This is a quadratic query speedup. The cost of implementing the oracle and accessing data still matters when considering a practical application.

What you will learn

• Describe an unstructured search problem using a phase oracle.
• Build the Grover iterator from the oracle and diffusion operator.
• Use geometric reflections to understand amplitude amplification.
• Explain why the number of oracle queries scales with the square root of the search space.

Prerequisites

Review bra-ket notation and outer products, the Hadamard gate in Single Qubit Gates, and tensor products in Multiple Qubits. The Deutsch-Jozsa algorithm provides a useful introduction to quantum oracle algorithms.

The unstructured search problem

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

Marking the solution with a phase oracle

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 multiplying the marked state's amplitude by $e^{i\pi} = -1$. In a superposition, this changes its phase relative to the unmarked states.

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.

The steps of Grover's algorithm

For the circuit below, assume $N = 2^n$ with $n \geq 1$. If the original number of candidates is not a power of two, pad the search space with non-matching candidates to the next power of two; $N$ then refers to this padded size.

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=\log_2{N}$ 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.

The Grover iterator and diffusion operator

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:

How reflections amplify the solution

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.

A two-dimensional picture of the search

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 = \log_2{N}$ qubits and thus $N$ different basis states. With 1024 candidates, for example, we have a 1024-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: orthogonal vectors have inner product 0, and each of our normalised basis vectors has inner product 1 with itself.

For $N > 2$, these results show 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?

How many Grover iterations are needed?

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?

In this two-dimensional subspace with real coefficients, 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{\theta} \approx \theta$ so:

The starting state is already at an angle of $\theta$ from $\ket{s^\prime}$. Every application of the Grover iterator adds $2\theta$, so after $r$ iterations the angle is $(2r+1)\theta$.

The solution direction is at an angle of $\pi/2$. Solving for the ideal number of iterations gives $r = \frac{\pi}{4\theta} - \frac{1}{2}$. We choose the nearest non-negative integer, since we can only apply a whole number of Grover iterations.

Subbing now in our approximation of $\theta$:

After $r$ iterations, the success probability is $\sin^2((2r+1)\theta)$. Continuing too far past the solution direction decreases this probability again.

The quadratic query speedup

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

We've shown that we require only $\sim \sqrt{N}$ Grover iterations, each using one query to the solution oracle, to obtain a high probability of measuring the solution.

Classical unstructured search requires a number of queries proportional to $N$ in general. The improvement is quadratic, as also explained in IBM Quantum Learning's introduction to Grover's algorithm.

Related lessons

• Deutsch-Jozsa: compare another quantum algorithm that uses an oracle.
• Quantum Fourier Transform: explore another building block for quantum algorithms.