Convergence guarantee for linearly-constrained combinatorial optimization with a quantum alternating operator ansatz

Understand

We present a quantum alternating operator ansatz (QAOA$^+$) that solves a class of linearly constrained optimization problems by evolving a quantum state within a Hilbert subspace of feasible problem solutions.

• Our main focus is on a class of problems with a linear constraint containing sequential integer coefficients.
• For problems in this class, we devise QAOA$^+$ circuits that provably converge to the optimal solution as the number of circuit layers increases, generalizing previous guarantees for solving unconstrained problems or problems with symmetric constraints.
• Our approach includes asymmetric ``mixing" Hamiltonians that drive transitions between feasible states, as well as a method to incorporate an arbitrary known feasible solution as the initial state, each of which can be applied beyond the specific linear constraints considered here.