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

Kunal Marwaha

doi:10.22331/q-2021-04-20-437

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

Berkeley Center for Quantum Information and Computation, University of California, Berkeley, California 94720, USA

Published:	2021-04-20, volume 5, page 437
Eprint:	arXiv:2101.05513v2
Doi:	https://doi.org/10.22331/q-2021-04-20-437
Citation:	Quantum 5, 437 (2021).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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 $\textit{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 \ge 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 $\textit{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.

Featured image: A plot of the expected performance of QAOA and local classical algorithms on MAX-CUT for regular graphs with girth above 5. Just as a 1-local classical algorithm outperforms $p=1$ QAOA, a related 2-local classical algorithm outperforms $p=2$ QAOA.

For further reading go to our presentation Local Competitors to QAOA

► BibTeX data

@article{Marwaha2021localclassicalmax,
  doi = {10.22331/q-2021-04-20-437},
  url = {https://doi.org/10.22331/q-2021-04-20-437},
  title = {Local classical {MAX}-{CUT} algorithm outperforms {$p=2$} {QAOA} on high-girth regular graphs},
  author = {Marwaha, Kunal},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {437},
  month = apr,
  year = {2021}
}

► References

[1] F. Arute, K. Arya, R. Babbush, et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. 2004.04197, doi:10.1038/s41567-020-01105-y.
https://doi.org/10.1038/s41567-020-01105-y
arXiv:2004.04197

[2] B. Barak, A. Moitra, R. O'Donnell, et al. Beating the random assignment on constraint satisfaction problems of bounded degree. 1505.03424.
arXiv:1505.03424

[3] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm. 1411.4028.
arXiv:1411.4028

[4] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. 1412.6062.
arXiv:1412.6062

[5] M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1115–1145, 1995. doi:10.1145/227683.227684, URL http://www-math.mit.edu/ goemans/PAPERS/maxcut-jacm.pdf.
https://doi.org/10.1145/227683.227684
http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf

[6] M. B. Hastings. Classical and quantum bounded depth approximation algorithms. 1905.07047.
arXiv:1905.07047

[7] J. Hirvonen, J. Rybicki, S. Schmid, and J. Suomela. Large cuts with local algorithms on triangle-free graphs. 1402.2543.
arXiv:1402.2543

[8] S. Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC '02, page 767–775, New York, NY, USA, 2002. Association for Computing Machinery. doi:10.1145/509907.510017.
https://doi.org/10.1145/509907.510017

[9] G. B. Mbeng, R. Fazio, and G. Santoro. Quantum annealing: a journey through digitalization, control, and hybrid quantum variational schemes. 1906.08948.
arXiv:1906.08948

[10] J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18(2):023023, feb 2016. doi:10.1088/1367-2630/18/2/023023.
https://doi.org/10.1088/1367-2630/18/2/023023

[11] A. Meurer, C. P. Smith, M. Paprocki, et al. Sympy: symbolic computing in python. PeerJ Computer Science, 3:e103, Jan. 2017. doi:10.7717/peerj-cs.103.
https://doi.org/10.7717/peerj-cs.103

[12] F. Pérez and B. E. Granger. IPython: a system for interactive scientific computing. Computing in Science and Engineering, 9(3):21–29, May 2007. doi:10.1109/MCSE.2007.53, URL https://ipython.org.
https://doi.org/10.1109/MCSE.2007.53
https://ipython.org

[13] J. Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, Aug 2018. doi:10.22331/q-2018-08-06-79.
https://doi.org/10.22331/q-2018-08-06-79

[14] J. B. Shearer. A note on bipartite subgraphs of triangle-free graphs. Random Structures & Algorithms, 3(2):223–226, 1992. doi:10.1002/rsa.3240030211.
https://doi.org/10.1002/rsa.3240030211

[15] M. Szegedy. What do qaoa energies reveal about graphs? 1912.12277.
arXiv:1912.12277

[16] P. Virtanen, R. Gommers, T. E. Oliphant, et al. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261–272, 2020. doi:10.1038/s41592-019-0686-2.
https://doi.org/10.1038/s41592-019-0686-2

[17] Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel. Quantum approximate optimization algorithm for maxcut: A fermionic view. Phys. Rev. A, 97:022304, Feb 2018. doi:10.1103/PhysRevA.97.022304.
https://doi.org/10.1103/PhysRevA.97.022304

[18] J. Wurtz and P. J. Love. Bounds on maxcut qaoa performance for p$>$1. 2010.11209.
arXiv:2010.11209

[19] L. Zhou, S.-T. Wang, S. Choi, et al. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10(2), Jun 2020. doi:10.1103/physrevx.10.021067.
https://doi.org/10.1103/physrevx.10.021067

Cited by

[1] Andrea Skolik, Michele Cattelan, Sheir Yarkoni, Thomas Bäck, and Vedran Dunjko, "Equivariant quantum circuits for learning on weighted graphs", npj Quantum Information 9 1, 47 (2023).

[2] Thorge Müller, Ajainderpal Singh, Frank K. Wilhelm, and Tim Bode, "Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems", Physical Review Research 7 2, 023165 (2025).

[3] Fanxu Meng, Xiangzhen Zhou, Pengcheng Zhu, and Yu Luo, "Conditional diffusion-based parameter generation for quantum approximate optimization algorithm", EPJ Quantum Technology 12 1, 100 (2025).

[4] Yuewen Hou, Dhanvi Bharadwaj, and Gokul Subramanian Ravi, Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 2063 (2026) ISBN:9798400723599.

[5] Jordi R. Weggemans, Alexander Urech, Alexander Rausch, Robert Spreeuw, Richard Boucherie, Florian Schreck, Kareljan Schoutens, Jiří Minář, and Florian Speelman, "Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach", Quantum 6, 687 (2022).

[6] Nongmeikapam Brajabidhu Singh and Anish Kumar Saha, "Exploring graph cuts in quantum approximate optimization algorithm", Physica Scripta 100 11, 115104 (2025).

[7] Karen Wintersperger, Hila Safi, and Wolfgang Mauerer, Lecture Notes in Computer Science 13642, 100 (2022) ISBN:978-3-031-21866-8.

[8] Yash J. Patel, Sofiene Jerbi, Thomas Bäck, and Vedran Dunjko, "Reinforcement learning assisted recursive QAOA", EPJ Quantum Technology 11 1, 6 (2024).

[9] Mateusz Slysz, Łukasz Grodzki, Piotr Rydlichowski, Dawid Siera, Krzysztof Kurowski, Grzegorz Waligóra, and Jan Węglarz, "Solving combinatorial optimization and machine learning problems on hybrid near-term quantum photonic computers", Future Generation Computer Systems 174, 107934 (2026).

[10] Eunok Bae and Soojoon Lee, "Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs", Quantum Information Processing 23 3, 78 (2024).

[11] Enhyeok Jang, Hyungseok Kim, Yongju Lee, Jaewon Kwon, Yipeng Huang, and Won Woo Ro, 2026 IEEE International Symposium on High Performance Computer Architecture (HPCA) 1 (2026) ISBN:979-8-3315-9302-5.

[12] Igor Gaidai and Rebekah Herrman, "Performance analysis of multi-angle QAOA for $$p > 1$$", Scientific Reports 14 1, 18911 (2024).

[13] Jonathan Wurtz, Stefan H. Sack, and Sheng-Tao Wang, "Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms", IEEE Transactions on Quantum Engineering 5, 1 (2024).

[14] Daniel J. Egger, Jakub Mareček, and Stefan Woerner, "Warm-starting quantum optimization", Quantum 5, 479 (2021).

[15] Taylor L. Patti, Jean Kossaifi, Anima Anandkumar, and Susanne F. Yelin, "Variational quantum optimization with multibasis encodings", Physical Review Research 4 3, 033142 (2022).

[16] Xinwei Lee, Ningyi Xie, Dongsheng Cai, Yoshiyuki Saito, and Nobuyoshi Asai, "A Depth-Progressive Initialization Strategy for Quantum Approximate Optimization Algorithm", Mathematics 11 9, 2176 (2023).

[17] Ramin Fakhimi and Hamidreza Validi, Encyclopedia of Optimization 1 (2023) ISBN:978-3-030-54621-2.

[18] Qi-Ming Ding, Yi-Ming Huang, and Xiao Yuan, "Molecular docking via quantum approximate optimization algorithm", Physical Review Applied 21 3, 034036 (2024).

[19] Benjamin C B Symons, David Galvin, Emre Sahin, Vassil Alexandrov, and Stefano Mensa, "A practitioner’s guide to quantum algorithms for optimisation problems", Journal of Physics A: Mathematical and Theoretical 56 45, 453001 (2023).

[20] Siddharth Dangwal, Suhas Vittal, Lennart Maximilian Seifert, Frederic T. Chong, and Gokul Subramanian Ravi, Proceedings of the 52nd Annual International Symposium on Computer Architecture 1417 (2025) ISBN:9798400712616.

[21] Phillip C. Lotshaw, George Siopsis, James Ostrowski, Rebekah Herrman, Rizwanul Alam, Sarah Powers, and Travis S. Humble, "Approximate Boltzmann distributions in quantum approximate optimization", Physical Review A 108 4, 042411 (2023).

[22] Elisabeth Wybo and Martin Leib, "Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm", Quantum 9, 1892 (2025).

[23] Stuart Hadfield, Tad Hogg, and Eleanor G Rieffel, "Analytical framework for quantum alternating operator ansätze", Quantum Science and Technology 8 1, 015017 (2023).

[24] Lis Arufe, Riccardo Rasconi, Angelo Oddi, Ramiro Varela, and Miguel A. González, "New coding scheme to compile circuits for Quantum Approximate Optimization Algorithm by genetic evolution", Applied Soft Computing 144, 110456 (2023).

[25] Eunok Bae, Hyukjoon Kwon, V Vijendran, and Soojoon Lee, "Modified recursive QAOA for exact MAX-CUT solutions on bipartite graphs: closing the gap beyond QAOA limit", Journal of Physics A: Mathematical and Theoretical 58 48, 485304 (2025).

[26] Sebastiano Corli, Daniele Dragoni, Massimiliano Proietti, Massimiliano Dispenza, Carlo Cavazzoni, and Enrico Prati, "Benchmarking the emulation of measurement-based quantum computing through the Max K-Cut algorithm", Quantum Information Processing 24 12, 396 (2025).

[27] Elijah Pelofske, Andreas Bärtschi, and Stephan Eidenbenz, "Short-depth QAOA circuits and quantum annealing on higher-order ising models", npj Quantum Information 10 1, 30 (2024).

[28] Sean Feeney, Reuben Tate, and Stephan Eidenbenz, 2025 International Conference on Quantum Communications, Networking, and Computing (QCNC) 450 (2025) ISBN:979-8-3315-3159-1.

[29] Kunal Marwaha and Stuart Hadfield, "Bounds on approximating Max kXOR with quantum and classical local algorithms", Quantum 6, 757 (2022).

[30] Shuaiqun Pan, Yash J. Patel, Aneta Neumann, Frank Neumann, Thomas Bäck, and Hao Wang, Proceedings of the Genetic and Evolutionary Computation Conference 443 (2025) ISBN:9798400714658.

[31] Zeqiao Zhou, Yuxuan Du, Xinmei Tian, and Dacheng Tao, "QAOA-in-QAOA: Solving Large-Scale MaxCut Problems on Small Quantum Machines", Physical Review Applied 19 2, 024027 (2023).

[32] Rizwanul Alam, George Siopsis, Rebekah Herrman, James Ostrowski, Phillip C. Lotshaw, and Travis S. Humble, "Solving MaxCut with quantum imaginary time evolution", Quantum Information Processing 22 7, 281 (2023).

[33] Tongyang Li, Yuexin Su, Ziyi Yang, and Shengyu Zhang, "Quantum approximate optimization algorithms for maximum cut on low-girth graphs", Physical Review Research 7 3, 033014 (2025).

[34] Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer, "A review on Quantum Approximate Optimization Algorithm and its variants", Physics Reports 1068, 1 (2024).

[35] Reuben Tate, Jai Moondra, Bryan Gard, Greg Mohler, and Swati Gupta, "Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths", Quantum 7, 1121 (2023).

[36] Phillip C. Lotshaw, Thien Nguyen, Anthony Santana, Alexander McCaskey, Rebekah Herrman, James Ostrowski, George Siopsis, and Travis S. Humble, "Scaling quantum approximate optimization on near-term hardware", Scientific Reports 12 1, 12388 (2022).

[37] James Sud, Stuart Hadfield, Eleanor Rieffel, Norm Tubman, and Tad Hogg, "Parameter-setting heuristic for the quantum alternating operator ansatz", Physical Review Research 6 2, 023171 (2024).

[38] Reuben Tate and Stephan Eidenbenz, "Theoretical approximation ratios for Warm-Started QAOA on 3-regular max-cut instances at depth p=1", Theoretical Computer Science 1059, 115571 (2026).

[39] T. Miki, D. Tsukayama, R. Okita, M Shimada, and J. Shirakashi, 2022 IEEE 22nd International Conference on Nanotechnology (NANO) 303 (2022) ISBN:978-1-6654-5225-0.

[40] Vivek Katial, Kate Smith-Miles, Charles Hill, and Lloyd Hollenberg, "On the Instance Dependence of Parameter Initialization for the Quantum Approximate Optimization Algorithm: Insights via Instance Space Analysis", INFORMS Journal on Computing 37 1, 146 (2025).

[41] Elijah Pelofske and Vincent Russo, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 01 (2025) ISBN:979-8-3315-5736-2.

[42] Xinwei Lee, Xinjian Yan, Ningyi Xie, Dongsheng Cai, Yoshiyuki Saito, and Nobuyoshi Asai, "Iterative layerwise training for the quantum approximate optimization algorithm", Physical Review A 109 5, 052406 (2024).

[43] Srikar Kasi, James Sud, Kyle Jamieson, and Gokul Subramanian Ravi, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 368 (2024) ISBN:979-8-3315-4137-8.

[44] Maxime Dupont, Bram Evert, Mark J. Hodson, Bhuvanesh Sundar, Stephen Jeffrey, Yuki Yamaguchi, Dennis Feng, Filip B. Maciejewski, Stuart Hadfield, M. Sohaib Alam, Zhihui Wang, Shon Grabbe, P. Aaron Lott, Eleanor G. Rieffel, Davide Venturelli, and Matthew J. Reagor, "Quantum-enhanced greedy combinatorial optimization solver", Science Advances 9 45, eadi0487 (2023).

[45] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou, "The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model", arXiv:2110.14206, (2021).

[46] Siddharth Dangwal, Suhas Vittal, Lennart Maximillian Seifert, Frederic T. Chong, and Gokul Subramanian Ravi, "Variational Quantum Algorithms in the era of Early Fault Tolerance", arXiv:2503.20963, (2025).

[47] Antares Chen, Neng Huang, and Kunal Marwaha, "Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs", arXiv:2310.01563, (2023).

[48] Shuaiqun Pan, Yash J. Patel, Aneta Neumann, Frank Neumann, Thomas Bäck, and Hao Wang, "Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms", arXiv:2502.12012, (2025).

[49] Elisabeth Wybo and Martin Leib, "Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm", arXiv:2406.14618, (2024).

[50] Elijah Pelofske and Vincent Russo, "Digital Zero-Noise Extrapolation with Quantum Circuit Unoptimization", arXiv:2503.06341, (2025).

[51] Dhanvi Bharadwaj, Yuewen Hou, Guang-Yi Li, and Gokul Subramanian Ravi, "Scalable Clifford-Based Classical Initialization for the Quantum Approximate Optimization Algorithm", arXiv:2602.14327, (2026).

[52] Vivek Katial, Kate Smith-Miles, and Charles Hill, "On the Instance Dependence of Optimal Parameters for the Quantum Approximate Optimisation Algorithm: Insights via Instance Space Analysis", arXiv:2401.08142, (2024).

[53] Yuewen Hou, Dhanvi Bharadwaj, and Gokul Subramanian Ravi, "TreeVQA: A Tree-Structured Execution Framework for Shot Reduction in Variational Quantum Algorithms", arXiv:2512.12068, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-17 20:46:53) and SAO/NASA ADS (last updated successfully 2026-08-17 20:46:54). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.