A Caltech Library Service

Hybrid quantum-classical algorithms for approximate graph coloring

Bravyi, Sergey and Kliesch, Alexander and Koenig, Robert and Tang, Eugene (2022) Hybrid quantum-classical algorithms for approximate graph coloring. Quantum, 6 . Art. No. 678. ISSN 2521-327X. doi:10.22331/q-2022-03-30-678.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


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 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 p: 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-1 QAOA and level-1 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-1 QAOA and RQAOA with up to 300 qutrits applied to ensembles of randomly generated 3-colorable constant-degree graphs. We find that level-1 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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Bravyi, Sergey0000-0002-4032-470X
Kliesch, Alexander0000-0001-7973-9665
Koenig, Robert0000-0002-0563-1229
Additional Information:Published under CC-BY 4.0. Published: 2022-03-30. This work is supported in part by the Army Research Office under Grant Number W911NF-20-1-0014. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. RK and AK gratefully acknowledge support by the DFG cluster of excellence 2111 (Munich Center for Quantum Science and Technology). ET acknowledges funding provided by DOE Award Number: DE-SC0018407 Quantum Error Correction and Spacetime Geometry and the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907).
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-20-1-0014
Deutsche Forschungsgemeinschaft (DFG)2111
Department of Energy (DOE)DE-SC0018407
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Record Number:CaltechAUTHORS:20220622-433041200
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:115235
Deposited By: Tony Diaz
Deposited On:22 Jun 2022 21:24
Last Modified:28 Jun 2022 18:19

Repository Staff Only: item control page