Quantum walks can find a marked element on any graph

This post is about my paper Quantum walks can find a marked element on any graph with Hari Krovi, Frédéric Magniez, and Jérémie Roland. We wrote it in 2010, but after spotting a subtle mistake in the original version, we have recently substantially revised it. It went from 15 to 50 pages after we added much more details and background material, as well as corrected some small bugs and addressed one major bug.

Problem statement

Imagine a huge graph with many vertices, some of which are marked. You are able to move around this graph and query one vertex at a time to figure out if it is marked or not. Your goal is to find any of the marked vertices.

Given an instance of such problem, a typical way to solve it is by setting up a random walk on the graph. You can imagine some probabilistic procedure that systematically moves from one vertex to another and looks for a marked one.

More formally, you would define a stochastic matrix P whose entry P_{xy} describes the probability to move from vertex x to y. Starting from some randomly chosen initial vertex, your goal is to end up in one of the marked vertices in the set M.

Random walk on a graph

Our result

We show that any classical algorithm that is based on such random walk can be turned into a quantum walk algorithm that finds a marked vertex quadratically faster. To state this more formally, let us define the hitting time of a random walk:

Definition. The hitting time of P with respect to a set of marked vertices M is the expected number of steps the walk P takes to find a marked vertex, starting from a random unmarked vertex chosen from a distribution which is proportional to the stationary distribution of P. Let us denote this quantity by \mathrm{HT}(P,M).

Our main result is as follows:

Theorem. Quantum walk can find a marked vertex in \sqrt{\mathrm{HT}^+(P,M)} steps.

As you can see, this is a very general result—no matter how cleverly the transition probabilities for the random walk P are chosen, we can always cook up a related quantum walk that beats the classical walk quadraticaly!

Note that this is much more general than what is achieved by Grover’s algorithm. Grover’s algorithm corresponds to the special case, where the underlying graph is complete and the random walk moves from any vertex to any other with equal probability.

It’s weaker than before…

You may have noticed a little “+” that appeared next to \mathrm{HT} in the statement of the theorem. Indeed, this has to do with the subtle mistake we spotted in our earlier proof. It turns out that if |M| = 1 (i.e., there is a unique marked vertex) then

\mathrm{HT}^+(P,M) = \mathrm{HT}(P,M)

and we indeed achieve a quadratic quantum speedup. Unfortunately, when |M| > 1 it can happen that

\mathrm{HT}^+(P,M) > \mathrm{HT}(P,M)

and thus we don’t get a fully quadratic speedup. Hence our result is weaker than what we claimed previously. On the other hand, the new version is more correct!

Proof idea

Our algorithm is based on Szegedy’s method for turning random walks into quantum walks. It constructs two unitary matrices, each corresponding to a reflection with respect to a certain subspace. These subspaces are defined by

  1. the standard basis vectors corresponding to marked vertices,
  2. the unit vectors obtained by taking entry-wise square roots of the rows of P.

Together these two reflections define one step of the quantum walk.

Our contribution consists in modifying the original walk P before we quantize it. We define a semi-absorbing walk P(s) that leaves a marked vertex with probability 1-s even when one is found. This might seem like a bad idea, but one can check that at least classically it does not make things worse by too much. In fact, the s \to 1 limit of P(s) corresponds to the classical algorithm that never leaves a marked vertex once it is found.

Glitch in the previous proof

Our proof makes extensive use of a certain quantity \mathrm{HT}(s) which we associate to P(s) and call interpolated hitting time. Then \mathrm{HT}^+(P,M), the extended hitting time that appears in the above theorem, is defined as the limit

\mathrm{HT}^+(P,M) := \lim_{s \to 1} \mathrm{HT}(s)

When |M| = 1, taking this limit is straightforward and one can easily see that it gives \mathrm{HT}(P,M), the regular hitting time.

It is tempting to guess that the same happens also when |M| > 1. Indeed, it is far from obvious why in this case the answer does not come out the same way as in the |M| = 1 case. This is exactly what was overlooked in the earlier version of our paper. Computing the limit properly when |M| > 1 is much harder (the expression contains inverse of some matrix that is singular at s = 1). This is done in detail in the final appendix of our paper.

Open problems

Here are some open questions:

  • Why is it that our algorithm has a harder time to find a needle in a haystack when there are several needles rather than just one?
  • What is the operational interpretation of the interpolated hitting time \mathrm{HT}(s)?
  • Can quadratic speedup for finding be achieved also when there are multiple marked vertices?
  • How can we efficiently prepare the initial state on which the walk is applied?

One might get some insight in the first two questions by observing that our algorithm actually solves a slightly harder problem than just finding a marked vertex—it samples the marked vertices according to a specific distribution (proportional to P(s^*) for some s^*). When there is only one marked vertex, finding it is the same as sampling it. However, for multiple marked vertices this is equivalence does not hold and in general it should be harder to sample.

Advertisements

Exact quantum query algorithms

Andris Ambainis, Jānis Iraids, and Juris Smotrovs recently have obtained some interesting quantum query algorithms [AIS13]. In this blog post I will explain my understanding of their result.

Throughout the post I will consider a specific type of quantum query algorithms which I will refer to as MCQ algorithms (the origin of this name will become clear shortly). They have the following two defining features:

  • they are exact (i.e., find answer with certainty)
  • they measure after each query

Quantum effects in an MCQ algorithm can take place only for a very short time — during the query. After the query the state is measured and becomes classical. Thus, answers obtained from two different queries do not interfere quantumly. This is very similar to deterministic classical algorithms that also find answer with certainty and whose state is deterministic after each query.

Basics of quantum query complexity

Our goal is to evaluate some (total) Boolean function f(x) on an unknown input string x \in \{1,-1\}^n (we assume for convenience that binary variables take values +1 and -1). We can access x only by applying oracle matrix

Q_x =    \begin{pmatrix}      x_1 & & & \\      & x_2 & & \\      & & \ddots & \\      & & & x_n    \end{pmatrix}

to some quantum state. The minimum number of queries needed to determine the value of f(x) with certainty is called the exact quantum query complexity of f.

Quantum questions with classical answers

Each interaction with oracle in an MCQ algorithm can be described as follows:

  1. prepare some state |\psi\rangle
  2. apply query matrix Q_x
  3. apply some unitary U
  4. measure in the standard basis

Intuitively, this interaction is a quantum question (specified by |\psi\rangle and U) which produces a classical answer (measurement outcome i that appears with probability |\langle i|UQ_x|\psi\rangle|^2).

Since each of the answers reveal some property of x, it is convenient to identify the collection of these properties with the question itself (I think of it as a “quantum Multiple Choice Question”, hence MCQ). Of course, not every collection of properties constitutes a valid quantum question — only those for which there exists a corresponding |\psi\rangle and U. (We will see some examples soon.)

MCQ algorithms

Simply put, an MCQ algorithm is a decision tree: each its leaf contains either 0 or 1 (the value of f(x) for corresponding x), and each of the remaining nodes contains a quantum question and children correspond to answers.

Classical deterministic decision trees are very similar to MCQ algorithms, except that their nodes contain classical questions — at each node we can only ask one of the n variables x_i. Quantumly, we have a larger variety of questions — for example, we can ask XOR of two variables (as in Deutsch’s algorithm). Another difference is that a quantum question does not have a unique answer: if several answers are consistent with the input string x, we will get one of them at random.

An obvious question regarding MCQ algorithms is this:

How can we exploit the quantum oracle to find f(x) with less queries than classically?

Surprisingly, until recently essentially no other way of exploiting the quantum oracle was known, other than Deutsch’s XOR trick (see [MJM11] by Ashley Montanaro, Richard Jozsa, and Graeme Mitchison for more details). What is interesting about the [AIS13] paper is that it provides a new trick!

Query, measure, recurse!

All algorithms discussed in [AIS13] are MCQ and recursive. They proceed as follows:

  1. query
  2. measure
  3. recurse

In the last step, depending on the measurement outcome, either f(x) is found or the problem is reduced to a smaller instance and we proceed recursively. Let me explain how this works for two functions which I will call BALANCED and MAJORITY (they are special cases of EXACT and THRESHOLD discussed in [AIS13]).

BALANCED

\mathrm{BALANCED}_{2k} (x_1, x_2, \dotsc, x_{2k}) = 1 iff exactly k of the variables x_i are equal to 1. An MCQ algorithm asks a quantum question that can reveal the following properties of the input string x:

  1. x is not balanced (the number of +1s and -1s is not equal)
  2. x_i is not equal to x_j (for some i \neq j)

If we get the first answer then \mathrm{BALANCED}_{2k}(x) = 0 and we are done. If we get the second answer for some i \neq j, we can ignore the variables x_i and x_j and recursively evaluate \mathrm{BALANCED}_{2(k-1)} on the remaining variables. In total, we need at most k queries (which can be shown to be optimal).

It remains to argue that the above is a valid quantum question. Alternatively, we can show how to prepare the following (unnormalized) quantum state:

\sum_{i=1}^{2k} x_i |0\rangle + \sum_{i<j} (x_i - x_j) |ij\rangle

(It lives in the space spanned by |0\rangle and |ij\rangle for all i<j.) This can be easily done by taking

|\psi\rangle = \sum_{i=0}^{2k} |i\rangle

and U that acts as

U |i\rangle = \frac{1}{\sqrt{2k}}    \Bigl( |0\rangle + \sum_{j>i} |ij\rangle - \sum_{j<i} |ji\rangle \Bigr)

To check that U is a valid isometry, notice that it maps |i_1\rangle and |i_2\rangle to paths that overlap in exactly one cell (rows are labeled by i and columns by j):
Grid_paths
Since both states also have |0\rangle in common, they are orthogonal.

MAJORITY

\mathrm{MAJORITY}_{2k+1} (x_1, x_2, \dotsc, x_{2k+1}) = 1 iff at least k+1 of the variables x_i are equal to 1. This time the quantum question has answers

  1. x is not balanced when x_i is omitted (for some i)
  2. x_i is not equal to x_j (for some i \neq j)

If we get the first answer for some i, we omit x_i and any other variable. If we get the second answer for some i \neq j, we ignore the variables x_i and x_j. In both cases we proceed by recursively evaluating \mathrm{MAJORITY}_{2k-1} on the remaining variables. When only one variable is left, we query it to determine the answer. This requires at most k+1 queries in total (which again can be shown to be optimal).

The corresponding (unnormalized) state in this case is

\sum_{i=1}^{2k+1} \sum_{j \neq i} x_i |j\rangle    + \sqrt{2k-1} \sum_{i<j} (x_i - x_j) |ij\rangle

(It lives in the space spanned by |j\rangle for all j and |ij\rangle for all i<j.) It can be obtained by choosing

|\psi\rangle = \sum_{i=1}^{2k+1} |i\rangle

and U acting as

U |i\rangle = \frac{1}{2k}    \Bigl(      \sum_{j \neq i} |j\rangle      + \sqrt{2k-1} \sum_{j>i} |ij\rangle      - \sqrt{2k-1} \sum_{j<i} |ji\rangle    \Bigr)

One can check that U is an isometry using a similar picture as above.

Open questions

The problem of finding a quantum query algorithm with a given number of queries and a given success probability can be formulated as a semi-definite program. This was shown by Howard Barnum, Michael Saks, and Mario Szegedy in [BSS03] and can be used to obtain exact quantum query algorithms numerically. Unfortunately, this approach does not necessarily give any insight of why and how the obtained algorithm works. Nevertheless, it would be interesting to know if there is a similar simple characterization of MCQ algorithms.

The algorithms from [AIS13] described above are relatively simple. However, that does not mean that they were simple to find. In fact, the SDP corresponding to \mathrm{BALANCED}_4 had already been solved numerically in [MJM11]. Unfortunately, it did not provide enough insight to obtain an algorithm for \mathrm{BALANCED}_{2k} for any k. A similar situation is now with \mathrm{EXACT}^6_{2,4} (which it is true if exactly two or four out of the six variables are true). From [MJM11] we know that it has an exact 3-query algorithm. Unfortunately, we do not have enough understanding to describe it in a simple way or generalize it. Besides, I wonder if \mathrm{EXACT}^6_{2,4} has a 3-query MCQ algorithm, or do we actually need interference between the queries to find the answer so fast?

Finally, it would be interesting to know if there is any connection between exact quantum query algorithms and non-local games or Kochen–Specker type theorems.

Three myths about quantum computing — Part 1: Exponential size state space

This is the first post in the series on myths about quantum computing. In this post I will discuss the first misconception about quantum computers—that the exponential size of their state space is the main feature that distinguishes them from their classical cousins—and explain why this should not be used as an argument to suggest that quantum computers are likely to be more powerful than the classical ones.

Consider a system S with states labelled by n-bit strings. Assume that S is initialized in all-zeroes state “00…0” and undergoes some kind of physical evolution. Let us consider three scenarios.

Deterministic classical world

If the evolution is deterministic, then one can specify the current state of the system by giving the corresponding label. Thus, one needs n bits of information to describe the state in this case.

Quantum world

If S is a quantum system, it can be in a superposition of all possible states. To describe this superposition, one has to assign a complex number to each state. Thus, in total one has to specify 2n complex numbers (say, to some finite precision), which is exponentially more information than in the deterministic case!

If you have never heard of this before (or remember your excitement when you heard it the first time), this definitely is mind-boggling. In fact, this is often mentioned as the main obstacle for efficiently simulating quantum computers, and also as a hand-waving argument to convince wider public that quantum computers are likely to be exponentially more powerful than classical ones.

Probabilistic classical world

One should not get too excited about the above observation, but instead think more carefully whether this comparison of deterministic and quantum computers is fair. Since the output of a quantum computer is intrinsically probabilistic, one should be looking at probabilistic evolution in the classical case, not deterministic.

If the transitions between states of the system S are described by probabilities, then the resulting state is a probability distribution over {0,1}n. To describe such distribution, one needs to specify 2n real numbers—one for each n-bit string. This is also exponentially more information than in the deterministic case!

Thus, with this comparison the only difference in the amount of information needed to describe classical and quantum states is a factor of two (since probability can be specified by a single real number whereas two real numbers are needed to specify one complex quantum amplitude).

Conclusion

The fact that an exponential amount of information is needed to describe the state space of a particular computational model does not immediately imply that it is exponentially more powerful. To be more specific, let us consider the classes of decision problems that can be solved in polynomial time by the three computational models discussed above:

The following inclusions are trivial:

\mathrm{P} \subseteq \mathrm{BPP} \subseteq \mathrm{BQP}

However, as of now, none of these inclusions is known to be strict.

Thus, one should not use the exponential size of the state space as an argument to claim that quantum computers are likely to be hard to simulate by deterministic classical computers, since the same argument could also be used in favor of probabilistic classical computers.

To me it seems that the main difference between probabilistic and quantum computers is the underlying field of numbers (non-negative real numbers versus complex numbers). It is a major open problem to show if this subtle difference can be used to separate the corresponding two complexity classes.

Three myths about quantum computing

In this series of posts I will discuss some misconceptions about quantum computing.

One often hears people saying that quantum physics is “strange” and that our classical intuition “breaks down” in the quantum world. I will try to argue that one should not brag about the weirdness of quantum mechanics without carefully investigating the corresponding phenomena in the classical world. In fact, many quantum phenomena no longer seem surprising once their lesser cousins in the classical probabilistic world are understood.

To illustrate my point, I will consider three basic properties of quantum information

  1. exponential state space
  2. no-cloning theorem
  3. quantum teleportation and superdense coding

and discuss how they translate to the classical case.

These topics are usually covered in the first class of an introductory quantum computing course, so none of what I discuss should come as a surprise to somebody who has taken such a course or read an introductory textbook on the topic. However, I have to admit that I was equally shocked both, when I learned these basic facts about quantum information in class, as when I later realized that they have a corresponding classical counterpart.

I would like to acknowledge all my “non-quantum” friends with whom I have had conversations about quantum physics. I would probably still believe in these misconceptions if I had not tried to explain you in simple terms why quantum physics is supposed to be so strange. Maybe it is not so strange after all…

p.s. For those of you who have never attempted to explain what you are doing to somebody who does not have a PhD degree in your area of expertise, consider the following three quotes by the founders of quantum mechanics:

Most of the fundamental ideas of science are essentially simple, and may, as a rule, be expressed in a language comprehensible to everyone.
—Albert Einstein

The physicist may be satisfied when he has the mathematical scheme and knows how to use it for the interpretation of the experiments. But he has to speak about his results also to non-physicists who will not be satisfied unless some explanation is given in plain language. Even for the physicist, the description in plain language will be the criterion of the degree of understanding that has been reached.
—Werner Heisenberg

If you cannot—in the long run—tell everyone what you have been doing, your doing has been worthless.
—Erwin Schrödinger