Hybrid quantum-classical algorithms for approximate graph coloring

Sergey Bravyi1, Alexander Kliesch2, Robert Koenig3, and Eugene Tang4

1IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, USA
2Zentrum Mathematik, Technical University of Munich, 85748 Garching, Germany
3Institute for Advanced Study & Zentrum Mathematik, Technical University of Munich, 85748 Garching, Germany
4Institute for Quantum Information and Matter, Caltech, Pasadena, CA 91125

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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.

► BibTeX data

► References

[1] Noga Alon and Nabil Kahale. A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput., 26(6):1733–1748, December 1997. https:/​/​doi.org/​10.1137/​S0097539794270248.

[2] Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances, 2018. https:/​/​doi.org/​10.48550/​arXiv.1812.04170.

[3] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Phys. Rev. Lett., 125:260505, Dec 2020. https:/​/​doi.org/​10.1103/​PhysRevLett.125.260505.

[4] Amin Coja-Oghlan, Cristopher Moore, and Vishal Sanwalani. Max-$k$-cut and approximating the chromatic number of random graphs. Random Structures & Algorithms, 28(3):289–322, 2006. https:/​/​doi.org/​10.1002/​rsa.20096.

[5] Daniel J. Egger, Jakub Mareček, and Stefan Woerner. Warm-starting quantum optimization. Quantum, 5:479, June 2021. https:/​/​doi.org/​10.22331/​q-2021-06-17-479.

[6] Edward Farhi, David Gamarnik, and Sam Gutmann. The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples, 2020. https:/​/​doi.org/​10.48550/​arXiv.2005.08747.

[7] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm, 2014. https:/​/​doi.org/​10.48550/​arXiv.1411.4028.

[8] Alan Frieze and M. Jerrum. Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. Algorithmica, 18(1):67–81, 05 1997. https:/​/​doi.org/​10.1007/​BF02523688.

[9] Michel X. Goemans and David Williamson. Approximation Algorithms for MAX-3-CUT and Other Problems via Complex Semidefinite Programming. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC '01, page 443–452, New York, NY, USA, 2001. Association for Computing Machinery. https:/​/​doi.org/​10.1145/​380752.380838.

[10] Michel X. Goemans and David P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM, 42(6):1115–1145, 1995. https:/​/​doi.org/​10.1145/​227683.227684.

[11] Jun-Dong Cho, S. Raje, and M. Sarrafzadeh. Fast Approximation Algorithms on Maxcut, k-Coloring, and k-Color Ordering for VLSI Applications. IEEE Transactions on Computers, 47(11):1253–1266, 1998. https:/​/​doi.org/​10.1109/​12.736440.

[12] Viggo Kann, Sanjeev Khanna, Jens Lagergren, and Alessandro Panconesi. On the Hardness of Approximating Max k-Cut and its Dual. Chicago Journal of Theoretical Computer Science, 1997:1–18, June 1997. https:/​/​doi.org/​10.4086/​cjtcs.1997.002.

[13] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs? SIAM Journal on Computing, 37(1):319–357, 2007. https:/​/​doi.org/​10.1137/​S0097539705447372.

[14] Etienne Klerk, Dmitrii Pasechnik, and J.P. Warners. On Approximate Graph Colouring and MAX-$k$-CUT Algorithms Based on the $\vartheta$-Function. Journal of Combinatorial Optimization, 8:267–294, 09 2004. https:/​/​doi.org/​10.1023/​B:JOCO.0000038911.67280.3f.

[15] Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9(4812):1–6, 2018. https:/​/​doi.org/​10.1038/​s41467-018-07090-4.

[16] Jarrod R. McClean, Matthew P. Harrigan, Masoud Mohseni, Nicholas C. Rubin, Zhang Jiang, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Low-depth mechanisms for quantum optimization. PRX Quantum, 2:030312, Jul 2021. https:/​/​doi.org/​10.1103/​PRXQuantum.2.030312.

[17] Alantha Newman. Complex Semidefinite Programming and Max-k-Cut. In 1st Symposium on Simplicity in Algorithms (SOSA 2018), volume 61 of OpenAccess Series in Informatics (OASIcs), pages 13:1–13:11, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. https:/​/​doi.org/​10.4230/​OASIcs.SOSA.2018.13.

[18] J.S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E. Schuyler Fried, S. Hong, et al. Unsupervised Machine Learning on a Hybrid Quantum Computer, 2017. https:/​/​doi.org/​10.48550/​arXiv.1712.05771.

[19] Ruslan Shaydulin, Ilya Safro, and Jeffrey Larson. Multistart Methods for Quantum Approximate Optimization. In 2019 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–8. IEEE, 2019. https:/​/​doi.org/​10.1109/​HPEC.2019.8916288.

[20] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler, and Swati Gupta. Bridging Classical and Quantum with SDP initialized warm-starts for QAOA, 2020. https:/​/​doi.org/​10.48550/​arXiv.2010.14021.

[21] Paul M. B. Vitányi. How well can a graph be $n$-colored? Discrete Math., 34(1):69–80, Jan 1981. https:/​/​doi.org/​10.1016/​0012-365X(81)90023-6.

[22] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel. Quantum approximate optimization algorithm for MaxCut: A fermionic view. Phys. Rev. A, 97:022304, Feb 2018. https:/​/​doi.org/​10.1103/​PhysRevA.97.022304.

[23] Nicholas C. Wormald. The asymptotic distribution of short cycles in random regular graphs. Journal of Combinatorial Theory, Series B, 31(2):168 – 182, 1981. https:/​/​doi.org/​10.1016/​S0095-8956(81)80022-6.

[24] Jiahao Yao, Marin Bukov, and Lin Lin. Policy Gradient based Quantum Approximate Optimization Algorithm, 2020. https:/​/​doi.org/​10.48550/​arXiv.2002.01068.

Cited by

[1] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, "Noisy intermediate-scale quantum algorithms", Reviews of Modern Physics 94 1, 015004 (2022).

[2] Jiahao Yao, Paul Köttering, Hans Gundlach, Lin Lin, and Marin Bukov, "Noise-Robust End-to-End Quantum Control using Deep Autoregressive Policy Networks", arXiv:2012.06701.

[3] Daniel J. Egger, Jakub Marecek, and Stefan Woerner, "Warm-starting quantum optimization", arXiv:2009.10095.

[4] Yannick Deller, Sebastian Schmitt, Maciej Lewenstein, Steve Lenk, Marika Federer, Fred Jendrzejewski, Philipp Hauke, and Valentin Kasper, "Quantum approximate optimization algorithm for qudit systems with long-range interactions", arXiv:2204.00340.

[5] Jordi R. Weggemans, Alexander Urech, Alexander Rausch, Robert Spreeuw, Richard Boucherie, Florian Schreck, Kareljan Schoutens, Jiří Minář, and Florian Speelman, "Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach", arXiv:2106.11672.

[6] Pablo Díez-Valle, Diego Porras, and Juan José García-Ripoll, "Quantum variational optimization: The role of entanglement and problem hardness", Physical Review A 104 6, 062426 (2021).

[7] Nishant Jain, Brian Coyle, Elham Kashefi, and Niraj Kumar, "Graph neural network initialisation of quantum approximate optimisation", arXiv:2111.03016.

[8] Ali Hamed Moosavian, Seyed Sajad Kahani, and Salman Beigi, "Limits of Short-Time Quantum Annealing", arXiv:2104.12808.

[9] Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron, and Margarita Veshchezerova, "Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles", arXiv:2012.14859.

[10] Sami Boulebnane, Xavier Lucas, Agnes Meyder, Stanislaw Adaszewski, and Ashley Montanaro, "Peptide conformational sampling using the Quantum Approximate Optimization Algorithm", arXiv:2204.01821.

[11] Eneko Osaba, Esther Villar-Rodriguez, Izaskun Oregi, and Aitor Moreno-Fernandez-de-Leceta, "Focusing on the Hybrid Quantum Computing -- Tabu Search Algorithm: new results on the Asymmetric Salesman Problem", arXiv:2102.05919.

[12] David A. Herrera-Martí, "Policy Gradient Approach to Compilation of Variational Quantum Circuits", arXiv:2111.10227.

[13] Anh-Dzung Doan, Michele Sasdelli, David Suter, and Tat-Jun Chin, "A Hybrid Quantum-Classical Algorithm for Robust Fitting", arXiv:2201.10110.

[14] Xin Wang, "Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation Algorithm", arXiv:2110.08016.

[15] Ruslan Shaydulin and Stefan M. Wild, "Exploiting Symmetry Reduces the Cost of Training QAOA", arXiv:2101.10296.

[16] Jingjing Cui, Yifeng Xiong, Soon Xin Ng, and Lajos Hanzo, "Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection", arXiv:2107.05020.

[17] Sayan Mukherjee, "A Grover search-based algorithm for the list coloring problem", arXiv:2108.09061.

[18] Libor Caha, Alexander Kliesch, and Robert Koenig, "Twisted hybrid algorithms for combinatorial optimization", arXiv:2203.00717.

[19] Ashish Kakkar, Jeffrey Larson, Alexey Galda, and Ruslan Shaydulin, "Characterizing Error Mitigation by Symmetry Verification in QAOA", arXiv:2204.05852.

The above citations are from SAO/NASA ADS (last updated successfully 2022-05-29 02:38:14). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2022-05-29 02:38:12).