Solving Combinatorial Optimization Problems via D-Wave's Quantum Annealer

Abstract

The exploitation of quantum mechanical principles seems to provide a decisive advantage over classical computation technologies. In the recent years there has been big progress in realizing different quantum computer architectures, especially by the Canadian company D-Wave Systems, which developed the first commercially available adiabatic quantum annealer. By adiabatic evolution of quantum mechanical systems it can solve NP-hard discrete optimization problems probabilistically. Due to the restrictions of the hardware architecture the directly computable problems are limited to Ising problems over a so called Chimera interaction graph. After introducing the physical background of the D-Wave machine, the presentation will focus on the difficulties in mapping more general problems onto its specific problem structure. In addition to the reductions on Ising problems this includes the minor embedding of the original problem graph onto the Chimera hardware graph. Afterwards the weight of an original node needs to be distributed over several hardware nodes in a certain way to enforce the equivalence of the solutions. Some first results tackling the latter will be shown and an outlook over the next steps of the PhD project will be provided.