Grover's algorithm

Introduction

In this lesson we'll discuss Grover's algorithm, which is a quantum algorithm for so-called unstructured search problems that offers a quadratic improvement over classical algorithms. What this means is that Grover's algorithm requires a number of operations on the order of the square-root of the number of operations required to solve unstructured search classically — which is equivalent to saying that classical algorithms for unstructured search must have a cost at least on the order of the square of the cost of Grover's algorithm. Grover's algorithm, together with its extensions and underlying methodology, turn out to be broadly applicable, leading to a quadratic advantage for many interesting computational tasks that may not initially look like unstructured search problems on the surface.

While the broad applicability of Grover's searching technique is compelling, it should be acknowledged here at the start of the lesson that the quadratic advantage it offers seems unlikely to lead to a practical advantage of quantum over classical computing any time soon. Classical computing hardware is currently so much more advanced than quantum computing hardware that the quadratic quantum-over-classical advantage offered by Grover's algorithm is certain to be washed away by the staggering clock speeds of modern classical computers for any unstructured search problem that could feasibly be run on the quantum computers of today.

As quantum computing technology advances, however, Grover's algorithm does have potential. Indeed, some of the most important and impactful classical algorithms ever discovered, including the fast Fourier transform and fast sorting (e.g., quicksort and mergesort), offer slightly less than a quadratic advantage over naive approaches to the problems they solve. The key difference here, of course, is that an entirely new technology (meaning quantum computing) is required to run Grover's algorithm. While this technology is still very much in its infancy in comparison to classical computing, we should not be so quick to underestimate the potential of technological advances that could allow a quadratic advantage of quantum over classical computing to one day offer tangible practical benefits.

Unstructured search

Summary

We'll begin with a description of the problem that Grover's algorithm solves. As usual, we'll let $\Sigma = \{0,1\}$ denote the binary alphabet throughout this discussion.

Suppose that

f:\Sigma^n \rightarrow \Sigma

is a function from binary strings of length $n$ to bits. We'll assume that we can compute this function efficiently, but otherwise it's arbitrary and we can't rely on it having a special structure or specific implementation that suits our needs.

What Grover's algorithm does is to search for a string $x\in\Sigma^n$ for which $f(x) = 1.$ We'll refer to strings like this as solutions to the searching problem. If there are multiple solutions, then any one of them is considered to be a correct output, and if there are no solutions, then a correct answer requires that we report that there are no solutions.

We describe this task as an unstructured search problem because we can't rely on $f$ having any particular structure to make it easy. We're not searching an ordered list or within some data structure specifically designed to facilitate searching, we're essentially looking for a needle in a haystack. From an intuitive point of view, we might imagine that we have an extremely complicated Boolean circuit that computes $f,$ and we can easily run this circuit on a selected input string if we choose — but because it's so convoluted, we have no hope of making sense of the circuit by examining it (beyond having the ability to evaluate it on selected input strings).

One way to perform this searching task classically is to simply iterate through all of the strings $x\in\Sigma^n,$ evaluating $f$ on each one to check whether or not it is a solution. Hereafter, let's write

N = 2^n

just for the sake of convenience, so we can say that there are $N$ strings in $\Sigma^n.$ Iterating through all of them requires $N$ evaluations of $f.$ Operating under the assumption that we're limited to evaluating $f$ on chosen inputs, this is the best we can do with a deterministic algorithm if we want to guarantee success. With a probabilistic algorithm, we might hope to save time by randomly choosing input strings to $f,$ but we'll still require $O(N)$ evaluations of $f$ in we want this method to succeed with high probability.

Grover's algorithm solves the unstructured search problem described above with high probability, and required just $O(\sqrt{N})$ evaluations of $f.$ To be clear, these function evaluations must happen in superposition, similar to the query algorithms discussed in Lesson 5 (including Deutsch's algorithm, the Deutsch-Jozsa algorithm, and Simon's algorithm). Grover's algorithm takes an iterative approach: it evaluates $f$ on superpositions of input strings and intersperses these evaluations with other operations that have the effect of creating interference patterns, leading to a solution with high probability (if one exists) after $O(\sqrt{N})$ iterations.

Formal problem statement

We'll formalize the problem that Grover's algorithm solves using the query model of computation. That is, we will assume that we have access to the function $f:\Sigma^n\rightarrow\Sigma$ through a query gate defined in the usual way, which is as

U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle

for every $x\in\Sigma^n$ and $a\in\Sigma.$ This is the action of $U_f$ on standard basis states, and its action in general is determined by linearity.

As discussed in Lesson 6, if we have a Boolean circuit for computing $f,$ we can transform that Boolean circuit description into a quantum circuit implementing $U_f$ (using some number of workspace qubits that start and end the computation in the $\vert 0\rangle$ state). So, while we're using the query model to formalize the problem that Grover's algorithm solves, it is not limited to this model: we can run Grover's algorithm on any function $f$ for which we have a Boolean circuit.

Here's a precise statement of the problem, which is called Search because we're searching for a solution, meaning a string $x$ that causes $f$ to evaluate to $1.$

Search
Input: a function $f:\Sigma^n\rightarrow\Sigma$
Output: a string $x\in\Sigma^n$ satisfying $f(x) = 1,$ or "no solution" if no such string $x$ exists

Notice that this is not a promise problem — the function $f$ is arbitrary. It will, however, be helpful to consider the following promise variant of the problem, where we're guaranteed that there's exactly one solution. This problem appeared as an example of a promise problem in Lesson 5.

Unique search
Input: a function of the form $f:\Sigma^n \rightarrow \Sigma$
Promise: there is exactly one string $z\in\Sigma^n$ for which $f(z) = 1,$ with $f(x) = 0$ for all strings $x\neq z$
Output: the string $z$

Also notice that the Or problem mentioned in Lesson 5 is closely related to Search. For this problem, the goal is simply to determine whether or not a solution exists, as opposed to actually finding a solution.

Grover's algorithm

Next we will describe Grover's algorithm itself.

Phase query gates

Grover's algorithm makes use of operations known as phase query gates. In contrast to an ordinary query gate $U_f,$ defined for a given function $f$ in the usual way described above, a phase query gate for the function $f$ is defined as

Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle

for every string $x\in\Sigma^n.$

The operation $Z_f$ can be implemented using one query gate $U_f$ as this diagram suggests:

A quantum circuit implementing a Z_f gate using one query gate together with the phase kickback phenomenon

This implementation makes use of the phase kickback phenomenon, and requires that one workspace qubit, initialized to a $\vert -\rangle$ state, is made available. This qubit remains in the $\vert - \rangle$ state after the implementation has completed, and can be reused (to implement subsequent $Z_f$ gates, for instance) or simply discarded.

In addition to the operation $Z_f,$ we will also make use of a phase query gate for the $n$ -bit OR function, which is defined as follows for each string $x\in\Sigma^n.$

\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}

Explicitly, the phase query gate for the $n$ -bit OR function operates like this:

Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[0.5mm] - \vert x\rangle & x \neq 0^n. \end{cases}

To be clear, this is how $Z_{\mathrm{OR}}$ operates on standard basis states; its behavior on arbitrary states is determined from this expression by linearity.

The operation $Z_{\mathrm{OR}}$ can be implemented as a quantum circuit by beginning with a Boolean circuit for the OR function, then constructing a $U_{\mathrm{OR}}$ operation (i.e., a standard query gate for the $n$ -bit OR function) using the procedure described in Lesson 6, and finally a $Z_{\mathrm{OR}}$ operation using the phase kickback phenomenon as described above.

Notice that the operation $Z_{\mathrm{OR}}$ has no dependence on the function $f$ and can therefore be implemented by a quantum circuit having no query gates.

Description of the algorithm

Now that we have the two operations $Z_f$ and $Z_{\mathrm{OR}},$ we can describe Grover's algorithm.

The algorithm refers to a number $t,$ which is the number of iterations it performs, as well as the number of queries to the function $f$ it requires. This number $t$ isn't specified by Grover's algorithm (as we're describing it), and we'll discuss in the section following this one how it can be chosen.

Grover's algorithm
Initialize an $n$ qubit register $\mathsf{Q}$ to the all-zero state $\vert 0^n \rangle$ and then apply a Hadamard operation to each qubit of $\mathsf{Q}.$
Apply $t$ times the unitary operation $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ to the register $\mathsf{Q}$
Measure the qubits of $\mathsf{Q}$ with respect to standard basis measurements and output the resulting string.

The operation $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ iterated in step 2 will be called the Grover operation throughout the remainder of this lesson. Here is a quantum circuit representation of the Grover operation:

A quantum circuit representation of the Grover operation

Here the $Z_f$ operation is depicted as being larger than $Z_{\mathrm{OR}}$ as a way to suggest that it is likely to be the more costly operation (but this is only meant a visual clue and not something with a formal meaning). In particular, when we're working within the query model $Z_f$ requires one query while $Z_{\mathrm{OR}}$ requires no queries — and if instead we have a Boolean circuit for the function $f$ and convert it to a quantum circuit for $Z_f,$ we can reasonably expect that the resulting quantum circuit will be larger and more complicated than one for $Z_{\mathrm{OR}}.$

Here's a description of a quantum circuit for the entire algorithm when $t=2.$ For larger values of $t$ we may simply insert additional instances of the Grover operation immediately before the measurements.

A quantum circuit for Grover's algorithm when t=2

Application to Search

Grover's algorithm can be applied to the Search problem described in the previous section as follows:

Choose the number $t$ in step 2. The section following this one discusses how we can choose $t.$
Run Grover's algorithm on the function $f,$ using whatever choice we made for $t,$ to obtain a string $x\in\Sigma^n.$
Query the function $f$ $f$ on the string $x$ $x$ to see if it's a valid solution:
- If $f(x) = 1,$ then we have found a solution, so we can stop and output $x.$
- Otherwise, if $f(x) = 0,$ then we can either run the procedure again, possibly with a different choice for $t,$ or we can decide to give up and output "no solution."

A bit later, once we've analyzed how Grover's algorithm works, we'll see that by taking $t = O(\sqrt{N})$ we'll obtain a solution to our search problem (if one exists) with high probability.

Analysis

Now we'll analyze Grover's algorithm to understand how it works. We'll start with what could be described as a symbolic analysis, where we calculate how the Grover operation $G$ acts on certain states, and then we'll then tie this symbolic analysis to a geometric picture that's helpful for visualizing how the algorithm works.

Solutions and non-solutions

Let's start by defining two sets of strings.

\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}

The set $A_1$ contains all of the solutions to our search problem, and $A_0$ contains the strings that aren't solutions (which we can refer to as non-solutions when it's convenient). These two sets satisfy $A_0 \cap A_1 = \varnothing$ and $A_0 \cup A_1 = \Sigma^n,$ which is to say that this is a bipartition of $\Sigma^n.$

Next we'll define two unit vectors representing uniform superpositions over the sets of solutions and non-solutions.

\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}

Formally speaking, each of these vectors is only defined when its corresponding set is nonempty, but hereafter we're going to focus on the case that neither $A_0$ nor $A_1$ is empty. The cases that $A_0 = \varnothing$ and $A_1 = \varnothing$ are easily handled separately, and we'll do that later.

As an aside, this notation is pretty common: any time we have a nonempty set $S,$ we can write $\vert S\rangle$ to denote the quantum state vector that's uniform over the elements of $S.$

Let us also define $\vert u \rangle$ to be a uniform quantum state over all $n$ -bit strings:

\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.

Notice that

\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.

We also have that $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle,$ so $\vert u\rangle$ represents the state of the register $\mathsf{Q}$ after the initialization in step 1 of Grover's algorithm. This implies that just before the iterations of $G$ happen in step 2, the state of $\mathsf{Q}$ is contained in the two-dimensional vector space spanned by $\vert A_0\rangle$ and $\vert A_1\rangle,$ and moreover the coefficients of these vectors are real numbers.

As we will see, the state of $\mathsf{Q}$ will always have these properties — meaning that the state is a real linear combination of $\vert A_0\rangle$ and $\vert A_1\rangle$ — after any number of iterations of the operation $G$ in step 2.

An observation about the Grover operation

We'll now turn our attention to the Grover operation

G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,

beginning with an interesting observation about it.

Imagine for a moment that we replaced the function $f$ by the composition of $f$ with the NOT function — or in other words the function we get by flipping the output bit of $f.$ We'll call this new function $g,$ and we can express it using symbols in a few alternative ways.

g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}

Now, notice that

Z_f = - Z_g.

Recalling that $Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$ for every string $x\in\Sigma^n,$ we can verify this by observing that

(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}

for every string $x\in\Sigma^n.$

So, Grover's algorithm behaves in exactly the same for $g$ as it does for $f.$ Intuitively speaking, the algorithm doesn't really care which strings are solutions — it only needs to be able to distinguish solutions and non-solutions to operate as it does.

Action of the Grover operation

Now let's consider the action of $G$ on the vectors $\vert A_0\rangle$ and $\vert A_1\rangle.$

First let's observe that the operation $Z_f$ has a very simple action on the vectors $\vert A_0\rangle$ and $\vert A_1\rangle.$

\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}

Second we have the operation $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ The operation $Z_{\mathrm{OR}}$ is defined as

Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[2mm] -\vert x\rangle & x \neq 0^n, \end{cases}

again for every string $x\in\Sigma^n,$ and a convenient alternative way to express this operation is like this:

Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.

(A simple way to verify that this expression agrees with the definition of $Z_{\mathrm{OR}}$ is to evaluate its action on standard basis states.) The operation $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ can therefore be written like this:

H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I}.

Using the same notation $\vert u \rangle$ that we used above for the uniform superposition over all $n$ -bit strings, we can alternatively express $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ like this:

H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.

And now we have what we need to compute the action of $G$ on $\vert A_0\rangle$ and $\vert A_1\rangle.$ First we compute the action of $G$ on $\vert A_0\rangle.$

\begin{aligned} G \vert A_0 \rangle & = \bigr( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigr( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = - \biggl( 1 - \frac{2\vert A_0\vert}{N} \biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}

And second, the action of $G$ on $\vert A_1\rangle.$

\begin{aligned} G \vert A_1 \rangle & = \bigr( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigr( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}

In both cases we're using the equation

\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle

along with the expressions

\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{and}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}

that follow.

In summary, we have

\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}

As we already noted, the state of $\mathsf{Q}$ just prior to step 2 is contained in the two-dimensional space spanned by $\vert A_0\rangle$ and $\vert A_1\rangle,$ and we have just established that $G$ maps any vector in this space to another vector in the same space. This means that, for the sake of the analysis, we can focus our attention exclusively on this subspace.

To better understand what's happening within this two-dimensional space, let's express the action of $G$ on this space as a matrix,

M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},

whose first and second rows/columns correspond to $\vert A_0\rangle$ and $\vert A_1\rangle,$ respectively. (So far in this series we've always connected the rows and columns of matrices with the classical states of a system, but matrices can also be used to describe the actions of linear mappings on different bases like we have here.)

While it isn't at all obvious at first glance, the matrix $M$ is what we obtain by squaring a simpler-looking matrix.

\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M

The matrix

(\begin{array}{cc} \sqrt{\frac{∣ A_{0} ∣}{N}} & - \sqrt{\frac{∣ A_{1} ∣}{N}} \\ \sqrt{\frac{∣ A_{1} ∣}{N}} & \sqrt{\frac{∣ A_{0} ∣}{N}} \end{array}