The randomized query complexity of the conjoined trees problem

Question

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 Ω(2^n/6), but I believe that a closer examination of their proof yields Ω(2^n/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 ~2^n/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 ~2ⁿ steps---say, in O(2^n/2), or O(2^2n/3)? Alternatively, can anyone give a lower bound better than Ω(2^n/2)?

(Note that, by the birthday paradox, it's not hard to find cycles in the graph after O(2^n/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 Ω(2^n/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~2ⁿ 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 Ω(2^n/3). If they were willing to accept constant (rather than exponentially-small) success probability, I believe they could improve the bound further, to Ω(2^n/2).

Answer 1

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