Learning Home Catalog Composer
Learning
Home Catalog Composer Return to course
Learning
Fundamentals of Quantum Algorithms
Quantum query algorithms Quantum algorithmic foundations Phase-estimation and factoring Grover's algorithm

Grover's algorithm

Download the slides for this lesson.

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.

Summary

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

Suppose that

f:ΣnΣf:\Sigma^n \rightarrow \Sigma

is a function from binary strings of length nn 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Σnx\in\Sigma^n for which f(x)=1.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 ff 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,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Σn,x\in\Sigma^n, evaluating ff on each one to check whether or not it is a solution. Hereafter, let's write

N=2nN = 2^n

just for the sake of convenience, so we can say that there are NN strings in Σn.\Sigma^n. Iterating through all of them requires NN evaluations of f.f. Operating under the assumption that we're limited to evaluating ff 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,f, but we'll still require O(N)O(N) evaluations of ff 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(N)O(\sqrt{N}) evaluations of f.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 ff 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(N)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:ΣnΣf:\Sigma^n\rightarrow\Sigma through a query gate defined in the usual way, which is as

Uf(ax)=af(x)xU_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle

for every xΣnx\in\Sigma^n and aΣ.a\in\Sigma. This is the action of UfU_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,f, we can transform that Boolean circuit description into a quantum circuit implementing UfU_f (using some number of workspace qubits that start and end the computation in the 0\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 ff 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 xx that causes ff to evaluate to 1.1.

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

Notice that this is not a promise problem — the function ff 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:ΣnΣf:\Sigma^n \rightarrow \Sigma
Promise: there is exactly one string zΣnz\in\Sigma^n for which f(z)=1,f(z) = 1, with f(x)=0f(x) = 0 for all strings xzx\neq z
Output: the string zz

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 Uf,U_f, defined for a given function ff in the usual way described above, a phase query gate for the function ff is defined as

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

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

The operation ZfZ_f can be implemented using one query gate UfU_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 ZfZ_f gates, for instance) or simply discarded.

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

OR(x)={0x=0n1x0n\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 nn-bit OR function operates like this:

ZORx={xx=0nxx0n.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 ZORZ_{\mathrm{OR}} operates on standard basis states; its behavior on arbitrary states is determined from this expression by linearity.

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

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

Description of the algorithm

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

The algorithm refers to a number t,t, which is the number of iterations it performs, as well as the number of queries to the function ff it requires. This number tt 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

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

The operation G=HnZORHnZfG = 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 ZfZ_f operation is depicted as being larger than ZORZ_{\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 ZfZ_f requires one query while ZORZ_{\mathrm{OR}} requires no queries — and if instead we have a Boolean circuit for the function ff and convert it to a quantum circuit for Zf,Z_f, we can reasonably expect that the resulting quantum circuit will be larger and more complicated than one for ZOR.Z_{\mathrm{OR}}.

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

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

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

  • Choose the number tt in step 2. The section following this one discusses how we can choose t.t.
  • Run Grover's algorithm on the function f,f, using whatever choice we made for t,t, to obtain a string xΣn.x\in\Sigma^n.
  • Query the function ff on the string xx to see if it's a valid solution:
    • If f(x)=1,f(x) = 1, then we have found a solution, so we can stop and output x.x.
    • Otherwise, if f(x)=0,f(x) = 0, then we can either run the procedure again, possibly with a different choice for t,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(N)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 GG 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.

A0={xΣn:f(x)=0}A1={xΣn:f(x)=1}\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 A1A_1 contains all of the solutions to our search problem, and A0A_0 contains the strings that aren't solutions (which we can refer to as non-solutions when it's convenient). These two sets satisfy A0A1=A_0 \cap A_1 = \varnothing and A0A1=Σn,A_0 \cup A_1 = \Sigma^n, which is to say that this is a bipartition of Σn.\Sigma^n.

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

A0=1A0xA0xA1=1A1xA1x\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 A0A_0 nor A1A_1 is empty. The cases that A0=A_0 = \varnothing and A1=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,S, we can write S\vert S\rangle to denote the quantum state vector that's uniform over the elements of S.S.

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

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

Notice that

u=A0NA0+A1NA1.\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 u=Hn0n,\vert u\rangle = H^{\otimes n} \vert 0^n \rangle, so u\vert u\rangle represents the state of the register Q\mathsf{Q} after the initialization in step 1 of Grover's algorithm. This implies that just before the iterations of GG happen in step 2, the state of Q\mathsf{Q} is contained in the two-dimensional vector space spanned by A0\vert A_0\rangle and A1,\vert A_1\rangle, and moreover the coefficients of these vectors are real numbers.

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

An observation about the Grover operation

We'll now turn our attention to the Grover operation

G=HnZORHnZf,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 ff by the composition of ff with the NOT function — or in other words the function we get by flipping the output bit of f.f. We'll call this new function g,g, and we can express it using symbols in a few alternative ways.

g(x)=¬f(x)=1f(x)=1f(x)={1f(x)=00f(x)=1g(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

Zf=Zg.Z_f = - Z_g.

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

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

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

So, Grover's algorithm behaves in exactly the same for gg as it does for f.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 GG on the vectors A0\vert A_0\rangle and A1.\vert A_1\rangle.

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

ZfA0=A0ZfA1=A1\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 HnZORHn.H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}. The operation ZORZ_{\mathrm{OR}} is defined as

ZORx={xx=0nxx0n,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Σn,x\in\Sigma^n, and a convenient alternative way to express this operation is like this:

ZOR=20n0nI.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 ZORZ_{\mathrm{OR}} is to evaluate its action on standard basis states.) The operation HnZORHnH^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} can therefore be written like this:

HnZORHn=2Hn0n0nHnI.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 u\vert u \rangle that we used above for the uniform superposition over all nn-bit strings, we can alternatively express HnZORHnH^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} like this:

HnZORHn=2uuI.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 GG on A0\vert A_0\rangle and A1.\vert A_1\rangle. First we compute the action of GG on A0.\vert A_0\rangle.

GA0=(2uuI)ZfA0=(2uuI)A0=2A0NuA0=2A0N(A0NA0+A1NA1)A0=(12A0N)A0+2A0A1NA1=A0A1NA0+2A0A1NA1\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 GG on A1.\vert A_1\rangle.

GA1=(2uuI)ZfA1=(2uuI)A1=2A1Nu+A1=2A1N(A0NA0+A1NA1)+A1=2A1A0NA0+(12A1N)A1=2A1A0NA0+A0A1NA1\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

u=A0NA0+A1NA1\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

uA0=A0NanduA1=A1N\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

GA0=A0A1NA0+2A0A1NA1GA1=2A1A0NA0+A0A1NA1.\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 Q\mathsf{Q} just prior to step 2 is contained in the two-dimensional space spanned by A0\vert A_0\rangle and A1,\vert A_1\rangle, and we have just established that GG 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 GG on this space as a matrix,

M=(A0A1N2A1A0N2A0A1NA0A1N),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 A0\vert A_0\rangle and A1,\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 MM is what we obtain by squaring a simpler-looking matrix.

(A0NA1NA1NA0N)2=(A0A1N2A1A0N2A0A1NA0A1N)=M\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