Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study
Open accessThe 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
Cites
Statistics
Figures
![Fig. 1 Overall protocol of our methodology based on Petersen et al. [207].](https://figures.cochat.ai/paper-figures/f17c4e7c66824cbab7738f24d113c5bc/quantum-combinatorial-optimization-in-the-nisq-era-a-systematic-mapping-study-figure-1.png)



Verification
Claims the paper makes
124 Valid · 10 Not valid · 37 Not checked · 74 Own results and interpretations
At least one cited source doesn’t support this claim or points to a different paper, and none confirmed it — see the verdicts below.
In the paper
“so-called Noisy Intermediate-Scale Quantum (NISQ) computers already exist today”
What the sources say
- Disputedcites [209] John Preskill. 2018. Quantum computing in the NISQ era and beyond. Quantum 2 (2018), 79. sourceExperimental — accuracy not yet measured
Preskill says on p. 1 that NISQ technology “will be available in the near future.” Section 4.1 (p. 4) likewise describes intermediate-scale quantum computers as becoming available “in the next few years,” rather than saying they already exist. (LLM, conf=0.86)
Checked by a reasoning model — may be wrong.
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Disputed
Every source the paper cites for this claim was checked and supports it.
In the paper
“However, the parameterized quantum circuits often utilize multi-controlled operations to encode constraints into the ansatz, e.g., the Quantum Alternating Operator Ansatz [58].”
What the sources say
- Supportedcites [58] source
The paper’s “Mixing operators” section describes mixers that restrict evolution to the feasible subspace and says a partitioned mixer uses multiqubit-controlled-NOT operators. Section 4.3.1 likewise describes operations controlled by neighboring vertices to preserve feasibility. These support the cited ansatz as an example of using multi-controlled operations to encode constraints. (LLM, conf=0.90)
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
Every source the paper cites for this claim was checked and supports it.
In the paper
“However, with the mappings of CO problems to Hamiltonians stated in the previous section, besides quantum chemical problems, the same approach can be used to solve CO problems [10].”
What the sources say
- Supportedcites [10] source
Section 2 explicitly says the VQE approach can be used to attempt to solve combinatorial optimization problems. It describes mapping a QUBO problem to a Hamiltonian and applying VQE to seek its ground state. (LLM, conf=0.95)
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“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].”
What the sources say
- Supportedcites [11] source
The comparison with standard QAOA (p. 3) describes the Quantum Alternating Operator Ansatz as focused on mixer design and says its mixing unitaries must preserve the feasible subspace. The description of adaptations as a byproduct is the citing authors’ framing; the source supports the attributed example and its mixer-design goal. (LLM, conf=0.88)
- Partly supportedcites [58] sourceExperimental — accuracy not yet measured
The Introduction and Conclusions describe designing mixing operators that keep evolution within the feasible subspace, supporting that part of the claim. But the paper presents its extension of the ansatz as an explicit aim, not a byproduct, and says its mixers need not arise from a fixed mixing Hamiltonian. The indexed passages provide section labels but no page numbers. (LLM, conf=0.86)
- Supportedcites [95] source
Section II (pp. 6–7) describes modifying the mixing operator to separate feasible from infeasible states, so the quantum walk remains in the feasible subspace. This supports the cited paper as an example of adapting an alternating-operator approach to preserve feasibility. (LLM, conf=0.88)
- Partly supportedcites [112] sourceExperimental — accuracy not yet measured
The Conclusion (p. 9) says the paper’s tailored variational forms explore only feasible solutions, supporting the general idea of adapting an ansatz to stay within a feasible search space. But the paper does not describe the Quantum Alternating Operator Ansatz or a mixing Hamiltonian as the means of doing so; its Applications section (p. 6) instead treats QAOA as a comparison method that uses constraint penalties. (LLM, conf=0.84)
- Supportedcites [116] source
The paper’s “XY mixer: Enforcing evolution in the feasible subspace” section (p. 4) says it selects a mixing term that preserves the feasible subspace. The Introduction (p. 1) identifies this as its approach to implementing the Quantum Alternating Operator Ansatz for constrained problems. The characterization of ansatz adaptation as a byproduct is the citing authors’ framing. (LLM, conf=0.91)
- Supportedcites [117] source
The Introduction (p. 1) identifies B as the mixing Hamiltonian, and Scheme 1 (p. 4) says encoding constraints in B connects feasible solutions while excluding infeasible ones. This supports the cited paper as an example of adapting the mixer to keep the evolution in the feasible subspace; calling that adaptation a “byproduct” is the citing authors’ framing. (LLM, conf=0.87)
- Not matchedcites [120]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Supportedcites [127] source
The paper’s C. MIXING OPERATORS section describes designing mixing operators that preserve the feasible subspace, and its Abstract identifies these as quantum alternating operator ansatz constructions. The citing authors’ description of ansatz adaptation as a “byproduct” is their framing of that design work. (LLM, conf=0.88)
hedgedstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
Every source the paper cites for this claim was checked and supports it.
In the paper
“In this sense, CVar [10], ascending CVar [78], and the Gibbs objective function [86] can be regarded as adaptations of standard QAOA or VQE that affect their underlying objective function.”
What the sources say
- Supportedcites [10] source
The Introduction states that the paper replaces minimization of expected energy with minimization of CVaR and applies this modification to VQE and QAOA. That supports the part of the citing sentence attached to this source, CVaR as an objective-function adaptation; the other two methods have separate citations. (LLM, conf=0.94)
- Supportedcites [78] source
The citation to this paper is attached to ascending CVaR, not to the other two objective functions in the sentence. Section III describes Ascending-CVaR as a dynamically evolving cost function, and “Our contributions” states that it is tested with both VQE and QAOA. (LLM, conf=0.93)
- Supportedcites [86] source
The Theory section describes the Gibbs objective function as an alternative to the standard energy-expectation objective for choosing variational parameters. The Numerical experiments section compares QAOA using Gibbs with the original QAOA prescription using energy, confirming the attributed change to QAOA’s objective function. This citation is attached to the Gibbs objective function, not to either CVaR variant. (LLM, conf=0.94)
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
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.
- Probably not a substantial claim. 119
- It may state two separate claims as one. 72
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.
Rated major: it would touch a result — a value a result rests on, reported and recomputed p-values on opposite sides of the significance level, two passages that conflict with no sign which is right, or a cited work retracted before this paper was published.
In the paper
§ 4.1 Solution Approaches to Quantum Combinatorial Optimization · p. 19
“A comparison with SA, spin-vector-monte-carlo [215], and simulated QA suggests that QA possesses the best scaling properties [7].”
§ 4.1 Solution Approaches to Quantum Combinatorial Optimization · p. 20
“QA shows superior scaling properties compared to SA, where both are significantly inferior to simulated QA [7].”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ 4.1 Solution Approaches to Quantum Combinatorial Optimization · p. 12
“The use of problem-specific parameterized quantum circuits of the VQE algorithm where the information on constraints is used for the circuit design has been suggested by DÃŋez-Valle et al. [96] to reduce the search space and accelerate convergence.”
§ PRIMARY LITERATURE · p. 31
“[96] Atsushi Matsuo, Yudai Suzuki, and Shigeru Yamashita. 2020. Problem-specific parameterized quantum circuits of the VQE algorithm for optimization problems.”
Citations
Cites
Items 201–269 of 269
Bass, G., Tomlin, C., Kumar, V., Rihaczek, P., & Dulny, J. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aaadc2 · Cited by 16 · cited 1×
“A comparison between various decomposition techniques, i.e., principal component decomposition [185], free-and-anneal [163], qbSolv, and iterative centrality halo [172] has demonstrated the superiority of qbsolv in terms of solution quality [12].”
BackgroundThe Complexity of Stoquastic Local Hamiltonian Problems
Bravyi, S., DiVincenzo, D. P., Oliveira, R. I., & Terhal, B. M. (2006) · arXiv · doi:10.48550/arxiv.quant-ph/0606140 · Cited by 15 · cited 1×
“Promising improvement strategies comprise non-stoquastic Hamiltonians [170], spatially inhomogeneous driving of the transverse field, and reverse annealing [205].”
BackgroundInvestigating quantum approximate optimization algorithms under bang-bang protocols
Liang, D., Li, L., & Leichenauer, S. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.033402 · Cited by 15 · cited 1×
“Studies on QAOA as a bang-bang protocol, like the ones by Liang et al. [87], allow to derive its properties for such large circuit depths.”
MethodBittner, T., & Groppe, S. (2020) · RonPub -- Research Online Publishing (RonPub UG) · Cited by 14
Classical symmetries and QAOAPreprint
Shaydulin, R., Hadfield, S., Hogg, T., & Safro, I. (2020) · arXiv (Cornell University) · Cited by 14
Garcia-Saez, A., & Riu, J. (2019) · arXiv · doi:10.48550/arxiv.1911.09682 · Cited by 13 · cited 5×
“…[10], [78], [86] Ansatz [11, 36, 48, 58, 82, 86, 88, 89, 95–97], [112], [116], [117, 120, 127, 131, 151], [152, 153, 155] Parameter Optimization [51], [75], [76, 99], [141], [143], [146] Measurement [122], [125] Grover-search [52], [118] Other gate-based approaches [15], [16], [24], [94]…”
BackgroundMethodInfluentialAdiabatic Quantum Computing for Max-Sum Diversification
Bauckhage, C., Sifa, R., & Wrobel, S. (2020) · Proceedings of the 2020 SIAM International Conference on Data Mining · doi:10.1137/1.9781611976236.39 · Cited by 13
Quantum constraint learning for quantum approximate optimization algorithmPreprint
Radha, S. K. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.06770 · Cited by 12 · cited 4×
“In this sense, the mixer unitary can be learned based on two cost functions and subsequently be directly inserted into the quantum circuit [114], allowing for a flexible control concerning the trade off between accuracy and the depth of the learned unitary.”
BackgroundMethodInfluentialLeveraging Special-Purpose Hardware for Local Search Heuristics
Liu, X., Ushijima-Mwesigwa, H., Mandal, A., Upadhyay, S., Safro, I., & Roy, A. (2019) · arXiv · doi:10.48550/arxiv.1911.09810 · Cited by 11
Foundations for Workflow Application Scheduling on D-Wave System
Tomasiewicz, D., Pawlik, M., Malawski, M., & Rycerz, K. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-50433-5_40 · Cited by 11 · cited 1×
“Additional QUBO-formulations for scheduling or routing problems that have been validated with QA comprise: the workflow scheduling problem [138], conflict management on a single-track railway [40], real-time multi-robot routing [31], and controlling automated guided vehicles on a factory floor…”
Solving Inequality-Constrained Binary Optimization Problems on Quantum Annealer
Yonaga, K., Miyama, M. J., & Ohzeki, M. (2020) · arXiv · doi:10.48550/arxiv.2012.06119 · Cited by 10 · cited 2×
“Hybrid approaches have also been proposed to treat inequality constraints [149], allowing to tackle larger problems compared to using standard approaches that introduce slack variables (cf. Section 2).”
Background(2020) · arXiv (Cornell University) · Cited by 9
Noise-tolerant quantum speedups in quantum annealing without fine tuning
Kapit, E., & Oganesyan, V. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/abd59a · Cited by 9
Chukwu, U., Dridi, R., Berwald, J., Booth, M., Dawson, J., Le, D., Wainger, M., & Reinhardt, S. P. (2020) · 2020 IEEE High Performance Extreme Computing Conference (HPEC) · doi:10.1109/hpec43674.2020.9286230 · Cited by 9
Quantum approximate algorithm for NP optimization problems with constraints
Ruan, Y., Marsh, S., Xue, X., Li, X., Liu, Z., & Wang, J. (2020) · arXiv · doi:10.48550/arxiv.2002.00943 · Cited by 9 · cited 3×
“Objective Function [10], [78], [86] Ansatz [11, 36, 48, 58, 82, 86, 88, 89, 95–97], [112], [116], [117, 120, 127, 131, 151], [152, 153, 155] Parameter Optimization [51], [75], [76, 99], [141], [143], [146] Measurement [122], [125] Grover-search [52], [118] Other gate-based approaches [15], [16],…”
BackgroundTomesh, T., Allen, N., Dilley, D., & Saleem, Z. (2022) · arXiv · doi:10.48550/arxiv.2210.04378 · Cited by 9
(2021) · arXiv (Cornell University) · Cited by 8
Unconventional quantum annealing methods for difficult trial problems
Tang, Z., & Kapit, E. (2021) · Physical Review A · doi:10.1103/physreva.103.032612 · Cited by 8 · cited 5×
“Tang and Kapit [136] provide an empirical benchmark study on mitigation techniques concerning the shrinking energy gap.”
BackgroundMethodInfluentialAdelomou, A. P., Ribé, E. G., & Cardona, X. V. (2020) · Journal of Computer and Communications · doi:10.4236/jcc.2020.811004 · Cited by 8 · cited 1×
“VQE has been applied to a QUBO formulation for the social workers problem, which explores problem specificities to avoid excessive auxiliary variables [1], and to multi-coloring graph problems [104].”
MethodQCI Qbsolv Delivers Strong Classical Performance for Quantum-Ready Formulation
Booth, M., Berwald, J., Chukwu, U., Dawson, J., Dridi, R., Le, D., Wainger, M., & Reinhardt, S. P. (2020) · arXiv · doi:10.48550/arxiv.2005.11294 · Cited by 8
Complex Semidefinite Programming and Max-k-Cut
Newman, A. (2018) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/oasics.sosa.2018.13 · Cited by 7 · cited 1×
“An empirical evaluation of recursive QAOA has demonstrated its superiority compared to the standard version as well as its competitiveness compared to the Newman benchmark algorithm [203] for the Max-Cut problem [23].”
MethodSolving tiling puzzles with quantum annealingPreprint
Eagle, A., Kato, T., & Minato, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1904.01770 · Cited by 7 · cited 1×
“Further problems that have been treated with the standard QA approaches include: max-sum diversification [13], model-predictive control [71], the tiling puzzle problem [41], and image acquisition planning for earth observation satellites [128].”
BackgroundLarge-scale Quantum Approximate Optimization via Divide-and-ConquerPreprint
Li, J., Alam, M., & Ghosh, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.13288 · Cited by 6 · cited 2×
“In this sense, QAOA has been utilized as a local neighborhood sampler for a Tabu-driven search [98], and a divide-and-conquer version of QAOA has been proposed to cope with larger problem instances [84].”
MethodQuinones, M. P., & Junqueira, C. (2020) · arXiv · doi:10.48550/arxiv.2007.13245 · Cited by 6
Improving Quantum Annealing Performance on Embedded Problems
(2020) · Supercomputing Frontiers and Innovations · doi:10.14529/jsfi200403 · Cited by 6
On Quantum Computing for Mixed-Integer ProgrammingPreprint
Chang, C.-Y., Jones, E. B., & Graf, P. A. (2020) · arXiv (Cornell University) · Cited by 6
Finding Maximum Cliques on the D-Wave Quantum AnnealerPreprint
Chapuis, G., Djidjev, H. N., Hahn, G., & Rizk, G. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.08649 · Cited by 5
Tabu-Driven Quantum Neighborhood Samplers
Moussa, C., Wang, H., Calandra, H., Bäck, T., & Dunjko, V. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-72904-2_7 · Cited by 4 · cited 2×
“In this sense, QAOA has been utilized as a local neighborhood sampler for a Tabu-driven search [98], and a divide-and-conquer version of QAOA has been proposed to cope with larger problem instances [84].”
MethodForecasting Election Polls with Spin Systems
Ibarrondo, R., Sanz, M., & Orús, R. (2022) · SN Computer Science · doi:10.1007/s42979-021-00942-9 · Cited by 4 · cited 1×
“The problem of election poll forecasting has also been formulated as a HUBO and QUBO for QA, respectively [68].”
MethodOptimizing Quantum Annealing Schedules: From Monte Carlo Tree Search to QuantumZeroPreprint
Chen, Y., Chen, Y., Lee, C., Zhang, S., & Hsieh, C. (2020) · arXiv (Cornell University) · Cited by 4
Combinatorial optimization through variational quantum power method
Daskin, A. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03283-x · Cited by 4
Svensson, M., Andersson, M., Grönkvist, M., Vikstål, P., Dubhashi, D., Ferrini, G., & Johansson, G. (2021) · arXiv (Cornell University) · Cited by 3
Tabu-driven Quantum Neighborhood SamplersPreprint
Moussa, C., Wang, H., Calandra, H., Bäck, T. H. W., & Dunjko, V. (2020) · Leiden Repository (Leiden University) · Cited by 3
Performance comparison of optimization methods on variational quantum algorithms
Bonet-Monroig, X., Wang, H., Vermetten, D., et al. (2021) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.48550/arxiv.2111.13454 · Cited by 3
A Leap among Quantum Computing and Quantum Neural Networks: A SurveyPreprint
Massoli, F. V., Vadicamo, L., Amato, G. M., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.03313 · Cited by 2 · cited 1×
“Continuous developments in QC raise the expectations that, in the near-term future, we could speed up simulations in quantum chemistry and improve optimization processes as well as machine learning approaches, compared to classical means of computation [164, 175, 187, 200].”
BackgroundTowards analyzing large graphs with quantum annealing and quantum gate computersPreprint
Reittu, H., Kotovirta, V., Leskelä, L., Rummukainen, H., & Räty, T. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.16702 · Cited by 2 · cited 2×
“Problem-specific hybrid approaches have been applied to the capacitated vehicle routing problem [45] and the community detection problem [115].”
BackgroundQuantum Scheduling for Millimeter-Wave Observation Satellite ConstellationPreprint
Kim, J., Kwak, Y., Jung, S., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.00626 · Cited by 2
Sweeping quantum annealing algorithm for constrained optimization problemsPreprint
Yan, Z., Zhou, Z., Wang, Y.-C., Meng, Z. Y., & Zhang, X.-F. (2021) · Research Square · doi:10.21203/rs.3.rs-556216/v1 · Cited by 2 · cited 2×
“…QAOA/VQE Multistart-method [123], RQAOA [23], Divide-and-Conquer QAOA [84], qCBR [8], Tabu-driven Search [98], k-step pruning [46] QA Sweeping QA [145], Problem-specific utilization (e.g., References [38, 45, 115]); Decomposition methods: generic [109], problem-specific [102, 107, 110] Any…”
MethodHybrid quantum-classical optimization for financial index trackingPreprint
Fernández-Lorenzo, S., Porras, D., & García‐Ripoll, J. J. (2020) · RePEc: Research Papers in Economics · doi:10.48550/arxiv.2008.12050 · Cited by 2
Characterization of QUBO reformulations for the maximum $k$-colorable subgraph problemPreprint
Quintero, R., Bernal, D. E., Terlaky, T., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.09462 · Cited by 1 · cited 1×
“…routing problem with time windows [61] on gate-based devices; the job-shop scheduling problem [156], the maximum k-colorable subgraph problem [113], as well as the 3-SAT problem [80] on quantum annealers; and the graph partitioning problem [30] on the classical QCI sampler tool [19] where…”
Backgroundquantum Case-Based Reasoning (qCBR)Preprint
Atchade-Adelomou, P., Casado-Fauli, D., Golobardes-Ribe, E., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.00409 · Cited by 1 · cited 2×
“Utilization method QAOA/VQE Multistart-method [123], RQAOA [23], Divide-and-Conquer QAOA [84], qCBR [8], Tabu-driven Search [98], k-step pruning [46] QA Sweeping QA [145], Problem-specific utilization (e.g., References [38, 45, 115]); Decomposition methods: generic [109], problem-specific [102,…”
MethodMost Frequent Itemset Optimization.Preprint
Nüßlein, J. (2019) · arXiv (Cornell University) · Cited by 1
Differentiable Quantum Architecture Search
Zhang, S.-X., Hsieh, C.-Y., Zhang, S., et al. (2020) · arXiv · doi:10.48550/arxiv.2010.08561
Iterative Quantum Assisted Eigensolver
Bharti, K., & Haug, T. (2020) · arXiv · doi:10.48550/arxiv.2010.05638
Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
Azad, U., Behera, B. K., Ahmed, E. A., et al. (2020) · arXiv · doi:10.48550/arxiv.2002.01351
Hybrid quantum-classical algorithms for approximate graph coloring
Bravyi, S., Kliesch, A., Koenig, R., et al. (2020) · arXiv · doi:10.48550/arxiv.2011.13420
Garden optimization problems for benchmarking quantum annealers
Calaza, C. D. G., Willsch, D., & Michielsen, K. (2021) · arXiv · doi:10.48550/arxiv.2101.10827
Ising-based Consensus Clustering on Specialized Hardware
Cohen, E., Mandal, A., Ushijima-Mwesigwa, H., et al. (2020) · arXiv · doi:10.48550/arxiv.2003.01887
Combinatorial optimization through variational quantum power method
Daskin, A. (2020) · arXiv · doi:10.48550/arxiv.2007.01004
Quantum variational optimization: The role of entanglement and problem hardness
Díez-Valle, P., Porras, D., & García-Ripoll, J. J. (2021) · arXiv · doi:10.48550/arxiv.2103.14479
Towards Prediction of Financial Crashes with a D-Wave Quantum Computer
Ding, Y., Gonzalez-Conde, J., Lamata, L., et al. (2019) · arXiv · doi:10.48550/arxiv.1904.05808
On the representation of Boolean and real functions as Hamiltonians for quantum computing
Hadfield, S. (2018) · arXiv · doi:10.48550/arxiv.1804.09130
Impact of Graph Structures for QAOA on MaxCut
Herrman, R., Treffert, L., Ostrowski, J., et al. (2021) · arXiv · doi:10.48550/arxiv.2102.05997
Forecasting Election Polls with Spin Systems
Ibarrondo, R., Sanz, M., & Orus, R. (2020) · arXiv · doi:10.48550/arxiv.2007.05070
An evolving objective function for improved variational quantum optimisation
Kolotouros, I., & Wallden, P. (2021) · arXiv · doi:10.48550/arxiv.2105.11766
Evaluation of QAOA based on the approximation ratio of individual samples
Larkin, J., Jonsson, M., Justice, D., et al. (2020) · arXiv · doi:10.48550/arxiv.2006.04831
Progress toward favorable landscapes in quantum combinatorial optimization
Lee, J., Magann, A. B., Rabitz, H. A., et al. (2021) · arXiv · doi:10.48550/arxiv.2105.01114
Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
Liu, X., Angone, A., Shaydulin, R., et al. (2021) · arXiv · doi:10.48550/arxiv.2102.05566
Empirical performance bounds for quantum approximate optimization
Lotshaw, P. C., Humble, T. S., Herrman, R., et al. (2021) · arXiv · doi:10.48550/arxiv.2102.06813
Feedback-based quantum optimization
Magann, A. B., Rudinger, K. M., Grace, M. D., et al. (2021) · arXiv · doi:10.48550/arxiv.2103.08619
Osaba, E., Villar-Rodriguez, E., Oregi, I., et al. (2021) · arXiv · doi:10.48550/arxiv.2102.05919
Approaches to Constrained Quantum Approximate Optimization
Saleem, Z. H., Tomesh, T., Tariq, B., et al. (2020) · arXiv · doi:10.48550/arxiv.2010.06660
Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
Stollenwerk, T., Michaud, V., Lobe, E., et al. (2020) · arXiv · doi:10.48550/arxiv.2006.09724
Neural Predictor based Quantum Architecture Search
Zhang, S.-X., Hsieh, C.-Y., Zhang, S., et al. (2021) · arXiv · doi:10.48550/arxiv.2103.06524
Complex Semidefinite Programming and Max-k-Cut
Newman, A. (2018) · arXiv · doi:10.48550/arxiv.1812.10770
Schedule path optimization for quantum annealing and adiabatic quantum computing
Zeng, L., Zhang, J., & Sarovar, M. (2015) · arXiv · doi:10.48550/arxiv.1505.00209
On multilevel iterative methods for optimization problems
Gelman, E., & Mandel, J. (1990) · Mathematical Programming · doi:10.1007/bf01582249
Research works printed but not linked: 8
- Tim Bittner and Sven Groppe. 2020. Avoiding blocking by scheduling transactions using quantum annealing. In 24th Symposium on International Database Engineering & Applications. 1–10.
- 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
- Jiahao Yao, Marin Bukov, and Lin Lin. 2020. Policy gradient based quantum approximate optimization algorithm. In Mathematical and Scientific Machine Learning. PMLR, 605–634.
- Elsevier. 2023. Quantum computing research trends report. https://beta.elsevier.com/insights/quantum-computing-report?trial=true
- 10.5555/3226649.3226818 · doi:10.5555/3226649.3226818
- Staffs Keele. 2007. Guidelines for Performing Systematic Literature Reviews in Software Engineering. Technical Report.
- 10.1103/PhysRevE.99.013304 · DOI · Paper page
- 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
Quantum annealing for combinatorial optimization: a benchmarking study
Kim, S., Ahn, S.-W., Suh, I.-S., Dowling, A. W., Lee, E., & Luo, T. (2025) · npj Quantum Information · doi:10.1038/s41534-025-01020-1 · Cited by 46
“38,39 : Here, t is the elapsed annealing time, and t a is the total annealing time.”
SoK: quantum computing methods for machine learning optimization
Baniata, H. (2024) · Quantum Machine Intelligence · doi:10.1007/s42484-024-00180-1 · Cited by 17
“Specifically, the Ising problem without an external field can be equivalently formulated as a graph maximum cut (Max-Cut) problem that can be solved via combinatorial optimization, which had been well studied in the literature to be solved using QC (Gemeinhardt et al. 2023; Zhou et al. 2023).”
Quantum Computing Through the Lens of Control: A Tutorial Introduction
Berberich, J., & Fink, D. (2024) · IEEE Control Systems · doi:10.1109/mcs.2024.3466448 · Cited by 28
“Various quantum algorithms were developed to solve combinatorial optimization problems [S8], [S9].”
MethodContemporary approaches in matheuristics an updated survey
Boschetti, M. A., & Maniezzo, V. (2024) · Annals of Operations Research · doi:10.1007/s10479-024-06302-z · Cited by 10
“The real turning point was the demonstration of the equivalence between the QUBO model and the Ising model, which plays a prominent role in quantum mechanics (see, Glover et al. (2019, 2022); Gemeinhardt et al. (2023)).”
Gnatowski, A., & Niżyński, T. (2026) · Lecture notes in networks and systems · doi:10.1007/978-3-032-14163-7_19 · Cited by 8
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
- hybrid
- doi.org
- Licence
- 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.