Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard
quant-ph
Submitted: 2026-11-04
Updated: 2026-11-04
Terminology
Sources
- A quantum lower bound for path finding in welded trees
- Quantum algorithms and the power of forgetting
- Compressed Permutation Oracles Revisited
- A note on the classical lower bound for a quantum walk algorithm
- (Sub)Exponential advantage of adiabatic quantum computation with no sign problem
- An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
- A Brief Introduction to Quantum Query Complexity
- Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs
- (Sub)Exponential Quantum Speedup for Optimization
- Hardness of Pathfinding in a Welded Tree
- Tight Bounds for Inverting Permutations via Compressed Oracle Arguments
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements