Solving Constrained Quadratic Binary Problems via Quantum Adiabatic Evolution

By Pooya Ronagh, Brad Woods, & Ehsan Iranmanesh

Quantum adiabatic evolution is perceived as useful for binary quadratic programming problems that are a priori unconstrained. For constrained problems, it is a common practice to relax linear equality constraints as penalty terms in the objective function. However, there has not yet been proposed a method for efficiently dealing with inequality constraints using the quantum adiabatic approach. In this paper, we give a method for solving the Lagrangian dual of a binary quadratic programming (BQP) problem in the presence of inequality constraints and employ this procedure within a branch-and-bound framework for constrained BQP (CBQP) problems.

Journal reference: Quantum Information & Computation 16(11&12): 1029-1047 (2016)
Presented at: The Fields Institute for Research in Mathematical Sciences, Quantum Optimization Workshop 2014 

RESEARCH PAPER arXiv preprint