Hybrid quantum-classical algorithms for approximate graph coloring
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
| 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
► 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] Camille Grange, Michael Poss, and Eric Bourreau, "An introduction to variational quantum algorithms for combinatorial optimization problems", Annals of Operations Research 343 2, 847 (2024).
[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] Eunok Bae, Hyukjoon Kwon, V Vijendran, and Soojoon Lee, "Modified recursive QAOA for exact MAX-CUT solutions on bipartite graphs: closing the gap beyond QAOA limit", Journal of Physics A: Mathematical and Theoretical 58 48, 485304 (2025).
[6] Anita Weidinger, Glen Bigan Mbeng, Michael Fellner, Davit Khachatryan, and Wolfgang Lechner, "Performance of parity QAOA for the signed Max-Cut problem", New Journal of Physics 28 3, 034514 (2026).
[7] Hui Geng, Tian-Ci Li, Yu-Xiang Gao, Wei-Bin Ye, Chun-Jing Si, Li-Mei Qi, and Ming-Deng Shi, "Strategies for optimizing resource efficiency in the laundry process", Water Supply 25 9, 1292 (2025).
[8] 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).
[9] Sebastiano Corli, Lorenzo Moro, Daniele Dragoni, Massimiliano Dispenza, and Enrico Prati, "Quantum machine learning algorithms for anomaly detection: A review", Future Generation Computer Systems 166, 107632 (2025).
[10] Filip B. Maciejewski, Jacob Biamonte, Stuart Hadfield, and Davide Venturelli, "Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping", Quantum 9, 1906 (2025).
[11] 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).
[12] Yash J. Patel, Sofiene Jerbi, Thomas Bäck, and Vedran Dunjko, "Reinforcement learning assisted recursive QAOA", EPJ Quantum Technology 11 1, 6 (2024).
[13] 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).
[14] Bidisha Dhara, Monika Agrawal, and Sumantra Dutta Roy, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 31 (2025) ISBN:979-8-3315-5736-2.
[15] 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).
[16] Anita Weidinger, Glen Bigan Mbeng, and Wolfgang Lechner, "Error mitigation for quantum approximate optimization", Physical Review A 108 3, 032408 (2023).
[17] Farzaneh Shayeganfar, Ali Ramazani, Veera Sundararaghavan, and Yuhua Duan, "Quantum graph learning and algorithms applied in quantum computer sciences and image classification", Applied Physics Reviews 12 2, 021327 (2025).
[18] Ali Al-Bayaty and Marek Perkowski, "The impact of optimization approximation algorithms on the performance of the BHT-QAOA", Academia Quantum 2 4(2025).
[19] Yifeng Peng, Xinyi Li, Zhiding Liang, and Ying Wang, "HyQ2: A Hybrid Quantum Neural Network for NextG Vulnerability Detection", IEEE Transactions on Quantum Engineering 5, 1 (2024).
[20] Hiromichi Matsuyama, Wei-hao Huang, Kohji Nishimura, and Yu Yamashiro, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 470 (2024) ISBN:979-8-3315-4137-8.
[21] Michele Cattelan, Sheir Yarkoni, and Wolfgang Lechner, "Parallel circuit implementation of variational quantum algorithms", npj Quantum Information 11 1, 27 (2025).
[22] Erik J. Gustafson, Henry Lamm, Diyi Liu, Edison M. Murairi, and Shuchen Zhu, "Synthesis of single-qutrit circuits from Clifford +R gates", Physical Review A 112 6, 062414 (2025).
[23] Friedrich Wagner, Jonas Nüßlein, and Frauke Liers, "Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming", ACM Transactions on Quantum Computing 6 2, 1 (2025).
[24] Frank Phillipson, Niels Neumann, and Robert Wezeman, Lecture Notes in Computer Science 14077, 18 (2023) ISBN:978-3-031-36029-9.
[25] Maxime Dupont and Bhuvanesh Sundar, "Extending relax-and-round combinatorial optimization solvers with quantum correlations", Physical Review A 109 1, 012429 (2024).
[26] 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).
[27] Prem Shanker Dwivedi, Abhinav Kumar, and Amit Biswas, 2025 2nd International Conference on Advanced Computing and Emerging Technologies (ACET) 1 (2025) ISBN:979-8-3315-6783-5.
[28] G. Paradezhenko, A. Pervishko, and D. Yudin, "Quantum-Assisted Open-Pit Optimization", JETP Letters 119 6, 470 (2024).
[29] Umadevi. G, Yamini. S, Sivakami Sundari. M, and Senthil Kumar. K, 2025 Tenth International Conference on Science Technology Engineering and Mathematics (ICONSTEM) 1 (2025) ISBN:979-8-3315-6187-1.
[30] Nisrean Jaber Thalji, 2024 7th International Conference on Internet Applications, Protocols, and Services (NETAPPS) 1 (2024) ISBN:979-8-3315-1951-3.
[31] Toonyawat Angkhanawin, Aydin Deger, Jonathan D Pritchard, and C Stuart Adams, "Graph coloring via quantum optimization on a Rydberg-qudit atom array", Quantum Science and Technology 11 2, 025012 (2026).
[32] Sukhpal Singh Gill, Muhammed Golec, Jianmin Hu, Minxian Xu, Junhui Du, Huaming Wu, Guneet Kaur Walia, Subramaniam Subramanian Murugesan, Babar Ali, Mohit Kumar, Kejiang Ye, Prabal Verma, Surendra Kumar, Felix Cuadrado, and Steve Uhlig, "Edge AI: A Taxonomy, Systematic Review and Future Directions", Cluster Computing 28 1, 18 (2025).
[33] Carlos A. Riofrío, Johannes Klepsch, Jernej Rudi Finžgar, Florian Kiwit, Leonhard Hölscher, Marvin Erdmann, Lukas Müller, Chandan Kumar, Youssef Achari Berrada, and Andre Luckow, Quantum Computational AI 181 (2026) ISBN:9780443302596.
[34] 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).
[35] Dongmei Liu, Jian Li, Xiubo Chen, Shibin Zhang, Yan Chang, and Lili Yan, "Hierarchical quantum approximation optimization algorithm for solving graph-coloring problems", Physical Review A 113 4, 042610 (2026).
[36] Ramin Fakhimi and Hamidreza Validi, Encyclopedia of Optimization 1 (2023) ISBN:978-3-030-54621-2.
[37] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Gerhard Kircher, Thomas Kleinert, Thorsten Koch, Georgios Korpas, Steve Lenk, Jakub Marecek, Vanio Markov, Guglielmo Mazzola, Stefano Mensa, Naeimeh Mohseni, Giacomo Nannicini, Corey O’Meara, Elena Peña Tapia, Sebastian Pokutta, Manuel Proissl, Patrick Rebentrost, Emre Sahin, Benjamin C. B. Symons, Sabine Tornow, Víctor Valls, Stefan Woerner, Mira L. Wolf-Bauwens, Jon Yard, Sheir Yarkoni, Dirk Zechiel, Sergiy Zhuk, and Christa Zoufal, "Challenges and opportunities in quantum optimization", Nature Reviews Physics 6 12, 718 (2024).
[38] Frank Phillipson, "Quantum Computing in Telecommunication—A Survey", Mathematics 11 15, 3423 (2023).
[39] G. Paradezhenko, A. Pervishko, and D. Yudin, "Variatsionnaya kvantovaya optimizatsiya otkrytogo kar'era", Pisʹma v žurnal êksperimentalʹnoj i teoretičeskoj fiziki 119 5-6, 459 (2024).
[40] Assia Brighen, Asma Chouikh, Hamida Ikhlef, Hachem Slimani, Abdelmounaam Rezgui, and Hamamache Kheddouci, "Giraph-Based Distributed Algorithms for Coloring Large-Scale Graphs", International Journal of Parallel Programming 53 1, 1 (2025).
[41] Brandon Barton, Jacob Sagal, Sean Feeney, George Grattan, Pratik Patnaik, Vadim Oganesyan, Lincoln D Carr, and Eliot Kapit, "Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields", Quantum Science and Technology 10 4, 045063 (2025).
[42] Lukas Schmidbauer, Carlos A. Riofrío, Florian Heinrich, Vanessa Junk, Ulrich Schwenk, Thomas Husslein, and Wolfgang Mauerer, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 2101 (2025) ISBN:979-8-3315-5736-2.
[43] Gunsik Min and Jun Heo, 2023 14th International Conference on Information and Communication Technology Convergence (ICTC) 517 (2023) ISBN:979-8-3503-1327-7.
[44] 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).
[45] Freddy Alejandro Chaurra-Gutierrez, Claudia Feregrino-Uribe, and Guohua Sun, 2026 International Conference on Quantum Communications, Networking, and Computing (QCNC) 181 (2026) ISBN:979-8-3315-6110-9.
[46] Nishant Jain, Brian Coyle, Elham Kashefi, and Niraj Kumar, "Graph neural network initialisation of quantum approximate optimisation", Quantum 6, 861 (2022).
[47] Michael A. Perlin, Ruslan Shaydulin, Benjamin Hall, Pierre Minssen, Changhao Li, Kabir Dubey, Rich Rines, Eric Anschuetz, Marco Pistoia, and Pranav Gokhale, "Q-CHOP: Quantum constrained Hamiltonian optimization", ACM Transactions on Quantum Computing 3778864 (2025).
[48] 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).
[49] Jonathan Wurtz, Stefan H. Sack, and Sheng-Tao Wang, "Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms", IEEE Transactions on Quantum Engineering 5, 1 (2024).
[50] Vijendran V, Dax Enshan Koh, Eunok Bae, Hyukjoon Kwon, Ping Koy Lam, and Syed M Assad, "Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models", Quantum 10, 2158 (2026).
[51] Ruho Kondo, Yuki Sato, Rudy Raymond, and Naoki Yamamoto, "Recursive Quantum Relaxation for Combinatorial Optimization Problems", Quantum 9, 1594 (2025).
[52] Xin Wang, 2023 42nd Chinese Control Conference (CCC) 6777 (2023) ISBN:978-988-75815-4-3.
[53] David Bucher, Daniel Porawski, Maximilian Janetschek, Jonas Stein, Corey O'Meara, Giorgio Cortiana, and Claudia Linnhoff-Popien, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 356 (2025) ISBN:979-8-3315-5736-2.
[54] 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).
[55] Alon Levi, Ziv Ossi, Eliahu Cohen, and Amit Te’eni, "Optimal quantum likelihood estimation", Quantum Science and Technology 11 1, 015029 (2026).
[56] Michael Tsakiroglou, Ioannis Liliopoulos, Georgios D. Varsamis, Kristin Milchanowski, and Ioannis G. Karafyllidis, "Graph-encoded strategic interactions in multiplayer quantum games", Quantum Information Processing 25 4, 109 (2026).
[57] Burhan Gülbahar, "Majority Voting With Recursive QAOA and Cost-Restricted Uniform Sampling for Maximum-Likelihood Detection in Massive MIMO", IEEE Transactions on Wireless Communications 24 3, 2620 (2025).
[58] 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).
[59] Xiyun Zhang, Jiyuan Liu, and He Li, 2025 International Conference on Field Programmable Technology (ICFPT) 252 (2025) ISBN:979-8-3315-5752-2.
[60] 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).
[61] Ilya Tyagin, Marwa H. Farag, Kyle Sherbert, Karunya Shirali, Yuri Alexeev, and Ilya Safro, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 1505 (2025) ISBN:979-8-3315-5736-2.
[62] 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.
[63] Shuaiqun Pan, Yash J. Patel, Aneta Neumann, Frank Neumann, Thomas Bäck, and Hao Wang, Proceedings of the Genetic and Evolutionary Computation Conference 443 (2025) ISBN:9798400714658.
[64] Libor Caha, Alexander Kliesch, and Robert Koenig, "Twisted hybrid algorithms for combinatorial optimization", Quantum Science and Technology 7 4, 045013 (2022).
[65] Haomu Yuan, Christopher K Long, Hugo V Lepage, and Crispin H W Barnes, "Quantifying the advantages of applying quantum approximate algorithms to portfolio optimisation", Quantum Science and Technology 11 2, 025034 (2026).
[66] Linus Ekstrom, Hao Wang, and Sebastian Schmitt, "Variational quantum multiobjective optimization", Physical Review Research 7 2, 023141 (2025).
[67] Lucas T. Brady and Stuart Hadfield, "Quantum Davis-Putnam-Logemann-Loveland and generalized constraints in iterative quantum algorithms", Physical Review A 114 2, 022404 (2026).
[68] 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).
[69] Sayan Mukherjee, "A Grover Search-Based Algorithm for the List Coloring Problem", IEEE Transactions on Quantum Engineering 3, 1 (2022).
[70] Pooja and Sandeep Kumar Sood, "Sustainable and energy-efficient electric vehicle route navigation using a hybrid quantum optimization algorithm", Engineering Applications of Artificial Intelligence 176, 114659 (2026).
[71] Davide Venturelli, Erik Gustafson, Doga Kurkcuoglu, and Silvia Zorzetti, 2025 55th Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W) 196 (2025) ISBN:979-8-3315-1205-7.
[72] Reuben Tate and Stephan Eidenbenz, "Theoretical approximation ratios for Warm-Started QAOA on 3-regular max-cut instances at depth p=1", Theoretical Computer Science 1059, 115571 (2026).
[73] Archismita Dalal and Amara Katabarwa, "Noise tailoring for robust amplitude estimation", New Journal of Physics 25 2, 023015 (2023).
[74] Lucas T. Brady and Stuart Hadfield, "Iterative quantum algorithms for maximum independent set", Physical Review A 110 5, 052435 (2024).
[75] Dong Pan, Na Yang, Bao Wang, Jianxiong Jia, Zhuangzhuang Cao, and Dabo Zhang, 2024 6th International Conference on Energy, Power and Grid (ICEPG) 1772 (2024) ISBN:979-8-3503-7779-8.
[76] Lutfiana Sausan and Hyunsoo Lee, "Grover Algorithm-based Quantum Scheduling Framework for Constrained Graph Coloring", Journal of the Korean Institute of Industrial Engineers 51 6, 454 (2025).
[77] 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).
[78] Maximilian Hess, Lilly Palackal, Abhishek Awasthi, and Karen Wintersperger, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 221 (2024) ISBN:979-8-3315-4137-8.
[79] 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).
[80] 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.
[81] David A. Herrera-Martí, "Policy Gradient Approach to Compilation of Variational Quantum Circuits", Quantum 6, 797 (2022).
[82] Alberto Bottarelli, Sebastian Schmitt, and Philipp Hauke, "Inequality constraints in variational quantum circuits with qudits", Physical Review Research 7 3, 033202 (2025).
[83] José A. Tirado-Domínguez, Eladio Gutiérrez, and Oscar Plata, "QTIS: A QAOA-based Quantum Time Interval Scheduler", Future Generation Computer Systems 183, 108594 (2026).
[84] Ali Hamed Moosavian, Seyed Sajad Kahani, and Salman Beigi, "Limits of Short-Time Evolution of Local Hamiltonians", Quantum 6, 744 (2022).
[85] 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).
[86] Daniel J. Egger, Jakub Mareček, and Stefan Woerner, "Warm-starting quantum optimization", Quantum 5, 479 (2021).
[87] Carlos A. Riofr\'io, Johannes Klepsch, Jernej Rudi Fin\v{z}gar, Florian Kiwit, Leonhard H\"olscher, Marvin Erdmann, Lukas M\"uller, Chandan Kumar, Youssef Achari Berrada, and Andre Luckow, "Quantum Computing for Automotive Applications", arXiv:2409.14183, (2024).
[88] 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).
[89] 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).
[90] 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", EPJ Quantum Technology 8 1, 12 (2021).
[91] 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).
[92] Reuben Tate and Stephan Eidenbenz, "Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$", arXiv:2402.12631, (2024).
[93] David Bucher, Daniel Porawski, Maximilian Janetschek, Jonas Stein, Corey O'Meara, Giorgio Cortiana, and Claudia Linnhoff-Popien, "Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems", arXiv:2506.03115, (2025).
[94] Ashish Kakkar, Jeffrey Larson, Alexey Galda, and Ruslan Shaydulin, "Characterizing Error Mitigation by Symmetry Verification in QAOA", arXiv:2204.05852, (2022).
[95] 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).
[96] Ruslan Shaydulin and Stefan M. Wild, "Exploiting Symmetry Reduces the Cost of Training QAOA", IEEE Transactions on Quantum Engineering 2, TQE.2021 (2021).
[97] Friedrich Wagner, Jonas Nüßlein, and Frauke Liers, "Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming", arXiv:2302.05493, (2023).
[98] Shuaiqun Pan, Yash J. Patel, Aneta Neumann, Frank Neumann, Thomas Bäck, and Hao Wang, "Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms", arXiv:2502.12012, (2025).
[99] Xiao-Hui Ni, Jia-Cheng Fan, Ling-Xiao Li, Zi-Wen Huang, Su-Juan Qin, Bing-Jie Xu, Wei-Huang, and Fei Gao, "Quantum-Assisted Recursive Algorithm for Solving the Exact Cover Problem", arXiv:2509.10811, (2025).
[100] Ruho Kondo, Yuki Sato, Rudy Raymond, and Naoki Yamamoto, "Recursive Quantum Relaxation for Combinatorial Optimization Problems", arXiv:2403.02045, (2024).
[101] Jingjing Cui, Yifeng Xiong, Soon Xin Ng, and Lajos Hanzo, "Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection", IEEE Transactions on Communications 70 8, 5386 (2022).
[102] Yifeng Peng, Xinyi Li, Zhiding Liang, and Ying Wang, "Hybrid Quantum Downsampling Networks", arXiv:2405.16375, (2024).
[103] 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).
[104] Noah L. Wach, Manuel S. Rudolph, Fred Jendrzejewski, and Sebastian Schmitt, "Data re-uploading with a single qudit", arXiv:2302.13932, (2023).
[105] Anh-Dzung Doan, Michele Sasdelli, David Suter, and Tat-Jun Chin, "A Hybrid Quantum-Classical Algorithm for Robust Fitting", arXiv:2201.10110, (2022).
[106] Jingjing Cui, Yifeng Xiong, Soon Xin Ng, and Lajos Hanzo, "Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection", arXiv:2107.05020, (2021).
[107] Lukas Schmidbauer, Carlos A. Riofrío, Florian Heinrich, Vanessa Junk, Ulrich Schwenk, Thomas Husslein, and Wolfgang Mauerer, "Path Matters: Industrial Data Meet Quantum Optimization", arXiv:2504.16607, (2025).
[108] Michael J. Cervia, Henry Lamm, Diyi Liu, Edison M. Murairi, and Shuchen Zhu, "Magic State Distillation using Asymptotically Good Codes on Qudits", arXiv:2512.21874, (2025).
[109] Xin Wang, "Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation Algorithm", arXiv:2110.08016, (2021).
[110] José A. Tirado-Domínguez, Eladio Gutiérrez, and Oscar Plata, "QTIS: A QAOA-Based Quantum Time Interval Scheduler", arXiv:2511.15590, (2025).
[111] András Czégel, Dávid Sipos, and Boglárka G. -Tóth, "A quantum-classical hybrid branch & bound algorithm", arXiv:2511.19501, (2025).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-13 15:26:58) and SAO/NASA ADS (last updated successfully 2026-08-13 15:26:59). 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.