CoChat

Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study

Open access
Gemeinhardt, Felix, Garmendia, Antonio, Wimmer, Manuel, Weder, Benjamin, Leymann, Frank · 2024 · ACM Computing Surveys

The DOI matches its Crossref record; 269 of the 305 references it cites were found in a registry or an index; 180 of the 283 sources its claims cite were checked for support.

Abstract

The application of quantum computing to combinatorial optimization problems is attracting increasing research interest, resulting in diverse approaches and research streams. This study aims at identifying, classifying, and understanding existing solution approaches as well as typical use cases in the field. The obtained classification schemes are based on a full-text analysis of 156 included papers. Our results can be used by researchers and practitioners to (i) better understand adaptations to and utilizations of existing gate-based and quantum annealing approaches and (ii) identify typical use cases for quantum computing in areas such as graph optimization, routing, and scheduling.

Overview

CoChat Summary

TL;DR

This systematic mapping study reviews 156 papers on quantum combinatorial optimization for NISQ devices, classifying solution approaches, adaptations, classical integration, and use cases. It finds gate-model approaches dominate, VQAs are the most studied, and Max-Cut is the most common validation problem.

Key findings

  • Among identified quantum CO approaches, 80% are gate-model, 16% quantum annealing, and 4% other; within gate-model approaches, VQAs account for 85%. For adaptations, the ansatz is the most prominent VQA adaptation (64%), while changes to the Hamiltonian are the most studied QA adaptation (50%).
  • Machine learning is the most generally applicable and popular classical means for enhancing quantum algorithms, appearing in 67% of identified studies. When quantum solvers are used as subroutines in classical frameworks, 42% use architecture-independent QUBO solvers, 17% use decomposition methods, and 25% use QAOA/VQE.
  • Typical use cases are graph optimization, routing, and scheduling; Max-Cut is the most popular validation problem, especially for gate-based approaches. Most solved problems are real-world instances with no given mapping to a standard CO problem in the original literature.
  • Bibliometric results: 38% of studies are ArXiv publications and 47% are journal articles from peer-reviewed repositories. Pure solution papers decreased from 17% to 0%, solution-plus-validation papers increased from 50% to 73%, and no evaluation papers were identified. Topic areas are gate-based approaches (53%), QA (35%), other approaches (4%), and problem formulation (8%).

Methods

  • Systematic mapping study following established guidelines, using the search string `('quantum AND computing' AND 'combinatorial AND optimization')` across DBLP, ACM, IEEE Xplore, Scopus, and ArXiv, limited to English papers published between January 2018 and May 2021.
  • Two-phase selection: database search retrieved 218 papers, initial assessment selected 79, full-text assessment selected 63; snowballing selected 328 papers, fully read 121, and included 93, yielding 156 total included studies. A pre-defined validation set of 15 relevant papers was used, with 11 found by the initial search and 4 by snowballing.
  • Classification scheme was iteratively developed from the full text of the 156 studies; bibliometric data extraction covered publication time, type, channel, and research facet, with results documented in a replication package.

Limitations

  • Stated: external validity may be threatened by a nonrepresentative sample, mitigated by including non-peer-reviewed e-print literature and two-phase snowballing; English-language limitation is considered minimal; the 2018 start date is discussed. Internal validity was mitigated by researcher agreement on inclusion/exclusion. Construct validity was addressed via multiple databases, search string derived from RQs, snowballing, and inter-researcher agreement. Conclusion validity notes other researchers may derive different concepts, with countermeasures including emergent concepts and multi-researcher extraction.
  • Evident from the text: the review is restricted to January 2018–May 2021 and English publications, and it excludes compilation/embedding techniques, error mitigation, classical numerical solvers for parameter optimization, classical post-processing, quantum Monte Carlo, quantum walk, quantum machine learning, and quantum-inspired approaches. The authors also report that no evaluation papers were identified.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1145/3620668

Cites

269 of 269 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Figures

Fig. 1 Overall protocol of our methodology based on Petersen et al. [207].
Fig. 1 Overall protocol of our methodology based on Petersen et al. [207].CC-BY · From the PDF
Fig. 2 Feature diagram for categorization of quantum algorithms for CO and their adaptations. (Numbers below leaves denote absolute number of identified studies and percentage regarding parent node.).
Fig. 2 Feature diagram for categorization of quantum algorithms for CO and their adaptations. (Numbers below leaves denote absolute number of identified studies and percentage regarding parent node.).CC-BY · From the PDF
Fig. 3 Optimization problem classes treated with QC: #studies (left) and #problems (right).
Fig. 3 Optimization problem classes treated with QC: #studies (left) and #problems (right).CC-BY · From the PDF
Fig. 4 Left: Distribution of papers by year and publication type; Right :Distribution of papers by year and research facet.
Fig. 4 Left: Distribution of papers by year and publication type; Right :Distribution of papers by year and research facet.CC-BY · From the PDF

Verification

Claims the paper makes

124 Valid · 10 Not valid · 37 Not checked · 74 Own results and interpretations

77 more claims · 30 with their cited sources checked

Create a free account to see all 245 claims and to verify the 4 references still open.

See all claims — free account
  • Probably not a substantial claim. 119
  • It may state two separate claims as one. 72

Create a free account to see these claims.

Self-check

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

Each contradiction between two passages listed here was confirmed by an independent check.

2 of 2

Citations

Cites

Research works printed but not linked: 8

  1. Tim Bittner and Sven Groppe. 2020. Avoiding blocking by scheduling transactions using quantum annealing. In 24th Symposium on International Database Engineering & Applications. 1–10.
  2. Atsushi Matsuo, Yudai Suzuki, and Shigeru Yamashita. 2020. Problem-specific parameterized quantum circuits of the VQE algorithm for optimization problems. arXiv preprint arXiv:2006.05643 (2020). · arXiv
  3. Jiahao Yao, Marin Bukov, and Lin Lin. 2020. Policy gradient based quantum approximate optimization algorithm. In Mathematical and Scientific Machine Learning. PMLR, 605–634.
  4. Elsevier. 2023. Quantum computing research trends report. https://beta.elsevier.com/insights/quantum-computing-report?trial=true
  5. 10.5555/3226649.3226818 · doi:10.5555/3226649.3226818
  6. Staffs Keele. 2007. Guidelines for Performing Systematic Literature Reviews in Software Engineering. Technical Report.
  7. 10.1103/PhysRevE.99.013304 · DOI · Paper page
  8. L. S. Pontryagin, V. G. Boltyanskii, R. V. Gamkrelidze, and E. F. Mishchenko. 1986. The Mathematical Theory of Optimal Processes’Selected Works of LS Pontryagin, Vol. 4, Gordon and Breach Science Pub. S.A. Montreux, Switzerland.

Cited by

See all 22

Metadata

Authors
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F.
Affiliations
  • Johannes Kepler University of Linz (AT)
  • Universidad Autónoma de Madrid, Modelling & Software Engineering Research Group, Spain
  • University of Stuttgart (DE)
Venue
ACM Computing Surveys
Published
2023-10-05
Volume
56
Issue
3
Pages
1-36
ISSN
  • 0360-0300 (ISSN-L)
  • 1557-7341
OpenAlex
W4386443168
Cited by
22
References
305
Citations by year
2026: 9 · 2025: 7 · 2024: 6
FWCI
1.95
Type
journal article
Language
en
Open access
Locations
  • ACM Computing Surveys (publishedVersion, cc-by)
  • Biblos-e Archivo (Universidad Autónoma de Madrid) (submittedVersion, cc-by)
  • BURJC Digital (King Juan Carlos University) (submittedVersion, cc-by)
  • University Library Linz repository (Johannes Kepler Universitat Linz) (submittedVersion, cc-by)
  • Hispana (submittedVersion)
  • Hispana (submittedVersion, cc-by)
Funders
  • Austrian Federal Ministry for Digital and Economic Affairs and the National Foundation for Research, Technology and Development and by the Austrian Science Fund (P 30525-N31)
  • Federal Ministry for Economic Affairs and Climate Action (PlanQK (01MK20005N) and EniQmA (01MQ22007B))
  • Spanish MICINN (PID2021-122270OB-I00 and TED2021-129381B-C21)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
Keywords
NISQ devices, quantum annealing, gate-based quantum computing, graph optimization, routing, scheduling

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.

The claim verdicts this report counts are experimental: their accuracy is not yet measured.

A language model drew the claims from the paper on 2026-10-12, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-12 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Cited sources are checked with a language model’s help (gpt-6-sol).

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

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.