量子近似优化算法在图着色中的应用

doi:10.3969/j.issn.1007-5461.2026.01.010

摘要/Abstract

摘要： 图着色问题属于NP完全问题, 目前尚未找到一种在所有情况下都能够在多项式时间内解决这类问题的算法。针对图着色问题, 本研究基于量子近似优化算法将其映射至量子比特并设计了量子电路。首先, 利用旋转算符和泡利算符对问题的经典伊辛模型进行量子化, 得到问题的哈密顿量。随后基于混合哈密顿量和问题哈密顿量设计了两种含参酉变换, 通过交替应用这两种酉变换得到问题哈密顿期望值。为提高正确解出现的概率, 在量子态演化的过程中使用Powell算法对参数进行优化以调整期望值。最后, 根据哈密顿量推导出算法的初始状态和所需的量子门, 生成量子电路, 并利用IBM量子框架Qiskit进行仿真实验。实验结果证实了该方案可以在多项式时间内以高概率获得问题解, 具备显著的指数级加速效果。

关键词: 量子计算, 量子近似优化算法, 量子电路, 哈密顿量, 图着色, 酉变换

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

中图分类号:

TP399

刘裕彤, 李志强, 尹经纬 . 量子近似优化算法在图着色中的应用[J]. 量子电子学报, 2026, 43(1): 120-130.

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.

参考文献

[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.