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] Camille Grange, Michael Poss, and Eric Bourreau, "An introduction to variational quantum algorithms for combinatorial optimization problems", 4OR 21 3, 363 (2023).

[2] Ewout van den Berg, Sergey Bravyi, Jay M. Gambetta, Petar Jurcevic, Dmitri Maslov, and Kristan Temme, "Single-shot error mitigation by coherent Pauli checks", Physical Review Research 5 3, 033193 (2023).

[3] Noah L. Wach, Manuel S. Rudolph, Fred Jendrzejewski, and Sebastian Schmitt, "Data re-uploading with a single qudit", Quantum Machine Intelligence 5 2, 36 (2023).

[4] Reuben Tate, Jai Moondra, Bryan Gard, Greg Mohler, and Swati Gupta, "Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths", Quantum 7, 1121 (2023).

[5] Xin Wang, 2023 42nd Chinese Control Conference (CCC) 6777 (2023) ISBN:978-988-75815-4-3.

[6] Yannick Deller, Sebastian Schmitt, Maciej Lewenstein, Steve Lenk, Marika Federer, Fred Jendrzejewski, Philipp Hauke, and Valentin Kasper, "Quantum approximate optimization algorithm for qudit systems", Physical Review A 107 6, 062410 (2023).

[7] Erdi Acar, Saim Hatipoğlu, and İhsan Yılmaz, "A quantum algorithm for solving weapon target assignment problem", Engineering Applications of Artificial Intelligence 125, 106668 (2023).

[8] Pradeep Niroula, Ruslan Shaydulin, Romina Yalovetzky, Pierre Minssen, Dylan Herman, Shaohan Hu, and Marco Pistoia, "Constrained quantum optimization for extractive summarization on a trapped-ion quantum computer", Scientific Reports 12 1, 17171 (2022).

[9] Ramin Fakhimi and Hamidreza Validi, Encyclopedia of Optimization 1 (2023) ISBN:978-3-030-54621-2.

[10] Frank Phillipson, "Quantum Computing in Telecommunication—A Survey", Mathematics 11 15, 3423 (2023).

[11] Archismita Dalal and Amara Katabarwa, "Noise tailoring for robust amplitude estimation", New Journal of Physics 25 2, 023015 (2023).

[12] He-Liang Huang, Xiao-Yue Xu, Chu Guo, Guojing Tian, Shi-Jie Wei, Xiaoming Sun, Wan-Su Bao, and Gui-Lu Long, "Near-term quantum computing techniques: Variational quantum algorithms, error mitigation, circuit compilation, benchmarking and classical simulation", Science China Physics, Mechanics & Astronomy 66 5, 250302 (2023).

[13] Anita Weidinger, Glen Bigan Mbeng, and Wolfgang Lechner, "Error mitigation for quantum approximate optimization", Physical Review A 108 3, 032408 (2023).

[14] I. S. Pichkovskiy and V. E. Zobov, "Clustering into Three Groups on a Quantum Processor of Five Spins S = 1, Controlled by Pulses of Resonant RF Fields", Applied Magnetic Resonance 54 7, 661 (2023).

[15] Libor Caha, Alexander Kliesch, and Robert Koenig, "Twisted hybrid algorithms for combinatorial optimization", Quantum Science and Technology 7 4, 045013 (2022).

[16] Frank Phillipson, Niels Neumann, and Robert Wezeman, Lecture Notes in Computer Science 10477, 18 (2023) ISBN:978-3-031-36029-9.

[17] David A. Herrera-Martí, "Policy Gradient Approach to Compilation of Variational Quantum Circuits", Quantum 6, 797 (2022).

[18] Nishant Jain, Brian Coyle, Elham Kashefi, and Niraj Kumar, "Graph neural network initialisation of quantum approximate optimisation", Quantum 6, 861 (2022).

[19] Sami Boulebnane, Xavier Lucas, Agnes Meyder, Stanislaw Adaszewski, and Ashley Montanaro, "Peptide conformational sampling using the Quantum Approximate Optimization Algorithm", npj Quantum Information 9 1, 70 (2023).

[20] Ali Hamed Moosavian, Seyed Sajad Kahani, and Salman Beigi, "Limits of Short-Time Evolution of Local Hamiltonians", Quantum 6, 744 (2022).

[21] 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).

[22] Daniel J. Egger, Jakub Mareček, and Stefan Woerner, "Warm-starting quantum optimization", Quantum 5, 479 (2021).

[23] 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", Quantum 6, 687 (2022).

[24] 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).

[25] 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, (2020).

[26] Asier Ozaeta, Wim van Dam, and Peter L. McMahon, "Expectation values from the single-layer quantum approximate optimization algorithm on Ising problems", Quantum Science and Technology 7 4, 045036 (2022).

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

[28] Lucas T. Brady and Stuart Hadfield, "Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms", arXiv:2309.13110, (2023).

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

[30] 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, (2020).

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

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

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

[34] 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, (2021).

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

The above citations are from Crossref's cited-by service (last updated successfully 2023-11-29 16:02:13) and SAO/NASA ADS (last updated successfully 2023-11-29 16:02:14). The list may be incomplete as not all publishers provide suitable and complete citation data.