• Open Access

Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem

Pontus Vikstål, Mattias Grönkvist, Marika Svensson, Martin Andersson, Göran Johansson, and Giulia Ferrini
Phys. Rev. Applied 14, 034009 – Published 3 September 2020

Abstract

Airlines today are faced with a number of large-scale scheduling problems. One such problem is the tail-assignment problem, which is the task of assigning individual aircraft to a given set of flights, minimizing the overall cost. Each aircraft is identified by the registration number on its tail fin. In this paper, we simulate the quantum approximate optimization algorithm (QAOA) applied to instances of this problem derived from real-world data. The QAOA is a variational hybrid quantum-classical algorithm recently introduced and likely to run on near-term quantum devices. The instances are reduced to fit on quantum devices with 8, 15, and 25 qubits. The reduction procedure leaves only one feasible solution per instance, which allows us to map the tail-assignment problem onto the exact-cover problem. We find that repeated runs of the QAOA identify the feasible solution with close to unit probability for all instances. Furthermore, we observe patterns in the variational parameters such that an interpolation strategy can be employed, which significantly simplifies the classical optimization part of the QAOA. Finally, we empirically find a relation between the connectivity of the problem graph and the single-shot success probability of the algorithm.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
3 More
  • Received 20 January 2020
  • Revised 20 May 2020
  • Accepted 10 August 2020
  • Corrected 2 December 2022

DOI:https://doi.org/10.1103/PhysRevApplied.14.034009

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.

Published by the American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & Technology

Corrections

2 December 2022

Correction: The copyright license statement was presented incorrectly and has been fixed.

Authors & Affiliations

Pontus Vikstål1,*, Mattias Grönkvist2, Marika Svensson1,2, Martin Andersson2, Göran Johansson1, and Giulia Ferrini1

  • 1Wallenberg Centre for Quantum Technology, Department of Microtechnology and Nanoscience, Chalmers University of Technology, 412 96 Gothenburg, Sweden
  • 2Jeppesen Systems AB, 411 03 Gothenburg, Sweden

  • *vikstal@chalmers.se

Article Text

Click to Expand

References

Click to Expand
Issue

Vol. 14, Iss. 3 — September 2020

Subject Areas
Reuse & Permissions
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Applied

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

×

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×