arXiv:2609.26712
A quantum lower bound for path finding in welded trees
Joseph Carolan, Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani
Abstract
In the welded tree problem, an algorithm is tasked with navigating a graph formed from two binary trees joined at the leaves through a ``weld'' of connecting edges. A quantum walk can navigate from root to root exponentially faster than any classical algorithm. However, known efficient quantum algorithms cannot find a path between the roots, as recording the path destroys constructive interference and thus the speedup. We prove that this is inherent: any quantum algorithm needs exponentially many queries to find a path between the roots of an independently matched welded tree graph. This provides an example of a problem that a quantum computer can solve exponentially faster than any classical algorithm by exploring exponentially many paths in superposition, but where it is provably intractable to find any such path. The proof uses compressed permutation oracles to record the progress of a quantum algorithm as it queries the graph. We show that the compressed database remains path-free up to a small error. By controlling such errors and bounding the progress of the algorithm with each compressed oracle query, we show that $Ω(2^{n/12})$ queries are required to find a path in a height-$n$ tree with constant success probability.
AI Summary
The welded-tree oracle problem admits an exponential quantum speedup for reaching the exit from the entrance, but known quantum-walk algorithms do not output a connecting path. This paper asks whether any quantum algorithm can find such a path efficiently, without the “rooted” and “genuine” restrictions imposed in earlier lower bounds. For height-$n$ trees with independently matched welds, it proves an exponential quantum query lower bound. Writing $N=2^n$, the quantitative theorem bounds the success probability of a $q$-query algorithm by $O((n+2)^4q^6/N^{1/2})$. Constant success therefore requires $q=\Omega(2^{n/12}/(n+2)^{2/3})$. The theorem allows arbitrary output length. This ensemble retains efficient quantum exit-finding, separating reaching the exit from producing an explicit path. The proof represents random weld matchings using compressed permutation oracles and extends the framework to sparse injective vertex labelings, controlling guesses of unseen labels. It constructs an approximately query-invariant subspace described by color words and partial database cores. Independent core placements and a clipping lemma control arbitrary superpositions despite overlapping descriptions. After $q$ queries, the database remains close to this subspace with core size $O(nq)$. A compressed-oracle recording argument then relates successful path output to a recorded entrance-to-exit path, whose weight is bounded. The proved ensemble uses independent colored matchings, allowing parallel edges, rather than the original single-cycle weld distribution. An adaptation to the original distribution is asserted but deferred. Similar concurrent independent work is noted.
The manuscript was written and revised with significant input from GPT-6 and additional input from Claude Opus 5, and was edited by the authors, who take sole responsibility for its correctness.
Error found: The abstract and introductory informal theorem claim an Ω(2^{n/12}) query lower bound, whereas the final theorem establishes only Ω(2^{n/12}/(n+2)^{2/3}), leaving an unaccounted polynomial factor.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.