Hybrid quantum-classical algorithms for approximate graph coloring

Sergey Bravyi, Alexander Kliesch, Robert Koenig +1

We show how to apply the recursive quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We compa…