Auxiliary-qubit-free quantum approximate optimization algorithm for the minimum dominating set problem

doi:10.1088/1674-1056/ae5052

Abstract Quantum approximate optimization algorithm (QAOA) is a promising framework for solving combinatorial optimization problems on near-term quantum devices. One such problem is the minimum dominating set (MDS), which is known to be NP-hard. Existing QAOA algorithms for this problem typically require numerous auxiliary qubits, increasing circuit overhead and hardware requirements. In this paper, we propose an auxiliary-qubit-free QAOA algorithm based on Hamiltonian evolution (AQFH-QAOA) for the MDS problem. Unlike previous studies that require numerous auxiliary qubits, our algorithm eliminates the need for auxiliary qubits, thereby significantly reducing circuit overhead. In addition, we present an auxiliary-qubit-free optimized implementation of the previously proposed Guerrero’s QAOA algorithm (AQFG-QAOA) by utilizing gate decomposition techniques. Through a detailed analysis of gate complexity, we evaluate the applicability of these two algorithms. Numerical experiments demonstrate that our proposed algorithm achieves competitive solution quality compared with existing QAOA algorithms, making it a promising candidate for implementation on near-term quantum devices.

Keywords: quantum algorithm quantum approximate optimization algorithm minimum dominating set Boolean algebra identities

Received: 23 January 2026
Revised: 09 March 2026
Accepted manuscript online: 11 March 2026

PACS:	03.67.Ac	(Quantum algorithms, protocols, and simulations)
	03.67.Lx	(Quantum computation architectures and implementations)

Fund: This project was supported by the National Natural Science Foundation of China (Grant Nos. 62372048, 62272056, 62371069, and U25B2014) and the National Key Laboratory of Secure Communication Foundation (Grant No. 2025,6142103042503).

Corresponding Authors: Wei Huang, Fei Gao
E-mail: huangwei096505@aliyun.com;gaof@bupt.edu.cn

Cite this article:

Guanghui Li(李广辉), Xiaohui Ni(倪晓慧), Junjian Su(苏俊健), Sujuan Qin(秦素娟), Fenzhuo Guo(郭奋卓), Bingjie Xu(徐兵杰), Wei Huang(黄伟), and Fei Gao(高飞) Auxiliary-qubit-free quantum approximate optimization algorithm for the minimum dominating set problem 2026 Chin. Phys. B 35 050304

[1] Wu H Y, Feng X N, Zhang K J and Sun H W 2024 Adv. Quantum Technol. 7 2300384
[2] Zhang H, Wang S, Liu X, Shen Y and Wang Y 2024 Chin. Phys. B 33 020310
[3] Xu H Z, Zhuang W F, Wang Z A, Huang K X, Shi Y H, Ma W G, Li T M, Chen C T, Xu K and Feng Y L 2024 Chin. Phys. B 33 050302
[4] Lloyd S, Mohseni M and Rebentrost P 2014 Nat. Phys. 10 631
[5] Wu Z, Song T and Zhang Y 2022 Quantum Inf. Process. 21 19
[6] Zeguendry A, Jarir Z and Quafafou M 2023 Entropy 25 287
[7] Yu K, Lin S and Cai B B 2025 J. Phys. A: Math. Theor. 58 495302
[8] Gao S and Yang Y G 2023 Chin. Phys. B 32 100309
[9] Su J, Fan J, Wu S, Li G, Qin S and Gao F 2025 Sci. China Inf. Sci. 68 180507
[10] Shor P W 1994 Proceedings 35th Annual Symposium on Foundations of Computer Science (Santa Fe: IEEE) pp. 124
[11] Grover L K 1996 Proceedings of the 28th Annual ACM Symposium on Theory of Computing (Philadelphia: ACM) pp. 212
[12] Harrow A W, Hassidim A and Lloyd S 2009 Phys. Rev. Lett. 103 150502
[13] Cerezo M, Arrasmith A, Babbush R, Benjamin S C, Endo S, Fujii K, McClean J R, Mitarai K, Yuan X and Cincio L 2021 Nat. Rev. Phys. 3 625
[14] Preskill J 2018 Quantum 2 79
[15] Peruzzo A, McClean J, Shadbolt P, Yung M H, Zhou X Q, Love P J, Aspuru-Guzik A and O’brien J L 2014 Nat. Commun. 5 4213
[16] Farhi E, Goldstone J and Gutmann S 2014 arxiv:1411.4028
[17] Vikstal P, Gronkvist M, Svensson M, Andersson M, Johansson G and Ferrini G 2020 Phys. Rev. Appl. 14 034009
[18] Azad U, Behera B K, Ahmed E A, Panigrahi P K and Farouk A 2022 IEEE Trans. Intell. Transp. Syst. 24 7564
[19] Kurowski K, Pecyna T, Slysz M, Rózycki R, Walig · ora G and Wglarz J 2023 Eur. J. Oper. Res. 310 518
[20] Hadfield S, Wang Z, Rieffel E G, O’Gorman B, Venturelli D and Biswas R 2017 Proceedings of the Second International Workshop on Post Moores Era Supercomputing (New York: ACM) pp. 15
[21] Saleem Z H, Tomesh T, Tariq B and Suchara M 2023 SN Comput. Sci. 4 183
[22] Pan H and Lu C 2024 Entropy 26 1057
[23] Li G H, Wang S S, Ni X H, Gao F, Guo F Z, Qin S J and Wen Q Y 2025 Phys. Lett. A 553 130690
[24] Li G, Wang S, Zhao X, Gao F, Qin S, Guo F and Jin Z 2025 Quantum Inf. Process. 24 166
[25] Ni X H, Li L X, Song Y Q, Jin Z P, Qin S J and Gao F 2025 Chin. Phys. B 34 070304
[26] Ore O 1962 Theory of Graphs (American Mathematical Society Colloquium Publications vol. 38) (Providence: AMS)
[27] Fomin F V, Kratsch D and Woeginger G J 2005 Graph-Theoretic Concepts in Computer Science ed. Hromkovic J, Nagl M and Westfechtel B (Berlin, Heidelberg: Springer) pp. 245
[28] Casado A, Bermudo S, Lopez-Sanchez A and Sanchez-Oro J 2023 Math. Comput. Simul. 207 41
[29] Dinneen M J and Hua R 2017 Proceedings of the Australasian Computer Science Week Multiconference (New York: ACM) pp. 1
[30] Pan H and Lu C 2025 J. Math UK 2025 3201094
[31] Guerrero N J 2020 Solving Combinatorial Optimization Problems Using The Quantum Approximation Optimization Algorithm Master’s Thesis, Air Force Institute of Technology
[32] Zhou L, Wang S T, Choi S, Pichler H and Lukin M D 2020 Phys. Rev. X 10 021067
[33] Krauss T, McCollum J, Pendery C, Litwin S and Michaels A J 2020 IEEE Trans. Quantum Eng. 1 1
[34] Glover F, Kochenberger G, Hennig R and Du Y 2022 Ann. Oper. Res. 314 141
[35] Hadfield S 2021 ACM T. Quantum. Comput. 2 1
[36] Maslov D and Zindorf B 2022 IEEE Trans. Quantum Eng. 3 1
[37] Barenco A, Bennett C H, Cleve R, DiVincenzo D P, Margolus N, Shor P, Sleator T, Smolin J A and Weinfurter H 1995 Phys. Rev. A 52 3457
[38] Liu Y, Long G L and Sun Y 2008 Int. J. Quantum Inf. 6 447
[39] Saeedi M and Pedram M 2013 Phys. Rev. A 87 062318
[40] Luo M X and Li H R 2016 Phys. Rev. A 94 026301
[41] da Silva A J and Park D K 2022 Phys. Rev. A 106 042602
[42] Maslov D and Dueck G W 2003 Electron. Lett. 39 1790
[43] He Y, Luo M X, Zhang E, Wang H K and Wang X F 2017 Int. J. Theor. Phys. 56 2350
[44] Bollobas B 1998 Random Graphs in: Modern Graph Theory Graduate Texts in Mathematics (New York: Springer) pp. 215
[45] Anand K and Bianconi G 2009 Phys. Rev. E 80 045102
[46] Xu X, Cui J, Cui Z, et al. 2024 arXiv:2406.17248
[47] Herrman R, Lotshaw P C, Ostrowski J, Humble T S and Siopsis G 2022 Sci. Rep. 12 6781
[48] Donkers H, Mesman K, Al-Ars Z and Moller M 2022 arXiv:2205.12142
[49] Vijendran V, Das A, Koh D E, Assad S M and Lam P K 2024 Quantum Sci. Technol. 9 025010

[1]	Hierarchical QAOA circuit design framework for distributed quantum computing Ting-Yu Luo(骆挺宇), and Yu-Xin Deng(邓玉欣). Chin. Phys. B, 2026, 35(4): 040309.
[2]	Preparation of digital-encoded and analog-encoded quantum states corresponding to matrix operations Kaitian Gao(高凯天), Youlong Yang(杨有龙), and Zhenye Du(杜振叶). Chin. Phys. B, 2026, 35(1): 010202.
[3]	Exact quantum algorithm for unit commitment optimization based on partially connected quantum neural networks Jian Liu(刘键), Xu Zhou(周旭), Zhuojun Zhou(周卓俊), and Le Luo(罗乐). Chin. Phys. B, 2025, 34(10): 100303.
[4]	Quantum algorithm for minimum dominating set problem with circuit design Haoying Zhang(张皓颖), Shaoxuan Wang(王绍轩), Xinjian Liu(刘新建), Yingtong Shen(沈颖童), and Yukun Wang(王玉坤). Chin. Phys. B, 2024, 33(2): 020310.
[5]	Simulation of optimal work extraction for quantum systems with work storage Peng-Fei Song(宋鹏飞) and Dan-Bo Zhang(张旦波). Chin. Phys. B, 2024, 33(2): 020312.
[6]	Variational quantum simulation of the quantum critical regime Zhi-Quan Shi(石志全), Xu-Dan Xie(谢旭丹), and Dan-Bo Zhang(张旦波). Chin. Phys. B, 2023, 32(8): 080305.
[7]	Variational quantum semi-supervised classifier based on label propagation Yan-Yan Hou(侯艳艳), Jian Li(李剑), Xiu-Bo Chen(陈秀波), and Chong-Qiang Ye(叶崇强). Chin. Phys. B, 2023, 32(7): 070309.
[8]	A quantum algorithm for Toeplitz matrix-vector multiplication Shang Gao(高尚) and Yu-Guang Yang(杨宇光). Chin. Phys. B, 2023, 32(10): 100309.
[9]	Variational quantum simulation of thermal statistical states on a superconducting quantum processer Xue-Yi Guo(郭学仪), Shang-Shu Li(李尚书), Xiao Xiao(效骁), Zhong-Cheng Xiang(相忠诚), Zi-Yong Ge(葛自勇), He-Kang Li(李贺康), Peng-Tao Song(宋鹏涛), Yi Peng(彭益), Zhan Wang(王战), Kai Xu(许凯), Pan Zhang(张潘), Lei Wang(王磊), Dong-Ning Zheng(郑东宁), and Heng Fan(范桁). Chin. Phys. B, 2023, 32(1): 010307.
[10]	Quantum algorithm for neighborhood preserving embedding Shi-Jie Pan(潘世杰), Lin-Chun Wan(万林春), Hai-Ling Liu(刘海玲), Yu-Sen Wu(吴宇森), Su-Juan Qin(秦素娟), Qiao-Yan Wen(温巧燕), and Fei Gao(高飞). Chin. Phys. B, 2022, 31(6): 060304.
[11]	Variational quantum eigensolvers by variance minimization Dan-Bo Zhang(张旦波), Bin-Lin Chen(陈彬琳), Zhan-Hao Yuan(原展豪), and Tao Yin(殷涛). Chin. Phys. B, 2022, 31(12): 120301.
[12]	Selected topics of quantum computing for nuclear physics Dan-Bo Zhang(张旦波), Hongxi Xing(邢宏喜), Hui Yan(颜辉), Enke Wang(王恩科), and Shi-Liang Zhu(朱诗亮). Chin. Phys. B, 2021, 30(2): 020306.
[13]	Experimental implementation of a continuous-time quantum random walk on a solid-state quantum information processor Maimaitiyiming Tusun(麦麦提依明·吐孙), Yang Wu(伍旸), Wenquan Liu(刘文权), Xing Rong(荣星), Jiangfeng Du(杜江峰). Chin. Phys. B, 2019, 28(11): 110302.
[14]	Demonstration of quantum permutation parity determine algorithm in a superconducting qutrit Kunzhe Dai(戴坤哲), Peng Zhao(赵鹏), Mengmeng Li(李蒙蒙), Xinsheng Tan(谭新生), Haifeng Yu(于海峰), Yang Yu(于扬). Chin. Phys. B, 2018, 27(6): 060305.
[15]	Coherent attacks on a practical quantum oblivious transfer protocol Guang-Ping He(何广平). Chin. Phys. B, 2018, 27(10): 100308.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Auxiliary-qubit-free quantum approximate optimization algorithm for the minimum dominating set problem

Cite this article:

Online attention