arXiv:2609.20651
Hardness of Pathfinding in a Welded Tree
David Miloschewsky, Supartha Podder
Abstract
Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height $n$, any quantum query algorithm requires at least $Ω(2^{n/24})$ queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records.
AI Summary
The welded-tree oracle problem admits a polynomial-query quantum algorithm for finding the exit label, despite exponential classical query complexity. This paper asks whether a quantum algorithm can also output an explicit entrance-to-exit path, removing the “genuine” and “rooted” restrictions imposed in an earlier negative result. For trees parameterized by height $n$, with $N=2^n$, it proves that any quantum algorithm making $1\leq q\leq\sqrt N/100$ queries has pathfinding success probability $O(q^6/N^{1/4})$. Constant success therefore requires $\Omega(N^{1/24})=\Omega(2^{n/24})$ queries. The formal theorem assumes even $n\geq16$. The proof applies compressed permutation oracles to random vertex labels and color-preserving edge permutations, producing quantum databases that track information retained or erased during computation. A nearby “fresh” oracle prevents newly recorded edges from joining already explored components. Path construction is then reduced to growing a component from a fixed weld crossing to the boundary of the middle region. An approximately invariant superposition over hidden vertex assignments bounds this escape probability, including under coherent insertion, erasure, and replacement of records. A separate analysis shows that a polynomial-length quantum walk approximately retains only its current position in the database. The oracle takes a vertex label and one of three edge colors, rather than returning all neighbors. The instance distribution also differs from the original uniformly random welded cycle: it respects fixed colorings. The proof first permits multiple weld cycles, then transfers the bound to that distribution conditioned on a single cycle.
Specifically, it found a much simpler way to prove the statements in \cref{sec:single_cycle,sec:general_intertwiner_lemma}
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 55 pages, 4 figures