Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard
Abstract
In the welded trees problem, an algorithm navigates a randomly labeled graph formed from two binary trees joined at their leaves through a "weld" of connecting edges. A quantum walk can navigate from root to root exponentially faster than any classical algorithm. However, recording its path destroys the constructive interference responsible for the speedup, leaving open whether some quantum algorithm can efficiently find a path between the roots. We prove that, for trees of height n, the quantum query complexity of finding a path between the roots with constant probability is Θ̃(2n/3). This establishes an algorithmic wave-particle duality, adapting the double-slit experiment to the high-complexity regime: interference between many paths lets a quantum algorithm reach the exit efficiently, but finding a single path (the algorithmic analog of the route of a particle) requires exponentially many queries. Furthermore, the bound is tight, matching the cost of a quantum algorithm that finds collisions between paths from each root to the weld. Our proof uses the compressed permutation oracle to track the information about the graph that an algorithm retains and forgets. We show that the compressed database remains close to a space of states that do not record a path between the roots by bounding the error introduced by each compressed oracle query.
Related
- Hardness of Pathfinding in a Welded Tree
- A quantum lower bound for path finding in welded trees
- Particle-Vortex Duality of Hydrodynamics
- Atomic limits of empirical measures of interacting particle systems with self-duality
- Wave-particle duality at eleven parameters: the half-sum of the two readings, and the experiments
BibTeX
@misc{carolan2026algorithmic,
title = {{Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard}},
author = {Joseph Carolan and Andrew M. Childs and Matthew Coudron and Amin Shiraz Gilani and David Miloschewsky and Supartha Podder},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05912},
eprint = {2611.05912},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05912},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard
AU - Joseph Carolan
AU - Andrew M. Childs
AU - Matthew Coudron
AU - Amin Shiraz Gilani
AU - David Miloschewsky
AU - Supartha Podder
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.05912
UR - https://arxiv.org/abs/2611.05912
AB - In the welded trees problem, an algorithm navigates a randomly labeled graph formed from two binary trees joined at their leaves through a "weld" of connecting edges. A quantum walk can navigate from root to root exponentially faster than any classical algorithm. However, recording its path destroys the constructive interference responsible for the speedup, leaving open whether some quantum algorithm can efficiently find a path between the roots. We prove that, for trees of height n, the quantum query complexity of finding a path between the roots with constant probability is Θ̃(2^n/3). This establishes an algorithmic wave-particle duality, adapting the double-slit experiment to the high-complexity regime: interference between many paths lets a quantum algorithm reach the exit efficiently, but finding a single path (the algorithmic analog of the route of a particle) requires exponentially many queries. Furthermore, the bound is tight, matching the cost of a quantum algorithm that finds collisions between paths from each root to the weld. Our proof uses the compressed permutation oracle to track the information about the graph that an algorithm retains and forgets. We show that the compressed database remains close to a space of states that do not record a path between the roots by bounding the error introduced by each compressed oracle query.
ER -