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