Quantum approximate optimization for combinatorial problems with constraints

The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems, derived from an approximation to the Quantum Adiabatic Algorithm (QAA). In solving combinatorial optimization problems with constraints in the context of QAOA, one needs to find a way to encode problem constraints into the scheme. In this paper, we propose and discuss several QAOA-based algorithms to solve combinatorial optimization problems with equality and/or inequality constraints. We formalize the encoding method of different types of constraints, and demonstrate the effectiveness and efficiency of the proposed scheme by providing examples and results for some well-known NP optimization problems. Compared to previous constraint-encoding methods, we argue our work leads to a more generalized framework for finding, in the context of QAOA, higher-quality approximate solutions to combinatorial problems with various types of constraints.