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

Bounds on MAXCUT QAOA performance for p>1

Jonathan Wurtz, Peter J. Love

Published Oct 21, 2020• 11 citations
OpenAlex

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

Related papers

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

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

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

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

Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$

Reuben Tate, Stephan Eidenbenz

We generalize Farhi et al.'s 0.6924-approximation result technique of the Max-Cut Quantum Approximate Optimization Algorithm (QAOA) on 3-regular graphs to obtain provable lower bounds on the approximation ratio for warm-started QAOA. Given an initialization angle $θ$, we consider warm-starts where the initial state is a product state where each qubit position is angle $θ$ away from either the north or south pole of the Bloch sphere; of the two possible qubit positions the position of each qubit is decided by some classically obtained cut encoded as a bitstring $b$. We illustrate through plots how the properties of $b$ and the initialization angle $θ$ influence the bound on the approximation ratios of warm-started QAOA. We consider various classical algorithms (and the cuts they produce which we use to generate the warm-start). Our results strongly suggest that there does not exist any choice of initialization angle that yields a (worst-case) approximation ratio that simultaneously beats standard QAOA and the classical algorithm used to create the warm-start. Additionally, we show that at $θ=60^\circ$, warm-started QAOA is able to (effectively) recover the cut used to generate the warm-start, thus suggesting that in practice, this value could be a promising starting angle to explore alternate solutions in a heuristic fashion.

arXiv:2402.12631•Feb 20, 2024•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
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.
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) 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.
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 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$.
Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth p=1p=1p=1
We generalize Farhi et al.'s 0.6924-approximation result technique of the Max-Cut Quantum Approximate Optimization Algorithm (QAOA) on 3-regular graphs to obtain provable lower bounds on the approximation ratio for warm-started QAOA. Given an initialization angle θθθ, we consider warm-starts where the initial state is a product state where each qubit position is angle θθθ away from either the north or south pole of the Bloch sphere; of the two possible qubit positions the position of each qubit is decided by some classically obtained cut encoded as a bitstring bbb. We illustrate through plots how the properties of bbb and the initialization angle θθθ influence the bound on the approximation ratios of warm-started QAOA. We consider various classical algorithms (and the cuts they produce which we use to generate the warm-start). Our results strongly suggest that there does not exist any choice of initialization angle that yields a (worst-case) approximation ratio that simultaneously beats standard QAOA and the classical algorithm used to create the warm-start. Additionally, we show that at θ=60∘θ=60^\circθ=60∘, warm-started QAOA is able to (effectively) recover the cut used to generate the warm-start, thus suggesting that in practice, this value could be a promising starting angle to explore alternate solutions in a heuristic fashion.
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.