A quantum lower bound for path finding in welded trees
quant-ph
Submitted: 2026-09-22
Updated: 2026-09-22
Terminology
Sources
- Quantum Snake Walk on Graphs
- Symmetries, graph properties, and quantum speedups
- Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
- Open Problems Related to Quantum Query Complexity
- (Sub)Exponential advantage of adiabatic quantum computation with no sign problem
- Quantum algorithms and the power of forgetting
- Exponential speedup of quantum algorithms for the pathfinding problem
- Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
- Using Large Language Models for a standard assessment mapping for sustainable communities
- Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs
- (Sub)Exponential Quantum Speedup for Optimization
- Compressed Permutation Oracles
- Quantum algorithms for path and cycle containment problems
- Hardness of Pathfinding in a Welded Tree
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
- Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity