Versenden
Drucken
Lobe, Elisabeth und Lutz, Annette (2023) Minor Embedding in Broken Chimera and Derived Graphs is NP-complete. Theoretical Computer Science. Elsevier. doi: 10.1016/j.tcs.2023.114369. ISSN 0304-3975.
 | Es ist eine neuere Version dieses Eintrags verfügbar. |
![[img]](https://elib.dlr.de/style/images/fileicons/application_pdf.png) |
PDF
- Preprintversion (eingereichte Entwurfsversion)
1MB |
Offizielle URL: https://www.sciencedirect.com/science/article/pii/S0304397523006825
Kurzfassung
The embedding is an essential step when calculating on the D-Wave machine. In this work, we show the hardness of the embedding problem for all types of currently existing hardware, represented by the Chimera and the derived Pegasus and Zephyr graphs, containing unavailable qubits. We construct certain broken Chimera graphs, where it is hard to find a Hamiltonian cycle. As the Hamiltonian cycle problem is a special case of the embedding problem, this proves the general complexity result for the Chimera graphs. By exploiting the subgraph relation between the Chimera and the derived graphs, the proof is then further extended to the Pegasus graphs and to the Zephyr graphs.
| elib-URL des Eintrags: | https://elib.dlr.de/201938/ | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Dokumentart: | Zeitschriftenbeitrag | ||||||||||||
| Titel: | Minor Embedding in Broken Chimera and Derived Graphs is NP-complete | ||||||||||||
| Autoren: |
| ||||||||||||
| Datum: | 28 Dezember 2023 | ||||||||||||
| Erschienen in: | Theoretical Computer Science | ||||||||||||
| Referierte Publikation: | Ja | ||||||||||||
| Open Access: | Ja | ||||||||||||
| Gold Open Access: | Nein | ||||||||||||
| In SCOPUS: | Ja | ||||||||||||
| In ISI Web of Science: | Ja | ||||||||||||
| DOI: | 10.1016/j.tcs.2023.114369 | ||||||||||||
| Verlag: | Elsevier | ||||||||||||
| Name der Reihe: | TCS-C | ||||||||||||
| ISSN: | 0304-3975 | ||||||||||||
| Status: | veröffentlicht | ||||||||||||
| Stichwörter: | Graph minor embedding, Hamiltonian cycle problem, quantum annealing, Chimera graph, Pegasus graph, Zephyr graph | ||||||||||||
| 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, R - Aufgaben SISTEC | ||||||||||||
| Standort: | Braunschweig | ||||||||||||
| Institute & Einrichtungen: | Institut für Softwaretechnologie > High-Performance Computing Institut für Softwaretechnologie | ||||||||||||
| Hinterlegt von: | Lobe, Elisabeth | ||||||||||||
| Hinterlegt am: | 10 Jan 2024 09:31 | ||||||||||||
| Letzte Änderung: | 10 Jan 2024 09:31 |
Verfügbare Versionen dieses Eintrags
-
Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete. (deposited 07 Dez 2021 11:52)
- Minor Embedding in Broken Chimera and Derived Graphs is NP-complete. (deposited 10 Jan 2024 09:31) [Gegenwärtig angezeigt]
Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags
