Cookies disclaimer

I agree Our site saves small pieces of text information (cookies) on your device in order to deliver better content and for statistical purposes. You can disable the usage of cookies by changing the settings of your browser. By browsing our website without changing the browser settings you grant us permission to store that information on your device.

Solutions to Integer Programming from Quantum Annealing

By Christopher Körber

On Demand Talk at Qubits 2020 (digital)

Keywords: Quantum Annealing, D-Wave, Integer Linear Programming, Quantum Simulations

qa-ilp-qubits-2020

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.