Application of quantum approximate optimization algorithm in graph coloring

doi:10.3969/j.issn.1007-5461.2026.01.010

Abstract

Abstract: The graph coloring problem is classified as one of NP-complete problems, and currently there is no known algorithm that can solve such problems in polynomial time in all cases. In response to this issue, we map it to quantum bits and design a quantum circuit in this work based on the quantum approximate optimization algorithm (QAOA). Firstly, we quantize the classical Ising model of the problem using rotation operators and Pauli operators to derive the problem's Hamiltonian. Subsequently, two parameterized unitary transformations are designed based on the mixing Hamiltonian and the problem Hamiltonian, and the expectation value of the problem's Hamiltonian is obtained by alternately applying these two unitary transformations. Specifically, to increase the probability of obtaining the correct solution, the Powell algorithm is used to optimize the parameters during the quantum state evolution to adjust the expectation value. Finally, based on the Hamiltonian, the initial state and the required quantum gates of the algorithm are derived, the quantum circuit is generated, and simulation experiments are conducted using Qiskit quantum framework of IBM. The experimental results show that the proposed approach can obtain the solution of graph coloring problem with high probability in polynomial time, demonstrating a significant exponential speedup.

Key words: quantum computing, quantum approximate optimization algorithm, quantum circuit, Hamiltonian, graph coloring, unitary transformation

CLC Number:

TP399

LIU Yutong, LI Zhiqiang , Yin Jingwei . Application of quantum approximate optimization algorithm in graph coloring[J]. Chinese Journal of Quantum Electronics, 2026, 43(1): 120-130.

References

[1] Karp R M, Miller R E, Thatcher J W. Reducibility among combinatorial problems [J]. The Journal of Symbolic Logic, 1975, 40: 618-619.
[2] Lewis R M R. Guide to Graph Colouring: Algorithms and Applications[M]. Cham: Springer International Publishing, 2021, 1-16.
[3] Ogunkan S K, Idowu P O, Omidiora E O, et al. First Fit Algorithm: A Graph Coloring Approach to Conflict-Free University Course Timetabling[J]. Asian Journal of Research in Computer Science, 2024, 17(5): 125–139.
[4] Tushir B, Dhurandher S K, Woungang I, et al. Graph colouring technique for efficient channel allocation in cognitive radio networks[C]//2016 IEEE International Conference on Communications (ICC). IEEE, 2016: 1-5.
[5] De S. An efficient technique of resource scheduling in cloud using graph coloring algorithm[J]. Global Transitions Proceedings, 2022, 3(1): 169–176.
[6] Sim K M, Sun W H. Multiple ant-colony optimization for network routing[A]. First International Symposium on Cyber Worlds, 2002. Proceedings.[C]. 2002: 277–281.
[7] Bairamkulov R, Friedman E. Graphs in VLSI circuits and systems[M]. Cham: Springer International Publishing, 2022: 59-100.
[8] Patidar H, Chakrabarti P. A tree-based graph coloring algorithm using independent set[C]//Progress in Advanced Computing and Intelligent Engineering: Proceedings of ICACIE 2017, Volume 2. Springer Singapore, 2019: 537-546.
[9] Brighen A, Slimani H, Rezgui A, et al. A new distributed graph coloring algorithm for large graphs[J]. Cluster Computing, 2024, 27(1): 875–891.
[10] Costa D, Hertz A. Ants can colour graphs[J]. Journal of the Operational Research Society, 1997, 48(3): 295–305.
[11] Chiarandini M, Stützle T. An application of iterated local search to graph coloring problem[C]//Proceedings of the computational symposium on graph coloring and its generalizations. New York (USA): Ithaca, 2002: 112-125.
[12] Salari E, Eshghi K. An ACO algorithm for graph coloring problem[C]//2005 ICSC Congress on computational intelligence methods and applications. IEEE, 2005: 5 pp.
[13] Kole A, De D, Pal A J. Solving graph coloring problem using ant colony optimization, simulated annealing and quantum annealing—A comparative study[M]. Singapore: Springer Singapore, 2022: 1-15.
[14] Marappan R, Sethumadhavan G. Solution to Graph Coloring Using Genetic and Tabu Search Procedures[J]. Arabian Journal for Science and Engineering, 2018, 43(2): 525–542.
[15] Elhachmi J, Guennoun Z. Cognitive radio spectrum allocation using genetic algorithm[J]. EURASIP Journal on Wireless Communications and Networking, SpringerOpen, 2016, 2016(1): 1–11.
[16] Agizza M, Balzano W, Stranieri S. An Improved Ant Colony Optimization Based Parking Algorithm with Graph Coloring[A]. Advanced Information Networking and Applications[C]. Springer, Cham, 2022: 82–94.
[17] Arute F, Arya K, Babbush R, et al. Quantum supremacy using a programmable superconducting processor[J]. Nature, Nature Publishing Group, 2019, 574(7779): 505–510.
[18] Zhong H-S, Wang H, Deng Y-H, et al. Quantum computational advantage using photons[J]. Science, American Association for the Advancement of Science, 2020, 370(6523): 1460–1463.
[19] Ahnefeld F, Theurer T, Egloff D, et al. Coherence as a Resource for Shor’s Algorithm[J]. Physical Review Letters, American Physical Society, 2022, 129(12): 120501.
[20] Farhi E, Goldstone J, Gutmann S. A Quantum Approximate Optimization Algorithm[EB/OL]. arXiv.org. 2014-11-14/2024-04-26. https://arxiv.longhoe.net/abs/1411.4028v1.
[21] Zhang Y J, Mu X D, Liu X W, et al. Applying the quantum approximate optimization algorithm to the minimum vertex cover problem[J]. Applied Soft Computing, 2022, 118: 108554.
[22] Roch C, Impertro A, Phan T, et al. Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA[A]. 2020 International Conference on Rebooting Computing (ICRC)[C]. 2020: 50–57.
[23] Ruan Y, Marsh S, Xue X, et al. The Quantum Approximate Algorithm for Solving Traveling Salesman Problem[J]. Computers, Materials & Continua, 2020, 63(3): 1237–1247.
[24] Farhi E, Harrow A W. Quantum supremacy through the quantum approximate optimization algorithm[J]. arxiv preprint arxiv:1602.07674, 2016.
[25] Fu Y, Anderson P W. Application of statistical mechanics to NP-complete problems in combinatorial optimisation[J]. Journal of Physics A: Mathematical and General, 1986, 19(9): 1605.
[26] Mézard M, Montanari A. Information, Physics, and Computation[M]. Oxford University Press, 2009, 381–399.
[27] Lucas A. Ising formulations of many NP problems[J]. Frontiers in Physics, Frontiers, 2014, 2.
[28] Vikst?l P, Gr?nkvist M, Svensson M, et al. Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem[J]. Physical Review Applied, American Physical Society, 2020, 14(3): 034009.
[29] Altshuler B, Krovi H, Roland J. Anderson localization makes adiabatic quantum optimization fail[J]. Proceedings of the National Academy of Sciences, Proceedings of the National Academy of Sciences, 2010, 107(28): 12446–12450.
[30] Choi V. Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3SAT problems[J]. Quantum Information & Computation, 2011, 11(7–8): 638–648.
[31] Powell M J D. A direct search optimization method that models the objective and constraint functions by linear interpolation[M]. Springer Netherlands, 1994, 51-67.
[32] Nelder J A, Mead R. A Simplex Method for Function Minimization[J]. The Computer Journal, 1965, 7(4): 308–313.
[33] Frazier P I. A Tutorial on Bayesian Optimization[EB/OL]. arXiv.org. 2018-07-08/2024-04-26. https://arxiv.longhoe.net/abs/1807.02811v1.
[34] Blekos K, Brand D, Ceschini A, et al. A review on Quantum Approximate Optimization Algorithm and its variants[J]. Physics Reports, 2024, 1068: 1–66.
[35] Powell M J D. An efficient method for finding the minimum of a function of several variables without calculating derivatives[J]. The Computer Journal, 1964, 7(2): 155–162.
[36] Zhou L, Wang S-T, Choi S, et al. Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices[J]. Physical Review X, American Physical Society, 2020, 10(2): 021067.