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

[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] Yash J. Patel, Sofiene Jerbi, Thomas Bäck, and Vedran Dunjko, "Reinforcement learning assisted recursive QAOA", EPJ Quantum Technology 11 1, 6 (2024).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-13 15:21:50) and SAO/NASA ADS (last updated successfully 2024-05-13 15:21:51). 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.