OpenAlex ·
Hardness of Pathfinding in a Welded Tree
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.20651
- Original
- Read it at the publisher
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
Human Language Shapes the Emerging Physical Reasoning in Large Language Models
Orbital-Free Surrogate Functionals Yield Transferable Interatomic Potentials and Electron Densities
Looking inside a quantum black hole
cboamd: A Machine Learning Molecular Dynamics Framework for Vibrational Strong Coupling
Dephasing-Enhanced Response and Phase Transitions in Quantum Boltzmann Samplers
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.