Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem
Open accessThe DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
Quantum supremacy using a programmable superconducting processor
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G. S. L., Buell, D. A., et al. (2019) · Nature · doi:10.1038/s41586-019-1666-5 · Cited by 7,720
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Branch-and-price: column generation for solving huge integer programs
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998) · Operations Research · doi:10.1287/opre.46.3.316 · Cited by 2,219
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
Zhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2020) · Physical Review X · doi:10.1103/physrevx.10.021067 · Cited by 913 · cited 3×
“[24] to work equally well as the BFGS method, for this heuristic strategy.”
MethodInfluentialFarhi, E., Goldstone, J., Gutmann, S., & Zhou, L. (2019) · arXiv · doi:10.48550/arxiv.1910.08187 · Cited by 226
Benchmarking the quantum approximate optimization algorithm
Willsch, M., Willsch, D., Jin, F., De Raedt, H., & Michielsen, K. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02692-8 · Cited by 128
Effects of Quantum Noise on Quantum Approximate Optimization Algorithm
Xue, C., Chen, Z.-Y., Wu, Y.-C., & Guo, G.-P. (2019) · arXiv · doi:10.48550/arxiv.1909.02196 · Cited by 96
Cited by
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 2,231
The potential and global outlook of integrated photonics for quantum technologies
Pelucchi, E., Fagas, G., Aharonovich, I., Englund, D., Figueroa, E., Gong, Q., Hannes, H., Liu, J., Lu, C.-Y., Matsuda, N., et al. (2021) · Nature Reviews Physics · doi:10.1038/s42254-021-00398-z · Cited by 533
A review on Quantum Approximate Optimization Algorithm and its variants
Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., & Summer, A. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.03.002 · Cited by 408
Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
Willsch, D., Willsch, M., Gonzalez Calaza, C. D., Jin, F., De Raedt, H., Svensson, M., & Michielsen, K. (2022) · Quantum Information Processing · doi:10.1007/s11128-022-03476-y · Cited by 114
“We remark that the 25 qubit tail assignment problem solved in this section is the same problem that was investigated as the largest problem instance in [47].”
BackgroundSelf-citationA study of the performance of classical minimizers in the Quantum Approximate Optimization Algorithm
Fernández-Pendás, M., Combarro, E. F., Vallecorsa, S., Ranilla, J., & Rúa, I. F. (2022) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2021.113388 · Cited by 52
Metadata
- Authors
- Vikstål, P., Grönkvist, M., Svensson, M., Andersson, M., Johansson, G., & Ferrini, G.
- Venue
- Physical Review Applied
- Publisher
- American Physical Society (APS)
- Published
- 2020-09-03
- Volume
- 14
- Issue
- 3
- ISSN
- 2331-7019 (ISSN-L)
- OpenAlex
- W2995218853
- Cited by
- 84
- References
- 12
- FWCI
- 3.79
- Type
- journal article
- Language
- en
- Open access
- hybrid
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem. https://app.cochat.ai/papers/10.1103/physrevapplied.14.034009
- The paper
- Vikstål, P., Grönkvist, M., Svensson, M., Andersson, M., Johansson, G., & Ferrini, G. (2020). Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem. Physical Review Applied. https://doi.org/10.1103/physrevapplied.14.034009
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.