{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T01:42:11Z","timestamp":1773193331630,"version":"3.50.1"},"reference-count":19,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T00:00:00Z","timestamp":1618876800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"The p<\/mml:mi><\/mml:math>-stage Quantum Approximate Optimization Algorithm (QAOAp<\/mml:mi><\/mml:msub><\/mml:math>) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum (NISQ) devices, but its theoretical behavior is not well understood beyond p<\/mml:mi>=<\/mml:mo>1<\/mml:mn><\/mml:math>. We analyze QAOA2<\/mml:mn><\/mml:msub><\/mml:math> for the maximum cut problem<\/mml:mtext><\/mml:mrow><\/mml:math> (MAX-CUT), deriving a graph-size-independent expression for the expected cut fraction on any D<\/mml:mi><\/mml:math>-regular graph of girth ><\/mml:mo>5<\/mml:mn><\/mml:math> (i.e. without triangles, squares, or pentagons).We show that for all degrees D<\/mml:mi>\u2265<\/mml:mo>2<\/mml:mn><\/mml:math> and every D<\/mml:mi><\/mml:math>-regular graph G<\/mml:mi><\/mml:math> of girth ><\/mml:mo>5<\/mml:mn><\/mml:math>, QAOA2<\/mml:mn><\/mml:msub><\/mml:math> has a larger expected cut fraction than QAOA1<\/mml:mn><\/mml:msub><\/mml:math> on G<\/mml:mi><\/mml:math>. However, we also show that there exists a 2<\/mml:mn><\/mml:math>-local randomized classical<\/mml:mtext><\/mml:mrow><\/mml:math> algorithm A<\/mml:mi><\/mml:math> such that A<\/mml:mi><\/mml:math> has a larger expected cut fraction than QAOA2<\/mml:mn><\/mml:msub><\/mml:math> on all G<\/mml:mi><\/mml:math>. This supports our conjecture that for every constant p<\/mml:mi><\/mml:math>, there exists a local classical MAX-CUT algorithm that performs as well as QAOAp<\/mml:mi><\/mml:msub><\/mml:math> on all graphs.<\/jats:p>","DOI":"10.22331\/q-2021-04-20-437","type":"journal-article","created":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T14:53:06Z","timestamp":1618930386000},"page":"437","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":44,"title":["Local classical MAX-CUT algorithm outperforms p<\/mml:mi>=<\/mml:mo>2<\/mml:mn><\/mml:math> QAOA on high-girth regular graphs"],"prefix":"10.22331","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9084-6971","authenticated-orcid":false,"given":"Kunal","family":"Marwaha","sequence":"first","affiliation":[{"name":"Berkeley Center for Quantum Information and Computation, University of California, Berkeley, California 94720, USA"}]}],"member":"9598","published-online":{"date-parts":[[2021,4,20]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s41567-020-01105-y"},{"key":"1","unstructured":"B. Barak, A. Moitra, R. O'Donnell, et al. Beating the random assignment on constraint satisfaction problems of bounded degree. 1505.03424."},{"key":"2","unstructured":"E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm. 1411.4028."},{"key":"3","unstructured":"E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. 1412.6062."},{"key":"4","doi-asserted-by":"publisher","unstructured":"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\u20131145, 1995. doi:10.1145\/227683.227684, URL http:\/\/www-math.mit.edu\/ goemans\/PAPERS\/maxcut-jacm.pdf.","DOI":"10.1145\/227683.227684"},{"key":"5","unstructured":"M. B. Hastings. Classical and quantum bounded depth approximation algorithms. 1905.07047."},{"key":"6","unstructured":"J. Hirvonen, J. Rybicki, S. Schmid, and J. Suomela. Large cuts with local algorithms on triangle-free graphs. 1402.2543."},{"key":"7","doi-asserted-by":"publisher","unstructured":"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\u2013775, New York, NY, USA, 2002. Association for Computing Machinery. doi:10.1145\/509907.510017.","DOI":"10.1145\/509907.510017"},{"key":"8","unstructured":"G. B. Mbeng, R. Fazio, and G. Santoro. Quantum annealing: a journey through digitalization, control, and hybrid quantum variational schemes. 1906.08948."},{"key":"9","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/1367-2630\/18\/2\/023023"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.7717\/peerj-cs.103"},{"key":"11","doi-asserted-by":"publisher","unstructured":"F. P\u00e9rez and B. E. Granger. IPython: a system for interactive scientific computing. Computing in Science and Engineering, 9(3):21\u201329, May 2007. doi:10.1109\/MCSE.2007.53, URL https:\/\/ipython.org.","DOI":"10.1109\/MCSE.2007.53"},{"key":"12","doi-asserted-by":"publisher","unstructured":"J. Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, Aug 2018. doi:10.22331\/q-2018-08-06-79.","DOI":"10.22331\/q-2018-08-06-79"},{"key":"13","doi-asserted-by":"publisher","unstructured":"J. B. Shearer. A note on bipartite subgraphs of triangle-free graphs. Random Structures & Algorithms, 3(2):223\u2013226, 1992. doi:10.1002\/rsa.3240030211.","DOI":"10.1002\/rsa.3240030211"},{"key":"14","unstructured":"M. Szegedy. What do qaoa energies reveal about graphs? 1912.12277."},{"key":"15","doi-asserted-by":"publisher","unstructured":"P. Virtanen, R. Gommers, T. E. Oliphant, et al. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261\u2013272, 2020. doi:10.1038\/s41592-019-0686-2.","DOI":"10.1038\/s41592-019-0686-2"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.97.022304"},{"key":"17","unstructured":"J. Wurtz and P. J. Love. Bounds on maxcut qaoa performance for p$>$1. 2010.11209."},{"key":"18","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physrevx.10.021067"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-04-20-437\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T14:54:27Z","timestamp":1618930467000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-04-20-437\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,20]]},"references-count":19,"URL":"https:\/\/doi.org\/10.22331\/q-2021-04-20-437","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,20]]},"article-number":"437"}}