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

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

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

[img] PDF - Published version

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


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.

Item URL in elib:https://elib.dlr.de/138683/
Document Type:Article
Title:Toward Quantum Gate-Model Heuristics for Real-World Planning Problems
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Stollenwerk, TobiasUNSPECIFIEDhttps://orcid.org/0000-0001-5445-8082
Hadfield, StuartNASA Quantum Artificial Intelligence LaboratoryUNSPECIFIED
Wang, ZhihuiNASA Quantum Artificial Intelligence LaboratoryUNSPECIFIED
Date:November 2020
Journal or Publication Title:IEEE Transactions on Quantum Engineering
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In ISI Web of Science:No
Page Range:pp. 1-16
Publisher:IEEE - Institute of Electrical and Electronics Engineers
Keywords:Quantum Computing, Quantum Algorithms
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 - Quantencomputing (old)
Location: Köln-Porz
Institutes and Institutions:Institute for Software Technology > High-Performance Computing
Institute for Software Technology
Deposited By: Stollenwerk, Tobias
Deposited On:08 Dec 2020 09:12
Last Modified:19 Nov 2021 20:40

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.