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

Computational phase transition in Quantum Approximate Optimization Algorithm -- the difference between hard and easy

Bingzhi Zhang, Quntao Zhuang

Published Sep 27, 2021• 0 citations
OpenAlex

Abstract

Quantum Approximate Optimization algorithm (QAOA) is one of the candidates to achieve a near-term quantum advantage. As QAOA seems only capable of solving optimization problems, there is a folklore that QAOA cannot see the difference between easy problems such as 2-SAT and hard problems such as 3-SAT -- although 2-SAT is in the polynomial-time (P) class, its optimization version is also nondeterministic polynomial-time (NP)-hard. In this paper, we show that the folklore is not true. We find a computational phase transition in QAOA when solving a variant of 3-SAT -- the amplitude of gradient and the success probability achieve their minimum at the well-known SAT-UNSAT phase transition. On the contrary, for 2-SAT, such a phenomenon is absent at SAT-UNSAT phase transition and the success probability is unity for a reasonable circuit depth. We connect the gradient transition to the dynamical Lie algebra of the QAOA circuit. In solving the NP-hard optimization versions of SAT, we identify quantum advantages over a classical approximate algorithm at quite a shallow depth of $p=4$ for the problem size of $n=10$.

Related papers

Quantum computational phase transition in combinatorial problems

Bingzhi Zhang, Akira Sone, Quntao Zhuang

Abstract Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.

arXiv:2109.13346•npj Quantum Information•Jul 22, 2022•26 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•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•57 citations

Evaluating QAOA expectation values can be as hard as counting optimal solutions

Stuart Hadfield

Evaluating expectation values is a critical task for variational quantum eigensolvers, parameterized quantum circuits, and many other quantum algorithms. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth $p\geq 2$, complementing past results showing efficiently computable formulas for $p=1$ with arbitrary problem graphs. We sharpen this dichotomy showing that for $p\geq 2$ exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at $p\geq 2$ is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from $p=1$ to $p=2$ is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.

quant-pharXiv:2608.11385•Aug 13, 2026•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•17 citations

Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem

Gavin E. Crooks

The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.

arXiv:1811.08419•Bulletin of the American Physical Society•Nov 20, 2018•158 citations
Quantum Approximate Optimization algorithm (QAOA) is one of the candidates to achieve a near-term quantum advantage. As QAOA seems only capable of solving optimization problems, there is a folklore that QAOA cannot see the difference between easy problems such as 2-SAT and hard problems such as 3-SAT -- although 2-SAT is in the polynomial-time (P) class, its optimization version is also nondeterministic polynomial-time (NP)-hard. In this paper, we show that the folklore is not true. We find a computational phase transition in QAOA when solving a variant of 3-SAT -- the amplitude of gradient and the success probability achieve their minimum at the well-known SAT-UNSAT phase transition. On the contrary, for 2-SAT, such a phenomenon is absent at SAT-UNSAT phase transition and the success probability is unity for a reasonable circuit depth. We connect the gradient transition to the dynamical Lie algebra of the QAOA circuit. In solving the NP-hard optimization versions of SAT, we identify quantum advantages over a classical approximate algorithm at quite a shallow depth of p=4p=4p=4 for the problem size of n=10n=10n=10.
Abstract Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.
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.
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
Evaluating expectation values is a critical task for variational quantum eigensolvers, parameterized quantum circuits, and many other quantum algorithms. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth p≥2p\geq 2p≥2, complementing past results showing efficiently computable formulas for p=1p=1p=1 with arbitrary problem graphs. We sharpen this dichotomy showing that for p≥2p\geq 2p≥2 exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at p≥2p\geq 2p≥2 is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from p=1p=1p=1 to p=2p=2p=2 is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.