Hybrid quantum-classical algorithms for approximate graph coloring
Sergey Bravyi, Alexander Kliesch, Robert Koenig, Eugene Tang
Abstract
We show how to apply the recursive quantum approximate optimization algorithm (RQAOA) to MAX-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>-CUT, the problem of finding an approximate <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>-vertex coloring of a graph. We compare this proposal to the best known classical and hybrid classical-quantum algorithms. First, we show that the standard (non-recursive) QAOA fails to solve this optimization problem for most regular bipartite graphs at any constant level <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>p</mml:mi></mml:math>: the approximation ratio achieved by QAOA is hardly better than assigning colors to vertices at random. Second, we construct an efficient classical simulation algorithm which simulates level-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>1</mml:mn></mml:math> QAOA and level-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>1</mml:mn></mml:math> RQAOA for arbitrary graphs. In particular, these hybrid algorithms give rise to efficient classical algorithms, and no benefit arising from the use of quantum mechanics is to be expected. Nevertheless, they provide a suitable testbed for assessing the potential benefit of hybrid algorithm: We use the simulation algorithm to perform large-scale simulation of level-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>1</mml:mn></mml:math> QAOA and RQAOA with up to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>300</mml:mn></mml:math> qutrits applied to ensembles of randomly generated <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>3</mml:mn></mml:math>-colorable constant-degree graphs. We find that level-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>1</mml:mn></mml:math> RQAOA is surprisingly competitive: for the ensembles considered, its approximation ratios are often higher than those achieved by the best known generic classical algorithm based on rounding an SDP relaxation. This suggests the intriguing possibility that higher-level RQAOA may be a potentially useful algorithm for NISQ devices.