Solutions to Integer Programming from Quantum Annealing

Many problems across several disciplines ranging from production planning over DNA, can be represented as constrained integer optimization problems. Utilizing classical algorithms, generally exact solutions to integer linear programming (ILP) problems are exponentially hard to obtain, and heuristic algorithms are employed to find approximate solutions. This talk demonstrates a new algorithm that solves such constrained ILP on a quantum annealer. Details of the formalism are presented in the case of the minimum dominating set problem, and annealing results for the D-Wave 2000Q architecture are benchmarked against brute force classical solutions. For a variety of different annealing schedules, results are compared against numerical simulations of the quantum architecture to interpret hardware-specific limitations, like the effects of decoherence and many-body localization.