中国物理B ›› 2026, Vol. 35 ›› Issue (5): 50304-050304.doi: 10.1088/1674-1056/ae5052

• •    

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

Guanghui Li(李广辉)1, Xiaohui Ni(倪晓慧)1, Junjian Su(苏俊健)1, Sujuan Qin(秦素娟)1, Fenzhuo Guo(郭奋卓)1, Bingjie Xu(徐兵杰)2, Wei Huang(黄伟)2,†, and Fei Gao(高飞)1,‡   

  1. 1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China;
    2 National Key Laboratory of Security Communication, Institute of Southwestern Communication, Chengdu 610041, China
  • 收稿日期:2026-01-23 修回日期:2026-03-09 接受日期:2026-03-11 发布日期:2026-04-24
  • 通讯作者: Wei Huang, Fei Gao E-mail:huangwei096505@aliyun.com;gaof@bupt.edu.cn
  • 基金资助:
    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).

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

Guanghui Li(李广辉)1, Xiaohui Ni(倪晓慧)1, Junjian Su(苏俊健)1, Sujuan Qin(秦素娟)1, Fenzhuo Guo(郭奋卓)1, Bingjie Xu(徐兵杰)2, Wei Huang(黄伟)2,†, and Fei Gao(高飞)1,‡   

  1. 1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China;
    2 National Key Laboratory of Security Communication, Institute of Southwestern Communication, Chengdu 610041, China
  • Received:2026-01-23 Revised:2026-03-09 Accepted:2026-03-11 Published:2026-04-24
  • Contact: Wei Huang, Fei Gao E-mail:huangwei096505@aliyun.com;gaof@bupt.edu.cn
  • Supported by:
    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).

PDF (PC)

5

赞

摘要： 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.

关键词: quantum algorithm, quantum approximate optimization algorithm, minimum dominating set, Boolean algebra identities

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.

Key words: quantum algorithm, quantum approximate optimization algorithm, minimum dominating set, Boolean algebra identities

中图分类号:  (Quantum algorithms, protocols, and simulations)

  • 03.67.Ac
03.67.Lx (Quantum computation architectures and implementations)