Quantum algorithms cannot efficiently find paths in welded trees
Hardness of Pathfinding in a Welded Tree
Computational Complexity
Summary
The paper explores whether quantum computers can quickly find a path through a special kind of tree called a welded tree, starting from the entrance and reaching the exit. While quantum algorithms can locate the exit much faster than classical methods, this work shows no quantum algorithm can efficiently trace the actual path between entrance and exit. The authors prove that any quantum method still needs an exponentially large number of queries as the tree gets taller. This highlights a clear limitation in what quantum computing can do for this problem.
What this means in practice
- •For quantum algorithm designers: Avoid attempts to develop efficient quantum algorithms for pathfinding in welded trees due to proven exponential query lower bounds.
- •For quantum cryptography engineers: Use welded tree pathfinding hardness as a theoretical basis when designing cryptographic protocols resistant to quantum attacks.
A theory result. No direct application yet.
Authors
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.