{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T03:12:51Z","timestamp":1778901171985,"version":"3.51.4"},"reference-count":24,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T00:00:00Z","timestamp":1648598400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"crossref","award":["W911NF-20-1-0014"],"award-info":[{"award-number":["W911NF-20-1-0014"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000015","name":"Department of Energy","doi-asserted-by":"crossref","award":["DE-SC0018407"],"award-info":[{"award-number":["DE-SC0018407"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["PHY-1733907"],"award-info":[{"award-number":["PHY-1733907"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.22331\/q-2022-03-30-678","type":"journal-article","created":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T18:42:46Z","timestamp":1648665766000},"page":"678","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":82,"title":["Hybrid quantum-classical algorithms for approximate graph coloring"],"prefix":"10.22331","volume":"6","author":[{"given":"Sergey","family":"Bravyi","sequence":"first","affiliation":[{"name":"IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Kliesch","sequence":"additional","affiliation":[{"name":"Zentrum Mathematik, Technical University of Munich, 85748 Garching, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Koenig","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study & Zentrum Mathematik, Technical University of Munich, 85748 Garching, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eugene","family":"Tang","sequence":"additional","affiliation":[{"name":"Institute for Quantum Information and Matter, Caltech, Pasadena, CA 91125"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2022,3,30]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Noga Alon and Nabil Kahale. A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput., 26(6):1733\u20131748, December 1997. https:\/\/doi.org\/10.1137\/S0097539794270248.","DOI":"10.1137\/S0097539794270248"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. For Fixed Control Parameters the Quantum Approximate Optimization Algorithm&apos;s Objective Function Value Concentrates for Typical Instances, 2018. https:\/\/doi.org\/10.48550\/arXiv.1812.04170.","DOI":"10.48550\/arXiv.1812.04170"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.125.260505"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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\u2013322, 2006. https:\/\/doi.org\/10.1002\/rsa.20096.","DOI":"10.1002\/rsa.20096"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Daniel J. Egger, Jakub Mare\u010dek, and Stefan Woerner. Warm-starting quantum optimization. Quantum, 5:479, June 2021. https:\/\/doi.org\/10.22331\/q-2021-06-17-479.","DOI":"10.22331\/q-2021-06-17-479"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.2005.08747"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm, 2014. https:\/\/doi.org\/10.48550\/arXiv.1411.4028.","DOI":"10.48550\/arXiv.1411.4028"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Alan Frieze and M. Jerrum. Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. Algorithmica, 18(1):67\u201381, 05 1997. https:\/\/doi.org\/10.1007\/BF02523688.","DOI":"10.1007\/BF02523688"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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 &apos;01, page 443\u2013452, New York, NY, USA, 2001. Association for Computing Machinery. https:\/\/doi.org\/10.1145\/380752.380838.","DOI":"10.1145\/380752.380838"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Michel X. Goemans and David P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM, 42(6):1115\u20131145, 1995. https:\/\/doi.org\/10.1145\/227683.227684.","DOI":"10.1145\/227683.227684"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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\u20131266, 1998. https:\/\/doi.org\/10.1109\/12.736440.","DOI":"10.1109\/12.736440"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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\u201318, June 1997. https:\/\/doi.org\/10.4086\/cjtcs.1997.002.","DOI":"10.4086\/cjtcs.1997.002"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O\u2019Donnell. Optimal Inapproximability Results for MAX\u2010CUT and Other 2\u2010Variable CSPs? SIAM Journal on Computing, 37(1):319\u2013357, 2007. https:\/\/doi.org\/10.1137\/S0097539705447372.","DOI":"10.1137\/S0097539705447372"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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\u2013294, 09 2004. https:\/\/doi.org\/10.1023\/B:JOCO.0000038911.67280.3f.","DOI":"10.1023\/B:JOCO.0000038911.67280.3f"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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\u20136, 2018. https:\/\/doi.org\/10.1038\/s41467-018-07090-4.","DOI":"10.1038\/s41467-018-07090-4"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PRXQuantum.2.030312"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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\u201313:11, Dagstuhl, Germany, 2018. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2018.13.","DOI":"10.4230\/OASIcs.SOSA.2018.13"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.1712.05771"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Ruslan Shaydulin, Ilya Safro, and Jeffrey Larson. Multistart Methods for Quantum Approximate Optimization. In 2019 IEEE High Performance Extreme Computing Conference (HPEC), pages 1\u20138. IEEE, 2019. https:\/\/doi.org\/10.1109\/HPEC.2019.8916288.","DOI":"10.1109\/HPEC.2019.8916288"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.2010.14021"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Paul M. B. Vit\u00e1nyi. How well can a graph be $n$-colored? Discrete Math., 34(1):69\u201380, Jan 1981. https:\/\/doi.org\/10.1016\/0012-365X(81)90023-6.","DOI":"10.1016\/0012-365X(81)90023-6"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.97.022304"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Nicholas C. Wormald. The asymptotic distribution of short cycles in random regular graphs. Journal of Combinatorial Theory, Series B, 31(2):168 \u2013 182, 1981. https:\/\/doi.org\/10.1016\/S0095-8956(81)80022-6.","DOI":"10.1016\/S0095-8956(81)80022-6"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Jiahao Yao, Marin Bukov, and Lin Lin. Policy Gradient based Quantum Approximate Optimization Algorithm, 2020. https:\/\/doi.org\/10.48550\/arXiv.2002.01068.","DOI":"10.48550\/arXiv.2002.01068"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-03-30-678\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T18:42:55Z","timestamp":1648665775000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-03-30-678\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,30]]},"references-count":24,"URL":"https:\/\/doi.org\/10.22331\/q-2022-03-30-678","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,30]]},"article-number":"678"}}