DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Embedding of Complete Graphs in Broken Chimera Graphs

Lobe, Elisabeth and Schürmann, Lukas and Stollenwerk, Tobias (2021) Embedding of Complete Graphs in Broken Chimera Graphs. Quantum Information Processing, 20 (7), pp. 1-27. Springer Nature. doi: 10.1007/s11128-021-03168-z. ISSN 1570-0755.

[img] PDF - Published version
[img] PDF - Only accessible within DLR - Preprint version (submitted draft)

Official URL: https://link.springer.com/article/10.1007/s11128-021-03168-z


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 and 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.

Item URL in elib:https://elib.dlr.de/139936/
Document Type:Article
Title:Embedding of Complete Graphs in Broken Chimera Graphs
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Lobe, ElisabethUNSPECIFIEDhttps://orcid.org/0000-0002-3473-8906
Schürmann, LukasUniversität Bonnhttps://orcid.org/0000-0003-4180-0744
Stollenwerk, TobiasUNSPECIFIEDhttps://orcid.org/0000-0001-5445-8082
Date:10 July 2021
Journal or Publication Title:Quantum Information Processing
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In ISI Web of Science:Yes
Page Range:pp. 1-27
Publisher:Springer Nature
Keywords:Graph minor embedding, Chimera, integer linear programming, bipartite matching, quantum annealing
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space System Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Space System Technology
DLR - Research theme (Project):R - Quantum computing
Location: Braunschweig
Institutes and Institutions:Institute for Software Technology > High-Performance Computing
Institute for Software Technology
Deposited By: Lobe, Elisabeth
Deposited On:07 Dec 2021 11:51
Last Modified:07 Dec 2021 11:51

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.