A quantum lower bound for path finding in welded trees
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 Ω(2n/12) queries are required to find a path in a height-n tree with constant success probability.
Related
- A Quantum Lower Bound for Triangle Finding
- Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard
- Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points
- Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means
- Improved lower bound for the two-way-assisted quantum capacity of the bosonic thermal-loss channel
BibTeX
@misc{carolan2026quantum,
title = {{A quantum lower bound for path finding in welded trees}},
author = {Joseph Carolan and Andrew M. Childs and Matthew Coudron and Amin Shiraz Gilani},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26712},
eprint = {2609.26712},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26712},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A quantum lower bound for path finding in welded trees
AU - Joseph Carolan
AU - Andrew M. Childs
AU - Matthew Coudron
AU - Amin Shiraz Gilani
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.26712
UR - https://arxiv.org/abs/2609.26712
AB - 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.
ER -