Abstract

Quantum annealers provide a novel paradigm for solving combinatorial optimization problems, by exploiting the quantum mechanical properties of a set of qubits with programmable interactions [1]. Quantum annealers like the D-Wave processor series, have been commercially available for several years, and a lot of research has been done trying to understand their properties, in particular whether or not they can provide a computational speedup [2]. But another important aspect of quantum annealers is related to the limitations that are imposed by the many times unavoidable engineering compromises that have to be reached in order to build a scalable and useful device.
Two of the main limitations of the D-Wave processor that would likely be shared by other implementations of quantum annealing, are size (largest available device has~ 1000 qubits) and hardware connectivity (not every interaction between variables is physically represented). This restricts the problems that can actually be solved by the device to those that can be mapped directly to the underlying architecture. Since most instances of real-world applications will no fit this restricted setting, tools need to be developed in order to apply quantum annealing to a wider range of problems. In this work we will present a set of tools designed to address these two important limitations, by providing strategies to decompose and embed general Quadratic Unconstrained Binary Optimization (QUBO) problems using the D-Wave processor.

Date

2016

Authors

T Albash, F Spedalieri, I Hen, K Pudenz, G Tallant

Journal

IEEE High Performance Extreme Computing