Progressive quantum algorithm for maximum independent set with quantum alternating operator ansatz

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.