|
Special Issue:
Featured Column — COMPUTATIONAL PROGRAMS FOR PHYSICS
|
| COMPUTATIONAL PROGRAMS FOR PHYSICS |
Prev
Next
|
|
|
Progressive quantum algorithm for maximum independent set with quantum alternating operator ansatz |
| Xiao-Hui Ni(倪晓慧)1,2, Ling-Xiao Li(李凌霄)1, Yan-Qi Song(宋燕琪)3, Zheng-Ping Jin(金正平)1,2, Su-Juan Qin(秦素娟)1,2,†, and Fei Gao(高飞)1,2,‡ |
1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China;
2 School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing 100876, China;
3 China Academy of Information and Communications Technology, Beijing 100191, China |
|
|
|
|
Abstract The quantum alternating operator ansatz algorithm (QAOA+) is widely used for constrained combinatorial optimization problems (CCOPs) due to its ability to construct feasible solution spaces. In this paper, we propose a progressive quantum algorithm (PQA) to reduce qubit requirements for QAOA+ in solving the maximum independent set (MIS) problem. PQA iteratively constructs a subgraph likely to include the MIS solution of the original graph and solves the problem on it to approximate the global solution. Specifically, PQA starts with a small-scale subgraph and progressively expands its graph size utilizing heuristic expansion strategies. After each expansion, PQA solves the MIS problem on the newly generated subgraph using QAOA+. In each run, PQA repeats the expansion and solving process until a predefined stopping condition is reached. Simulation results show that PQA achieves an approximation ratio of 0.95 using only $5.57%$ ($2.17%$) of the qubits and $17.59%$ ($6.43%$) of the runtime compared with directly solving the original problem with QAOA+ on Erdös-Rényi (3-regular) graphs, highlighting the efficiency and scalability of PQA.
|
Received: 21 April 2025
Revised: 27 May 2025
Accepted manuscript online: 28 May 2025
|
|
PACS:
|
03.67.Ac
|
(Quantum algorithms, protocols, and simulations)
|
|
| Fund: We thank the Tianyan Quantum Computing Program. This work is supported by the National Natural Science Foundation of China (Grant Nos. 62371069, 62372048, and 62272056) and BUPT Excellent Ph.D. Students Foundation (Grant No. CX2023123). |
Corresponding Authors:
Su-Juan Qin, Fei Gao
E-mail: qsujuan@bupt.edu.cn;gaof@bupt.edu.cn
|
Cite this article:
Xiao-Hui Ni(倪晓慧), Ling-Xiao Li(李凌霄), Yan-Qi Song(宋燕琪), Zheng-Ping Jin(金正平), Su-Juan Qin(秦素娟), and Fei Gao(高飞) Progressive quantum algorithm for maximum independent set with quantum alternating operator ansatz 2025 Chin. Phys. B 34 070304
|
[1] Grover L K 1997 Phys. Rev. Lett. 79 325
[2] Shor P W 1999 SIAM Rev. 41 303
[3] Harrow A W, Hassidim A and Lloyd S 2009 Phys. Rev. Lett. 103 150502
[4] Preskill J 2018 Quantum 2 79
[5] Grimsley H R, Economou S E, Barnes E and Mayhall N J 2019 Nat. Commun. 10 3007
[6] Tang H L, Shkolnikov V O, Barron G S, Grimsley H R, Mayhall N J, Barnes E and Economou S E 2021 PRX Quantum 2 020310
[7] Du Y X, Huang T, You S, Hsieh M H and Tao D C 2022 npj Quantum Inf. 8 62
[8] Wu S Y, Song Y Q, Li R Z, Qin S J, Wen Q Y and Gao F 2025 Adv. Quantum Technol. 2400484
[9] Song Y Q,Wu Y S,Wu S Y, Li D D,Wen Q Y, Qin S J and Gao F 2024 Sci. China Phys. Mech. Astron. 67 250311
[10] Farhi E, Goldstone J and Gutmann S 2014 arXiv:1411.4028 [quant-ph]
[11] Bravyi S, Kliesch A, Koenig R and Tang E 2020 Phys. Rev. Lett. 125 260505
[12] Streif M and Leib M 2020 Quantum Sci. Technol. 5 034008
[13] Zhu L H, Tang H L, Barron G S, Calderon-Vargas F A, Mayhall N J, Barnes E and Economou S E 2022 Phys. Rev. Res. 4 033029
[14] Zhou Z Q, Du Y X, Tian X M and Tao D C 2023 Phys. Rev. Appl. 19 024027
[15] Cook J, Eidenbenz S and Bärtschi A 2020 Proceedings of the International Conference on Quantum Computing and Engineering, October 12-16, 2020, Denver, CO, USA, pp. 83-92
[16] Vikstål P, Grönkvist M, Svensson M, Andersson M, Johansson G and Ferrini G 2020 Phys. Rev. Appl. 14 034009
[17] Zhou L, Wang S T, Choi S, Pichler H and Lukin M D 2020 Phys. Rev. X 10 021067
[18] Brandhofer S, Braun D, Dehn V, Hellstern G, Hüls M, Ji Y J, Polian I, Bhatia A S and Wellens T 2022 Quantum Inf. Process. 22 25
[19] Tomesh T, Saleem Z H, Perlin M A, Gokhale P, Suchara M and Martonosi M 2023 Proceedings of the International Conference on Quantum Computing and Engineering, September 17-22, 2023, Bellevue, WA, USA, pp. 1-12
[20] Ni X H, Cai B B, Liu H L, Qin S J, Gao F and Wen Q Y 2024 Adv. Quantum Technol. 7 2300419
[21] Zhang Y J, Mu X D, Liu X W, Wang X Y, Zhang X, Li K, Wu T Y, Zhao D and Dong C 2022 Appl. Soft Comput. 118 108554
[22] Finžgar J R, Kerschbaumer A, Schuetz M J A, Mendl C B and Katzgraber H G 2024 PRX Quantum 5 020327
[23] Lucas A 2014 Front. Phys. 2 5
[24] Ruan Y, Yuan Z Q, Xue X L and Liu Z H 2023 Inf. Sci. 619 98
[25] Hadfield S, Wang Z H, O Gorman B, Rieffel E G, Venturelli D and Biswas R 2019 Algorithms 12 34
[26] Hadfield S, Wang Z H, Rieffel E G, O’Gorman B, Venturelli D and Biswas R 2017 Proceedings of the Second International Workshop on Post Moores Era Supercomputing, November 12-17, 2017, Denver, CO, USA pp. 15-21
[27] Wang Z H, Rubin N C, Dominy J M and Rieffel E G 2020 Phys. Rev. A 101 012320
[28] He Z C, Shaydulin R, Chakrabarti S, Herman D, Li C H, Sun Y and Pistoia M 2023 npj Quantum Inf. 9 121
[29] Brady L T and Hadfield S 2024 Phys. Rev. A 110 052435
[30] Wang S S, Liu H L, Song Y Q, Gao F, Qin S J and Wen Q Y 2023 Physica A 626 129089
[31] Moscibroda T and Wattenhofer R 2005 Proceedings of the Twenty- Fourth Annual ACM Symposium on Principles of Distributed Computing, July 17-20, 2005, Las Vegas, NV, USA, pp. 148-157
[32] Eddy D and Kochenderfer M J 2021 J. Spacecr. Rockets 58 1416
[33] Hochbaum D S 1997 Approximation Algorithms for NP-Hard Problems (Boston: PWS Publishing) pp. 94-143
[34] Tomesh T, Saleem Z H and Suchara M 2022 Quantum 6 781
[35] Saleem Z H 2020 Int. J. Quantum Inf. 18 2050011
[36] Li L X, Li J, Song Y Q, Qin S J, Wen Q Y and Gao F 2024 Sci. China Phys. Mech. Astron. 68 210313
[37] Bondy J A and Murty U S R 1976 Graph Theory with Applications (London: Macmillan)
[38] Vale R, Azevedo T M D, Aráujo I C S, Araujo I F and da Silva A J 2024 Trans. Comput.-Aided Des. Integr. Circuits Syst. 43 802
[39] Tomesh T, Allen N, Dilley D and Saleem Z H 2024 Quantum 8 1493
[40] Lyngfelt I and García-Á lvarez L 2025 Phys. Rev. A 111 022418
[41] Shaydulin R, Lotshaw P C, Larson J, Ostrowski J and Humble T S 2023 ACM Trans. Quantum Comput. 4 19
[42] Wurtz J and Lykov D 2021 Phys. Rev. A 104 052419
[43] Brandao F G S L, Broughton M, Farhi E, Gutmann S and Neven H 2018 arXiv:1812.04170 [quant-ph]
[44] Chinnasamy S, Ramachandran M, Amudha M and Ramu K 2022 Recent Trends Manag. Commer. 3 1
[45] Guerreschi G G and Matsuura A Y 2019 Sci. Rep. 9 6903 |
| No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|
