# The randomized query complexity of the conjoined trees problem

An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of. In this problem, we're given an exponentially-large graph like the one pictured below, which consists of two complete binary trees of depth n, whose leaves are connected to each other by a random cycle. We're supplied with the label of the ENTRANCE vertex. We're also supplied with an oracle that, given as input the label of any vertex, tells us the labels of its neighbors. Our goal is to find the EXIT vertex (which can easily be recognized, as the only degree-2 vertex in the graph other than the ENTRANCE vertex). We can assume that the labels are long random strings, so that with overwhelming probability, the only way to learn the label of any vertex other than the ENTRANCE vertex is to be given it by the oracle.

Childs et al. showed that a quantum walk algorithm is able simply to barrel through this graph, and find the EXIT vertex after poly(n) steps. By contrast, they also showed that any classical randomized algorithm requires exp(n) steps to find the EXIT vertex with high probability. They stated their lower bound as Ω(2n/6), but I believe that a closer examination of their proof yields Ω(2n/2). Intuitively, this is because with overwhelming probability, a random walk on the graph (even a self-avoiding walk, etc.) will get stuck in the vast middle region for an exponential amount of time: any time a walker starts heading toward the EXIT, the much larger number of edges pointing away from the EXIT will act as a "repulsive force" that pushes it back toward the middle.

The way they formalized the argument was to show that, until it's visited ~2n/2 vertices, a randomized algorithm hasn't even found any cycles in the graph: the induced subgraph that it's seen so far is just a tree, providing no information whatsoever about where the EXIT vertex might be.

I'm interested in pinning down the randomized query complexity of this problem more precisely. My question is this:

Can anyone come up with a classical algorithm that finds the EXIT vertex in fewer than ~2n steps---say, in O(2n/2), or O(22n/3)? Alternatively, can anyone give a lower bound better than Ω(2n/2)?

(Note that, by the birthday paradox, it's not hard to find cycles in the graph after O(2n/2) steps. The question is whether one can use the cycles to get any clues about where the EXIT vertex is.)

If anyone can improve the lower bound past Ω(2n/2), then to my knowledge, this would provide the very first provable example of a black-box problem with an exponential quantum speedup, whose randomized query complexity is greater than √N. (Where N~2n is the problem size.)

Update: I've learned from Andrew Childs that, in this note, Fenner and Zhang explicitly improve the randomized lower bound for conjoined trees to Ω(2n/3). If they were willing to accept constant (rather than exponentially-small) success probability, I believe they could improve the bound further, to Ω(2n/2).

I think I have a deterministic algorithm that finds the exit in $O(n2^{n/2})$ oracle calls.

First, find the labels for all the vertices of distance $n/2$ from the entrance. This takes $O(2^{n/2})$ queries. Then, start from the entrance and walk $n+1$ steps to get to a node $X$ of distance $n+1$ from the entrance. We will try to reach the exit from this node.

We have two options of where to go from $X$, and we wish to choose the one closer to the exit. To do this, pick one of the options arbitrarily, arriving at a node $Y$. Then explore all the $O(2^{n/2})$ ways of walking $n/2$ steps from $Y$. If one of them gives a label of distance $n/2$ from the entrance, we know that going from $X$ to $Y$ was the wrong choice. Otherwise, $Y$ was the right choice. Thus in $O(2^{n/2})$ we found a node $X_2$ of distance $n+2$ from the entrance.

We can keep proceeding this way. To find a node of distance $n+3$ from the entrance, we start at $X_2$ and walk two arbitrary steps. We then explore all options of walking $n/2$ additional steps (while never walking backwards), and check if any of them have distance $n/2$ from the entrance. This will happen if and only if the first step we walked from $X_2$ was wrong.

Getting to the exit requires doing this $n$ times, for a total of $O(n2^{n/2})$ oracle calls. In addition, perhaps surprisingly, this algorithm is deterministic.

Edit: Just to clarify, to get from $X_t$ to $X_{t+1}$, we walk $t$ arbitrary steps, then run a search of depth $n/2$, for a total of $t+2^{n/2}$ steps. If the first step lead away from the exit, then all the first $t$ steps did, and we therefore find a label of distance $n/2$ from the entrance. This means $t+2^{n/2}$ steps suffice for determining the next single step to take from $X_t$.

• I don't understand. To find $X_{t+1}$, you would make $t$ arbitrary steps from $X_t$ and then $n/2$ additional steps? Wouldn't this give $2^t2^{n/2}$ steps which is too much? – domotorp Jul 20 '14 at 11:31
• I second domotorp's confusion. Isn't it the case that, the closer you get to the EXIT, the longer the path you're going to need to get to one of the $2^{n/2}$ points that you queried at the beginning? Still, maybe you could exploit the fact that paths that start close to the EXIT are extremely likely to move left toward the center until they reach it? (This would add a bit of randomization to your algorithm.) – Scott Aaronson Jul 20 '14 at 13:30
• Come to think of it, what if we took advantage of the fact that, from any vertex in the right half of the graph, you have a 1/2 chance of picking a direction that's going to lead you inexorably back to the center? That might be enough to get us n/2 away from the EXIT vertex, which would then allow us to find the EXIT vertex itself with $2^{n/2}$ further queries. – Scott Aaronson Jul 20 '14 at 14:44
• To find $X_{t+1}$, make $t$ arbitrary steps from $X_t$, but only once. This takes $t$ steps, not $2^t$ steps. Then make $n/2$ steps in all possible ways. This takes $2^{n/2}$ steps. The total is $t+2^{n/2}$. I'm using the fact that if the first of the $t$ steps was wrong, then all $t$ of these steps lead away from the exit (and back towards the entrance). This stops being the case after the first $t$ steps, which is why you need to start an exhaustive search. – Shalev Jul 20 '14 at 15:55
• The idea of starting a search from both ends and leading to a sqrt() improvement over the naive algorithm is known as bidirectional search and has been rediscovered independently many times in various contexts e.g. route planning in google maps. The original reference seems to be: G. B. Dantzig. Linear Programming and Extensions. Princeton University Press, 1962. – Alex Lopez-Ortiz Jul 21 '14 at 20:03