Embedding of Complete Graphs in Broken Chimera Graphs

Abstract

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.

arXiv comment26 pages, 9 figures, 2 tables

References in corpus (4)

• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• A case study in programming a quantum annealer for hard operational planning problems
• Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
• Flight Gate Assignment with a Quantum Annealer

Cited by in corpus (6)

• Quantum Annealing for Industry Applications: Introduction and Review
• Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features
• 4-clique Network Minor Embedding for Quantum Annealers
• Quantum Software Ecosystem Design
• Optimal Sufficient Requirements on the Embedded Ising Problem in Polynomial Time