1. Progressive Quantum Algorithm for Maximum Independent Set with Quantum Alternating Operator Ansatz
- Author
-
Ni, Xiao-Hui, Li, Ling-Xiao, Song, Yan-Qi, Jin, Zheng-Ping, Qin, Su-Juan, and Gao, Fei
- Subjects
Quantum Physics - Abstract
Recently, Hadfield et al. proposed the Quantum Alternating Operator Ansatz (QAOA+) to tackle Constrained Combinatorial Optimization Problems (CCOPs). This paper proposes a Progressive Quantum Algorithm (PQA) to reduce the required qubits in solving the Maximum Independent Set (MIS) problem using QAOA+ ansatz. PQA constructs a subgraph that contains the MIS solution of the target graph $G$ and then solves the MIS problem on this subgraph to obtain the solution for $G$. To induce such a subgraph, PQA starts with a small-scale initial subgraph and progressively expands its graph size utilizing designed expansion rules. After each expansion, PQA solves the MIS problem on the current subgraph using QAOA+. In each run, PQA repeats the graph expansion and solving process until a predefined stopping condition is reached. Simulation results demonstrate that to achieve an optimal approximation ratio of 0.95, PQA requires only $5.5565\%$ ($15.4\%$) of the qubits and $10.695\%$ ($7.23\%$) of the runtime compared with QAOA+ on Erd\H{o}s-R\'enyi (regular) graphs, highlighting the efficiency of PQA.
- Published
- 2024