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$.

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.

2 thoughts on “Quantum walks can find a marked element on any graph”

1. cătălin

You mean, your algorithm is slower when the number of marked items is unknown, right? If you know you have two marked items, then you define a new oracle which, if given as input a marked item, declares “marked” with probability 1/2.

Do you know any expression for the hitting time involving the eigenvectors of P (not P’). I mean, I give you a nice graph, with a lot of symmetry, I know its spectrum and I ask you “what is the hitting time?” And you reply: “Sorry, I don’t care about the symmetries, I don’t care that you know the eigenvectors of the graph, I can tell you the hitting time if you give me the eigenvectors of P’, which doesn’t have any symmetries.” By symmetries I mean regular, translation-invariant graph. The hypercube for instance.

Thanks!

• Hi Cătălin,

> You mean, your algorithm is slower when the number of marked items is unknown, right?

I’m not sure I understand your question. Our algorithm does not rely on “knowing the number of marked items”. We use other assumptions (see Table 1 in our paper) that are very similar though. What I mean is that we don’t get a quadratic speed-up over the classical algorithm in the case when there is more than one marked item. The run-time of our algorithm decreases when the number of marked elements is increased, but we would like it to decrease faster.

> If you know you have two marked items, then you define a new oracle which, if given as input a marked item, declares “marked” with probability 1/2.

Our oracle is not probabilistic — it will always tell you with certainty whether an element is marked or not (it does not matter whether there is only one such element or more). We do, however, make the walk “lazy” in the sense that with probability 1/2 it does nothing and with probability 1/2 is proceeds as usual. This is for technical reasons and affects the run-time only by a factor of 2.

> Do you know any expression for the hitting time involving the eigenvectors of P (not P’).

By definition, the hitting time is the expected time it takes to find a marked item (starting from some initial distribution). Thus, different sets of marked elements will result in different hitting times. However, P does not encode what the set of marked elements is whereas P’ does. For this reason I don’t see how one would be able to express the hitting time using P. Note that even if your graph has lots of symmetries, the set of marked elements can be arbitrary and thus not obey those symmetries.