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 random access 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 $\Sigma = \{0,1\}$ 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 $n$ and $m.$ Naturally, we could choose a different name in place of $f,$ but we'll stick with $f$ throughout the lesson.

To say that a computation makes a query means that some string $x \in \Sigma^n$ is selected and then the string $f(x)\in\Sigma^m$ 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 $f:\Sigma^n \rightarrow \Sigma$ (so $m=1$ for this problem). The task is to output $1$ if there exists a string $x\in\Sigma^n$ for which $f(x) = 1,$ and to output $0$ if there is no such string. If we think about the function $f$ as representing a sequence of $2^n$ 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 $f:\Sigma^n \rightarrow \Sigma.$ The task is to determine whether the number of strings $x\in\Sigma^n$ for which $f(x) = 1$ is even or odd. To be precise, the required output is $0$ if the set $\{x\in\Sigma^n : f(x) = 1\}$ has an even number of elements and $1$ if it has an odd number of elements. If we think about the function $f$ as representing a sequence of $2^n$ 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 $f:\Sigma^n \rightarrow \Sigma^m$ for any choices of positive integers $n$ and $m.$ The required output is the string $y \in \{f(x) : x\in\Sigma^n\}$ that comes first in the lexicographic (i.e., dictionary) ordering of $\Sigma^m.$ If we think about the function $f$ as representing a sequence of $2^n$ integers encoded as strings of length $m$ 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 $f:\Sigma^n \rightarrow \Sigma,$ and we are promised that there is exactly one string $z\in\Sigma^n$ for which $f(z) = 1,$ with $f(x) = 0$ for all strings $x\neq z.$ The task is to find this unique string $z.$

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 $f$ directly, as the following figure suggests.

When we create a Boolean circuit for a query problem, the input function $f$ 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 $f:\Sigma\rightarrow\Sigma$:

This algorithm makes two queries because there are two query gates. The way it works is that the function $f$ is queried on the two possible inputs, $0$ and $1,$ 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 $f,$ 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 $x\in\Sigma^n$ and $y\in\Sigma^m$ are arbitrary strings. The notation $y\oplus f(x)$ refers to the bitwise exclusive OR of strings (which have length $m$ in this case). For example, $001 \oplus 101 = 100.$

Intuitively speaking, what the gate $U_f$ does (for any chosen function $f$) is to echo the top input string $x$ and XOR the function value $f(x)$ onto the bottom input string $y.$ This is a unitary operation for every function $f.$ To be more precise, as a matrix $U_f$ is always a permutation matrix, meaning a matrix with a single $1$ in each row and each column, with all other entries being $0.$ 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 $n = 1.$ 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 $f:\Sigma \rightarrow \Sigma$ 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 $f:\{0,1\}\rightarrow\{0,1\}$
Output: $0$ if $f$ is constant, $1$ if $f$ is balanced

If we view the input function $f$ in Deutsch's problem as representing random access to a string, we're thinking about a two-bit string: $f(0)f(1).$

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, $f(0)$ and $f(1).$ If we learn that $f(1) = 1,$ for instance, the answer could still be $0$ (in case $f(0) = 1$) or $1$ (in case $f(0) = 0$). 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 $\vert 1\rangle \vert 0 \rangle,$ 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 $\vert + \rangle$ but not $\vert - \rangle$). 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 $U_f$ gate is performed. According to the definition of the $U_f$ gate, the value of the function $f$ for the classical state of the top/rightmost qubit is XORed onto the bottom/leftmost qubit, which transforms $\vert \pi_1\rangle$ into the state

We can simplify this expression by observing that the formula

works for both possible values $a\in\Sigma.$ More explicitly, the two cases are as follows.

Thus, we can alternatively express $\vert\pi_2\rangle$ like this:

Something interesting has happened here! Although the action of the $U_f$ 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 $\vert - \rangle$ state before and after the $U_f$ 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 $(-1)^{f(0)}$ outside of the sum, we obtain this expression of the state $\vert\pi_2\rangle$:

Notice that in this expression, we have $f(0) \oplus f(1)$ in the exponent of $-1$ rather than $f(1) - f(0),$ but we obtain the same value after exponentiating either way. This is because the value $(-1)^k$ for any integer $k$ depends only on whether $k$ 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 $1$ 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 $b,c\in\Sigma.$

This can be verified by checking it for the two possible values $c = 0$ and $c = 1$:

Using this formula, we see that

for every choice of bits $a,b\in\Sigma.$ Because this formula is true for $b=0$ and $b=1,$ we see by linearity that

for all qubit state vectors $\vert \psi\rangle,$ and therefore

The key that makes this work is that $X\vert - \rangle = - \vert - \rangle.$ In mathematical terms, the vector $\vert - \rangle$ is an eigenvector of the matrix $X$ having eigenvalue $-1.$ (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 $U_f$ transforms $\vert \pi_1\rangle$ into $\vert \pi_2\rangle$ in the analysis above:

Implementation

First we'll define a quantum circuit that implements a query gate for one of the four functions $f_1,$ $f_2,$ $f_3,$ or $f_4$ 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).

We can see what each circuit looks like using the draw method.

Copy to clipboard

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 deutsch_function we defined earlier. Barriers are included to show the visual separation between the query gate implementation and the rest of the circuit, but they aren't necessary and can safely be removed.

Again we can see what the circuit looks like using the draw method.

Copy to clipboard

Output:

Finally, we'll create a function that runs the circuit just defined one time and outputs the appropriate result: "constant" or "balanced."

The following code cell runs Deutsch's algorithm on any one of the four functions defined above.

Copy to clipboard

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 $f:\Sigma^n \rightarrow \Sigma$ for an arbitrary positive integer $n.$ Like Deutsch's problem, the task is to output $0$ if $f$ is constant and $1$ if $f$ is balanced (which again means that the number of input strings on which the function takes the value $0$ is equal to the number of input strings on which the function takes the value $1$).

Notice that when $n$ is larger than $1,$ there are functions of the form $f:\Sigma^n \rightarrow \Sigma$ that are neither constant nor balanced. If $n = 2,$ 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 $f$ is either constant or balanced.

Deutsch-Jozsa problem
Input: a function $f:\{0,1\}^n\rightarrow\{0,1\}$
Promise: $f$ is either constant or balanced
Output: $0$ if $f$ is constant, $1$ if $f$ is balanced

The Deutsch-Jozsa algorithm, with its single query, solves this problem in the following sense: if every one of the $n$ measurement outcomes is $0,$ then the function $f$ is constant; and otherwise, if at least one of the measurement outcomes is $1,$ then the function $f$ 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 $a\in\Sigma.$

Now suppose that instead of just a single qubit we have $n$ qubits, and we perform a Hadamard operation on each. The combined operation on the $n$ qubits is described by the tensor product $H\otimes \cdots \otimes H$ ($n$ times), which we write as $H^{\otimes n}$ 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 $n$ qubits like this:

Here, by the way, we're writing binary strings of length $n$ as $x_{n-1}\cdots x_0$ and $y_{n-1}\cdots y_0,$ 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 $n+1$ qubits (including the leftmost/bottom qubit, which is treated separately from the rest) is

When the $U_f$ 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

This state may appear to be a bit complicated, and without knowing more about the function $f$ there is little that can be concluded about the probabilities to obtain different measurement outcomes. But fortunately, all we need to know is the probability that every one of the measurement outcomes is $0,$ because that's the probability that the algorithm concludes that $f$ is constant. This probability is

In greater detail, if $f$ is constant, then either $f(x_{n-1}\cdots x_0) = 0$ for every string $x_{n-1}\cdots x_0,$ in which case the value of the sum is $2^n,$ or $f(x_{n-1}\cdots x_0) = 1$ for every string $x_{n-1}\cdots x_0,$ in which case the value of the sum is $-2^n.$ Dividing by $2^n$ and taking the square of the absolute value yields $1.$ If, on the other hand, $f$ is balanced, then $f$ takes the value $0$ on half of the strings $x_{n-1}\cdots x_0$ and the value $1$ on the other half, so the $+1$ terms and $-1$ terms in the sum cancel and we're left with the value $0.$

So, we conclude that the algorithm operates correctly in the two cases that $f$ is constant and $f$ is balanced. (If $f$ is neither constant nor balanced, then all bets are off and we can't say too much — although there will always be a nonzero probability to obtain the outcome $1$ for at least one of the measurements when $f$ is not constant.)

Classical difficulty

The Deutsch-Jozsa algorithm works 100% of the time, always giving us the correct answer when the promise is met, and requires a single query. How does this compare with classical query algorithms for the Deutsch-Jozsa problem?

Any deterministic classical algorithm for the Deutsch-Jozsa problem must make lots of queries — exponentially many, in fact. To be precise, $2^{n-1} + 1$ queries are required in the worst case. This is because if a deterministic algorithm queries $f$ on $2^{n-1}$ different input strings and obtains the same value every time, it still doesn't know for sure if the function is constant or balanced — both answers are still possible depending on the output of $f$ on the strings that weren't queried. So, we have a very significant advantage of quantum over classical algorithms in this regard.

However, there is a catch, which is that probabilistic classical algorithms can solve the Deutsch-Jozsa problem with very high probability using just a few queries. In particular, if we simply choose some inputs to $f$ randomly and evaluate $f$ on those strings, it would be very unlikely for the output values to all be the same when $f$ is balanced. To be specific, if we choose $k$ input strings $x^1,\ldots,x^k \in \Sigma^n$ uniformly at random, evaluate $f(x^1),\ldots,f(x^k)$ and answer $0$ if they're all the same and $1$ if not, then we'll always be correct when $f$ is constant and wrong in the case that $f$ is balanced with probability just $2^{-k + 1}.$ So, if we take $k = 11,$ for instance, this algorithm will answer correctly with probability greater than $99.9$%.

So, for this reason we do still have a rather modest advantage of quantum over classical algorithms — but it is nevertheless a quantifiable advantage that represents an improvement over Deutsch's algorithm.

Implementation

To implement the Deutsch-Jozsa algorithm in Qiskit, we'll start by generating a quantum circuit that implements a query operation for a randomly selected function that satisfies the promise: with 50% chance the function is constant, and with 50% change the function is balanced. For each possibility, the function is selected uniformly from the possibilities.

The argument to dj_function is the number of input bits of the function.

We can show the quantum circuit implementation of the query gate using the draw method as usual.

Copy to clipboard

Output:

Next we define a function that creates the Deutsch-Jozsa circuit, taking a quantum circuit implementation of a query gate as an argument.

Finally, a function that runs the Deutsch-Jozsa circuit once is defined.

We can test our implementation by choosing a function randomly, displaying the quantum circuit implementation of a query gate for this function, and then running the Deutsch-Jozsa algorithm on that function.

Copy to clipboard

Output:

'balanced'

The Bernstein-Vazirani problem

Next we will discuss a problem known as the Bernstein-Vazirani problem. It is also called the Fourier sampling problem, although there are more general formulations of this problem that also go by that name.

In order to describe this problem, it will be helpful to introduce some notation. For two binary strings $x = x_{n-1} \cdots x_0$ and $y = y_{n-1}\cdots y_0$ of length $n,$ we define

We'll refer to this operation as the binary dot product. An alternative way to define it is as follows.

Notice that this is a symmetric operation, meaning that the result doesn't change if we swap $x$ and $y,$ so we're free to do that whenever it's convenient.

One way to think about the binary dot product $x \cdot y$ is that it equals the parity of those bits of $x$ in positions where the string $y$ has a $1,$ which is equivalent to the parity of those bits of $y$ in positions where the string $x$ has a $1.$

With this notation in hand we can now define the Bernstein-Vazirani problem.

Bernstein-Vazirani problem
Input: a function $f:\{0,1\}^n\rightarrow\{0,1\}$
Promise: there exists a binary string $s = s_{n-1} \cdots s_0$ for which $f(x) = s\cdot x$ for all $x\in\Sigma^n$
Output: the string $s$

We don't actually need a new quantum algorithm for this problem, the Deutsch-Jozsa algorithm (not including the post-processing step of computing the OR of the measurement outcomes) solves it. In the interest of clarity, let's refer to the quantum circuit above (without the classical post-processing step) as the Deutsch-Jozsa circuit.

Algorithm analysis

To analyze the Deutsch-Jozsa circuit for the Bernstein-Vazirani problem, we'll begin with a quick observation. Using the binary dot product, we can alternatively describe the action of $n$ Hadamard gates on the standard basis states of $n$ qubits as follows.

Similar to what we saw when analyzing Deutsch's algorithm, this is because the value $(-1)^k$ for any integer $k$ depends only on whether $k$ is even or odd.

Turning to the circuit, after the first layer of Hadamard gates is performed, the state of the $n+1$ qubits is

The query gate is then performed, which (through the phase kickback phenomenon) transforms the state to

Using the formula above for the action of the second layer of Hadamard gates, the state becomes

We can now make some simplifications to this state, focusing on the exponent of $-1$ inside the sum. We're promised that $f(x) = s\cdot x$ for some string $s = s_{n-1} \cdots s_0,$ so we can express the state as

Because $s\cdot x$ and $x\cdot y$ are binary values, we can replace the addition with the exclusive-OR — again because the only thing that matters for an integer in the exponent of $-1$ is whether it is even or odd. Making use of the symmetry of the binary dot product, we obtain this expression for the state:

(Parentheses have been added for clarity, although they aren't really necessary: it is conventional to treat the binary dot product as having higher precedence than the exclusive-OR. An easy way to remember this is that the binary dot product looks like multiplication and the exclusive-OR looks like addition.)

At this point we will make use of the following formula.

We can obtain the formula through a similar formula for bits,

together with an expansion of the binary dot product and bitwise exclusive-OR:

This allows us to express the state of the circuit immediately prior to the measurements like this:

The final step is to make use of yet another formula, which works for every binary string $z = z_{n-1}\cdots z_0.$

(Here we're using a simple notation for strings that we'll use several more times in the lesson: $0^n$ is the all-zero string of length $n.$)

A simple way to argue that this formula works is to consider the two cases separately. If $z = 0^n,$ then $z\cdot x = 0$ for every string $x\in\Sigma^n,$ so the value of each term in the sum is $1,$ and we obtain $1$ by summing and dividing by $2^n.$ On the other hand, if any one of the bits of $z$ is equal to $1,$ then the binary dot product $z\cdot x$ is equal to $0$ for exactly half of the possible choices for $x\in\Sigma^n$ and $1$ for the other half — because the value of the binary dot product $z\cdot x$ flips (from $0$ to $1$ or from $1$ to $0$) if we flip the bit of $x$ in any position where $z$ has a $1.$

If we now apply this formula to simplify the state of the circuit prior to the measurements, we obtain

owing to the fact that $s\oplus y = 0^n$ if and only if $y = s.$

Thus, the measurements reveal precisely the string $s$ we're looking for.

Classical difficulty

While the Deutsch-Jozsa circuit solves the Bernstein-Vazirani problem with a single query, any classical query algorithm must make at least $n$ queries to solve the problem. This can be reasoned through a so-called information theoretic argument. Each classical query reveals a single bit of information about the solution, and there are $n$ bits of information that need to be uncovered.

It is, in fact, possible to solve the Bernstein-Vazirani problem classically by querying the function on each of the $n$ strings having a single $1,$ in each possible position, and $0$ for all other bits, which reveals the bits of $s$ one at a time.

So, the advantage of quantum over classical algorithms for this problem is $1$ query versus $n$ queries.

Implementation

We've already implemented the Deutsch-Jozsa circuit above, and here we will make use of it to solve the Bernstein-Vazirani problem. First we'll define a function that implements a query gate for the Bernstein-Vazirani problem given any binary string $s.$

Copy to clipboard

Output:

Now we can run the Deutsch-Jozsa circuit on the function. Note that the compile_circuit function was defined in a previous code cell, which must be run prior to the cell that follows.

'1001'

Remark on nomenclature

In the context of the Bernstein-Vazirani problem, it is common that the Deutsch-Jozsa algorithm is referred to as the "Bernstein-Vazirani algorithm." This is slightly misleading, because the algorithm is the Deutsch-Jozsa algorithm, as Bernstein and Vazirani made clear in their work.

What Bernstein and Vazirani did after showing that the Deutsch-Jozsa algorithm solves the Bernstein-Vazirani problem (as it is stated above) was to define a much more complicated problem, known as the recursive Fourier sampling problem. This is a highly contrived problem where solutions to different instances of the problem effectively unlock new levels of the problem arranged in a tree-like structure. The Bernstein-Vazirani problem described earlier is essentially just the base case of this more complicated problem.

This more complicated problem was the first known example of a query problem where quantum algorithms have a so-called super-polynomial advantage over probabilistic algorithms, thereby surpassing the advantage of quantum over classical offered by the Deutsch-Jozsa algorithm. Intuitively speaking, the recursive version of the problem effectively amplifies the $1$ versus $n$ advantage of quantum algorithms to something much larger. Arguably, the most difficult part of this analysis is to show that classical query algorithms cannot solve the problem without making lots and lots of queries. This is actually quite typical — it can be very difficult to rule out creative approaches that allow classical query algorithms to solve problems efficiently.

Simon's problem, and the algorithm for it described in the next section, does provide a much simpler example of a super-polynomial (and, in fact, exponential) advantage of quantum over classical algorithms, and for this reason the recursive Fourier sampling problem is less often discussed. It is, nevertheless, a very interesting computational problem from the viewpoint of computational complexity theory.

Simon's algorithm

Simon's algorithm is a quantum query algorithm for a problem known as Simon's problem. This is a promise problem with a flavor similar to the Deutsch-Jozsa and Bernstein-Vazirani problems, but the specifics are different. Simon's algorithm is significant because it provides an exponential advantage of quantum over classical (including probabilistic) algorithms, and the technique it uses inspired Peter Shor's discovery of an efficient quantum algorithm for factoring integers.

Simon's problem

The input function for Simon's problem takes the form

for positive integers $n$ and $m.$ We could restrict our attention to the case $m = n$ in the interest of simplicity, but there's not much to be gained in making this assumption — Simon's algorithm and its analysis are basically the same either way.

Simon's problem
Input: a function $f:\Sigma^n \rightarrow \Sigma^m$
Promise: there exists a string $s\in\Sigma^n$ such that $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$ for all $x,y\in\Sigma^n$
Output: the string $s$

We'll unpack the promise to better understand what says momentarily, but before doing this let's be clear that most functions don't satisfy this promise; it requires that $f$ has a very special structure. It's also important to note that if the promise is met, there can only be one string $s$ that works. So, there is always a unique correct answer to the problem for functions that satisfy the promise.

To better understand the promise, it is helpful to consider two main cases: the first case is that $s$ is the all-zero string $0^n,$ and the second case is that $s$ is not the all-zero string.

• Case 1: $s=0^n.$ If $s$ is the all-zero string, then we can simplify the if and only if statement in the promise so that it reads $[f(x) = f(y)] \Leftrightarrow [x = y].$ Because this if and only if statement must be true for all strings $x,y\in\Sigma^n,$ we see that saying that the promise is met for the string $s = 0^n$ is equivalent to saying that $f$ is a one-to-one function.

• Case 2: $s\neq 0^n.$ If $s$ is not the all-zero string, then the promise implies that $f$ is two-to-one, meaning that for every possible output string of $f,$ there are exactly two input strings that cause $f$ to output that string — and moreover these two input strings must take the form $x$ and $x \oplus s$ for some string $x.$

Here's an example of a function taking the form $f:\Sigma^3 \rightarrow \Sigma^5$ that satisfies the promise for the string $s = 011.$

There are $8$ different input strings and $4$ different output strings, each of which occurs twice — so this is a two-to-one function. Moreover, for any two different input strings that produce the same output string, we see that the bitwise XOR of these two input strings is equal to $011,$ which is equivalent to saying that either one of them equals the other XORed with $s.$

Notice that the only thing that matters about the actual output strings is whether they're the same or different for different choices of input strings. For instance, in the example above, there are four strings ($10011,$ $00101,$ $00001,$ and $11010$) that appear as outputs of $f.$ We could replace these four strings with different strings, so long as they're all distinct, and the correct solution $s = 011$ would not change.

Quantum circuit description

Here is a quantum circuit diagram representing Simon's algorithm.

To be clear, there are $n$ qubits on the top that are acted upon by Hadamard gates and $m$ qubits on the bottom that go directly into the query gate. It looks very similar to the algorithms we've already discussed in the lesson, but this time there's no phase kickback.

To solve Simon's problem using this circuit will actually require several independent runs of this circuit followed by a classical post-processing step, which will be described later after the behavior of the circuit is analyzed.

Analysis

The analysis of Simon's algorithm begins along similar lines to the Deutsch-Jozsa algortithm. After the first layer of Hadamard gates is performed on the top $n$ qubits, the state becomes

When the $U_f$ is performed, the output of the function $f$ is XORed onto the all-zero state of the bottom $m$ qubits, leaving the $n+m$ qubits in the state

When the second layer of Hadamard gates is performed, we obtain the following state by using the same formula for the action of a layer of Hadamard gates as before.

At this point the analysis diverges from the ones for the previous algorithms in this lesson. We're interested in the probability for the measurements to result in each possible string $y\in\Sigma^n.$ Using the rule discussed in Lesson 2, the probability $p(y)$ to obtain the string $y$ is equal to

To get a better handle on these probabilities, we'll need just a bit more notation and terminology. First, the range of the function $f$ is the set containing all of its output strings.

Second, for each string $z\in\operatorname{range}(f),$ we express the set of all input strings that cause the function to evaluate to this output string $z$ as $f^{-1}(\{z\}).$

(This notation should not be confused with the inverse of the function $f.$ Here we don't necessarily have that $f$ is invertible. We also see that the argument on the left-hand side is the set $\{z\}$ rather than the element $z,$ which is the clue we need to avoid confusion. The set $f^{-1}(\{z\})$ is known as the preimage of $\{z\}$ under $f.$ We can define the preimage under $f$ of any set in place of $\{z\}$ in an analogous way — it's the set of all elements that $f$ maps to that set.)

Using this notation, we can split up the sum in our expression for the probabilities above to obtain

Every string $x\in\Sigma^n$ is represented exactly once by the two summations — we're basically just putting these strings into separate buckets depending on which output string $z = f(x)$ they produce when we evaluate the function $f,$ and then summing separately over all the buckets.

We can now evaluate the Euclidean norm squared to obtain

To simplify these probabilities further, let's take a look at the value

for an arbitrary selection of $z\in\operatorname{range}(f).$

If it happens to be the case that $s = 0^n,$ then $f$ is a one-to-one function and there's always just a single element $x\in f^{-1}(\{z\}),$ for every $z\in\operatorname{range}(f).$ The value of the expression $(1)$ is $1$ in this case.

If, on the other hand, $s\neq 0^n,$ then there are exactly two strings in the set $f^{-1}(\{z\}).$ To be precise, if we choose $w\in f^{-1}(\{z\})$ to be any one of these two strings, then the other string must be $w \oplus s$ by the promise in Simon's problem. Using this observation we can simply $(1)$ as follows.

So, it turns out that the value $(1)$ is independent of the specific choice of $z\in\operatorname{range}(f)$ in both cases.

We can now finish off the analysis by looking at the same two cases as before separately.

• Case 1: $s = 0^n.$ In this case the function $f$ is one-to-one, so there are $2^n$ strings $z\in\operatorname{range}(f),$ and we obtain

  $$p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.$$

  In words, the measurements result in a string $y\in\Sigma^n$ chosen uniformly at random.

• Case 2: $s \neq 0^n.$ In this case $f$ is two-to-one, so there are $2^{n-1}$ elements in $\operatorname{range}(f).$ Using the formula from above we conclude that the probability to measure each $y\in\Sigma^n$ is

  $$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{y\cdot x} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\ 0 & y \cdot s = 1 \end{cases}$$

  In words, we obtain a string chosen uniformly at random from the set $\{y\in\Sigma^n : y \cdot s = 0\},$ which contains $2^{n-1}$ strings. (Because $s\neq 0^n,$ exactly half of the binary strings of length $n$ have binary dot product $1$ with $s$ and the other have binary dot product $0$ with $s,$ as we already observed in the analysis of the Deutsch-Jozsa algorithm for the Bernstein-Vazirani problem.)

Classical post-processing

We now know what the probabilities are for the possible measurement outcomes when we run the quantum circuit for Simon's algorithm. Is this enough information to determine $s$?

The answer is yes, provided that we're willing to repeat the process several times and accept that it could fail with some probability (which we can make very small by running the circuit enough times). The essential idea is that each execution of the circuit provides us with statistical evidence concerning $s,$ and we can use that evidence find $s$ with very high probability if we run the circuit sufficiently many times.

Let's suppose that we run the circuit independently $k$ times, for $k = n + 10.$ There's nothing special about this particular number of iterations — we could take $k$ to be larger (or smaller) depending on the probability of failure we're willing to tolerate, as we will see. Choosing $k = n + 10$ will ensure that we have greater than a $99.9$% chance to recover $s.$

By running the circuit $k$ times, we obtain strings $y^1,...,y^{k} \in \Sigma^n.$ To be clear, the superscripts here are part of the names of these strings, not exponents or indexes to their bits, so we have

We now form a matrix $M$ having $k$ rows and $n$ columns by inserting the bits of these string as follows.

Now, we don't know what $s$ is at this point — our goal is to find this string. But imagine for a moment that we do know the string $s,$ and we form a column vector $v$ from the bits of the string $s = s_{n-1} \cdots s_0$ as follows.

If we perform the matrix-vector multiplication $M v$ modulo $2$ — meaning that we performed the multiplication as usual and then take the remainder of the entries of the result after dividing by $2$ — we obtain this:

That is, treated as a column vector $v$ as just described, the string $s$ will always be an element of the null space of the matrix $M,$ provided that we do the arithmetic modulo $2.$ This is true in both the case that $s = 0^n$ and $s\neq 0^n.$ (The all-zero vector is always in the null space of $M,$ regardless of how $M$ is chosen — and the all-zero vector will be joined by the vector $v$ whose entries are the bits of $s$ in case $s\neq 0^n.$)