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

Physical Review A

Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs

Jonathan Wurtz, Danylo Lykov

Published Nov 17, 2021• 68 citations
Publisher

Abstract

The quantum approximate optimization algorithm (QAOA) is a near-term combinatorial optimization algorithm suitable for noisy quantum devices. However, little is known about performance guarantees for $p>2$. A recent work computing MaxCut performance guarantees for 3-regular graphs conjectures that any $d$-regular graph evaluated at particular fixed angles has an approximation ratio greater than some worst-case guarantee. In this work, we provide numerical evidence for this fixed angle conjecture for $p<12$. We compute and provide these angles via numerical optimization and tensor networks. These fixed angles serve for an optimization-free version of QAOA and have universally good performance on any 3-regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are ``close'' to global optimum. Under the fixed angle conjecture, QAOA has a larger performance guarantee than the Goemans Williamson algorithm on 3-regular graphs for $p\ensuremath{\ge}11$.

DOI
10.1103/physreva.104.052419

Related papers

The fixed angle conjecture for QAOA on regular MaxCut graphs

Jonathan Wurtz, Danylo Lykov

The quantum approximate optimization algorithm (QAOA) is a near-term combinatorial optimization algorithm suitable for noisy quantum devices. However, little is known about performance guarantees for $p>2$. A recent work \cite{Wurtz_guarantee} computing MaxCut performance guarantees for 3-regular graphs conjectures that any $d$-regular graph evaluated at particular fixed angles has an approximation ratio greater than some worst-case guarantee. In this work, we provide numerical evidence for this fixed angle conjecture for $p<12$. We compute and provide these angles via numerical optimization and tensor networks. These fixed angles serve for an optimization-free version of QAOA, and have universally good performance on any 3 regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are ``close" to global optimum. Under the fixed angle conjecture, QAOA has a larger performance guarantee than the Goemans Williamson algorithm on 3-regular graphs for $p\geq 11$.

arXiv:2107.00677•Jul 1, 2021•11 citations

MaxCut quantum approximate optimization algorithm performance guarantees for p>1

Jonathan Wurtz, Peter J. Love

We obtain worst-case performance guarantees for $p=2$ and 3 QAOA for MaxCut on uniform 3-regular graphs. Previous work by Farhi et al. obtained a lower bound on the approximation ratio of 0.692 for $p=1$. We find a lower bound of 0.7559 for $p=2$, where worst-case graphs are those with no cycles $\ensuremath{\le}5$. This bound holds for any 3-regular graph evaluated at particular fixed parameters. We conjecture a hierarchy for all $p$, where worst-case graphs have with no cycles $\ensuremath{\le}2p+1$. Under this conjecture, the approximation ratio is at least 0.7924 for all 3-regular graphs and $p=3$. In addition, using an indistinguishable argument we find an upper bound on the worst-case approximation ratio for all $p$, which indicates classes of graphs for which there can be no quantum advantage for at least $p<6$.

arXiv:2010.11209•Physical Review A•Apr 27, 2021•103 citations

Refuting the QAOA fixed-angle conjecture

Lennart Binkowski

The fixed-angle conjecture for the quantum approximate optimisation algorithm (QAOA) is shown to be false for depth-2 QAOA on 9-regular graphs, and proven to be correct for depth-1 on any regular graph, as well as for any depth on all 2-regular graphs.

quant-pharXiv:2609.27703•Sep 24, 2026•0 citations

The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model

Joao Basso, Edward Farhi, Kunal Marwaha +2 more

The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to combinatorial optimization problems. Its performance monotonically improves with its depth $p$. We apply the QAOA to MaxCut on large-girth $D$-regular graphs. We give an iterative formula to evaluate performance for any $D$ at any depth $p$. Looking at random $D$-regular graphs, at optimal parameters and as $D$ goes to infinity, we find that the $p=11$ QAOA beats all classical algorithms (known to the authors) that are free of unproven conjectures. While the iterative formula for these $D$-regular graphs is derived by looking at a single tree subgraph, we prove that it also gives the ensemble-averaged performance of the QAOA on the Sherrington-Kirkpatrick (SK) model defined on the complete graph. We also generalize our formula to Max-$q$-XORSAT on large-girth regular hypergraphs. Our iteration is a compact procedure, but its computational complexity grows as $O(p^2 4^p)$. This iteration is more efficient than the previous procedure for analyzing QAOA performance on the SK model, and we are able to numerically go to $p=20$. Encouraged by our findings, we make the optimistic conjecture that the QAOA, as $p$ goes to infinity, will achieve the Parisi value. We analyze the performance of the quantum algorithm, but one needs to run it on a quantum computer to produce a string with the guaranteed performance.

arXiv:2110.14206•Leibniz international proceedings in informatics•Oct 27, 2021•43 citations

Bounds on MAXCUT QAOA performance for p>1

Jonathan Wurtz, Peter J. Love

We obtain worst case performance guarantees for $p=2$ and $3$ QAOA for MAXCUT on uniform 3-regular graphs. Previous work by Farhi et al obtained a lower bound on the approximation ratio of $0.692$ for $p=1$. We find a lower bound of $0.7559$ for $p=2$, where worst case graphs are those with no cycles $\leq 5$. This bound holds for any 3 regular graph evaluated at particular fixed parameters. We conjecture a hierarchy for all $p$, where worst case graphs have with no cycles $\leq 2p+1$. Under this conjecture, the approximation ratio is at least $0.7924$ for all 3 regular graphs and $p=3$. In addition, using a simple indistinguishability argument we find an upper bound on the worst case approximation ratio for all $p$, which indicates classes of graphs for which there can be no quantum advantage for at least $p<6$.

•Oct 21, 2020•11 citations

A Unified Complexity-Algorithm Account of Constant-Round QAOA Expectation Computation

Jingheng Wang, Shengminjie Chen, Xiaoming Sun +1 more

The Quantum Approximate Optimization Algorithm (QAOA) is widely studied for combinatorial optimization and has achieved significant advances both in theoretical guarantees and practical performance, yet for general combinatorial optimization problems the expected performance and classical simulability of fixed-round QAOA remain unclear. Focusing on Max-Cut, we first show that for general graphs and any fixed round $p\ge2$, exactly evaluating the expectation of fixed-round QAOA at prescribed angles is $\mathrm{NP}$-hard, and that approximating this expectation within additive error $2^{-O(n)}$ in the number $n$ of vertices is already $\mathrm{NP}$-hard. To evaluate the expected performance of QAOA, we propose a dynamic programming algorithm leveraging tree decomposition. As a byproduct, when the $p$-local treewidth grows at most logarithmically with the number of vertices, this yields a polynomial-time \emph{exact} evaluation algorithm in the graph size $n$. Beyond Max-Cut, we extend the framework to general Binary Unconstrained Combinatorial Optimization (BUCO). Finally, we provide reproducible evaluations for rounds up to $p=3$ on representative structured families, including the generalized Petersen graph $GP(15,2)$, double-layer triangular 2-lifts, and the truncated icosahedron graph $C_{60}$, and report cut ratios while benchmarking against locality-matched classical baselines.

quant-pharXiv:2511.20212•Nov 26, 2025•0 citations
The quantum approximate optimization algorithm (QAOA) is a near-term combinatorial optimization algorithm suitable for noisy quantum devices. However, little is known about performance guarantees for p>2p>2p>2. A recent work computing MaxCut performance guarantees for 3-regular graphs conjectures that any ddd-regular graph evaluated at particular fixed angles has an approximation ratio greater than some worst-case guarantee. In this work, we provide numerical evidence for this fixed angle conjecture for p<12p<12p<12. We compute and provide these angles via numerical optimization and tensor networks. These fixed angles serve for an optimization-free version of QAOA and have universally good performance on any 3-regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are ``close'' to global optimum. Under the fixed angle conjecture, QAOA has a larger performance guarantee than the Goemans Williamson algorithm on 3-regular graphs for p\ensuremath≥11p\ensuremath{\ge}11p\ensuremath≥11.
The quantum approximate optimization algorithm (QAOA) is a near-term combinatorial optimization algorithm suitable for noisy quantum devices. However, little is known about performance guarantees for p>2p>2p>2. A recent work \cite{Wurtz_guarantee} computing MaxCut performance guarantees for 3-regular graphs conjectures that any ddd-regular graph evaluated at particular fixed angles has an approximation ratio greater than some worst-case guarantee. In this work, we provide numerical evidence for this fixed angle conjecture for p<12p<12p<12. We compute and provide these angles via numerical optimization and tensor networks. These fixed angles serve for an optimization-free version of QAOA, and have universally good performance on any 3 regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are ``close" to global optimum. Under the fixed angle conjecture, QAOA has a larger performance guarantee than the Goemans Williamson algorithm on 3-regular graphs for p≥11p\geq 11p≥11.
We obtain worst-case performance guarantees for p=2p=2p=2 and 3 QAOA for MaxCut on uniform 3-regular graphs. Previous work by Farhi et al. obtained a lower bound on the approximation ratio of 0.692 for p=1p=1p=1. We find a lower bound of 0.7559 for p=2p=2p=2, where worst-case graphs are those with no cycles $\ensuremath{\le}5$. This bound holds for any 3-regular graph evaluated at particular fixed parameters. We conjecture a hierarchy for all ppp, where worst-case graphs have with no cycles $\ensuremath{\le}2p+1$. Under this conjecture, the approximation ratio is at least 0.7924 for all 3-regular graphs and p=3p=3p=3. In addition, using an indistinguishable argument we find an upper bound on the worst-case approximation ratio for all ppp, which indicates classes of graphs for which there can be no quantum advantage for at least p<6p<6p<6.
The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to combinatorial optimization problems. Its performance monotonically improves with its depth ppp. We apply the QAOA to MaxCut on large-girth DDD-regular graphs. We give an iterative formula to evaluate performance for any DDD at any depth ppp. Looking at random DDD-regular graphs, at optimal parameters and as DDD goes to infinity, we find that the p=11p=11p=11 QAOA beats all classical algorithms (known to the authors) that are free of unproven conjectures. While the iterative formula for these DDD-regular graphs is derived by looking at a single tree subgraph, we prove that it also gives the ensemble-averaged performance of the QAOA on the Sherrington-Kirkpatrick (SK) model defined on the complete graph. We also generalize our formula to Max-qqq-XORSAT on large-girth regular hypergraphs. Our iteration is a compact procedure, but its computational complexity grows as O(p24p)O(p^2 4^p)O(p24p). This iteration is more efficient than the previous procedure for analyzing QAOA performance on the SK model, and we are able to numerically go to p=20p=20p=20. Encouraged by our findings, we make the optimistic conjecture that the QAOA, as ppp goes to infinity, will achieve the Parisi value. We analyze the performance of the quantum algorithm, but one needs to run it on a quantum computer to produce a string with the guaranteed performance.
We obtain worst case performance guarantees for p=2p=2p=2 and 333 QAOA for MAXCUT on uniform 3-regular graphs. Previous work by Farhi et al obtained a lower bound on the approximation ratio of 0.6920.6920.692 for p=1p=1p=1. We find a lower bound of 0.75590.75590.7559 for p=2p=2p=2, where worst case graphs are those with no cycles ≤5\leq 5≤5. This bound holds for any 3 regular graph evaluated at particular fixed parameters. We conjecture a hierarchy for all ppp, where worst case graphs have with no cycles ≤2p+1\leq 2p+1≤2p+1. Under this conjecture, the approximation ratio is at least 0.79240.79240.7924 for all 3 regular graphs and p=3p=3p=3. In addition, using a simple indistinguishability argument we find an upper bound on the worst case approximation ratio for all ppp, which indicates classes of graphs for which there can be no quantum advantage for at least p<6p<6p<6.
The Quantum Approximate Optimization Algorithm (QAOA) is widely studied for combinatorial optimization and has achieved significant advances both in theoretical guarantees and practical performance, yet for general combinatorial optimization problems the expected performance and classical simulability of fixed-round QAOA remain unclear. Focusing on Max-Cut, we first show that for general graphs and any fixed round p≥2p\ge2p≥2, exactly evaluating the expectation of fixed-round QAOA at prescribed angles is NP\mathrm{NP}NP-hard, and that approximating this expectation within additive error 2−O(n)2^{-O(n)}2−O(n) in the number nnn of vertices is already NP\mathrm{NP}NP-hard. To evaluate the expected performance of QAOA, we propose a dynamic programming algorithm leveraging tree decomposition. As a byproduct, when the ppp-local treewidth grows at most logarithmically with the number of vertices, this yields a polynomial-time \emph{exact} evaluation algorithm in the graph size nnn. Beyond Max-Cut, we extend the framework to general Binary Unconstrained Combinatorial Optimization (BUCO). Finally, we provide reproducible evaluations for rounds up to p=3p=3p=3 on representative structured families, including the generalized Petersen graph GP(15,2)GP(15,2)GP(15,2), double-layer triangular 2-lifts, and the truncated icosahedron graph C60C_{60}C60​, and report cut ratios while benchmarking against locality-matched classical baselines.