Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2212.01513 · ACM Symposium on Theory of Computing (STOC)

Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End

Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, Fernando G. S. L. Brandão

Published May 16, 2023• 14 citations
arXivHTMLPDF

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*(2(0.5−c)n) for an n-independent constant c, a 2cn advantage over Grover’s algorithm; or (b) there are sufficiently many low-cost solutions such that classical random guessing produces a (1−η) approximation to the optimal cost value in sub-exponential time for arbitrarily small choice of η. Additionally, we show that for a large fraction of random instances from the k-spin model and for any fully satisfiable or slightly frustrated k-CSP formula, statement (a) is the case. The algorithm and its analysis are largely inspired by Hastings’ short-path algorithm.

DOI
10.1145/3564246.3585203

Related papers

Dequantizing Short-Path Quantum Algorithms

François Le Gall, Suguru Tamaki

The short-path quantum algorithm introduced by Hastings (Quantum 2018, 2019) is a variant of adiabatic quantum algorithms that enables an easier worst-case analysis by avoiding the need to control the spectral gap along a long adiabatic path. Dalzell, Pancotti, Campbell, and Brandão (STOC 2023) recently revisited this framework and obtained a clear analysis of the complexity of the short-path algorithm for several classes of constraint satisfaction problems (MAX-$k$-CSPs), leading to quantum algorithms with complexity $2^{(1-c)n/2}$ for some constant $c>0$. This suggested a super-quadratic quantum advantage over classical algorithms. In this work, we identify an explicit classical mechanism underlying a substantial part of this line of work, and show that it leads to clean dequantizations. As a consequence, we obtain classical algorithms that run in time $2^{(1-c')n}$, for some constant $c'>c$, for the same classes of constraint satisfaction problems. This shows that current short-path quantum algorithms for these problems do not achieve a super-quadratic advantage. On the positive side, our results provide a new ``quantum-inspired'' approach to designing classical algorithms for important classes of constraint satisfaction problems.

quant-pharXiv:2604.12131•Apr 15, 2026•0 citations

Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization

Shouvanik Chakrabarti, Dylan Herman, Guneykan Ozgul +6 more

We analyze generalizations of quantum algorithms based on the short path framework first proposed by Hastings~[\textit{Quantum} 2, 78 (2018)], which has been extended and shown by Dalzell~et~al.~[STOC~'23] to achieve super-Grover speedups for certain binary optimization problems. We demonstrate that, under some commonly satisfied technical conditions, an appropriate generalization can achieve super-quadratic speedups not only over unstructured search but also over a classical optimization algorithm that searches for the optimum by drawing samples from the stationary distribution of a Markov chain. We employ this framework to obtain algorithms for problems including variants of Max Bisection, Max Independent Set, and finding the ground states of the Antiferromagnetic Ising Model and the Sherrington-Kirkpatrick Model, whose runtimes are asymptotically faster than those obtainable with previous short path techniques. In certain cases, our algorithms achieve super-quadratic speedups compared to the best known classical algorithms with rigorously established runtimes.

arXiv:2410.23270•Oct 30, 2024•0 citations

Applying quantum algorithms to constraint satisfaction problems

Earl T. Campbell, Ankur Khurana, Ashley Montanaro

Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, there are few cases where a substantial quantum speedup has been worked out in detail for reasonably-sized problems, when compared with the best classical algorithms and taking into account realistic hardware parameters and overheads for fault-tolerance. All known examples of such speedups correspond to problems related to simulation of quantum systems and cryptography. Here we apply general-purpose quantum algorithms for solving constraint satisfaction problems to two families of prototypical NP-complete problems: boolean satisfiability and graph colouring. We consider two quantum approaches: Grover's algorithm and a quantum algorithm for accelerating backtracking algorithms. We compare the performance of optimised versions of these algorithms, when applied to random problem instances, against leading classical algorithms. Even when considering only problem instances that can be solved within one day, we find that there are potentially large quantum speedups available. In the most optimistic parameter regime we consider, this could be a factor of over 105 relative to a classical desktop computer; in the least optimistic regime, the speedup is reduced to a factor of over 103 . However, the number of physical qubits used is extremely large, and improved fault-tolerance methods will likely be needed to make these results practical. In particular, the quantum advantage disappears if one includes the cost of the classical processing power required to perform decoding of the surface code using current techniques.

arXiv:1810.05582•Quantum•Jul 18, 2019•76 citations

Local Algorithms and the Failure of Log-Depth Quantum Advantage on Sparse Random CSPs

Antares Chen, Neng Huang, Kunal Marwaha

We construct and analyze a message-passing algorithm for random constraint satisfaction problems (CSPs) at large clause density, generalizing work of El Alaoui, Montanari, and Sellke for Maximum Cut [arXiv:2111.06813] through a connection between random CSPs and mean-field Ising spin glasses. For CSPs with even predicates, the algorithm asymptotically solves a stochastic optimal control problem dual to an extended Parisi variational principle. This gives an optimal fraction of satisfied constraints among algorithms obstructed by the branching overlap gap property of Huang and Sellke [arXiv:2110.07847], notably including the Quantum Approximate Optimization Algorithm and all quantum circuits on a bounded-degree architecture of up to $ε\cdot \log n$ depth.

arXiv:2310.01563•Leibniz international proceedings in informatics•Oct 2, 2023•1 citation

A Short Path Quantum Algorithm for Exact Optimization

M. B. Hastings

We give a quantum algorithm to exactly solve certain problems in combinatorial optimization, including weighted MAX-2-SAT as well as problems where the objective function is a weighted sum of products of Ising variables, all terms of the same degree D ; this problem is called weighted MAX-E D -LIN2. We require that the optimal solution be unique for odd D and doubly degenerate for even D ; however, we expect that the algorithm still works without this condition and we show how to reduce to the case without this assumption at the cost of an additional overhead. While the time required is still exponential, the algorithm provably outperforms Grover's algorithm assuming a mild condition on the number of low energy states of the target Hamiltonian. The detailed analysis of the runtime dependence on a tradeoff between the number of such states and algorithm speed: fewer such states allows a greater speedup. This leads to a natural hybrid algorithm that finds either an exact or approximate solution.

arXiv:1802.10124•Quantum•Jul 26, 2018•17 citations

Quantum-Enhanced Algorithm Design for Constraint Satisfaction Problems

Jincheng Zhang

Constraint satisfaction problems (CSPs) represent a fundamental class of NP-complete problems that pose significant challenges for classical computation, particularly as problem instances grow in size. This work investigates the application of quantum computing techniques – specifically quantum annealing and quantum walks – to accelerate the solution process for CSPs. The core idea involves mapping the CSP to an equivalent quantum Ising model. This model is then targeted for solution via quantum annealing, exploiting quantum tunneling to escape local minima and explore the solution space. Furthermore, quantum walk algorithms are explored for efficient solution space traversal. The potential for achieving speedups over traditional CSP solvers is examined, highlighting the promise of quantum computing for tackling computationally intensive combinatorial optimization problems. The research focuses on the theoretical design and analysis of these quantum algorithms, without requiring experimental validation. The primary outcome is a framework for designing quantum algorithms tailored to specific CSP instances, providing a foundation for future research and potential implementation.

•Sep 3, 2026•0 citations
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*(2(0.5−c)n) for an n-independent constant c, a 2cn advantage over Grover’s algorithm; or (b) there are sufficiently many low-cost solutions such that classical random guessing produces a (1−η) approximation to the optimal cost value in sub-exponential time for arbitrarily small choice of η. Additionally, we show that for a large fraction of random instances from the k-spin model and for any fully satisfiable or slightly frustrated k-CSP formula, statement (a) is the case. The algorithm and its analysis are largely inspired by Hastings’ short-path algorithm.
The short-path quantum algorithm introduced by Hastings (Quantum 2018, 2019) is a variant of adiabatic quantum algorithms that enables an easier worst-case analysis by avoiding the need to control the spectral gap along a long adiabatic path. Dalzell, Pancotti, Campbell, and Brandão (STOC 2023) recently revisited this framework and obtained a clear analysis of the complexity of the short-path algorithm for several classes of constraint satisfaction problems (MAX-kkk-CSPs), leading to quantum algorithms with complexity 2(1−c)n/22^{(1-c)n/2}2(1−c)n/2 for some constant c>0c>0c>0. This suggested a super-quadratic quantum advantage over classical algorithms. In this work, we identify an explicit classical mechanism underlying a substantial part of this line of work, and show that it leads to clean dequantizations. As a consequence, we obtain classical algorithms that run in time 2(1−c′)n2^{(1-c')n}2(1−c′)n, for some constant c′>cc'>cc′>c, for the same classes of constraint satisfaction problems. This shows that current short-path quantum algorithms for these problems do not achieve a super-quadratic advantage. On the positive side, our results provide a new ``quantum-inspired'' approach to designing classical algorithms for important classes of constraint satisfaction problems.
We analyze generalizations of quantum algorithms based on the short path framework first proposed by Hastings~[\textit{Quantum} 2, 78 (2018)], which has been extended and shown by Dalzell~et~al.~[STOC~'23] to achieve super-Grover speedups for certain binary optimization problems. We demonstrate that, under some commonly satisfied technical conditions, an appropriate generalization can achieve super-quadratic speedups not only over unstructured search but also over a classical optimization algorithm that searches for the optimum by drawing samples from the stationary distribution of a Markov chain. We employ this framework to obtain algorithms for problems including variants of Max Bisection, Max Independent Set, and finding the ground states of the Antiferromagnetic Ising Model and the Sherrington-Kirkpatrick Model, whose runtimes are asymptotically faster than those obtainable with previous short path techniques. In certain cases, our algorithms achieve super-quadratic speedups compared to the best known classical algorithms with rigorously established runtimes.
Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, there are few cases where a substantial quantum speedup has been worked out in detail for reasonably-sized problems, when compared with the best classical algorithms and taking into account realistic hardware parameters and overheads for fault-tolerance. All known examples of such speedups correspond to problems related to simulation of quantum systems and cryptography. Here we apply general-purpose quantum algorithms for solving constraint satisfaction problems to two families of prototypical NP-complete problems: boolean satisfiability and graph colouring. We consider two quantum approaches: Grover's algorithm and a quantum algorithm for accelerating backtracking algorithms. We compare the performance of optimised versions of these algorithms, when applied to random problem instances, against leading classical algorithms. Even when considering only problem instances that can be solved within one day, we find that there are potentially large quantum speedups available. In the most optimistic parameter regime we consider, this could be a factor of over 105 relative to a classical desktop computer; in the least optimistic regime, the speedup is reduced to a factor of over 103 . However, the number of physical qubits used is extremely large, and improved fault-tolerance methods will likely be needed to make these results practical. In particular, the quantum advantage disappears if one includes the cost of the classical processing power required to perform decoding of the surface code using current techniques.
We construct and analyze a message-passing algorithm for random constraint satisfaction problems (CSPs) at large clause density, generalizing work of El Alaoui, Montanari, and Sellke for Maximum Cut [arXiv:2111.06813] through a connection between random CSPs and mean-field Ising spin glasses. For CSPs with even predicates, the algorithm asymptotically solves a stochastic optimal control problem dual to an extended Parisi variational principle. This gives an optimal fraction of satisfied constraints among algorithms obstructed by the branching overlap gap property of Huang and Sellke [arXiv:2110.07847], notably including the Quantum Approximate Optimization Algorithm and all quantum circuits on a bounded-degree architecture of up to ε⋅log⁡nε\cdot \log nε⋅logn depth.
We give a quantum algorithm to exactly solve certain problems in combinatorial optimization, including weighted MAX-2-SAT as well as problems where the objective function is a weighted sum of products of Ising variables, all terms of the same degree D ; this problem is called weighted MAX-E D -LIN2. We require that the optimal solution be unique for odd D and doubly degenerate for even D ; however, we expect that the algorithm still works without this condition and we show how to reduce to the case without this assumption at the cost of an additional overhead. While the time required is still exponential, the algorithm provably outperforms Grover's algorithm assuming a mild condition on the number of low energy states of the target Hamiltonian. The detailed analysis of the runtime dependence on a tradeoff between the number of such states and algorithm speed: fewer such states allows a greater speedup. This leads to a natural hybrid algorithm that finds either an exact or approximate solution.
Constraint satisfaction problems (CSPs) represent a fundamental class of NP-complete problems that pose significant challenges for classical computation, particularly as problem instances grow in size. This work investigates the application of quantum computing techniques – specifically quantum annealing and quantum walks – to accelerate the solution process for CSPs. The core idea involves mapping the CSP to an equivalent quantum Ising model. This model is then targeted for solution via quantum annealing, exploiting quantum tunneling to escape local minima and explore the solution space. Furthermore, quantum walk algorithms are explored for efficient solution space traversal. The potential for achieving speedups over traditional CSP solvers is examined, highlighting the promise of quantum computing for tackling computationally intensive combinatorial optimization problems. The research focuses on the theoretical design and analysis of these quantum algorithms, without requiring experimental validation. The primary outcome is a framework for designing quantum algorithms tailored to specific CSP instances, providing a foundation for future research and potential implementation.