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

On Crossref's cited-by service no data on citing works was found (last attempt 2021-05-06 16:24:53). On SAO/NASA ADS no data on citing works was found (last attempt 2021-05-06 16:24:53).