Q-CHOP: Quantum Constrained Hamiltonian OPtimization

We introduce, Q-CHOP (Quantum Constrained Hamiltonian OPtimization), a method for solving constrained optimization problems with a quantum computer. Q-CHOP extends a recently discovered adiabatic quantum algorithm to support arbitrary constraints and objective functions. The method yields high-quality solutions with short evolution times by confining evolution to occur within the degenerate subspace of feasible solutions. We demonstrate Q-CHOP for constrained optimization problems like Maximum Weighted Independent Set, which push the limits of classical solvers. Q-CHOP on a small graph configuration problem achieves 90% success probability, a >15x advantage over random guessing. Moreover, this result is attained with modest quantum evolution time of T = N², discretized over 40 Trotter steps.