Local classical MAXCUT algorithm outperforms $p=2$ QAOA on highgirth regular graphs
Abstract
The $p$stage Quantum Approximate Optimization Algorithm (QAOA$_p$) is a promising approach for combinatorial optimization on noisy intermediatescale quantum (NISQ) devices, but its theoretical behavior is not well understood beyond $p=1$. We analyze QAOA$_2$ for the maximum cut problem (MAXCUT), deriving a graphsizeindependent 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 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 MAXCUT algorithm that performs as well as QAOA$_p$ on all graphs.
 Publication:

arXiv eprints
 Pub Date:
 January 2021
 arXiv:
 arXiv:2101.05513
 Bibcode:
 2021arXiv210105513M
 Keywords:

 Quantum Physics
 EPrint:
 7+10 pages, 2 figures, code online at https://nbviewer.jupyter.org/github/marwahaha/qaoalocalcompetitors/blob/master/2stepcomparison.ipynb