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:2206.06876 · Physical Review Research

Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms

Puya Mirkarimi, Adam Callison, Lewis Light, Nicholas Chancellor, Viv M. Kendon

Published Jun 5, 2023• 9 citations
arXivHTMLPDF

Abstract

An algorithm for a particular problem may find some instances of the problem easier and others harder to solve, even for a fixed input size. We numerically analyze the relative hardness of MAX 2-SAT problem instances for various continuous-time quantum algorithms and a comparable classical algorithm. This has two motivations: To investigate whether small-sized problem instances, which are commonly used in numerical simulations of quantum algorithms for benchmarking purposes, are a good representation of larger instances in terms of their hardness to solve, and to determine the applicability of continuous-time quantum algorithms in a portfolio approach, where we take advantage of the variation in the hardness of instances between different algorithms by running them in parallel. We find that, while there are correlations in instance hardness between all of the algorithms considered, they appear weak enough that a portfolio approach would likely be desirable in practice. Our results also show a widening range of hardness of randomly generated instances as the problem size is increased, which demonstrates both the difference in the distribution of hardness at small sizes and the value of a portfolio approach that can reduce the number of extremely hard instances. We identify specific weaknesses of these quantum algorithms that can be overcome with a portfolio approach, such their inability to efficiently solve satisfiable instances (which is easy classically).

DOI
10.1103/physrevresearch.5.023151

Related papers

A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.

arXiv:quant-ph/0007071•Jul 19, 2000•74 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•92 citations

Training a quantum optimizer

Dave Wecker, Matthew B. Hastings, Matthias Troyer

We study a variant of the quantum approximate optimization algorithm [E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028] with a slightly different parametrization and a different objective: rather than looking for a state which approximately solves an optimization problem, our goal is to find a quantum algorithm that, given an instance of the maximum 2-satisfiability problem (MAX-2-SAT), will produce a state with high overlap with the optimal state. Using a machine learning approach, we chose a ``training set'' of instances and optimized the parameters to produce a large overlap for the training set. We then tested these optimized parameters on a larger instance set. As a training set, we used a subset of the hard instances studied by Crosson, Farhi, C. Y.-Y. Lin, H.-H. Lin, and P. Shor (CFLLS) (arXiv:1401.7320). When tested, on the full set, the parameters that we find produce a significantly larger overlap than the optimized annealing times of CFLLS. Testing on other random instances from 20 to 28 bits continues to show improvement over annealing, with the improvement being most notable on the hardest instances. Further tests on instances of MAX-3-SAT also showed improvement on the hardest instances. This algorithm may be a possible application for near-term quantum computers with limited coherence times.

arXiv:1605.05370•Physical Review A•Aug 10, 2016•97 citations

Scaling of the running time of the quantum adiabatic algorithm for propositional satisfiability

Marko Žnidarič

We numerically study the quantum adiabatic algorithm for propositional satisfiability. A new class of previously unknown hard instances is identified among random problems. We numerically find that the running time for such instances grows exponentially with their size. The worst case complexity of the quantum adiabatic algorithm therefore seems to be exponential.

arXiv:quant-ph/0502077•Physical Review A•Jun 8, 2005•37 citations

Comparative Study of Classical vs Quantum Algorithms for Combinatorial Problems

Daniel Popescu, Helena Petrov

Claims of quantum advantage for combinatorial optimisation require rigorous comparison against state-of-the-art classical algorithms under controlled experimental conditions -- yet the quantum computing literature frequently benchmarks quantum methods against weak classical baselines such as greedy heuristics or random search, inflating apparent quantum advantage. This paper presents the Quantum-Classical Combinatorial Benchmark (QCCB), a rigorous comparative study of quantum optimisation algorithms (QAOA, VQE-QUBO, hybrid QA) against nine state-of-the-art classical algorithms (Goemans-Williamson SDP, simulated annealing, tabu search, CPLEX branch-and-bound, OR-Tools CP-SAT, Gurobi MIP, Benders decomposition, extremal optimisation, and population-based iterated local search) across six canonical combinatorial problem classes (MaxCut, Vertex Cover, Graph Colouring, Knapsack, Set Cover, and Weighted Max-SAT) at problem sizes n = 12 to n = 256. QCCB finds that no quantum algorithm consistently outperforms all classical baselines across all problem classes at current NISQ scale. QAOA with QOAS adaptive depth (Bianchi, 2024) outperforms all nine classical algorithms on MaxCut at n = 48 (approximation ratio 0.924 vs. GW 0.878). However, classical Gurobi MIP and CPLEX solve MaxCut exactly for n up to n = 84 within the same time budget, eliminating the QAOA advantage at moderate scale. QCCB provides nuanced guidance on problem classes, instance sizes, and time budgets where quantum algorithms offer genuine near-term advantage.

Quantum Frontiers Journal•Mar 28, 2024•0 citations

Solving Boolean Satisfiability Problems With The Quantum Approximate Optimization Algorithm

Sami Boulebnane, Ashley Montanaro

One of the most prominent application areas for quantum computers is solving hard constraint satisfaction and optimization problems. However, detailed analyses of the complexity of standard quantum algorithms have suggested that outperforming classical methods for these problems would require extremely large and powerful quantum computers. The quantum approximate optimization algorithm (QAOA) is designed for near-term quantum computers, yet previous work has shown strong limitations on the ability of QAOA to outperform classical algorithms for optimization problems. Here we instead apply QAOA to hard constraint satisfaction problems, where both classical and quantum algorithms are expected to require exponential time. We analytically characterize the average success probability of QAOA on a constraint satisfaction problem commonly studied using statistical physics methods: random k -SAT at the threshold for satisfiability, as the number of variables n goes to infinity. We complement these theoretical results with numerical experiments on the performance of QAOA for small n , which match the limiting theoretical bounds closely. We then compare QAOA with leading classical solvers. For random 8-SAT, we find that for more than 14 quantum circuit layers, QAOA achieves more efficient scaling than the highest-performance classical solver we tested, WalkSATlm. Our results suggest that near-term quantum algorithms for solving constraint satisfaction problems may outperform their classical counterparts. Published by the American Physical Society 2024

arXiv:2208.06909•PRX Quantum•Sep 10, 2024•114 citations
An algorithm for a particular problem may find some instances of the problem easier and others harder to solve, even for a fixed input size. We numerically analyze the relative hardness of MAX 2-SAT problem instances for various continuous-time quantum algorithms and a comparable classical algorithm. This has two motivations: To investigate whether small-sized problem instances, which are commonly used in numerical simulations of quantum algorithms for benchmarking purposes, are a good representation of larger instances in terms of their hardness to solve, and to determine the applicability of continuous-time quantum algorithms in a portfolio approach, where we take advantage of the variation in the hardness of instances between different algorithms by running them in parallel. We find that, while there are correlations in instance hardness between all of the algorithms considered, they appear weak enough that a portfolio approach would likely be desirable in practice. Our results also show a widening range of hardness of randomly generated instances as the problem size is increased, which demonstrates both the difference in the distribution of hardness at small sizes and the value of a portfolio approach that can reduce the number of extremely hard instances. We identify specific weaknesses of these quantum algorithms that can be overcome with a portfolio approach, such their inability to efficiently solve satisfiable instances (which is easy classically).
Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.
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 study a variant of the quantum approximate optimization algorithm [E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028] with a slightly different parametrization and a different objective: rather than looking for a state which approximately solves an optimization problem, our goal is to find a quantum algorithm that, given an instance of the maximum 2-satisfiability problem (MAX-2-SAT), will produce a state with high overlap with the optimal state. Using a machine learning approach, we chose a ``training set'' of instances and optimized the parameters to produce a large overlap for the training set. We then tested these optimized parameters on a larger instance set. As a training set, we used a subset of the hard instances studied by Crosson, Farhi, C. Y.-Y. Lin, H.-H. Lin, and P. Shor (CFLLS) (arXiv:1401.7320). When tested, on the full set, the parameters that we find produce a significantly larger overlap than the optimized annealing times of CFLLS. Testing on other random instances from 20 to 28 bits continues to show improvement over annealing, with the improvement being most notable on the hardest instances. Further tests on instances of MAX-3-SAT also showed improvement on the hardest instances. This algorithm may be a possible application for near-term quantum computers with limited coherence times.
Claims of quantum advantage for combinatorial optimisation require rigorous comparison against state-of-the-art classical algorithms under controlled experimental conditions -- yet the quantum computing literature frequently benchmarks quantum methods against weak classical baselines such as greedy heuristics or random search, inflating apparent quantum advantage. This paper presents the Quantum-Classical Combinatorial Benchmark (QCCB), a rigorous comparative study of quantum optimisation algorithms (QAOA, VQE-QUBO, hybrid QA) against nine state-of-the-art classical algorithms (Goemans-Williamson SDP, simulated annealing, tabu search, CPLEX branch-and-bound, OR-Tools CP-SAT, Gurobi MIP, Benders decomposition, extremal optimisation, and population-based iterated local search) across six canonical combinatorial problem classes (MaxCut, Vertex Cover, Graph Colouring, Knapsack, Set Cover, and Weighted Max-SAT) at problem sizes n = 12 to n = 256. QCCB finds that no quantum algorithm consistently outperforms all classical baselines across all problem classes at current NISQ scale. QAOA with QOAS adaptive depth (Bianchi, 2024) outperforms all nine classical algorithms on MaxCut at n = 48 (approximation ratio 0.924 vs. GW 0.878). However, classical Gurobi MIP and CPLEX solve MaxCut exactly for n up to n = 84 within the same time budget, eliminating the QAOA advantage at moderate scale. QCCB provides nuanced guidance on problem classes, instance sizes, and time budgets where quantum algorithms offer genuine near-term advantage.
One of the most prominent application areas for quantum computers is solving hard constraint satisfaction and optimization problems. However, detailed analyses of the complexity of standard quantum algorithms have suggested that outperforming classical methods for these problems would require extremely large and powerful quantum computers. The quantum approximate optimization algorithm (QAOA) is designed for near-term quantum computers, yet previous work has shown strong limitations on the ability of QAOA to outperform classical algorithms for optimization problems. Here we instead apply QAOA to hard constraint satisfaction problems, where both classical and quantum algorithms are expected to require exponential time. We analytically characterize the average success probability of QAOA on a constraint satisfaction problem commonly studied using statistical physics methods: random k -SAT at the threshold for satisfiability, as the number of variables n goes to infinity. We complement these theoretical results with numerical experiments on the performance of QAOA for small n , which match the limiting theoretical bounds closely. We then compare QAOA with leading classical solvers. For random 8-SAT, we find that for more than 14 quantum circuit layers, QAOA achieves more efficient scaling than the highest-performance classical solver we tested, WalkSATlm. Our results suggest that near-term quantum algorithms for solving constraint satisfaction problems may outperform their classical counterparts. Published by the American Physical Society 2024