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

Toward Quantum Gate-Model Heuristics for Real-World Planning Problems

Stollenwerk, Tobias und Hadfield, Stuart und Wang, Zhihui (2020) Toward Quantum Gate-Model Heuristics for Real-World Planning Problems. IEEE Transactions on Quantum Engineering, 1 (1), Seiten 1-16. IEEE - Institute of Electrical and Electronics Engineers. doi: 10.1109/TQE.2020.3030609. ISSN 2689-1808.

[img] PDF - Verlagsversion (veröffentlichte Fassung)
1MB

Offizielle URL: https://ieeexplore.ieee.org/document/9222273

Kurzfassung

Many challenging scheduling, planning, and resource allocation problems come with real-world input data and hard problem constraints, and reduce to optimizing a cost function over a combinatorially defined feasible set, such as colorings of a graph. Toward tackling such problems with quantum computers using quantum approximate optimization algorithms, we present novel efficient quantum alternating operator ansatz (QAOA) constructions for optimization problems over proper colorings of chordal graphs. As our primary application, we consider the flight-gate assignment problem , where flights are assigned to airport gates as to minimize the total transit time of all passengers, and feasible assignments correspond to proper graph colorings of a conflict graph derived instancewise from the input data. We leverage ideas from classical algorithms and graph theory to show our constructions have the desirable properties of restricting quantum state evolution to the feasible subspace, and satisfying a particular reachability condition for most problem parameter regimes. Using classical preprocessing we show that we can always find and construct a suitable initial quantum (superposition) state efficiently. We show our constructions in detail, including explicit decompositions to a universal set of basic quantum gates, which we use to bound the required resource scaling as low-degree polynomials of the input parameters. In particular, we derive novel QAOA mixing operators and show that their implementation cost is commensurate with that of the QAOA phase operator for flight-gate assignment. A number of quantum circuit diagrams are included such that our constructions may be used as a template toward development and implementation of quantum gate-model approaches for a wider variety of potentially impactful real-world applications.

elib-URL des Eintrags:https://elib.dlr.de/138683/
Dokumentart:Zeitschriftenbeitrag
Titel:Toward Quantum Gate-Model Heuristics for Real-World Planning Problems
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Stollenwerk, Tobiastobias.stollenwerk (at) dlr.dehttps://orcid.org/0000-0001-5445-8082NICHT SPEZIFIZIERT
Hadfield, StuartNASA Quantum Artificial Intelligence LaboratoryNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Wang, ZhihuiNASA Quantum Artificial Intelligence LaboratoryNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datum:November 2020
Erschienen in:IEEE Transactions on Quantum Engineering
Referierte Publikation:Ja
Open Access:Ja
Gold Open Access:Nein
In SCOPUS:Nein
In ISI Web of Science:Nein
Band:1
DOI:10.1109/TQE.2020.3030609
Seitenbereich:Seiten 1-16
Verlag:IEEE - Institute of Electrical and Electronics Engineers
ISSN:2689-1808
Status:veröffentlicht
Stichwörter:Quantum Computing, Quantum Algorithms
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 (alt)
Standort: Köln-Porz
Institute & Einrichtungen:Institut für Softwaretechnologie > High-Performance Computing
Institut für Softwaretechnologie
Hinterlegt von: Stollenwerk, Tobias
Hinterlegt am:08 Dez 2020 09:12
Letzte Änderung:24 Okt 2023 13:48

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.