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

This paper proves that while quantum walks can traverse welded trees exponentially faster than classical algorithms, any quantum algorithm attempting to explicitly record the path between the roots requires exponentially many queries ($\tilde{\Theta}(2^{n/3})$), thereby establishing an "algorithmic wave-particle duality" where interference enables efficient navigation but path reconstruction remains hard.

Original author: Joseph Carolan, Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani, David Miloschewsky, Supartha Podder