CoChat
Sign Up
Cited by 30Quantum Computing Algorithms and ArchitectureQuantum many-body systemsQuantum Information and Cryptography

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

Open access
Stollenwerk, Tobias, Hadfield, Stuart, Wang, Zhihui·2020·IEEE Transactions on Quantum Engineering
DOI 10.1109/tqe.2020.3030609
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/tqe.2020.3030609

Cites

44 of 44 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • A method has been proposed to derive the initial state and possible mixing Hamiltonian for the flight-gate assignment problem, with construction principles extendable to general graph coloring and scheduling problems.

    “Specifically for the flight-gate assignment problem, a method has been proposed to derive the initial state and possible mixing Hamiltonian where the construction principles can be extended for treating general graph coloring and scheduling problems [127].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [127]

    The ‘Finding Initial Feasible Assignments’ section describes constructing a suitable initial QAOA state, and ‘Mixing Operators’ derives mixers for flight-gate assignment and other problems whose feasible solutions are colorings of chordal graphs. The copy does not establish that these constructions extend to general graph-coloring and scheduling problems without that restriction. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • Ansatz adaptations can occur as a byproduct, as in the Quantum Alternating Operator Ansatz where the primary goal is to find a mixing Hamiltonian that ensures staying in the feasible subspace.

    “Besides the mentioned ansatz search, as the driving force behind ansatz adaptation, there is also the possibility of having these adaptations as a byproduct, like it happens, e.g., within the Quantum Alternating Operator Ansatz where the primary goal is to find a mixing Hamiltonian that ensures to stay in the feasible subspace [11, 58, 95, 112, 116, 117, 120, 127].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [127]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

2 of the 46 references couldn’t be matched to a known paper.

Research works printed but not linked: 2

  1. "Imaging acquisition planning for earth observation satellites with a quan- tum annealer," 2020, arXiv:2006.09724. [Online]. Available: https://arxiv. org/abs/2006.09724 · arXiv
  2. M. R. Garey and D. S. Johnson, Computers and Intractability, vol. 29. New York, NY, USA: W. H. Freeman, 2002. [Online]. Available: https://dl.acm.org/doi/book/10.5555/578533 · DOI

Cited by

Sorted by citations

Related

Authors
Stollenwerk, T., Hadfield, S., & Wang, Z.
Affiliations
  • Deutsches Zentrum für Luft- und Raumfahrt e. V. (DLR) (DE)
  • Ames Research Center (US)
ORCID
Venue
IEEE Transactions on Quantum Engineering
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Published
2020
Volume
1
Pages
1-16
ISSN
2689-1808 (ISSN-L)
DOI
10.1109/tqe.2020.3030609
OpenAlex
W3111324546
Cited by
29
References
46
Citations by year
2026: 3 · 2025: 5 · 2024: 6 · 2023: 9 · 2022: 5 · 2021: 1
FWCI
1.57
Type
journal article
Language
en
Open access
Licence
Locations
  • IEEE Transactions on Quantum Engineering (publishedVersion, cc-by)
  • elib (German Aerospace Center) (acceptedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
Funders
  • Deutsches Zentrum für Luft- und Raumfahrt
  • Ames Research Center
  • AFRL Information Directorate (F4HBKC4162G001)
  • Office of the Director of National Intelligence
  • Intelligence Advanced Research Projects Activity (IAA 145483)
  • Advanced Exploration Systems
  • NASA Transformative Aeronautic Concepts Program
  • NASA Academic Mission Services (NNA16BD14C)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
quantum approximate optimization algorithm, chordal graphs, graph coloring, conflict graph, quantum circuit decomposition, resource scaling, combinatorial optimization

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review