Efficient Embedding of Integer Programming Problems on Quantum Annealers

Quantum Annealers are being considered as a possible platform to solve challenging Integer Optimization Problems (IOP). Hard-coding an IOP as an Ising model onto an annealer is however no easy task due to the severe restrictions imposed mostly by the connectivity of the graph implemented by the hardware architecture, as it has widely discussed for the D-Wave machines. The current approaches employ graph minor embedding algorithms that require a significant overhead of resources (number of qubits, computing power) with respect to the number of logical variables in the IOP. This overhead is arguably the primary problems for practitioners of quantum annealing. We present a new method to deterministically embed an arbitrary IOP in a generic class of annealing chip layouts such that the asymptotic scaling beats all the current methods. It is shown on the latest D-Wave chips to allow programming of problems, relevant for database and space sciences, with approximately 5-10x more variables with respect to the published approaches. The method is efficient in the sense that a valid embedding can be computed at run-time in polynomial time. The discussed methods can inform the design of next-generation of quantum annealers.