  In order to solve real world combinatorial optimization problems with a
D-Wave quantum annealer it is necessary to embed the problem at hand into the
D-Wave hardware graph, namely Chimera or Pegasus. Most hard real world problems
exhibit a strong connectivity. For the worst case scenario of a complete graph,
there exists an efficient solution for the embedding into the ideal Chimera
graph. However, since real machines almost always have broken qubits it is
necessary to find an embedding into the broken hardware graph.
  We present a new approach to the problem of embedding complete graphs into
broken Chimera graphs. This problem can be formulated as an optimization
problem, more precisely as a matching problem with additional linear
constraints. Although being NP-hard in general it is fixed parameter tractable
in the number of inaccessible vertices in the Chimera graph. We tested our
exact approach on various instances of broken hardware graphs, both related to
real hardware as well as randomly generated. For fixed runtime, we were able to
embed larger complete graphs compared to previous, heuristic approaches. As an
extension, we developed a fast heuristic algorithm which enables us to solve
even larger instances. We compared the performance of our heuristic and exact
approaches.

Quantum Physics;Optimization and Control