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

Kunal Marwaha

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

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


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.

For further reading go to our presentation Local Competitors to QAOA


► BibTeX data

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

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

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

[4] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. 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.

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

[7] J. Hirvonen, J. Rybicki, S. Schmid, and J. Suomela. Large cuts with local algorithms on triangle-free graphs. 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.

[9] G. B. Mbeng, R. Fazio, and G. Santoro. Quantum annealing: a journey through digitalization, control, and hybrid quantum variational schemes. 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.

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

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

[13] J. Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, Aug 2018. doi: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.

[15] M. Szegedy. What do qaoa energies reveal about graphs? 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.

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

[18] J. Wurtz and P. J. Love. Bounds on maxcut qaoa performance for p$>$1. 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.

Cited by

[1] 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).

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

[3] 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).

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

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

[6] 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.

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

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

[9] 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).

[10] Kunal Marwaha and Stuart Hadfield, "Bounds on approximating Max $k$XOR with quantum and classical local algorithms", arXiv:2109.10833, (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2023-01-27 02:18:38) and SAO/NASA ADS (last updated successfully 2023-01-27 02:18:39). The list may be incomplete as not all publishers provide suitable and complete citation data.