Quantum query algorithms
Download the slides for this lesson.
Introduction
This course investigates computational advantages offered by quantum information. That is, we will think about what we can do with quantum computers, and the advantages they can offer over ordinary classical computers. To be specific, our focus will be on what we can do with a single quantum computer — as opposed to a distributed setting where multiple quantum computers interact over a network, for instance. (There are, in fact, quantum advantages to be found in distributed settings, where communication and cryptography come into play, but this topic is outside of the scope of this unit.)
We will begin with a natural question: What are the advantages that a quantum computer might potentially offer?
The first potential advantage, which is paramount among all others, is that quantum computers might provide faster solutions to some computational problems. Time is a truly precious resource — and it is this potential, that quantum computers may allow us to solve certain computational problems that classical computers are too slow to solve, that has driven quantum computing research for the past few decades.
There are other computational resources besides time that can be considered. The amount computer memory required to perform computations — usually referred to as the space required for computations — is one alternative that is often studied. As it turns out, however, quantum computers have a limited potential to offer advantages in space usage over classical computers. Computer memory is also relatively inexpensive and, unlike time, can be reused. For these reasons, time is of greater concern, and will be our primary focus.
One thing that quantum computers cannot do is to provide computational solutions to problems that classical computers cannot solve — irrespective of the resources required — such as the famous halting problem formulated by Alan Turing in the 1930s. Quantum computers can be simulated by classical computers, so any computational problem that can be solved by a quantum computer can also be solved by a classical computer, though it might take the classical computer much, much longer to find a solution.
While the time required to solve problems is our main concern, we will deviate slightly from this focus for the purposes of this first lesson. What we will do is to formulate a simple algorithmic framework — known as the query model — and explore the advantages that quantum computers offer within this framework.
The query model of computation is like a petri dish for quantum algorithmic ideas. It is rigid and unnatural, in the sense that it does not accurately represent the sorts of computational problems we generally care about in practice. Nevertheless, it has proved to be incredibly useful as a tool for developing quantum algorithmic techniques, including ones that power the most well-known quantum algorithms (such as Shor's factoring algorithm). It also happens to be a very useful framework for explaining these techniques.
After introducing the query model, we will discuss the very first quantum algorithm discovered, which is Deutsch's algorithm, along with an extension of Deutsch's algorithm known as the Deutsch-Jozsa algorithm. These algorithms demonstrate quantifiable advantages of quantum over classical computers, and in fact the Deutsch-Jozsa algorithm can be used to solve multiple computational problems in the query model framework. We will then discuss a related quantum algorithm — known as Simon's algorithm — which, for reasons that will be explained, offers a more robust and satisfying advantage of quantum over classical computations.
Pre-course Survey
Before we begin, please take a moment to complete our pre-course survey, which is important to help improve our content offerings and user experience.
The query model of computation
When we model computations in mathematical terms, we typically have in mind the sort of process represented by the following figure, where information is provided as input, a computation takes place, and output is produced.
It is true that the computers we use today continuously receive input and produce output, essentially interacting with both us and with other computers in a way not reflected by the figure. Here, however, the intention is not to represent the ongoing operation of computers, but rather to create a simple abstraction of computation, focusing on isolated computational tasks.
For example, the input might encode a number, a vector, a matrix, a graph, a description of a molecule, or something more complicated, while the output encodes a solution to the computational task we have in mind. The key point is that the input is provided to the computation, usually in the form of a binary string, with no part of it being hidden.
High-level description
In the query model of computation, on the other hand, the entire input is not provided to the computation. Rather, the input is made available in the form of a function, which the computation accesses by making queries. Alternatively, we may view that computations in the query model have to bits (or segments of bits) of the input.
We often refer to the input as being provided by an oracle or black box in the context of the query model. Both terms suggest that a complete description of the input is hidden from the computation, with the only way to access it being to ask questions. It is as if we're consulting the Oracle at Delphi about the input: she won't tell us everything she knows, she only answers specific questions. The term black box makes sense especially when we think about the input as being represented by a function: we cannot look inside the function and understand how it works, we can only evaluate it on arguments we select.
We're going to be working exclusively with binary strings throughout the lesson, so let's write to refer to the binary alphabet throughout for the sake of brevity. We'll be thinking about different computational problems, with some simple examples described shortly, but for all of them the input will be represented by a function taking the form
for two positive integers and Naturally, we could choose a different name in place of but we'll stick with throughout the lesson.
To say that a computation makes a query means that some string is selected and then the string is made available. The precise way that this works for quantum algorithms will be discussed shortly — we need to make sure that this is possible to do with a unitary quantum operation allowing queries to be made in superposition — but for now we can think about it intuitively at a high level.
Finally, the way that we will measure efficiency of query algorithms is simple: we'll count the number of queries to the input they require. This is related to the time required to perform a computation, but it's not exactly the same because we're ignoring the time required for operations other than the queries, and we're treating the queries as if they each have unit cost. (We can also take the operations besides the queries into account, and that is sometimes done — but restricting our attention just to the number of queries helps to keep things simple.)
Examples of query problems
Here are a few simple examples of query problems.
OR. The input function takes the form (so for this problem). The task is to output if there exists a string for which and to output if there is no such string. If we think about the function as representing a sequence of bits to which we have random access, the problem is to compute the OR of these bits.
Parity. The input function again takes the form The task is to determine whether the number of strings for which is even or odd. To be precise, the required output is if the set has an even number of elements and if it has an odd number of elements. If we think about the function as representing a sequence of bits to which we have random access, the problem is to compute the parity (or XOR) of these bits.
Minimum. The input function takes the form for any choices of positive integers and The required output is the string that comes first in the lexicographic (i.e., dictionary) ordering of If we think about the function as representing a sequence of integers encoded as strings of length in binary notation to which we have random access, the problem is to compute the minimum of these integers.
Sometimes we also consider query problems where we have a promise on the input. What this means is that we're given some sort of guarantee on the input, and we're not responsible for what happens when this guarantee is not met. Another way to describe this type of problem is that some input functions (the ones for which the promise is not satisfied) are considered as "don't care" inputs. No requirements at all are placed on algorithms when they're given "don't care" inputs.
Here's one example of a problem with a promise:
- Unique search. The input function takes the form and we are promised that there is exactly one string for which with for all strings The task is to find this unique string
All four of the examples just described are natural in the sense that they're easy to describe and we can imagine a variety of situations or contexts in which they might arise — but some query problems of interest aren't like this at all. In the study of the query model we sometimes come up with very complicated and highly contrived problems where it's difficult to imagine that anyone would ever actually want to solve them in practice. This doesn't mean the problems aren't interesting, it's just part of the study of the model to look for extremes that reveal potential advantages of quantum computing. Sometimes things that seems contrived or unnatural can provide unexpected clues or inspire new ideas. Shor's quantum algorithm for factoring, which was directly inspired by Simon's algorithm, is a great example.
Query gates
When we're working with circuit models of computation, queries are made by special gates called query gates. The simplest way to do this for classical Boolean circuits is to define query gates that compute the input function directly, as the following figure suggests.
When we create a Boolean circuit for a query problem, the input function is accessed through these gates, and the number of queries that the circuit makes is simply the number of query gates that appear in the circuit. In this case the wires of the circuit are initialized to fixed values, which should be considered as part of the algorithm rather than as part of the input.
For example, here is a Boolean circuit with classical query gates that solves the parity problem described above for a function of the form :
This algorithm makes two queries because there are two query gates. The way it works is that the function is queried on the two possible inputs, and and the results are plugged into the Boolean circuit from Lesson 3 that computes the XOR.
For quantum circuits, this definition of query gates doesn't work very well because we'll get non-unitary gates for some functions and we won't be able to apply them to quantum states. What we do instead is to define unitary query gates that operate as this figure suggests on standard basis states:
Here our assumption is that and are arbitrary strings. The notation refers to the bitwise exclusive OR of strings (which have length in this case). For example,
Intuitively speaking, what the gate does (for any chosen function ) is to echo the top input string and XOR the function value onto the bottom input string This is a unitary operation for every function To be more precise, as a matrix is always a permutation matrix, meaning a matrix with a single in each row and each column, with all other entries being Applying a permutation matrix to a vector simply shuffles the entries of the vector (hence the term permutation matrix), and therefore does not change that vector's Euclidean norm — revealing that permutation matrices are always unitary.
Notice that when we analyze query algorithms by simply counting the number of queries that a query algorithm makes, we're completely ignoring the difficulty of physically constructing the query gates (for both the classical and quantum versions just described). That might seem unreasonable — but we must keep in mind that we're not trying to describe practical computing or fully account for the resources required. Rather, we're just defining a theoretical model that helps to shed light on the potential advantages of quantum computing. We will have more to say about this point in the lesson following this one when we turn our attention to a more standard model of computation where inputs are given explicitly to circuits as binary strings.
Deutsch's algorithm
Deutsch's algorithm solves the parity problem (described above) for the special case that In the context of quantum computing this problem is sometimes referred to as Deutsch's problem, and we will follow that nomenclature in this lesson — but really it's just the simplest possible nontrivial version of the parity problem.
To be precise, the input is represented by a function from one bit to one bit. As we observed in Lesson 1, there are 4 such functions:
The first and last of these functions are constant and the middle two are balanced, meaning that the two possible output values for the function occur the same number of times as we range over the inputs. Deutsch's problem is to determine which of these two categories the input function belongs to: constant or balanced.
Deutsch's problem
Input: a function
Output: if is constant, if is balanced
If we view the input function in Deutsch's problem as representing random access to a string, we're thinking about a two-bit string:
When viewed in this way, Deutsch's problem is to compute the parity (or, equivalently, the exclusive-OR) of the two bits.
Any classical query algorithm for this problem must query both bits, and If we learn that for instance, the answer could still be (in case ) or (in case ). Every other case is similar: knowing just one of two bits doesn't provide any information at all about their parity. So, the Boolean circuit described in the previous section is the best we can do in terms of the number of queries required to solve this problem.
Quantum circuit description
Deutsch's algorithm solves Deutsch's problem using a single query, therefore providing a quantifiable advantage of quantum over classical computations. This may be a modest advantage — one query as opposed to two — but we have to start somewhere. Scientific advancements often have seemingly humble origins.
Here is a quantum circuit that describes Deutsch's algorithm:
Analysis
To analyze Deutsch's algorithm, we will trace through the action of the circuit above and identify the states of the qubits at the times suggested by this figure:
The initial state is and the two Hadamard operations on the left-hand side of the circuit transform this state to
Notice here that we've only partially expanded out the expression of this state (by expanding but not ). There is nothing a priori that tells us that we should express the state in this way, but it turns out to be convenient for the analysis.
Next, the gate is performed. According to the definition of the gate, the value of the function for the classical state of the top/rightmost qubit is XORed onto the bottom/leftmost qubit, which transforms into the state
We can simplify this expression by observing that the formula
works for both possible values More explicitly, the two cases are as follows.
Thus, we can alternatively express like this:
Something interesting has happened here! Although the action of the gate on standard basis states leaves the top/rightmost qubit alone and XORs the function value onto the bottom/leftmost qubit, here we see that the state of the top/rightmost qubit has changed (in general) while the state of the bottom/leftmost qubit remains the same — specifically being in the state before and after the gate is performed. This phenomenon is known as the phase kickback, and we will have more to say about it shortly.
With one final simplification, which is to pull the factor of outside of the sum, we obtain this expression of the state :
Notice that in this expression, we have in the exponent of rather than but we obtain the same value after exponentiating either way. This is because the value for any integer depends only on whether is even or odd.
Applying the final Hadamard gate to the top qubit leaves us with the state
which leads to the correct outcome with probability when the right/topmost qubit is measured.
Further remarks on the phase kickback
Before moving on, let's look at the analysis above from a slightly different angle that sheds some light on the phase kickback phenomenon.
First, notice the following formula works for all choices of bits
This can be verified by checking it for the two possible values and :
Using this formula, we see that
for every choice of bits Because this formula is true for and we see by linearity that
for all qubit state vectors and therefore
The key that makes this work is that In mathematical terms, the vector is an eigenvector of the matrix having eigenvalue (We'll discuss eigenvectors and eigenvalues in greater detail in Lesson 7, where the phase kickback phenomenon is generalized to other unitary operations.)
Keeping in mind that scalars float freely through tensor products, we find an alternative way of reasoning how the operation transforms into in the analysis above:
Implementation
First we'll define a quantum circuit that implements a query gate for one of the four functions or from one bit to one bit described above (and in Lesson 1). As was discussed previously, the implementation of query gates is not really a part of Deutsch's algorithm itself — here we're essentially just showing one way to prepare the input (in the form of a circuit implementation of a query gate).
No output produced
We can see what each circuit looks like using the
Output:
Next we will create the actual quantum circuit for Deutsch's algorithm, substituting the query gate with a quantum circuit implementation given as an argument. Shortly we'll plug in one of the four circuits defined by the function
No output produced
Again we can see what the circuit looks like using the
Output:
Finally, we'll create a function that runs the circuit just defined one time and outputs the appropriate result: "constant" or "balanced."
No output produced
The following code cell runs Deutsch's algorithm on any one of the four functions defined above.
Output:
'balanced'
The Deutsch-Jozsa algorithm
Deutsch's algorithm provides an example of a quantum algorithm for a query problem that outperforms classical algorithms, but the advantage is quite modest: one query versus two. The Deutsch-Josza algorithm extends this advantage, and it can in fact be used to solve a couple of different query problems.
Here is a quantum circuit description of the Deutsch-Jozsa algorithm. (There may also be a classical post-processing step depending on the specific problem being solved.)
Of course, we haven't actually discussed what problems this algorithm solves; that is done in the subsections that follow.
The Deutsch-Jozsa problem
We will begin with the query problem for which the Deutsch-Josza algorithm was originally intended, which is known as the Deutsch-Jozsa problem.
For this problem, the input function takes the form for an arbitrary positive integer Like Deutsch's problem, the task is to output if is constant and if is balanced (which again means that the number of input strings on which the function takes the value is equal to the number of input strings on which the function takes the value ).
Notice that when is larger than there are functions of the form that are neither constant nor balanced. If for instance, the function defined as
falls into neither of these two categories. For the Deutsch-Jozsa problem, we simply don't worry about functions like this — they are considered to be "don't care" inputs. That is, for this problem we have a promise that is either constant or balanced.
Deutsch-Jozsa problem
Input: a function
Promise: is either constant or balanced
Output: if is constant, if is balanced
The Deutsch-Jozsa algorithm, with its single query, solves this problem in the following sense: if every one of the measurement outcomes is then the function is constant; and otherwise, if at least one of the measurement outcomes is then the function is balanced. Another way to say this is that there is a classical post-processing step, which is to compute the OR of the measurement outcomes.
Algorithm analysis
To analyze the performance of the Deutsch-Jozsa algorithm for the Deutsch-Jozsa problem, it's helpful to begin by thinking about the action of a single layer of Hadamard gates.
A Hadamard operation can be expressed as a matrix in the usual way,
but we can also express this operation in terms of its action on standard basis states:
These two equations can be combined into a single formula,
which is true for both choices of
Now suppose that instead of just a single qubit we have qubits, and we perform a Hadamard operation on each. The combined operation on the qubits is described by the tensor product ( times), which we write as for succinctness and clarity. Using the formula from above, followed by expanding and then simplifying, we can express the action of this combined operation on the classical states of qubits like this:
Here, by the way, we're writing binary strings of length as and following the convention for numbering the individual bits used in Qiskit.
This formula provides us with a useful tool for analyzing the quantum circuit above. After the first layer of Hadamard gates is performed, the state of the qubits (including the leftmost/bottom qubit, which is treated separately from the rest) is
When the operation is performed, this state is transformed into
through exactly the same phase kick-back phenomenon that we saw in the analysis of Deutsch's algorithm.
Then the second layer of Hadamard gates is performed, which (by the same formula as above) transforms this state to