中国物理B ›› 2025, Vol. 34 ›› Issue (7): 70304-070304.doi: 10.1088/1674-1056/addd83

所属专题： Featured Column — COMPUTATIONAL PROGRAMS FOR PHYSICS

• • 上一篇    下一篇

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. 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
  • 收稿日期:2025-04-21 修回日期:2025-05-27 接受日期:2025-05-28 出版日期:2025-06-18 发布日期:2025-07-07
  • 通讯作者: Su-Juan Qin, Fei Gao E-mail:qsujuan@bupt.edu.cn;gaof@bupt.edu.cn
  • 基金资助:
    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).

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. 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
  • Received:2025-04-21 Revised:2025-05-27 Accepted:2025-05-28 Online:2025-06-18 Published:2025-07-07
  • Contact: Su-Juan Qin, Fei Gao E-mail:qsujuan@bupt.edu.cn;gaof@bupt.edu.cn
  • Supported by:
    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).

RichHTML

0

PDF (PC)

220

赞

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

关键词: quantum alternating operator ansatz algorithm (QAOA+), constrained combinatorial optimization problems (CCOPs), maximum independent set (MIS), feasible space

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.

Key words: quantum alternating operator ansatz algorithm (QAOA+), constrained combinatorial optimization problems (CCOPs), maximum independent set (MIS), feasible space

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

  • 03.67.Ac