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:2010.11209 · Physical Review A

MaxCut quantum approximate optimization algorithm performance guarantees for p>1

Jonathan Wurtz, Peter J. Love

Published Apr 27, 2021• 103 citations
arXivHTMLPDF

Abstract

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$.

DOI
10.1103/physreva.103.042612

Related papers

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

Fixed-angle conjectures for the quantum approximate optimization algorithm 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 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$.

Physical Review A•Nov 17, 2021•68 citations

Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs

Flaviano Morone, Shivang Rawat, Dries Sels

Every 3-regular graph of girth at least $g$ has a cut containing at least a fraction $M_g$ of its edges, and the best rigorous bounds at large girth are $0.912\le \lim_{g\to\infty}M_g \le 0.92386$. Lower bounds on $M_g$ follow from the performance of local algorithms: on a graph of girth $g \ge 2p+2$ a depth-$p$ local algorithm sees the same tree around every edge, so its expected cut fraction on that tree bounds $M_g$ from below. We apply this strategy to the Variational Iterative Rotation Algorithm (VIRAL), a classical local algorithm, and evaluate it on the depth-$p$ tree for every even depth up to $p=32$. The resulting bounds exceed those recently obtained from the Quantum Approximate Optimization Algorithm (QAOA) for every $p\ge 4$, by $0.005$ to $0.011$, and they extend the range of girths covered from $g=36$ to $g=66$. Notably, at $g=66$ we obtain $M_{66} \ge 0.9127$ at $99.99999\%$ confidence level, which raises the asymptotic lower bound from $0.912$ to $0.9127$.

quant-pharXiv:2610.17236•Oct 14, 2026•0 citations

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

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

Quantum approximate optimization algorithms for maximum cut on low-girth graphs

Tongyang Li, Yan‐Kun Su, Ziyi Yang +1 more

Abstract Maximum cut (MaxCut) on graphs is a classic NP-hard problem. In quantum computing, Farhi, Gutmann, and Goldstone proposed the Quantum Approximate Optimization Algorithm (QAOA) for solving the MaxCut problem. Its guarantee on cut fraction (the fraction of edges in the output cut over all edges) was mainly studied for high-girth graphs, i.e., graphs with only long cycles. On the other hand, low-girth graphs are ubiquitous in theoretical computer science, including expander graphs being outstanding examples with wide applications in theory and beyond. In this paper, we apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell known as additive product graphs. Additionally, we apply multi-angle QAOA (ma-QAOA) to better utilize the graph structure of additive product graphs in ansatz design. In theory, we derive an iterative formula to calculate the expected cut fraction of such graphs. This formula also extends to the quantum MaxCut problem. On the other hand, we conduct numerical experiments to compare between best-known classical local algorithms and QAOA with constant depth. Our results demonstrate that QAOA outperforms the best-known classical algorithms by 0.3% to 5.2% on several additive product graphs, while ma-QAOA further enhances this advantage by an additional 0.6% to 2.5%. In particular, we observe cases that ma-QAOA exhibits superiority over best-known classical algorithms but QAOA does not. Furthermore, we extend our experiments to planar graphs such as tiling grid graphs, where QAOA also demonstrates an advantage.

arXiv:2410.04409•Physical Review Research•May 28, 2025•3 citations
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≤5\ensuremath{\le}5\ensuremath≤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≤2p+1\ensuremath{\le}2p+1\ensuremath≤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.
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 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{\ge}11$.
Every 3-regular graph of girth at least ggg has a cut containing at least a fraction MgM_gMg​ of its edges, and the best rigorous bounds at large girth are 0.912≤lim⁡g→∞Mg≤0.923860.912\le \lim_{g\to\infty}M_g \le 0.923860.912≤limg→∞​Mg​≤0.92386. Lower bounds on MgM_gMg​ follow from the performance of local algorithms: on a graph of girth g≥2p+2g \ge 2p+2g≥2p+2 a depth-ppp local algorithm sees the same tree around every edge, so its expected cut fraction on that tree bounds MgM_gMg​ from below. We apply this strategy to the Variational Iterative Rotation Algorithm (VIRAL), a classical local algorithm, and evaluate it on the depth-ppp tree for every even depth up to p=32p=32p=32. The resulting bounds exceed those recently obtained from the Quantum Approximate Optimization Algorithm (QAOA) for every p≥4p\ge 4p≥4, by 0.0050.0050.005 to 0.0110.0110.011, and they extend the range of girths covered from g=36g=36g=36 to g=66g=66g=66. Notably, at g=66g=66g=66 we obtain M66≥0.9127M_{66} \ge 0.9127M66​≥0.9127 at 99.99999%99.99999\%99.99999% confidence level, which raises the asymptotic lower bound from 0.9120.9120.912 to 0.91270.91270.9127.
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.
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.
Abstract Maximum cut (MaxCut) on graphs is a classic NP-hard problem. In quantum computing, Farhi, Gutmann, and Goldstone proposed the Quantum Approximate Optimization Algorithm (QAOA) for solving the MaxCut problem. Its guarantee on cut fraction (the fraction of edges in the output cut over all edges) was mainly studied for high-girth graphs, i.e., graphs with only long cycles. On the other hand, low-girth graphs are ubiquitous in theoretical computer science, including expander graphs being outstanding examples with wide applications in theory and beyond. In this paper, we apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell known as additive product graphs. Additionally, we apply multi-angle QAOA (ma-QAOA) to better utilize the graph structure of additive product graphs in ansatz design. In theory, we derive an iterative formula to calculate the expected cut fraction of such graphs. This formula also extends to the quantum MaxCut problem. On the other hand, we conduct numerical experiments to compare between best-known classical local algorithms and QAOA with constant depth. Our results demonstrate that QAOA outperforms the best-known classical algorithms by 0.3% to 5.2% on several additive product graphs, while ma-QAOA further enhances this advantage by an additional 0.6% to 2.5%. In particular, we observe cases that ma-QAOA exhibits superiority over best-known classical algorithms but QAOA does not. Furthermore, we extend our experiments to planar graphs such as tiling grid graphs, where QAOA also demonstrates an advantage.