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:2101.05513 · Quantum

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

Kunal Marwaha

Published Apr 20, 2021• 55 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2021-04-20-437

Related papers

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

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

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

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

Design of quantum approximation optimization algorithm for the maximum cut problem

Yun-Jiang Wang, XI Huiming, XIAO Zhuoyan +2 more

The max-cut problem (MCP) is a classic problem in the field of combinatorial optimization and has important applications in various fields, including statistical physics and image processing. However, except for some special cases, the MCP still encounters a non-deterministic polynomial complete problem (an NP-complete problem), and there is currently no known efficient classical algorithm that can solve it in polynomial time. The quantum approximate optimization algorithm (QAOA), as a pivotal algorithm in the noisy intermediate-scale quantum (NISQ) computing era, has shown significant potential for solving the MCP. However, due to the lack of quantum error correction, the reliability of computations in NISQ systems sharply declines as the circuit depth of the algorithm increases. Therefore, designing an efficient, shallow-depth, and low-complexity QAOA for the MCP is a critical challenge in demonstrating the advantages of quantum computing in the NISQ era.In this paper, according to the standard QAOA algorithm, we introduce Pauli Y rotation gates into the target Hamiltonian circuit for the MCP. By enhancing the flexibility of quantum trial functions and improving the efficiency of Hilbert space exploration within a single iteration, we significantly improve the performance of QAOA on the MCP.We conduct extensive numerical simulations using the MindSpore quantum platform, and compare the proposed RY-layer-assisted QAOA with standard QAOA and its existing variants, including MA-QAOA and QAOA+. The experiments are performed on various graph types, including complete graphs, 3-regular graphs, 4-regular graphs, and random graphs with edge probabilities between 0.3 and 0.5. Our results show that the RY-layer-assisted QAOA achieves higher approximation ratios in all graph types, particularly in regular and random graphs, where traditional QAOA variants are difficult to implement. Moreover, the proposed method exhibits strong robustness as the graph size increases, and can maintain high performance even for larger graphs. Importantly, the RY-layer-assisted QAOA requires fewer CNOT gates and has a lower circuit depth than the standard QAOA and its variants, making it more suitable for NISQ devices with limited coherence times and high error rates.In conclusion, the RY-layer-assisted QAOA provides a promising approach for solving MCP in the NISQ era. By improving the approximation ratio while reducing circuit complexity, this method demonstrates significant potential for practical quantum computing applications, thus paving the way for developing more efficient and reliable quantum optimization algorithms.

Acta Physica Sinica•Jan 1, 2025•1 citation
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.
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.
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.
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.
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 max-cut problem (MCP) is a classic problem in the field of combinatorial optimization and has important applications in various fields, including statistical physics and image processing. However, except for some special cases, the MCP still encounters a non-deterministic polynomial complete problem (an NP-complete problem), and there is currently no known efficient classical algorithm that can solve it in polynomial time. The quantum approximate optimization algorithm (QAOA), as a pivotal algorithm in the noisy intermediate-scale quantum (NISQ) computing era, has shown significant potential for solving the MCP. However, due to the lack of quantum error correction, the reliability of computations in NISQ systems sharply declines as the circuit depth of the algorithm increases. Therefore, designing an efficient, shallow-depth, and low-complexity QAOA for the MCP is a critical challenge in demonstrating the advantages of quantum computing in the NISQ era.In this paper, according to the standard QAOA algorithm, we introduce Pauli Y rotation gates into the target Hamiltonian circuit for the MCP. By enhancing the flexibility of quantum trial functions and improving the efficiency of Hilbert space exploration within a single iteration, we significantly improve the performance of QAOA on the MCP.We conduct extensive numerical simulations using the MindSpore quantum platform, and compare the proposed RY-layer-assisted QAOA with standard QAOA and its existing variants, including MA-QAOA and QAOA+. The experiments are performed on various graph types, including complete graphs, 3-regular graphs, 4-regular graphs, and random graphs with edge probabilities between 0.3 and 0.5. Our results show that the RY-layer-assisted QAOA achieves higher approximation ratios in all graph types, particularly in regular and random graphs, where traditional QAOA variants are difficult to implement. Moreover, the proposed method exhibits strong robustness as the graph size increases, and can maintain high performance even for larger graphs. Importantly, the RY-layer-assisted QAOA requires fewer CNOT gates and has a lower circuit depth than the standard QAOA and its variants, making it more suitable for NISQ devices with limited coherence times and high error rates.In conclusion, the RY-layer-assisted QAOA provides a promising approach for solving MCP in the NISQ era. By improving the approximation ratio while reducing circuit complexity, this method demonstrates significant potential for practical quantum computing applications, thus paving the way for developing more efficient and reliable quantum optimization algorithms.