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].

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

References in corpus (9)

• Fixed-point quantum search with an optimal number of queries
• Quantum Simulations of Classical Annealing Processes
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Speed-up via Quantum Sampling
• Adiabatic optimization versus diffusion Monte Carlo
• Quantum Walks and Electric Networks
• On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm
• Fast Quantum Methods for Optimization
• The Short Path Algorithm Applied to a Toy Model

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