Solving Combinatorial Optimization Problems using a Quantum Annealer

Abstract

In this talk we will start with a brief introduction of the rough concept of quantum annealing and how it can be used for combinatorial optimization. In the following we mainly focus on the steps that are necessary to transform an arbitrary discrete optimization problem to the specific class of problems D-Wave's quantum annealer is able to process, which are, in general, quadratic unconstrained binary optimization problems (QUBO) respectively so-called Ising models. We will summarize some established transformation steps, such as encoding and reduction. However, due to several physical limitations the class of problems that can be solved on the machine is further restricted. E.g. by graph minor embedding we need to overcome the non-complete hardware connectivity. 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. We will show the accompanying difficulties and some first approaches to tackle them.