elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

Embedding of Complete Graphs in Broken Chimera Graphs

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

[img] PDF - Verlagsversion (veröffentlichte Fassung)
1MB
[img] PDF - Nur DLR-intern zugänglich - Preprintversion (eingereichte Entwurfsversion)
428kB

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

Kurzfassung

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.

elib-URL des Eintrags:https://elib.dlr.de/139936/
Dokumentart:Zeitschriftenbeitrag
Titel:Embedding of Complete Graphs in Broken Chimera Graphs
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Lobe, ElisabethElisabeth.Lobe (at) dlr.dehttps://orcid.org/0000-0002-3473-8906NICHT SPEZIFIZIERT
Schürmann, LukasUniversität Bonnhttps://orcid.org/0000-0003-4180-0744NICHT SPEZIFIZIERT
Stollenwerk, TobiasTobias.Stollenwerk (at) dlr.dehttps://orcid.org/0000-0001-5445-8082NICHT SPEZIFIZIERT
Datum:10 Juli 2021
Erschienen in:Quantum Information Processing
Referierte Publikation:Ja
Open Access:Ja
Gold Open Access:Nein
In SCOPUS:Ja
In ISI Web of Science:Ja
Band:20
DOI:10.1007/s11128-021-03168-z
Seitenbereich:Seiten 1-27
Verlag:Springer Nature
ISSN:1570-0755
Status:veröffentlicht
Stichwörter:Graph minor embedding, Chimera, integer linear programming, bipartite matching, quantum annealing
HGF - Forschungsbereich:Luftfahrt, Raumfahrt und Verkehr
HGF - Programm:Raumfahrt
HGF - Programmthema:Technik für Raumfahrtsysteme
DLR - Schwerpunkt:Raumfahrt
DLR - Forschungsgebiet:R SY - Technik für Raumfahrtsysteme
DLR - Teilgebiet (Projekt, Vorhaben):R - Quantencomputing
Standort: Braunschweig
Institute & Einrichtungen:Institut für Softwaretechnologie > High-Performance Computing
Institut für Softwaretechnologie
Hinterlegt von: Lobe, Elisabeth
Hinterlegt am:07 Dez 2021 11:51
Letzte Änderung:07 Dez 2021 11:51

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.