Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard

arXiv:2611.05912v1 Announce Type: new 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 $\tilde{\Theta}(2^{n/3})$.