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:2610.17236

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

Flaviano Morone, Shivang Rawat, Dries Sels

quant-phcond-mat.dis-nnmath.COSubmitted Oct 12, 2026• Announced Oct 14, 2026• 0 citations
arXivHTMLPDF

Abstract

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

AI Summary

The paper asks how well classical local algorithms can approximate Max-Cut on large-girth 3-regular graphs, and whether QAOA retains an advantage over classical benchmarks there. It studies $M_g$, the minimum maximum-cut fraction over graphs of girth at least $g$, whose asymptotic bounds were $0.912\le\lim_{g\to\infty}M_g\le0.92386$. It evaluates the previously introduced Variational Iterative Rotation Algorithm (VIRAL), which synchronously updates classical unit vectors initialized with independent random signs, then thresholds their final components. At depth $p$, an edge’s output depends only on its radius-$p$ neighborhood. For girth $g\ge2p+2$, this neighborhood is a fixed tree, so its expected cut probability gives a universal lower bound on $M_g$. Parameters trained previously on finite random graphs are held fixed; tree expectations are estimated using $10^7$ independent samples at each even depth through $p=32$, with exact binomial lower confidence bounds. At evaluated depths overlapping available QAOA results, VIRAL improves the cut fraction by approximately $0.005$–$0.011$ for $p\ge4$. At $p=32$, its estimated fraction is $0.913183\pm0.000089$, yielding $M_{66}\ge0.91271$ at $99.99999\%$ confidence and hence an asymptotic lower bound of $0.9127$. Running the fixed algorithm on a graph costs $O(p|E|)$. The guarantees beyond the lowest depth are statistical rather than exact evaluations. Parameters are not optimized directly on trees, QAOA comparisons stop at its available depth-$17$ result, and the data do not determine VIRAL’s infinite-depth limit. Higher-degree graphs and Max-$k$-Cut remain untested here.

No sign of AI-generated textOverclaims

Error found: The paper claims VIRAL outperforms QAOA at equal even depths through p=32, but its data support equal-depth comparisons only through p=16; deeper VIRAL results are compared with a shallower QAOA result or have no QAOA comparator.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
5 pages, 3 figures, 1 table

Related papers

Provable Classical and Quantum Local Algorithms for Max-$k$-Cut and Quantum Advantage at Moderate Girth

Anuj Apte, Abid Khan, Edward Farhi +3 more

Broadening the study of quantum optimization algorithms from binary to $k$-element alphabets has been shown to open new avenues for potential quantum advantage. A quantum advantage claim for approximate optimization requires showing that, under the same assumptions, an efficient quantum algorithm provably achieves a better performance than can be proven for the best known efficient classical algorithms. We study local classical and quantum algorithms for Max-$k$-Cut on $d$-regular graphs of girth $g$. We advance classical algorithms for this problem by developing a local vector algorithm based on the explicit vector construction of Thompson, Parekh, and Marwaha (TPM). Our algorithm gives the best provable cut fraction guarantee among known efficient classical algorithms on regular graphs for $k\geq3$. To evaluate the performance of QAOA under identical assumptions of girth and regularity, we develop tensor network techniques for general $d$ and $k \geq 2$. In addition, using an equivalence to a coupled qudit--boson system, we compute the QAOA performance in the infinite-degree limit. Together, these techniques give provable guarantees on QAOA performance on large graphs. Despite the improvements we introduce to the classical algorithm, QAOA achieves a better cut fraction guarantee for depths $p\geq 9$, corresponding to girth $g\geq 20$, for both finite- and infinite-degree regimes. Thus, we obtain an apparent quantum advantage from applying QAOA to the Max-$k$-Cut problem.

quant-pharXiv:2609.39042•Oct 1, 2026•4 citations

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

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

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 the 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, which are 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 the 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 the best-known classical local algorithms and QAOA with constant depth. Our results demonstrate that QAOA outperforms these 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 in which ma-QAOA exhibits superiority over the 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•5 citations

Local classical MAX-CUT algorithm outperforms p=2 QAOA on high-girth regular graphs

Kunal Marwaha

The p -stage Quantum Approximate Optimization Algorithm (QAOA p ) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum (NISQ) devices, but its theoretical behavior is not well understood beyond p=1 . We analyze QAOA 2 for the maximum cut problem (MAX-CUT), deriving a graph-size-independent expression for the expected cut fraction on any D -regular graph of girth >5 (i.e. without triangles, squares, or pentagons).We show that for all degrees D≥2 and every D -regular graph G of girth >5 , QAOA 2 has a larger expected cut fraction than QAOA 1 on G . However, we also show that there exists a 2 -local randomized classical algorithm A such that A has a larger expected cut fraction than QAOA 2 on all G . This supports our conjecture that for every constant p , there exists a local classical MAX-CUT algorithm that performs as well as QAOA p on all graphs.

arXiv:2101.05513•Quantum•Apr 20, 2021•55 citations

Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut

Anuj Apte, Sami Boulebnane, Yuwei Jin +3 more

Quantum algorithms for binary optimization problems have been the subject of extensive study. However, the application of quantum algorithms to integer optimization problems remains comparatively unexplored. In this paper, we study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs, with each integer variable encoded in a qudit. We derive a general iterative formula for depth-$p$ QAOA expectation on high-girth $d$-regular graphs of arbitrary size. The cost of evaluating the formula is exponential in the QAOA depth $p$ but does not depend on the graph size. Evaluating this formula for Max-$k$-Cut problem for $p\leq 4$, we identify parameter regimes ($k=3$ with degree $d \leq 10$ and $k=4$ with $d \leq 40$) in which QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm, which provides the best worst-case guarantee on the approximation ratio. To strengthen the classical baseline, we introduce a new heuristic algorithm based on the degree-of-saturation that achieves strong results on the \texttt{GSet} benchmark with quasi-linear runtime in the number of edges. It empirically outperforms both the Frieze-Jerrum algorithm and shallow-depth QAOA on regular graphs. Nevertheless, we provide numerical evidence that QAOA may overtake this heuristic at depth $p\leq 20$. Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage.

quant-pharXiv:2602.05956•Feb 6, 2026•7 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•116 citations

Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs

Boaz Barak, Kunal Marwaha

We study the performance of local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of classical algorithms. (1) We prove that every (quantum or classical) one-local algorithm achieves on $D$-regular graphs of girth $> 5$ a maximum cut of at most $1/2 + C/\sqrt{D}$ for $C=1/\sqrt{2} \approx 0.7071$. This is the first such result showing that one-local algorithms achieve a value bounded away from the true optimum for random graphs, which is $1/2 + P_*/\sqrt{D} + o(1/\sqrt{D})$ for $P_* \approx 0.7632$. (2) We show that there is a classical $k$-local algorithm that achieves a value of $1/2 + C/\sqrt{D} - O(1/\sqrt{k})$ for $D$-regular graphs of girth $> 2k+1$, where $C = 2/π\approx 0.6366$. This is an algorithmic version of the existential bound of Lyons and is related to the algorithm of Aizenman, Lebowitz, and Ruelle (ALR) for the Sherrington-Kirkpatrick model. This bound is better than that achieved by the one-local and two-local versions of QAOA on high-girth graphs. (3) Through computational experiments, we give evidence that the ALR algorithm achieves better performance than constant-locality QAOA for random $D$-regular graphs, as well as other natural instances, including graphs that do have short cycles. Our experimental work suggests that it could be possible to extend beyond our theoretical constraints. This points at the tantalizing possibility that $O(1)$-local quantum maximum-cut algorithms might be *pointwise dominated* by polynomial-time classical algorithms, in the sense that there is a classical algorithm outputting cuts of equal or better quality *on every possible instance*. This is in contrast to the evidence that polynomial-time algorithms cannot simulate the probability distributions induced by local quantum algorithms.

arXiv:2106.05900•Leibniz international proceedings in informatics•Jun 10, 2021•44 citations
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 paper asks how well classical local algorithms can approximate Max-Cut on large-girth 3-regular graphs, and whether QAOA retains an advantage over classical benchmarks there. It studies MgM_gMg​, the minimum maximum-cut fraction over graphs of girth at least ggg, whose asymptotic bounds were 0.912≤lim⁡g→∞Mg≤0.923860.912\le\lim_{g\to\infty}M_g\le0.923860.912≤limg→∞​Mg​≤0.92386.
It evaluates the previously introduced Variational Iterative Rotation Algorithm (VIRAL), which synchronously updates classical unit vectors initialized with independent random signs, then thresholds their final components. At depth ppp, an edge’s output depends only on its radius-ppp neighborhood. For girth g≥2p+2g\ge2p+2g≥2p+2, this neighborhood is a fixed tree, so its expected cut probability gives a universal lower bound on MgM_gMg​. Parameters trained previously on finite random graphs are held fixed; tree expectations are estimated using 10710^7107 independent samples at each even depth through p=32p=32p=32, with exact binomial lower confidence bounds.
At evaluated depths overlapping available QAOA results, VIRAL improves the cut fraction by approximately 0.0050.0050.005–0.0110.0110.011 for p≥4p\ge4p≥4. At p=32p=32p=32, its estimated fraction is 0.913183±0.0000890.913183\pm0.0000890.913183±0.000089, yielding M66≥0.91271M_{66}\ge0.91271M66​≥0.91271 at 99.99999%99.99999\%99.99999% confidence and hence an asymptotic lower bound of 0.91270.91270.9127. Running the fixed algorithm on a graph costs O(p∣E∣)O(p|E|)O(p∣E∣).
The guarantees beyond the lowest depth are statistical rather than exact evaluations. Parameters are not optimized directly on trees, QAOA comparisons stop at its available depth-171717 result, and the data do not determine VIRAL’s infinite-depth limit. Higher-degree graphs and Max-kkk-Cut remain untested here.
Provable Classical and Quantum Local Algorithms for Max-kkk-Cut and Quantum Advantage at Moderate Girth
Broadening the study of quantum optimization algorithms from binary to kkk-element alphabets has been shown to open new avenues for potential quantum advantage. A quantum advantage claim for approximate optimization requires showing that, under the same assumptions, an efficient quantum algorithm provably achieves a better performance than can be proven for the best known efficient classical algorithms. We study local classical and quantum algorithms for Max-kkk-Cut on ddd-regular graphs of girth ggg. We advance classical algorithms for this problem by developing a local vector algorithm based on the explicit vector construction of Thompson, Parekh, and Marwaha (TPM). Our algorithm gives the best provable cut fraction guarantee among known efficient classical algorithms on regular graphs for k≥3k\geq3k≥3. To evaluate the performance of QAOA under identical assumptions of girth and regularity, we develop tensor network techniques for general ddd and k≥2k \geq 2k≥2. In addition, using an equivalence to a coupled qudit--boson system, we compute the QAOA performance in the infinite-degree limit. Together, these techniques give provable guarantees on QAOA performance on large graphs. Despite the improvements we introduce to the classical algorithm, QAOA achieves a better cut fraction guarantee for depths p≥9p\geq 9p≥9, corresponding to girth g≥20g\geq 20g≥20, for both finite- and infinite-degree regimes. Thus, we obtain an apparent quantum advantage from applying QAOA to the Max-kkk-Cut problem.
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 the 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, which are 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 the 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 the best-known classical local algorithms and QAOA with constant depth. Our results demonstrate that QAOA outperforms these 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 in which ma-QAOA exhibits superiority over the 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.
The p -stage Quantum Approximate Optimization Algorithm (QAOA p ) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum (NISQ) devices, but its theoretical behavior is not well understood beyond p=1 . We analyze QAOA 2 for the maximum cut problem (MAX-CUT), deriving a graph-size-independent expression for the expected cut fraction on any D -regular graph of girth >5 (i.e. without triangles, squares, or pentagons).We show that for all degrees D≥2 and every D -regular graph G of girth >5 , QAOA 2 has a larger expected cut fraction than QAOA 1 on G . However, we also show that there exists a 2 -local randomized classical algorithm A such that A has a larger expected cut fraction than QAOA 2 on all G . This supports our conjecture that for every constant p , there exists a local classical MAX-CUT algorithm that performs as well as QAOA p on all graphs.
Quantum algorithms for binary optimization problems have been the subject of extensive study. However, the application of quantum algorithms to integer optimization problems remains comparatively unexplored. In this paper, we study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs, with each integer variable encoded in a qudit. We derive a general iterative formula for depth-ppp QAOA expectation on high-girth ddd-regular graphs of arbitrary size. The cost of evaluating the formula is exponential in the QAOA depth ppp but does not depend on the graph size. Evaluating this formula for Max-kkk-Cut problem for p≤4p\leq 4p≤4, we identify parameter regimes (k=3k=3k=3 with degree d≤10d \leq 10d≤10 and k=4k=4k=4 with d≤40d \leq 40d≤40) in which QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm, which provides the best worst-case guarantee on the approximation ratio. To strengthen the classical baseline, we introduce a new heuristic algorithm based on the degree-of-saturation that achieves strong results on the \texttt{GSet} benchmark with quasi-linear runtime in the number of edges. It empirically outperforms both the Frieze-Jerrum algorithm and shallow-depth QAOA on regular graphs. Nevertheless, we provide numerical evidence that QAOA may overtake this heuristic at depth p≤20p\leq 20p≤20. Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage.
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 study the performance of local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of classical algorithms. (1) We prove that every (quantum or classical) one-local algorithm achieves on DDD-regular graphs of girth >5> 5>5 a maximum cut of at most 1/2+C/D1/2 + C/\sqrt{D}1/2+C/D​ for C=1/2≈0.7071C=1/\sqrt{2} \approx 0.7071C=1/2​≈0.7071. This is the first such result showing that one-local algorithms achieve a value bounded away from the true optimum for random graphs, which is 1/2+P∗/D+o(1/D)1/2 + P_*/\sqrt{D} + o(1/\sqrt{D})1/2+P∗​/D​+o(1/D​) for P∗≈0.7632P_* \approx 0.7632P∗​≈0.7632. (2) We show that there is a classical kkk-local algorithm that achieves a value of 1/2+C/D−O(1/k)1/2 + C/\sqrt{D} - O(1/\sqrt{k})1/2+C/D​−O(1/k​) for DDD-regular graphs of girth >2k+1> 2k+1>2k+1, where C=2/π≈0.6366C = 2/π\approx 0.6366C=2/π≈0.6366. This is an algorithmic version of the existential bound of Lyons and is related to the algorithm of Aizenman, Lebowitz, and Ruelle (ALR) for the Sherrington-Kirkpatrick model. This bound is better than that achieved by the one-local and two-local versions of QAOA on high-girth graphs. (3) Through computational experiments, we give evidence that the ALR algorithm achieves better performance than constant-locality QAOA for random DDD-regular graphs, as well as other natural instances, including graphs that do have short cycles. Our experimental work suggests that it could be possible to extend beyond our theoretical constraints. This points at the tantalizing possibility that O(1)O(1)O(1)-local quantum maximum-cut algorithms might be *pointwise dominated* by polynomial-time classical algorithms, in the sense that there is a classical algorithm outputting cuts of equal or better quality *on every possible instance*. This is in contrast to the evidence that polynomial-time algorithms cannot simulate the probability distributions induced by local quantum algorithms.