Quantum Constrained Hamiltonian Optimization

Finding the best solution to an optimization problem is much-sought-after yet often difficult task. However, for some such problems, the task of finding any feasible solution is actually easy. In this work we present the Quantum Constrained Hamiltonian OPtimization (Q-CHOP) algorithm as an alternative to the standard adiabatic algorithm for solving this type of optimization problem. Q-CHOP evolves from any feasible state of a problem to the best feasible state, and is thus applicable to constrained optimization problems with at least one easy-to-find, easy-to-prepare feasible state. Q-CHOP achieves this feat by evolving the feasible state under a linear combination of the constraint Hamiltonian (which constrains the dynamics to the feasible subspace) and a ramp Hamiltonian (which adiabatically flips the sign of the objective Hamiltonian). We present of Q-CHOP to solve several optimization problems including: maximum independent set, combinatorial auction, and minimum directed set on a di-graph. We will explain Q-CHOP, along with each problem and how it was mapped to Q-CHOP. Additionally, simulations comparing the performance of Q-CHOP against the standard adiabatic algorithm (SAA) when applied to each problem. A theoretical discussion of the advantages of Q-CHOP over SAA is also presented along with corroborating numerical evidence. We conclude with ideas for further applications and extensions of this novel adiabatic quantum algorithm.