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.
Unstructured search
Summary
We'll begin with a description of the problem that Grover's algorithm solves. As usual, we'll let denote the binary alphabet throughout this discussion.
Suppose that
is a function from binary strings of length 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 for which 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 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 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 evaluating on each one to check whether or not it is a solution. Hereafter, let's write
just for the sake of convenience, so we can say that there are strings in Iterating through all of them requires evaluations of Operating under the assumption that we're limited to evaluating 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 but we'll still require evaluations of 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 evaluations of 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 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 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 through a query gate defined in the usual way, which is as
for every and This is the action of 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 we can transform that Boolean circuit description into a quantum circuit implementing (using some number of workspace qubits that start and end the computation in the 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 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 that causes to evaluate to
Search
Input: a function
Output: a string satisfying or "no solution" if no such string exists
Notice that this is not a promise problem — the function 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
Promise: there is exactly one string for which with for all strings
Output: the string
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 defined for a given function in the usual way described above, a phase query gate for the function is defined as
for every string
The operation can be implemented using one query gate as this diagram suggests:
This implementation makes use of the phase kickback phenomenon, and requires that one workspace qubit, initialized to a state, is made available. This qubit remains in the state after the implementation has completed, and can be reused (to implement subsequent gates, for instance) or simply discarded.
In addition to the operation we will also make use of a phase query gate for the -bit OR function, which is defined as follows for each string
Explicitly, the phase query gate for the -bit OR function operates like this:
To be clear, this is how operates on standard basis states; its behavior on arbitrary states is determined from this expression by linearity.
The operation can be implemented as a quantum circuit by beginning with a Boolean circuit for the OR function, then constructing a operation (i.e., a standard query gate for the -bit OR function) using the procedure described in Lesson 6, and finally a operation using the phase kickback phenomenon as described above.
Notice that the operation has no dependence on the function and can therefore be implemented by a quantum circuit having no query gates.
Description of the algorithm
Now that we have the two operations and we can describe Grover's algorithm.
The algorithm refers to a number which is the number of iterations it performs, as well as the number of queries to the function it requires. This number 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 qubit register to the all-zero state and then apply a Hadamard operation to each qubit of
- Apply times the unitary operation to the register
- Measure the qubits of with respect to standard basis measurements and output the resulting string.
The operation 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:
Here the operation is depicted as being larger than 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 requires one query while requires no queries — and if instead we have a Boolean circuit for the function and convert it to a quantum circuit for we can reasonably expect that the resulting quantum circuit will be larger and more complicated than one for
Here's a description of a quantum circuit for the entire algorithm when For larger values of we may simply insert additional instances of the Grover operation immediately before the measurements.
Application to Search
Grover's algorithm can be applied to the Search problem described in the previous section as follows:
- Choose the number in step 2. The section following this one discusses how we can choose
- Run Grover's algorithm on the function using whatever choice we made for to obtain a string
- Query the function on the string to see if it's a valid solution:
- If then we have found a solution, so we can stop and output
- Otherwise, if then we can either run the procedure again, possibly with a different choice for 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 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 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.
The set contains all of the solutions to our search problem, and contains the strings that aren't solutions (which we can refer to as non-solutions when it's convenient). These two sets satisfy and which is to say that this is a bipartition of
Next we'll define two unit vectors representing uniform superpositions over the sets of solutions and non-solutions.
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 nor is empty. The cases that and 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 we can write to denote the quantum state vector that's uniform over the elements of
Let us also define to be a uniform quantum state over all -bit strings:
Notice that
We also have that so represents the state of the register after the initialization in step 1 of Grover's algorithm. This implies that just before the iterations of happen in step 2, the state of is contained in the two-dimensional vector space spanned by and and moreover the coefficients of these vectors are real numbers.
As we will see, the state of will always have these properties — meaning that the state is a real linear combination of and — after any number of iterations of the operation in step 2.
An observation about the Grover operation
We'll now turn our attention to the Grover operation
beginning with an interesting observation about it.
Imagine for a moment that we replaced the function by the composition of with the NOT function — or in other words the function we get by flipping the output bit of We'll call this new function and we can express it using symbols in a few alternative ways.
Now, notice that
Recalling that for every string we can verify this by observing that
for every string
So, Grover's algorithm behaves in exactly the same for as it does for 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 on the vectors and
First let's observe that the operation has a very simple action on the vectors and
Second we have the operation The operation is defined as
again for every string and a convenient alternative way to express this operation is like this:
(A simple way to verify that this expression agrees with the definition of is to evaluate its action on standard basis states.) The operation can therefore be written like this:
Using the same notation that we used above for the uniform superposition over all -bit strings, we can alternatively express like this:
And now we have what we need to compute the action of on and First we compute the action of on
And second, the action of on
In both cases we're using the equation
along with the expressions
that follow.
In summary, we have
As we already noted, the state of just prior to step 2 is contained in the two-dimensional space spanned by and and we have just established that 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 on this space as a matrix,
whose first and second rows/columns correspond to and 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 is what we obtain by squaring a simpler-looking matrix.
The matrix