Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end

Abstract

We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems, including Quadratic Unconstrained Binary Optimization (QUBO), Ising spin glasses ($p$-spin model), and $k$-local constraint satisfaction problems ($k$-CSP). We show that either (a) the algorithm finds the optimal solution in time $O^{\ast }(2^{(0.5-c)n})$ for an $n$-independent constant $c$, a $2^{cn}$ advantage over Grover's algorithm; or (b) there are sufficiently many low-cost solutions such that classical random guessing produces a $(1-\eta )$ approximation to the optimal cost value in sub-exponential time for arbitrarily small choice of $\eta$. Additionally, we show that for a large fraction of random instances from the $k$-spin model and for any sufficiently close-to-regular, fully satisfiable (or slightly frustrated) $k$-CSP formula, statement (a) is the case. The algorithm and its analysis is largely inspired by Hastings' short-path algorithm [$\text{Quantum}$ $\text{2}$ (2018) 78].

arXiv comment54 pages, 3 figures. v2: updated to fix error in part of Theorem 7 regarding its scope of applicability, see Footnote 2

References in corpus (29)

• Adiabatic Quantum Computing
• Quantum Amplitude Amplification and Estimation
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum speedup of Monte Carlo methods
• Anderson localization casts clouds over adiabatic quantum optimization
• Fixed-point quantum search with an optimal number of queries
• Quantum Simulations of Classical Annealing Processes
• First order phase transition in the Quantum Adiabatic Algorithm
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Speed-up via Quantum Sampling
• Nested quantum search and NP-complete problems
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• Training A Quantum Optimizer
• An improved 1D area law for frustration-free systems
• Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
• Rigorous RG algorithms and area laws for low energy eigenstates in 1D
• Applying quantum algorithms to constraint satisfaction problems
• Quantum speedup of branch-and-bound algorithms
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Adiabatic optimization versus diffusion Monte Carlo
• Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
• Quantum Walks and Electric Networks
• On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm
• On the Spectral Gap of Spherical Spin Glass Dynamics
• Fast Quantum Methods for Optimization
• Improved quantum backtracking algorithms using effective resistance estimates
• The Short Path Algorithm Applied to a Toy Model
• Practical implementation of a quantum backtracking algorithm

Cited by in corpus (9)

• Quantum computing for finance
• Challenges and Opportunities in Quantum Optimization
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Optimization by Decoded Quantum Interferometry
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Optimization via Quantum Preconditioning
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
• A Quantum Constraint Generation Framework for Binary Linear Programs
• Entanglement Trajectory and its Boundary