Penalty-enhanced quantum approximate optimization algorithm framework for maximization and minimization problems

The Quantum Approximate Optimization Algorithm (QAOA for short) has demonstrated great potential in solving NP-hard combinatorial optimization problems. This study proposes a penalty-enhanced QAOA framework for addressing both maximization and minimization problems. By uniformly setting penalty coefficients, the framework provides general support for both types of problems. It ensures the feasibility of output solutions and improves the quality of approximate solutions by adjusting the objective function and the construction of the Hamiltonian. We apply this framework to the Minimum Vertex Cover problem (as a minimization task) and the Maximum Independent Set problem (as a maximization task), designing corresponding quantum Hamiltonians and penalty terms.

Authors

• Hao Zhong
• Qi Zhang School of Computer Science, Fudan University, Shanghai, China Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai, China

Keywords

• Quantum approximation optimization algorithm
• Hamiltonian
• Vertex cover
• Independent set