Hybrid quantum-classical algorithms for approximate graph coloring

Sergey Bravyi; Alexander Kliesch; Robert Koenig; Eugene Tang

doi:10.22331/q-2022-03-30-678

Hybrid quantum-classical algorithms for approximate graph coloring

Sergey Bravyi¹, Alexander Kliesch², Robert Koenig³, and Eugene Tang⁴

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

Published:	2022-03-30, volume 6, page 678
Eprint:	arXiv:2011.13420v2
Doi:	https://doi.org/10.22331/q-2022-03-30-678
Citation:	Quantum 6, 678 (2022).

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

Abstract

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

@article{Bravyi2022hybridquantum,
  doi = {10.22331/q-2022-03-30-678},
  url = {https://doi.org/10.22331/q-2022-03-30-678},
  title = {Hybrid quantum-classical algorithms for approximate graph coloring},
  author = {Bravyi, Sergey and Kliesch, Alexander and Koenig, Robert and Tang, Eugene},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {678},
  month = mar,
  year = {2022}
}

► 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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] Eunok Bae and Soojoon Lee, "Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs", Quantum Information Processing 23 3, 78 (2024).

[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] Shao-Hen Chiew, Kilian Poirier, Rajesh Mishra, Ulrike Bornheimer, Ewan Munro, Si Han Foon, Christopher Wanru Chen, Wei Sheng Lim, and Chee Wei Nga, "Multiobjective Optimization and Network Routing With Near-Term Quantum Computers", IEEE Transactions on Quantum Engineering 5, 1 (2024).

[9] Yash J. Patel, Sofiene Jerbi, Thomas Bäck, and Vedran Dunjko, "Reinforcement learning assisted recursive QAOA", EPJ Quantum Technology 11 1, 6 (2024).

[10] Jernej Rudi Finžgar, Aron Kerschbaumer, Martin J.A. Schuetz, Christian B. Mendl, and Helmut G. Katzgraber, "Quantum-Informed Recursive Optimization Algorithms", PRX Quantum 5 2, 020327 (2024).

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

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

[13] Márton Karácsony, László Oroszlány, and Zoltan Zimboras, "Efficient qudit based scheme for photonic quantum computing", SciPost Physics Core 7 2, 032 (2024).

[14] Han Qi, Sihui Xiao, Zhuo Liu, Changqing Gong, and Abdullah Gani, "Variational quantum algorithms: fundamental concepts, applications and challenges", Quantum Information Processing 23 6, 224 (2024).

[15] Chiara Vercellino, Giacomo Vitali, Paolo Viviani, Edoardo Giusto, Alberto Scionti, Andrea Scarabosio, Olivier Terzo, and Bartolomeo Montrucchio, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 141 (2023) ISBN:979-8-3503-4323-6.

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

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

[18] Maxime Dupont and Bhuvanesh Sundar, "Extending relax-and-round combinatorial optimization solvers with quantum correlations", Physical Review A 109 1, 012429 (2024).

[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] G. Paradezhenko, A. Pervishko, and D. Yudin, "Quantum-Assisted Open-Pit Optimization", JETP Letters 119 6, 470 (2024).

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

[22] Sayan Mukherjee, "A Grover Search-Based Algorithm for the List Coloring Problem", IEEE Transactions on Quantum Engineering 3, 1 (2022).

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

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

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

[26] G. Paradezhenko, A. Pervishko, and D. Yudin, "Variatsionnaya kvantovaya optimizatsiya otkrytogo kar'era", Письма в Журнал экспериментальной и теоретической физики 119 5-6, 459 (2024).

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

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

[29] Gunsik Min and Jun Heo, 2023 14th International Conference on Information and Communication Technology Convergence (ICTC) 517 (2023) ISBN:979-8-3503-1327-7.

[30] Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer, "A review on Quantum Approximate Optimization Algorithm and its variants", Physics Reports 1068, 1 (2024).

[31] V Vijendran, Aritra Das, Dax Enshan Koh, Syed M Assad, and Ping Koy Lam, "An expressive ansatz for low-depth quantum approximate optimisation", Quantum Science and Technology 9 2, 025010 (2024).

[32] Gabriel Bottrill, Mudit Pandey, and Olivia Di Matteo, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 177 (2023) ISBN:979-8-3503-4323-6.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2024-08-08 20:50:24) and SAO/NASA ADS (last updated successfully 2024-08-08 20:50:25). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.