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

Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems

Thorge Müller, Ajainderpal Singh, Frank K. Wilhelm, Tim Bode

Published May 19, 2025• 12 citations
arXivHTMLPDF

Abstract

The ability of the quantum approximate optimization algorithm (QAOA) to deliver a quantum advantage on combinatorial optimization problems is still unclear. Recently, a scaling advantage over a classical solver was postulated to exist for random 8-SAT at the satisfiability threshold. At the same time, the viability of quantum error mitigation for deep circuits on near-term devices has been put into doubt. Here we analyze the QAOA's performance on random Max- k XOR as a function of k and the clause-to-variable ratio. As a classical benchmark, we use the mean-field approximate optimization algorithm and find that it performs better than or equal to the QAOA on average. Still, for large k and numbers of layers p , there may remain a window of opportunity for the QAOA. However, by extrapolating our numerical results, we find that reaching high levels of satisfaction would require extremely large p , which must be considered rather difficult both in the variational context and on near-term devices.

DOI
10.1103/physrevresearch.7.023165

Related papers

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

On the power of the Quantum Approximate Optimization Algorithm

Sami Boulebnane

The main object of study of this work is the Quantum Approximate Optimization Algorithm (QAOA) —the best-known heuristic quantum algorithm for addressing combinatorial optimization problems. Despite its popularity, QAOA poses major challenges. Namely, its performance remains poorly understood, especially in the low depth regime most relevant to near-term quantum computing. Besides, the algorithm is of variational nature, relying on several hyperparameters to be classically trained. In this work, we contribute to addressing these issues by developing techniques to understand the performance of QAOA at low depth, and deducing from these pretrained hyperparameters, thereby eliminating or considerably reducing the need for a classical optimization loop. We first consider applying QAOA to constraint satisfaction problems with the goal of maximizing the algorithm’s approximation ratio (fraction of satisfied constraints). As a particular example, we consider QAOA applied to MAXCUT on non-regular graphs, showing how analytic techniques provide good guess hyperparameters in this setting. Next, we analyze the performance of QAOA on a well-studied constraint satisfaction problem: random k-SAT. In this case, the performance is measured by the probability of finding an assignment satisfying all constraints (“success probability”). To estimate this quantity, we develop new techniques, mapping quantum expectation values of the QAOA circuits to classical spin models. We further show how these techniques can be generalized to a larger family of random constraint satisfaction problems. We conclude the work by two feasibility studies inspired by real-world use cases encountered in collaborations with industrial partners: peptide sampling, and solving flow problems. These problems are naturally phrased by encoding combinatorial variables in qudits, a relatively unexplored setting in the existing literature. We present partial analytic and numerical results for optimal QAOA hyperparameters and the scaling of its success probability in this framework, underlining potential specific difficulties when using QAOA with qudits.

•Nov 28, 2024•0 citations

Solution of SAT problems with the adaptive-bias quantum approximate optimization algorithm

Yunlong Yu, Chenfeng Cao, Xiang‐Bin Wang +2 more

The quantum approximate optimization algorithm (QAOA) is a promising method for solving certain classical combinatorial optimization problems on near-term quantum devices. When employing the QAOA to 3-SAT and Max-3-SAT problems, the quantum cost exhibits an easy-hard-easy or easy-hard pattern, respectively, as the clause density is changed. The quantum resources needed in the hard-region problems are out of reach for current noisy intermediate-scale quantum (NISQ) devices. We show by numerical simulations with up to 14 variables and analytical arguments that the adaptive-bias QAOA (ab-QAOA) greatly improves performance in the hard region of the 3-SAT problems and hard region of the Max-3-SAT problems. For similar accuracy, on average, ab-QAOA needs 3 levels for 10-variable 3-SAT problems as compared to 22 for QAOA. For 10-variable Max-3-SAT problems, the numbers are 7 levels and 62 levels. The improvement comes from a more targeted and more limited generation of entanglement during the evolution. We demonstrate that classical optimization is not strictly necessary in the ab-QAOA since local fields are used to guide the evolution. This leads us to propose an optimization-free ab-QAOA that can solve the hard-region 3-SAT and Max-3-SAT problems effectively with significantly fewer quantum gates as compared to the original ab-QAOA. Our work paves the way for realizing quantum advantages for optimization problems on NISQ devices.

arXiv:2210.02822•Physical Review Research•Jun 2, 2023•21 citations

Quantum Approximate Optimisation for Not-All-Equal SAT

Andrew El-Kadi, Roberto Bondesan

Establishing quantum advantage for variational quantum algorithms is an important direction in quantum computing. In this work, we apply the Quantum Approximate Optimisation Algorithm (QAOA) -- a popular variational quantum algorithm for general combinatorial optimisation problems -- to a variant of the satisfiability problem (SAT): Not-All-Equal SAT (NAE-SAT). We focus on regimes where the problems are known to have solutions with low probability and introduce a novel classical solver that outperforms existing solvers. Extensively benchmarking QAOA against this, we show that while the runtime of both solvers scales exponentially with the problem size, the scaling exponent for QAOA is smaller for large enough circuit depths. This implies a polynomial quantum speedup for solving NAE-SAT.

arXiv:2401.02852•Jan 5, 2024•1 citation

Scaling quantum approximate optimization on near-term hardware

Phillip C. Lotshaw, Thien Nguyen, Anthony Santana +5 more

The quantum approximate optimization algorithm (QAOA) is an approach for near-term quantum computers to potentially demonstrate computational advantage in solving combinatorial optimization problems. However, the viability of the QAOA depends on how its performance and resource requirements scale with problem size and complexity for realistic hardware implementations. Here, we quantify scaling of the expected resource requirements by synthesizing optimized circuits for hardware architectures with varying levels of connectivity. Assuming noisy gate operations, we estimate the number of measurements needed to sample the output of the idealized QAOA circuit with high probability. We show the number of measurements, and hence total time to solution, grows exponentially in problem size and problem graph degree as well as depth of the QAOA ansatz, gate infidelities, and inverse hardware graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.

arXiv:2201.02247•Scientific Reports•Jul 20, 2022•46 citations

Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

Leo Zhou, Sheng-Tao Wang, Soonwon Choi +2 more

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.

arXiv:1812.01041•Physical Review X•Jun 24, 2020•1,132 citations
The ability of the quantum approximate optimization algorithm (QAOA) to deliver a quantum advantage on combinatorial optimization problems is still unclear. Recently, a scaling advantage over a classical solver was postulated to exist for random 8-SAT at the satisfiability threshold. At the same time, the viability of quantum error mitigation for deep circuits on near-term devices has been put into doubt. Here we analyze the QAOA's performance on random Max- k XOR as a function of k and the clause-to-variable ratio. As a classical benchmark, we use the mean-field approximate optimization algorithm and find that it performs better than or equal to the QAOA on average. Still, for large k and numbers of layers p , there may remain a window of opportunity for the QAOA. However, by extrapolating our numerical results, we find that reaching high levels of satisfaction would require extremely large p , which must be considered rather difficult both in the variational context and on near-term devices.
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
The main object of study of this work is the Quantum Approximate Optimization Algorithm (QAOA) —the best-known heuristic quantum algorithm for addressing combinatorial optimization problems. Despite its popularity, QAOA poses major challenges. Namely, its performance remains poorly understood, especially in the low depth regime most relevant to near-term quantum computing. Besides, the algorithm is of variational nature, relying on several hyperparameters to be classically trained. In this work, we contribute to addressing these issues by developing techniques to understand the performance of QAOA at low depth, and deducing from these pretrained hyperparameters, thereby eliminating or considerably reducing the need for a classical optimization loop. We first consider applying QAOA to constraint satisfaction problems with the goal of maximizing the algorithm’s approximation ratio (fraction of satisfied constraints). As a particular example, we consider QAOA applied to MAXCUT on non-regular graphs, showing how analytic techniques provide good guess hyperparameters in this setting. Next, we analyze the performance of QAOA on a well-studied constraint satisfaction problem: random k-SAT. In this case, the performance is measured by the probability of finding an assignment satisfying all constraints (“success probability”). To estimate this quantity, we develop new techniques, mapping quantum expectation values of the QAOA circuits to classical spin models. We further show how these techniques can be generalized to a larger family of random constraint satisfaction problems. We conclude the work by two feasibility studies inspired by real-world use cases encountered in collaborations with industrial partners: peptide sampling, and solving flow problems. These problems are naturally phrased by encoding combinatorial variables in qudits, a relatively unexplored setting in the existing literature. We present partial analytic and numerical results for optimal QAOA hyperparameters and the scaling of its success probability in this framework, underlining potential specific difficulties when using QAOA with qudits.
The quantum approximate optimization algorithm (QAOA) is a promising method for solving certain classical combinatorial optimization problems on near-term quantum devices. When employing the QAOA to 3-SAT and Max-3-SAT problems, the quantum cost exhibits an easy-hard-easy or easy-hard pattern, respectively, as the clause density is changed. The quantum resources needed in the hard-region problems are out of reach for current noisy intermediate-scale quantum (NISQ) devices. We show by numerical simulations with up to 14 variables and analytical arguments that the adaptive-bias QAOA (ab-QAOA) greatly improves performance in the hard region of the 3-SAT problems and hard region of the Max-3-SAT problems. For similar accuracy, on average, ab-QAOA needs 3 levels for 10-variable 3-SAT problems as compared to 22 for QAOA. For 10-variable Max-3-SAT problems, the numbers are 7 levels and 62 levels. The improvement comes from a more targeted and more limited generation of entanglement during the evolution. We demonstrate that classical optimization is not strictly necessary in the ab-QAOA since local fields are used to guide the evolution. This leads us to propose an optimization-free ab-QAOA that can solve the hard-region 3-SAT and Max-3-SAT problems effectively with significantly fewer quantum gates as compared to the original ab-QAOA. Our work paves the way for realizing quantum advantages for optimization problems on NISQ devices.
Establishing quantum advantage for variational quantum algorithms is an important direction in quantum computing. In this work, we apply the Quantum Approximate Optimisation Algorithm (QAOA) -- a popular variational quantum algorithm for general combinatorial optimisation problems -- to a variant of the satisfiability problem (SAT): Not-All-Equal SAT (NAE-SAT). We focus on regimes where the problems are known to have solutions with low probability and introduce a novel classical solver that outperforms existing solvers. Extensively benchmarking QAOA against this, we show that while the runtime of both solvers scales exponentially with the problem size, the scaling exponent for QAOA is smaller for large enough circuit depths. This implies a polynomial quantum speedup for solving NAE-SAT.
The quantum approximate optimization algorithm (QAOA) is an approach for near-term quantum computers to potentially demonstrate computational advantage in solving combinatorial optimization problems. However, the viability of the QAOA depends on how its performance and resource requirements scale with problem size and complexity for realistic hardware implementations. Here, we quantify scaling of the expected resource requirements by synthesizing optimized circuits for hardware architectures with varying levels of connectivity. Assuming noisy gate operations, we estimate the number of measurements needed to sample the output of the idealized QAOA circuit with high probability. We show the number of measurements, and hence total time to solution, grows exponentially in problem size and problem graph degree as well as depth of the QAOA ansatz, gate infidelities, and inverse hardware graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.