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

Kunal Marwaha

doi:10.22331/q-2021-04-20-437

paper

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

arXiv:2101.05513 · doi:10.22331/q-2021-04-20-437

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 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 \geq 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 MAX-CUT algorithm that performs as well as QAOA $_{p}$ on all graphs.

7+10 pages, 2 figures, code online at https://nbviewer.jupyter.org/github/marwahaha/qaoa-local-competitors/blob/master/2-step-comparison.ipynb

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

Abstract

References in corpus (2)

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