Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks

arXiv:2609.40088 · quant-ph, cs.DS, math.OC · Submitted 2026-09-30 · Read on arXiv

quant-ph, cs.DS, math.OC

Submitted: 2026-09-30

Updated: 2026-09-30

Terminology

• Spectral Gap — 30× in this paper · explained in 5 episodes
• Block Encoding — 26× in this paper · explained in 4 episodes
• Objective Function — 6× in this paper · explained in 2 episodes
• Combinatorial Optimization — 5× in this paper · explained in 2 episodes
• Accuracy — 2× in this paper · explained in 1 episode
• Generalization — 1× in this paper · explained in 13 episodes
• Hamming Distance — 1× in this paper · explained in 2 episodes
• Homogeneity — 1× in this paper · explained in 2 episodes
• Metastability — 1× in this paper · explained in 3 episodes
• Quantization — 1× in this paper · explained in 12 episodes
• Unified Framework — 1× in this paper · explained in 5 episodes

Sources

• Dequantizing Short-Path Quantum Algorithms
• Spatial search by quantum walk
• Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms
• Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization
• A Quantum Algorithm for Finding the Minimum
• A Short Path Quantum Algorithm for Exact Optimization
• Weaker Assumptions for the Short Path Optimization Algorithm
• Quantum speedup of Monte Carlo methods
• Quantum walk speedup of backtracking algorithms
• Quantum Simulations of Classical Annealing Processes

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