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 prog...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.展开更多
Constrained combinatorial optimization with strict linear constraints underpins applications in drug discovery,power grids,logistics,and finance,yet remains computationally demanding for classical algorithms,especiall...Constrained combinatorial optimization with strict linear constraints underpins applications in drug discovery,power grids,logistics,and finance,yet remains computationally demanding for classical algorithms,especially at large scales.The quantum approximate optimization algorithm(QAOA)offers a promising quantum framework,but conventional penalty-based formulations distort optimization landscapes and demand deep circuits,undermining scalability on near-term hardware.In this work,we introduce Hamming weight operators,a new class of constraint-aware operators that confine quantum evolution strictly within the feasible subspace.Building on this idea,we develop an adaptive Hamming weight operator QAOA,which dynamically selects the most effective operators to construct shallow,problem-tailored circuits.We validate our approach on benchmark tasks from both finance and high-energy physics,specifically portfolio optimization and two-jet clustering with energy balance.Across these problems,our method inherently satisfies all constraints by construction,converges faster,and achieves higher approximation ratios than penalty-based QAOA,while requiring roughly half as many gates.By embedding constraint-aware operators into an adaptive variational framework,our approach establishes a scalable and hardware-efficient pathway for solving practical constrained optimization problems on near-term quantum devices.展开更多
基金supported by the National Natural Science Foundation of China(Grant Nos.62371069,62372048,and 62272056)BUPT Excellent Ph.D.Students Foundation(Grant No.CX2023123)。
文摘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.
基金supported by the National Natural Science Foundation of China(Grant No.92265208)the Beijing Natural Science Foundation(Grant No.Z250004)the Sichuan Science and Technology Program(Grant No.2025YFHZ0336)。
文摘Constrained combinatorial optimization with strict linear constraints underpins applications in drug discovery,power grids,logistics,and finance,yet remains computationally demanding for classical algorithms,especially at large scales.The quantum approximate optimization algorithm(QAOA)offers a promising quantum framework,but conventional penalty-based formulations distort optimization landscapes and demand deep circuits,undermining scalability on near-term hardware.In this work,we introduce Hamming weight operators,a new class of constraint-aware operators that confine quantum evolution strictly within the feasible subspace.Building on this idea,we develop an adaptive Hamming weight operator QAOA,which dynamically selects the most effective operators to construct shallow,problem-tailored circuits.We validate our approach on benchmark tasks from both finance and high-energy physics,specifically portfolio optimization and two-jet clustering with energy balance.Across these problems,our method inherently satisfies all constraints by construction,converges faster,and achieves higher approximation ratios than penalty-based QAOA,while requiring roughly half as many gates.By embedding constraint-aware operators into an adaptive variational framework,our approach establishes a scalable and hardware-efficient pathway for solving practical constrained optimization problems on near-term quantum devices.
