Resource‐Efficient Adaptive Variational Quantum Algorithm for Combinatorial Optimization Problems

Abstract Variational quantum algorithms (VQAs) are quantum‐classical hybrid algorithms that are promising for the near future. The Quantum Approximate Optimization Algorithm (QAOA) is a representative VQA for solving combinatorial optimization problems. However, the parameterized quantum circuit (PQC) of QAOA still has room for improvement. The existing method, called ADAPT‐QAOA, has improved the PQC of QAOA, but the circuit depth remains deep. A Resource‐Efficient Adaptive VQA (RE‐ADAPT‐VQA) that utilizes gates from a new gate pool is proposed to construct a PQC. RE‐ADAPT‐VQA incrementally integrates parameterized quantum gates based on the gradient until the predefined stopping criteria are satisfied, and a rollback mechanism is proposed to ensure that the circuit remains shallow. The algorithm is experimentally simulated to solve Max‐Cut problem and the maximum independent set problem. The results show that RE‐ADAPT‐VQA significantly reduces circuit depth, single‐qubit gates, and CNOT gates compared to existing methods, while maintaining the same level of energy error.