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
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134 · cited 1×
“QA [178] is a heuristic related to adiabatic quantum computation [178] that is inspired by simulated annealing [195].”
BackgroundQuantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Fast unfolding of communities in large networks
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2008/10/p10008 · Cited by 21,424 · cited 1×
“Kalehbasti et al.[74] proposed the generalizable idea of replacing the greedy heuristic within the Louvain algorithm [165], a classical heuristic for the k-community detection problem, by a QUBO solver to consider a larger search space in each iteration [74].”
MethodQuantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 18,842
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830 · cited 2×
“Furthermore, the concept of NISQ quantum computing has been introduced in 2018 [209].”
BackgroundA fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Exploring Network Structure, Dynamics, and Function Using NetworkX
Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008) · Proceedings of the Python in Science Conference · doi:10.25080/tcwv9851 · Cited by 7,477 · 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].”
BackgroundCase-Based Reasoning: Foundational Issues, Methodological Variations, and System Approaches
Aamodt, A., & Plaza, E. (1994) · AI Communications · doi:10.3233/aic-1994-7104 · Cited by 5,624 · cited 1×
“A further specific application of variational algorithms within a classical framework is a proposed quantum version of case-based reasoning [158].”
BackgroundCombinatorial optimization. Polyhedra and efficiency.
Schrijver, A. (2003) · UvA-DARE (University of Amsterdam) · Cited by 4,637
A variational eigenvalue solver on a photonic quantum processor
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014) · Nature Communications · doi:10.1038/ncomms5213 · Cited by 4,552 · cited 2×
“Therefore, the Variational Quantum Eigensolver (VQE) [206] and Quantum Approximate Optimization Algorithm (QAOA) [177] are introduced subsequently as prominent examples of VQAs for the domain of CO.”
BackgroundMethodSystematic Literature Reviews in Software Engineering—A Systematic Literature Review
Kitchenham, B., Pearl Brereton, O., Budgen, D., Turner, M., Bailey, J., & Linkman, S. (2009) · Information and Software Technology · doi:10.1016/j.infsof.2008.09.009 · Cited by 4,537
Wohlin, C. (2014) · Proceedings of the 18th International Conference on Evaluation and Assessment in Software Engineering · doi:10.1145/2601248.2601268 · Cited by 4,234 · cited 3×
“As a guideline, this study was performed following well-known principles of systematic studies: References [193, 196, 207, 220].”
MethodBeitrag zur Theorie des Ferromagnetismus
Ising, E. (1925) · Zeitschrift für Physik · doi:10.1007/bf02980577 · Cited by 3,871
Variational quantum algorithms
Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., et al. (2021) · Nature Reviews Physics · doi:10.1038/s42254-021-00348-9 · Cited by 3,385 · cited 3×
“Whereas comprehensive reviews on VQAs, in general, can be found, e.g., in References [164, 171], the focus in this work lies on VQAs for CO.”
BackgroundMethodSystematic Mapping Studies in Software Engineering
Petersen, K., Feldt, R., Mujtaba, S., & Mattsson, M. (2008) · Electronic Workshops in Computing · doi:10.14236/ewic/ease2008.8 · Cited by 3,239 · cited 3×
“As a guideline, this study was performed following well-known principles of systematic studies: References [193, 196, 207, 220].”
MethodSurface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059 · cited 1×
“A universal fault-tolerant quantum computer would require millions of qubits of highest quality [179].”
BackgroundHardware-efficient variational quantum eigensolver for small molecules and quantum magnets
Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J. M., & Gambetta, J. M. (2017) · Nature · doi:10.1038/nature23879 · Cited by 2,982 · cited 1×
“The variational form of the parametrized quantum circuit, also called ansatz, is important in this regard, where standard approaches (e.g., References [191, 202]) comprise the iterative alternating application of non-commuting single qubit rotations and controlled two-qubit operations.”
MethodIsing formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512 · cited 3×
“Finally, there are several already existent direct mappings for many NP-hard and NP-complete problems to QUBO/Ising form [199].”
BackgroundNumerical Methods for Large Eigenvalue Problems: Revised Edition
Saad, Y. (2011) · doi:10.1137/1.9781611970739 · Cited by 2,364 · cited 1×
“A variational quantum circuit for CO that is not derived from QAOA or VQE is represented by a quantum version of the shifted power method [211], where the rationale is based on finding the dominant eigenpair of a matrix [36].”
MethodBranch-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 · cited 1×
“QUBO solvers have also been applied within the Branch-and-Price method [162] to solve the Restricted Master Problem within this approach [133].”
MethodA Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789 · cited 4×
“The QAOA [177] has been specifically developed for CO problems.”
BackgroundMethodInfluentialAlbash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
Systematic literature reviews in software engineering – A tertiary study
Kitchenham, B., Pretorius, R., Budgen, D., Pearl Brereton, O., Turner, M., Niazi, M., & Linkman, S. (2010) · Information and Software Technology · doi:10.1016/j.infsof.2010.03.006 · Cited by 1,230
Requirements engineering paper classification and evaluation criteria: a proposal and a discussion
Wieringa, R., Maiden, N., Mead, N., & Rolland, C. (2006) · Requirements Engineering · doi:10.1007/s00766-005-0021-6 · Cited by 940 · cited 3×
“The data extraction of bibliometric information happened for the following dimensions: time of publication, type of publication, publication channel, and research facet as defined by Wieringa et al. [219].”
MethodInfluentialZhou, 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 4×
“…VQAs and QA have demonstrated (i) the reachability issues of QAOA compared to VQE [10], (ii) the ability of QAOA to harness diabatic processes in contrast to QA [154], (iii) the superiority of QA in terms of performance [142], and (iv) the character of QAOA as a digitized version of QA [141].”
BackgroundMethodInfluentialFault-tolerant quantum computation
Shor, P. W. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548464 · Cited by 892
Garousi, V., Felderer, M., & Mäntylä, M. V. (2019) · Information and Software Technology · doi:10.1016/j.infsof.2018.09.006 · Cited by 831
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827 · cited 1×
“The potentially large overhead in the number of variables lead to the development of several methods for degree reduction (e.g., References [160, 167, 168, 180, 188]), which are explained and compared in References [53, 62, 135, 218].”
MethodFrom the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019) · Algorithms · doi:10.3390/a12020034 · Cited by 772 · cited 5×
“Hadfield et al. [58] propose the Quantum Alternating Operator Ansatz where the problem-agnostic mixing Hamiltonian of the original QAOA is replaced by a mixing Hamiltonian that enforces constraints and ensures that transitions between all pairs of feasible states are provided.”
BackgroundMethodInfluentialHybrid Quantum-Classical Algorithms and Quantum Error Mitigation
Endo, S., Cai, Z., Benjamin, S. C., & Yuan, X. (2021) · Journal of the Physical Society of Japan · doi:10.7566/jpsj.90.032001 · Cited by 566 · cited 2×
“A promising strategy to cope with the existent resource limitations is represented by hybrid quantum-classical approaches, which comprise quantum as well as classical computation (e.g., References [164, 176]).”
BackgroundQuantum approximate optimization of non-planar graph problems on a planar superconducting processor
Harrigan, M. P., Sung, K. J., Neeley, M., Satzinger, K. J., Arute, F., Arya, K., Atalaya, J., Bardin, J. C., Barends, R., Boixo, S., et al. (2021) · Nature Physics · doi:10.1038/s41567-020-01105-y · Cited by 564 · cited 4×
“Noisy computation leads to scaling issues for QAOA [56, 60].”
BackgroundInfluentialQuantum Computation by Adiabatic Evolution
Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000) · arXiv · doi:10.48550/arxiv.quant-ph/0001106 · Cited by 536 · cited 2×
“QA [178] is a heuristic related to adiabatic quantum computation [178] that is inspired by simulated annealing [195].”
BackgroundPerspectives of quantum annealing: methods and implementations
Hauke, P., Katzgraber, H. G., Lechner, W., Nishimori, H., & Oliver, W. D. (2020) · Reports on Progress in Physics · doi:10.1088/1361-6633/ab85b8 · Cited by 507 · cited 7×
“…[51], [75], [76, 99], [141], [143], [146] Measurement [122], [125] Grover-search [52], [118] Other gate-based approaches [15], [16], [24], [94] Hamiltonians [62, 111, 136], [136] Space [136] Time [27], [62, 88] Other approaches [19, 63] sensitivity of QAOA to initial parameter settings [137].”
BackgroundMethodInfluential2019 IEEE Congress on Evolutionary Computation (CEC)
(2019) · doi:10.1109/cec44084.2019 · Cited by 504
Hamilton, C. S., Kruse, R., Sansoni, L., Barkhofen, S., Silberhorn, C., & Jex, I. (2017) · Physical Review Letters · doi:10.1103/physrevlett.119.170501 · Cited by 503 · cited 1×
“Gaussian boson sampling, however, is a special-purpose photonic platform to perform sampling tasks that are classically intractable [186].”
BackgroundQuantum Computation and Quantum Information.
Campbell, P. J., & Rosenthal, E. S. (2001) · Mathematics Magazine · Cited by 476
Minor-embedding in adiabatic quantum computation: I. The parameter setting problem
Choi, V. (2008) · Quantum Information Processing · doi:10.1007/s11128-008-0082-9 · Cited by 410 · cited 1×
“In quantum annealing, this mapping to the hardware topology is called embedding, where the standard technique in use is denoted as minor embedding [174].”
MethodQAOA for Max-Cut requires hundreds of qubits for quantum speed-up
Guerreschi, G. G., & Matsuura, A. Y. (2019) · Scientific Reports · doi:10.1038/s41598-019-43176-9 · Cited by 337 · cited 3×
“Noisy computation leads to scaling issues for QAOA [56, 60].”
BackgroundQuantum Bridge Analytics I: a tutorial on formulating and using QUBO models
Glover, F., Kochenberger, G., & Du, Y. (2019) · 4OR · doi:10.1007/s10288-019-00424-y · Cited by 298 · cited 8×
“Inequality constraints can be mapped to equality constraints, where additional variables have to be introduced [53, 135].”
BackgroundMethodInfluentialQuantum computing for energy systems optimization: Challenges and opportunities
Ajagekar, A., & You, F. (2019) · Energy · doi:10.1016/j.energy.2019.04.186 · Cited by 289 · cited 1×
“Ajagekar and You [3] apply QA to three problems from energy systems, namely, facility location allocation, unit commitment, and heat exchanger networks, whereas Ding et al. [39] used QA for the prediction of financial crashes [39].”
MethodObstacles to State Preparation and Variational Optimization from Symmetry Protection
Bravyi, S., Kliesch, A., Koenig, R., & Tang, E. (2019) · arXiv · doi:10.48550/arxiv.1910.08980 · Cited by 279
Obstacles to Variational Quantum Optimization from Symmetry Protection
Bravyi, S., Kliesch, A., Koenig, R., & Tang, E. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.260505 · Cited by 278 · cited 3×
“To overcome fundamental limitations of QAOA, like the ones mentioned in Section 4.1.4 (e.g., References [43, 44]), a drastically different, non-local version of QAOA is proposed by Bravyi et al. [23], which is called Recursive QAOA (RQAOA) .”
MethodInfluentialWarm-starting quantum optimization
Egger, D. J., Mareček, J., & Woerner, S. (2021) · Quantum · doi:10.22331/q-2021-06-17-479 · Cited by 269 · cited 3×
“Concerning the former, a preconditioning of the quantum algorithm for VQAs is provided by warm-starting with classical solvers for relaxed CO problems [42], e.g., an SDP solver [137].”
BackgroundMethodImproving Variational Quantum Optimization using CVaR
Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I., & Woerner, S. (2020) · Quantum · doi:10.22331/q-2020-04-20-256 · Cited by 263 · cited 8×
“It can be regarded as a form of VQE with a specific choice of the variational form that is derived from the problem Hamiltonian [10].”
BackgroundMethodInfluentialDemonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing
Albash, T., & Lidar, D. A. (2018) · Physical Review X · doi:10.1103/physrevx.8.031016 · Cited by 238 · cited 2×
“SA, spin-vector-monte-carlo [215], and simulated QA suggests that QA possesses the best scaling properties [7].”
BackgroundReverse quantum annealing approach to portfolio optimization problems
Venturelli, D., & Kondratyev, A. (2019) · Quantum Machine Intelligence · doi:10.1007/s42484-019-00001-w · Cited by 233 · cited 1×
“When it comes to more advanced quantum annealing methods, forward as well as reverse annealing have been applied to the nurse scheduling problem [69] and portfolio optimization [140].”
MethodThe Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical CasePreprint
Farhi, E., Gamarnik, D., & Gutmann, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.09002 · Cited by 226 · cited 4×
“It has been theoretically proven [4, 43, 44] and empirically validated [121].”
BackgroundMethodInfluentialSequential minimal optimization for quantum-classical hybrid algorithms
Nakanishi, K. M., Fujii, K., & Todo, S. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.043158 · Cited by 221 · cited 5×
“Besides the vast amount of available numerical optimizers, solvers for sequential minimal optimization [99] represent another alternative for parameter optimization.”
BackgroundMethodInfluentialBenchmarking Quantum Computers and the Impact of Quantum Noise
Resch, S., & Karpuzcu, U. R. (2021) · ACM Computing Surveys · doi:10.1145/3464420 · Cited by 218 · cited 1×
“To leverage the potential of NISQ devices and according hybrid algorithms, great advancements have been accomplished, ranging from computer architecture [210] to software engineering aspects [214].”
MethodRecent advances in quantum machine learning
Zhang, Y., & Ni, Q. (2020) · Quantum Engineering · doi:10.1002/que2.34 · Cited by 210 · cited 1×
“Quantum Monte Carlo [221], quantum walk [225], and quantum machine learning [224] denote topics where quantum versions of classical approaches are developed that may be applied, among others, to CO problems, but are not associated with traditional CO approaches.”
BackgroundZhu, L., Tang, H. L., Barron, G. S., Calderon-Vargas, F. A., Mayhall, N. J., Barnes, E., & Economou, S. E. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.033029 · Cited by 209
Ajagekar, A., Humble, T., & You, F. (2020) · Computers & Chemical Engineering · doi:10.1016/j.compchemeng.2019.106630 · Cited by 191 · cited 2×
“Finally, Ajagekar et al. [2] presented four examples of large-scale optimization problems solved with problem class–specific hybrid decomposition techniques: molecular conformation, job-shop-scheduling, manufacturing cell formation, and vehicle routing [2].”
BackgroundMethodXY mixers: Analytical and numerical results for the quantum alternating operator ansatz
Wang, Z., Rubin, N. C., Dominy, J. M., & Rieffel, E. G. (2020) · Physical Review A · doi:10.1103/physreva.101.012320 · Cited by 190
Efficient partition of integer optimization problems with one-hot encoding
Okada, S., Ohzeki, M., & Taguchi, S. (2019) · Scientific Reports · doi:10.1038/s41598-019-49539-6 · Cited by 190
A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
Feld, S., Roch, C., Gabor, T., Seidel, C., Neukart, F., Galter, I., Mauerer, W., & Linnhoff-Popien, C. (2019) · Frontiers in ICT · doi:10.3389/fict.2019.00013 · Cited by 188 · cited 2×
“…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 QUBO-solver Problem-agnostic: ADMM [50, 61, 149], Branch &…”
BackgroundMethodQuantum Optimization and Quantum Learning: A Survey
Li, Y., Tian, M., Liu, G., Peng, C., & Jiao, L. (2020) · IEEE Access · doi:10.1109/access.2020.2970105 · Cited by 177 · cited 2×
“Quantum-inspired algorithms, also known as quantum intelligent algorithms, have been covered by Li et al. [198].”
BackgroundMethodEnergy Minimization via Graph Cuts: Settling What is Possible
Freedman, D., & Drineas, P. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.143 · Cited by 173 · cited 1×
“The potentially large overhead in the number of variables lead to the development of several methods for degree reduction (e.g., References [160, 167, 168, 180, 188]), which are explained and compared in References [53, 62, 135, 218].”
MethodQuantum Computing: An Applied Approach
Hidary, J. D. (2019) · Springer eBooks · doi:10.1007/978-3-030-23922-0 · Cited by 167 · 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].”
BackgroundNoisy intermediate-scale quantum (NISQ) 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. (2021) · arXiv · doi:10.48550/arxiv.2101.08448 · Cited by 166
Generating shortcuts to adiabaticity in quantum and classical dynamics
Jarzynski, C. (2013) · Physical Review A · doi:10.1103/physreva.88.040101 · Cited by 159 · cited 1×
“The method of counter-diabatic driving [190] circumvents the bottle-neck of the adiabatic regime where proposals for implementation on current devices work with an approximate two-parameter Hamiltonian [111].”
MethodPerformance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
Crooks, G. E. (2018) · arXiv · doi:10.48550/arxiv.1811.08419 · Cited by 158 · cited 2×
“In this sense, the effects of parameter symmetry exploitation and parameter regression have been investigated [85], and the training of parameters on a whole batch of randomly generated graph instances to reduce training costs [33] has been studied, yielding promising results.”
BackgroundMethodDifferentiable quantum architecture search
Zhang, S.-X., Hsieh, C.-Y., Zhang, S., & Yao, H. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/ac87cd · Cited by 158 · cited 8×
“…Bender’s decompostition [26], C-QUBO-LS / U-QUBO-LS [90], Problem-class specific decomposition [2] Problem-specific: QLS [124], Multilevel approach [139], Adapted Louvain algorithm [74] Quantum Alternating Operator Ansatz [114], and for program generation and architecture search [88, 97, 151, 152].”
BackgroundMethodInfluentialGrover Adaptive Search for Constrained Polynomial Binary Optimization
Gilliam, A., Woerner, S., & Gonciulea, C. (2021) · Quantum · doi:10.22331/q-2021-04-08-428 · Cited by 153 · cited 3×
“An efficient way for the oracle construction within this algorithm that may allow it to be run on NISQ devices has been proposed [52].”
BackgroundMethodReachability Deficits in Quantum Approximate Optimization
Akshay, V., Philathong, H., Morales, M. E. S., & Biamonte, J. D. (2020) · Physical Review Letters · doi:10.1103/physrevlett.124.090504 · Cited by 151 · cited 3×
“It has been theoretically proven [4, 43, 44] and empirically validated [121].”
BackgroundMethodSolving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
Azad, U., Behera, B. K., Ahmed, E. A., Panigrahi, P. K., & Farouk, A. (2023) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2022.3172241 · Cited by 149 · cited 1×
“Standard QAOA has been applied to: the cluster head selection problem [28], the wireless scheduling problem [29], the vehicle routing problem [14], multi-coloring graph problems [104], the graph isomorphism problem [66], and a satellite scheduling problem [128].”
Method2022 IEEE Congress on Evolutionary Computation (CEC)
(2022) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec55065.2022.9870329 · Cited by 147
Formulating and Solving Routing Problems on Quantum Computers
Harwood, S., Gambella, C., Trenev, D., Simonetto, A., Bernal Neira, D., & Greenberg, D. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3049230 · Cited by 145 · cited 3×
“The CO problems that have been studied in this context are the vehicle 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…”
BackgroundTraffic signal optimization on a square lattice with quantum annealing
Inoue, D., Okada, A., MATSUMORI, T., Aihara, K., & Yoshida, H. (2021) · Scientific Reports · doi:10.1038/s41598-021-82740-0 · Cited by 144 · cited 1×
“…problem [103], consensus clustering [32], the online advertisement allocation problem [135], traffic signal optimization on a square lattice [70], the Multi-depot Capacitated Vehicle Routing problem in its static and dynamic version [59], and the Vehicle Routing Problem including the…”
BackgroundTransformation of General Binary MRF Minimization to the First-Order Case
Ishikawa, H. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.91 · Cited by 144 · cited 1×
“The potentially large overhead in the number of variables lead to the development of several methods for degree reduction (e.g., References [160, 167, 168, 180, 188]), which are explained and compared in References [53, 62, 135, 218].”
MethodApplication of Ising Machines and a Software Development for Ising Machines
Tanahashi, K., Takayanagi, S., Motohashi, T., & Tanaka, S. (2019) · Journal of the Physical Society of Japan · doi:10.7566/jpsj.88.061010 · Cited by 142 · cited 5×
“Inequality constraints can be mapped to equality constraints, where additional variables have to be introduced [53, 135].”
BackgroundMethodInfluentialThe Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case ExamplesPreprint
Farhi, E., Gamarnik, D., & Gutmann, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.08747 · Cited by 141 · cited 3×
“It has been theoretically proven [4, 43, 44] and empirically validated [121].”
BackgroundMethodInfluentialApplication of Quantum Annealing to Nurse Scheduling Problem
Ikeda, K., Nakamura, Y., & Humble, T. S. (2019) · Scientific Reports · doi:10.1038/s41598-019-49172-3 · Cited by 139 · cited 1×
“When it comes to more advanced quantum annealing methods, forward as well as reverse annealing have been applied to the nurse scheduling problem [69] and portfolio optimization [140].”
MethodPerformance of hybrid quantum-classical variational heuristics for combinatorial optimization
Nannicini, G. (2019) · Physical Review E · doi:10.1103/physreve.99.013304 · Cited by 138 · cited 2×
“Investigations on the impact of different classical optimizers for parameter optimization in general advocate for gradient-free global optimizers when dealing with real quantum hardware [37, 47, 100, 121].”
BackgroundThe complexity of stoquastic local Hamiltonian problems
Bravyi, S. B., Divincenzo, D. P., Oliveira, R. I., & Terhal, B. M. (2008) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2011772.2011773 · Cited by 135
Quantum annealing with antiferromagnetic fluctuations
Seki, Y., & Nishimori, H. (2012) · Physical Review E · doi:10.1103/physreve.85.051112 · Cited by 131 · cited 1×
“The methods comprise inhomogeneous driving, added transverse couplers [213] and RFQA (Random Field Quantum Annealing or Radio Frequency Quantum Annealing) [192].”
MethodQuantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
Stollenwerk, T., O'Gorman, B., Venturelli, D., Mandra, S., Rodionova, O., Ng, H., Sridhar, B., Rieffel, E. G., & Biswas, R. (2020) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2019.2891235 · Cited by 129 · cited 1×
“A simplified version of the air-traffic management conflict-resolution problem has been tackled with QA after extraction of feasible subproblems [129].”
BackgroundQuantum Software Components and Platforms: Overview and Quality Assessment
Serrano, M., Cruz-Lemus, J. A., Pérez‐Castillo, R., & Piattini, M. G. (2022) · ACM Computing Surveys · doi:10.1145/3548679 · Cited by 129
Applications of near-term photonic quantum computers: software and algorithms
Bromley, T. R., Arrazola, J. M., Jahangiri, S., Izaac, J., Quesada, N., Gran, A. D., Schuld, M., Swinarton, J., Zabaneh, Z., & Killoran, N. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8504 · Cited by 128 · cited 3×
“Within the gate-model domain, a further distinction can be made between VQAs, Grover-based approaches [52, 118], and other gate-based approaches that have been mentioned above, e.g., References [15, 16, 24, 94].”
BackgroundMethodBenchmarking 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 · cited 2×
“…VQAs and QA have demonstrated (i) the reachability issues of QAOA compared to VQE [10], (ii) the ability of QAOA to harness diabatic processes in contrast to QA [154], (iii) the superiority of QA in terms of performance [142], and (iv) the character of QAOA as a digitized version of QA [141].”
BackgroundFull-stack, real-system quantum computer studies: architectural comparisons and design insights
Murali, P., Linke, N. M., Martonosi, M., Abhari, A. J., Nguyen, N. H., & Alderete, C. H. (2019) · Proceedings of the 46th International Symposium on Computer Architecture · doi:10.1145/3307650.3322273 · Cited by 128 · cited 1×
“These multi-controlled operations are not natively supported by most available NISQ devices [201], limiting the practical applicability of approaches relying on this concept.”
BackgroundTraining the quantum approximate optimization algorithm without access to a quantum processing unit
Streif, M., & Leib, M. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8c2b · Cited by 125 · cited 4×
“An adaptation to QAOA, which does not require exhaustive access to the quantum processing unit [131], has been used to solve the binary paint shop problem [132].”
BackgroundMethodInfluentialGrover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
Bartschi, A., & Eidenbenz, S. (2020) · 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce49297.2020.00020 · Cited by 122 · cited 3×
“Another possibility is to shift the complexity to the generation of the initial state [11], where the idea is to further utilize the state preparation circuit, which creates an equal superposition of all feasible states, for the design of the mixing Hamiltonian.”
BackgroundLearning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
Khairy, S., Shaydulin, R., Cincio, L., Alexeev, Y., & Balaprakash, P. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i03.5616 · Cited by 117 · cited 5×
“…[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] Hamiltonians [62,…”
BackgroundMethodInfluentialPyQUBO: Python Library for Mapping Combinatorial Optimization Problems to QUBO Form
Zaman, M., Tanahashi, K., & Tanaka, S. (2021) · arXiv · doi:10.48550/arxiv.2103.01708 · Cited by 114 · cited 4×
“Automated approaches for the problem formulation comprise formulation transformations, with the PyQUBO software tool [150], and penalty parameter setting utilizing reinforcement learning [9].”
BackgroundMethodInfluentialPyQUBO: Python Library for Mapping Combinatorial Optimization Problems to QUBO Form
Zaman, M., Tanahashi, K., & Tanaka, S. (2022) · IEEE Transactions on Computers · doi:10.1109/tc.2021.3063618 · Cited by 114
Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
Tabi, Z., El-Safty, K. H., Kallus, Z., Haga, P., Kozsik, T., Glos, A., & Zimborás, Z. (2020) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce49297.2020.00018 · Cited by 111 · cited 1×
“Similarly, a problem-specific encoding for the graph coloring problem has been proposed regarding the gate-model quantum computation [134].”
BackgroundA study of heuristic guesses for adiabatic quantum computation
Perdomo-Ortiz, A., Venegas-Andraca, S. E., & Aspuru-Guzik, A. (2011) · Quantum Information Processing · doi:10.1007/s11128-010-0168-z · Cited by 111 · cited 1×
“Promising improvement strategies comprise non-stoquastic Hamiltonians [170], spatially inhomogeneous driving of the transverse field, and reverse annealing [205].”
BackgroundMultistart Methods for Quantum Approximate optimization
Shaydulin, R., Safro, I., & Larson, J. (2019) · 2019 IEEE High Performance Extreme Computing Conference (HPEC) · doi:10.1109/hpec.2019.8916288 · Cited by 110 · cited 4×
“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,…”
BackgroundMethodInfluentialBenchmarking the quantum approximate optimization algorithm
Willsch, M., Willsch, D., Jin, F., Raedt, H. A. D., & Michielsen, K. F. L. (2020) · RWTH Publications (RWTH Aachen) · Cited by 109
Bridging Classical and Quantum with SDP initialized warm-starts for QAOA
Tate, R., Farhadi, M., Herold, C. D., Mohler, G., & Gupta, S. (2022) · ACM Transactions on Quantum Computing · doi:10.1145/3549554 · Cited by 108 · cited 3×
“Concerning the former, a preconditioning of the quantum algorithm for VQAs is provided by warm-starting with classical solvers for relaxed CO problems [42], e.g., an SDP solver [137].”
BackgroundMethodGrover's Quantum Algorithm Applied to Global Optimization
Baritompa, W. P., Bulger, D. W., & Wood, G. R. (2005) · SIAM Journal on Optimization · doi:10.1137/040605072 · Cited by 108 · cited 1×
“In this sense, Grover-based optimization algorithms [184] such as Grover Adaptive Search [161] have been proposed.”
MethodPerformance comparison of optimization methods on variational quantum algorithms
Bonet-Monroig, X., Wang, H., Vermetten, D., Senjean, B., Moussa, C., Bäck, T., Dunjko, V., & O'Brien, T. E. (2023) · Physical Review A · doi:10.1103/physreva.107.032407 · Cited by 107 · cited 2×
“It shall be noted at this point that, according to our exclusion criteria, we refrain from taking into account the former in our analysis, as these approaches deserve a survey on their own [166].”
MethodResultControl of Automated Guided Vehicles Without Collision by Quantum Annealer and Digital Devices
Ohzeki, M., Miki, A., Miyama, M. J., & Terabe, M. (2019) · Frontiers in Computer Science · doi:10.3389/fcomp.2019.00009 · Cited by 102 · cited 1×
“…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 [106].”
BackgroundEffects of Quantum Noise on Quantum Approximate Optimization Algorithm
Xue, C., Chen, Z.-Y., Wu, Y.-C., & Guo, G.-P. (2021) · Chinese Physics Letters · doi:10.1088/0256-307x/38/3/030302 · Cited by 100 · cited 2×
“Ideal parameter values do not deviate when noise is not serious [144].”
BackgroundHybrid quantum-classical algorithms for approximate graph coloring
Bravyi, S., Kliesch, A., Koenig, R., & Tang, E. (2022) · Quantum · doi:10.22331/q-2022-03-30-678 · Cited by 99 · cited 2×
“The Max-k-Cut problem has also served for a comparative study concerning standard QAOA and RQAOA [22].”
MethodResultQuantum optimization with a novel Gibbs objective function and ansatz architecture search
Li, L., Fan, M., Coram, M., Riley, P., & Leichenauer, S. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.023074 · Cited by 98 · cited 8×
“But also greedy heuristics have been proposed for the purpose of ansatz search [86].”
BackgroundMethodInfluentialEffects 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
A Leap among Quantum Computing and Quantum Neural Networks: A Survey
Massoli, F. V., Vadicamo, L., Amato, G. M., & Falchi, F. (2022) · ACM Computing Surveys · doi:10.1145/3529756 · Cited by 94 · 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].”
BackgroundDigital-analog quantum simulations with superconducting circuits
Lamata, L., Parra-Rodriguez, A., Sanz, M., & Solano, E. (2018) · Advances in Physics: X · doi:10.1080/23746149.2018.1457981 · Cited by 93 · cited 1×
“Other approaches to quantum CO comprise digital-analogue QC and photonic QC. Digital-analogue QC can be understood as a mixture between continuous QC (e.g., QA) and discrete QC (e.g., gate-model QC) [197].”
BackgroundBenchmarking Quantum Annealing Controls with Portfolio Optimization
Grant, E., Humble, T. S., & Stump, B. (2021) · Physical Review Applied · doi:10.1103/physrevapplied.15.014012 · Cited by 90 · cited 2×
“The impact of various quantum controls, such as annealing time and number of spin reversals [194], on the success probability and chain breaks has been studied by Grant et al. [55], yielding a saturation effect for both controls.”
BackgroundHow "Quantum" is the D-Wave Machine?
Shin, S. W., Smith, G., Smolin, J. A., & Vazirani, U. (2014) · arXiv · doi:10.48550/arxiv.1401.7087 · Cited by 89 · cited 1×
“SA, spin-vector-monte-carlo [215], and simulated QA suggests that QA possesses the best scaling properties [7].”
BackgroundBrandao, F. G. S. L., Broughton, M., Farhi, E., Gutmann, S., & Neven, H. (2018) · arXiv · doi:10.48550/arxiv.1812.04170 · Cited by 88 · cited 3×
“Continuing with empirical studies on gate-based quantum CO approaches, a large-scale evaluation on QAOA [92, 121] validated the theoretical properties [4, 21, 43] and yielded further empirical performance bounds.”
BackgroundMethodNeural predictor based quantum architecture search
Zhang, S.-X., Hsieh, C.-Y., Zhang, S., & Yao, H. (2021) · Machine Learning: Science and Technology · doi:10.1088/2632-2153/ac28dd · Cited by 88 · cited 7×
“…Bender’s decompostition [26], C-QUBO-LS / U-QUBO-LS [90], Problem-class specific decomposition [2] Problem-specific: QLS [124], Multilevel approach [139], Adapted Louvain algorithm [74] Quantum Alternating Operator Ansatz [114], and for program generation and architecture search [88, 97, 151, 152].”
BackgroundMethodInfluentialOn the Representation of Boolean and Real Functions as Hamiltonians for Quantum Computing
Hadfield, S. (2021) · ACM Transactions on Quantum Computing · doi:10.1145/3478519 · Cited by 86 · cited 1×
“Generic transformation techniques have been covered by Glover et al. [53] and Hadfield [57].”
MethodBreaking limitation of quantum annealer in solving optimization problems under constraints
Ohzeki, M. (2020) · Scientific Reports · doi:10.1038/s41598-020-60022-5 · Cited by 84
A cross-disciplinary introduction to quantum annealing-based algorithms
Venegas-Andraca, S. E., Cruz-Santos, W., McGeoch, C., & Lanzagorta, M. (2018) · Contemporary Physics · doi:10.1080/00107514.2018.1450720 · Cited by 83 · cited 6×
“The Hamiltonian of the system then continuously changes with time according to References [178, 218]: where t a is the total annealing time, A(s) and B(s) are functions that obey A(s=0)=1, B(s=0)=0 and A(s=1)=0, B(s=1)=1.”
BackgroundMethodInfluentialDetecting multiple communities using quantum annealing on the D-Wave system
Negre, C. F. A., Ushijima-Mwesigwa, H., & Mniszewski, S. M. (2020) · PLOS ONE · doi:10.1371/journal.pone.0227538 · Cited by 80 · cited 1×
“In this sense, QUBO formulations for the graph coloring problem [126], the k-community detection problem [101], the Maximum Independent Set problem [148], the Minimum Multicut problem [34], the most frequent itemset problem [103], consensus clustering [32], the online advertisement allocation…”
BackgroundReinforcement-learning-assisted quantum optimization
Wauters, M. M., Panizon, E., Mbeng, G. B., & Santoro, G. E. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.033446 · Cited by 80 · cited 6×
“…VQAs and QA have demonstrated (i) the reachability issues of QAOA compared to VQE [10], (ii) the ability of QAOA to harness diabatic processes in contrast to QA [154], (iii) the superiority of QA in terms of performance [142], and (iv) the character of QAOA as a digitized version of QA [141].”
BackgroundMethodInfluentialOptimizing quantum heuristics with meta-learning
Wilson, M., Stromswold, R., Wudarski, F., Hadfield, S., Tubman, N. M., & Rieffel, E. G. (2021) · Quantum Machine Intelligence · doi:10.1007/s42484-020-00022-w · Cited by 79 · cited 5×
“Machine learning [9] Parameter initialization and optimization Analytical solver [99] Knowledge base [123, 154] Machine learning [6, 51, 75, 76, 141, 143, 146] Preconditioning for QA Analytical solver [72] Preconditioning for VQAs (warm-start) Solver for relaxed CO problem [42, 120, 137] approach…”
BackgroundMethodInfluentialLayer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
Liu, X., Angone, A., Shaydulin, R., Safro, I., Alexeev, Y., & Cincio, L. (2022) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3140190 · Cited by 78 · cited 3×
“In this regard, the Layer-VQE [89] iteratively builds the quantum circuit.”
Optimizing quantum heuristics with meta-learning
Wilson, M., Stromswold, S., Wudarski, F., Hadfield, S., Tubman, N. M., & Rieffel, E. (2019) · arXiv · doi:10.48550/arxiv.1908.03185 · Cited by 77
Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity
Irie, H., Wongpaisarnsin, G., Terabe, M., Miki, A., & Taguchi, S. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-14082-3_13 · Cited by 74
Large-Scale Quantum Approximate Optimization via Divide-and-Conquer
Li, J., Alam, M., & Ghosh, S. (2022) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2022.3212196 · Cited by 73 · 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].”
MethodItem Listing Optimization for E-Commerce Websites Based on Diversity
Nishimura, N., Tanahashi, K., Suganuma, K., Miyama, M. J., & Ohzeki, M. (2019) · Frontiers in Computer Science · doi:10.3389/fcomp.2019.00002 · Cited by 73 · cited 2×
“Further problem-specific decomposition methods have been proposed for the item listing problem [102] and the Max-Clique problem [110].”
MethodFinding Maximum Cliques on the D-Wave Quantum Annealer
Chapuis, G., Djidjev, H., Hahn, G., & Rizk, G. (2019) · Journal of Signal Processing Systems · doi:10.1007/s11265-018-1357-8 · Cited by 70 · 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].”
BackgroundFeedback-Based Quantum Optimization
Magann, A. B., Rudinger, K. M., Grace, M. D., & Sarovar, M. (2022) · Physical Review Letters · doi:10.1103/physrevlett.129.250502 · Cited by 67 · cited 3×
“Within the gate-model domain, a further distinction can be made between VQAs, Grover-based approaches [52, 118], and other gate-based approaches that have been mentioned above, e.g., References [15, 16, 24, 94].”
BackgroundMethodOptimal control of traffic signals using quantum annealing
Hussain, H., Javaid, M. B., Khan, F. S., Dalal, A., & Khalique, A. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02815-1 · Cited by 66 · cited 1×
“Hybrid quantum-classical solvers have been applied to the garden optimization problem [25] and traffic optimization [67].”
MethodBridging Classical and Quantum with SDP initialized warm-starts for QAOA
Tate, R., Farhadi, M., Herold, C., Mohler, G., & Gupta, S. (2020) · arXiv · doi:10.48550/arxiv.2010.14021 · Cited by 61 · cited 3×
“Concerning the former, a preconditioning of the quantum algorithm for VQAs is provided by warm-starting with classical solvers for relaxed CO problems [42], e.g., an SDP solver [137].”
BackgroundMethodA Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing ProblemPreprint
Harikrishnakumar, R., Nannapaneni, S., Nguyen, N. H., Steck, J. E., & Behrman, E. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.12478 · Cited by 61 · cited 1×
“…the online advertisement allocation problem [135], traffic signal optimization on a square lattice [70], the Multi-depot Capacitated Vehicle Routing problem in its static and dynamic version [59], and the Vehicle Routing Problem including the concepts of time, capacity, and state are provided [73].”
BackgroundMultiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
Gambella, C., & Simonetto, A. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3033139 · Cited by 60 · cited 4×
“Similarly, Alternating Direction Method of Multipliers (ADMM) heuristics [169] have been utilized for such extensions to MBO problems, where the constraints are treated classically [50].”
BackgroundMethodInfluentialEmpirical performance bounds for quantum approximate optimization
Lotshaw, P. C., Humble, T. S., Herrman, R., Ostrowski, J., & Siopsis, G. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03342-3 · Cited by 59 · cited 1×
“Continuing with empirical studies on gate-based quantum CO approaches, a large-scale evaluation on QAOA [92, 121] validated the theoretical properties [4, 21, 43] and yielded further empirical performance bounds.”
BackgroundMultilevel Combinatorial Optimization across Quantum Architectures
Ushijima-Mwesigwa, H., Shaydulin, R., Negre, C. F. A., Mniszewski, S. M., Alexeev, Y., & Safro, I. (2021) · ACM Transactions on Quantum Computing · doi:10.1145/3425607 · Cited by 57 · cited 2×
“…Analytical solver [99] Knowledge base [123, 154] Machine learning [6, 51, 75, 76, 141, 143, 146] Preconditioning for QA Analytical solver [72] Preconditioning for VQAs (warm-start) Solver for relaxed CO problem [42, 120, 137] approach (e.g., Reference [182]) to tackle even larger problems [139].”
BackgroundMethodReinforcement Quantum Annealing: A Hybrid Quantum Learning Automata
Ayanzadeh, R., Halem, M., & Finin, T. (2020) · Scientific Reports · doi:10.1038/s41598-020-64078-1 · Cited by 57 · cited 5×
“Furthermore, penalty terms in the cost Hamiltonian for constraint incorporation have been defined using reinforcement learning [9].”
BackgroundMethodInfluentialQuantum Approximate Optimization With Parallelizable Gates
Lechner, W. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3034798 · Cited by 57 · cited 4×
“Several other approaches have been identified where the ansatz adaptations happen as a secondary effect, e.g., References [36, 48, 82, 131, 153].”
BackgroundMethodInfluentialNetwork Community Detection on Small Quantum Computers
Shaydulin, R., Ushijima‐Mwesigwa, H., Safro, I., Mniszewski, S., & Alexeev, Y. (2019) · Advanced Quantum Technologies · doi:10.1002/qute.201900029 · Cited by 56 · cited 2×
“A problem-specific example is the Quantum Local Search (QLS) algorithm, which is designed for the community detection problem [124].”
MethodAgile Earth Observation Satellite Scheduling With a Quantum Annealer
Stollenwerk, T., Michaud, V., Lobe, E., Picard, M., Basermann, A., & Botter, T. (2021) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2021.3088490 · Cited by 56
Efficient Encoding of the Weighted MAX $$k$$-CUT on a Quantum Computer Using QAOA
Fuchs, F. G., Kolden, H. Ø., Aase, N. H., & Sartor, G. (2021) · SN Computer Science · doi:10.1007/s42979-020-00437-z · Cited by 56 · cited 4×
“Continuing with the encoding of discrete problems, the encoding of constraints in the cost Hamiltonian rather than restricting the subspace via the mixing Hamiltonian has also been considered [48].”
BackgroundMethodInfluentialImplementation of a Hybrid Classical-Quantum Annealing Algorithm for Logistic Network Design
Ding, Y., Chen, X., Lamata, L., Solano, E., & Sanz, M. (2021) · SN Computer Science · doi:10.1007/s42979-021-00466-2 · Cited by 55 · cited 2×
“These approaches include the combination of QA with Simulated Annealing (SA) [38] and with a molecular dynamics algorithm [72], which serves as a preconditioner for QA.”
MethodEvaluating Quantum Approximate Optimization Algorithm: A Case Study
Shaydulin, R., & Alexeev, Y. (2019) · 2019 Tenth International Green and Sustainable Computing Conference (IGSC) · doi:10.1109/igsc48788.2019.8957201 · Cited by 55 · cited 4×
“It has been theoretically proven [4, 43, 44] and empirically validated [121].”
BackgroundMethodInfluentialIterative quantum-assisted eigensolver
Bharti, K., & Haug, T. (2021) · Physical Review A · doi:10.1103/physreva.104.l050401 · Cited by 54 · cited 3×
“Within the gate-model domain, a further distinction can be made between VQAs, Grover-based approaches [52, 118], and other gate-based approaches that have been mentioned above, e.g., References [15, 16, 24, 94].”
BackgroundMethodEvaluation of QAOA based on the approximation ratio of individual samples
Larkin, J. M., Jonsson, M., Justice, D., & Guerreschi, G. G. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/ac6973 · Cited by 54 · cited 2×
“Other investigations highlight the strong dependence of QAOA on the problem instance, the number of parameters, and their initialization [81, 142].”
BackgroundMethodA 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 · cited 1×
“Investigations on the impact of different classical optimizers for parameter optimization in general advocate for gradient-free global optimizers when dealing with real quantum hardware [37, 47, 100, 121].”
BackgroundQuantum Algorithms for Mixed Binary Optimization Applied to Transaction Settlement
Braine, L., Egger, D. J., Glick, J., & Woerner, S. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3063635 · Cited by 51 · cited 2×
“Additionally, the class of treatable problems of VQAs has been extended to Mixed Binary Optimization (MBO) problems using appropriate problem formulations [20].”
BackgroundA quantum walk-assisted approximate algorithm for bounded NP optimisation problems
Marsh, S., & Wang, J. B. (2019) · Quantum Information Processing · doi:10.1007/s11128-019-2171-3 · Cited by 50 · 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],…”
BackgroundMethodQuantum Shuttle: traffic navigation with Quantum computing
Yarkoni, S., Neukart, F., Tagle, E. M. G., Magiera, N., Mehta, B., Hire, K., Narkhede, S., & Hofmann, M. (2020) · Proceedings of the 1st ACM SIGSOFT International Workshop on Architectures and Paradigms for Engineering Quantum Software · doi:10.1145/3412451.3428500 · Cited by 50 · cited 1×
“QA has also been utilized for traffic optimization within the Web Sum-mit Conference in Lisbon, where it has been shown how QA can be applied within a classical application to enable real-world utility [147].”
MethodQuantum variational optimization: The role of entanglement and problem hardness
Díez-Valle, P., Porras, D., & García-Ripoll, J. J. (2021) · Physical Review A · doi:10.1103/physreva.104.062426 · Cited by 47 · cited 3×
“Investigations on the impact of different classical optimizers for parameter optimization in general advocate for gradient-free global optimizers when dealing with real quantum hardware [37, 47, 100, 121].”
BackgroundMethodQuantum Annealing-Based Software Components: An Experimental Case Study with SAT Solving
Krüger, T., & Mauerer, W. (2020) · doi:10.1145/3387940.3391472 · Cited by 47 · cited 1×
“…[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 two alternative quantum-ready…”
BackgroundDalyac, C., Henriet, L., Jeandel, E., Lechner, W., Perdrix, S., Porcheron, M., & Veshchezerova, M. (2021) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-021-00100-3 · Cited by 46 · cited 1×
“Dalyac et al. [35] utilized tailored implementations of QAOA to solve two problems arising in the field of smart charging electric vehicles, which can be mapped to Max-k-Cut and Maximum Independent Set problems, respectively [35].”
BackgroundAccelerating Quantum Approximate Optimization Algorithm using Machine Learning
Alam, M., Ash-Saki, A., & Ghosh, S. (2020) · 2020 Design, Automation & Test in Europe Conference & Exhibition (DATE) · doi:10.23919/date48585.2020.9116348 · Cited by 46 · cited 3×
“Similarly, patterns in the parameters have been explored during advancement to higher depths of the circuit for parameter initialization [6, 154], e.g., via different regression techniques [6].”
BackgroundMethodOn Hybrid Quantum and Classical Computing Algorithms for Mixed-Integer ProgrammingPreprint
Chang, C.-Y., Jones, E. D., Yao, Y., Graf, P., & Jain, R. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.07852 · Cited by 45
Full-Stack, Real-System Quantum Computer Studies: Architectural Comparisons and Design InsightsPreprint
Murali, P., Linke, N. M., Martonosi, M., Javadi-Abhari, A., Nguyen, N. H., & Alderete, C. H. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.11349 · Cited by 45
Quantum Approximation for Wireless Scheduling
Choi, J., Oh, S., & Kim, J. (2020) · Applied Sciences · doi:10.3390/app10207116 · Cited by 44 · cited 1×
“Standard QAOA has been applied to: the cluster head selection problem [28], the wireless scheduling problem [29], the vehicle routing problem [14], multi-coloring graph problems [104], the graph isomorphism problem [66], and a satellite scheduling problem [128].”
MethodImpact of graph structures for QAOA on MaxCut
Herrman, R., Treffert, L., Ostrowski, J., Lotshaw, P. C., Humble, T. S., & Siopsis, G. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03232-8 · Cited by 44
Benchmark Test of Black-box Optimization Using D-Wave Quantum Annealer
Koshikawa, A. S., Ohzeki, M., Kadowaki, T., & Tanaka, K. (2021) · Journal of the Physical Society of Japan · doi:10.7566/jpsj.90.064001 · Cited by 43 · cited 1×
“Finally, Koshikawa et al. [79] utilized and bench-marked QA within black-box optimization.”
BackgroundToward Prediction of Financial Crashes with a D-Wave Quantum Annealer
Ding, Y., Gonzalez-Conde, J., Lamata, L., Martín‐Guerrero, J. D., Lizaso, E., Mugel, S., Chen, X., Orús, R., Solano, E., & Sanz, M. (2023) · Entropy · doi:10.3390/e25020323 · Cited by 42
Approaches to Constrained Quantum Approximate Optimization
Saleem, Z. H., Tomesh, T., Tariq, B., & Suchara, M. (2023) · SN Computer Science · doi:10.1007/s42979-022-01638-4 · Cited by 41 · cited 5×
“The warm-starting procedure has also been applied for initializing a dynamic version of the Quantum Alternating Operator Ansatz [120].”
BackgroundMethodInfluentialStreif, M., Yarkoni, S., Skolik, A., Neukart, F., & Leib, M. (2021) · Physical Review A · doi:10.1103/physreva.104.012403 · Cited by 41 · cited 1×
“An adaptation to QAOA, which does not require exhaustive access to the quantum processing unit [131], has been used to solve the binary paint shop problem [132].”
Method(2021) · doi:10.1109/cec45853.2021.9504923 · Cited by 40
Exploiting Symmetry Reduces the Cost of Training QAOA
Shaydulin, R., & Wild, S. M. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3066275 · Cited by 39 · cited 3×
“…[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] Hamiltonians [62, 111, 136], [136] Space [136] Time [27], [62, 88]…”
BackgroundMethodAlgorithm engineering for a quantum annealing platform
King, A. D., & McGeoch, C. C. (2014) · arXiv · doi:10.48550/arxiv.1410.2628 · Cited by 39 · cited 1×
“The impact of various quantum controls, such as annealing time and number of spin reversals [194], on the success probability and chain breaks has been studied by Grant et al. [55], yielding a saturation effect for both controls.”
BackgroundQuantum adiabatic algorithm design using reinforcement learning
Lin, J., Lai, Z. Y., & Li, X. (2020) · Physical Review A · doi:10.1103/physreva.101.052327 · Cited by 39 · cited 9×
“…[51], [75], [76, 99], [141], [143], [146] Measurement [122], [125] Grover-search [52], [118] Other gate-based approaches [15], [16], [24], [94] Hamiltonians [62, 111, 136], [136] Space [136] Time [27], [62, 88] Other approaches [19, 63] sensitivity of QAOA to initial parameter settings [137].”
BackgroundMethodInfluentialModel Predictive Control for Finite Input Systems using the D-Wave Quantum Annealer
Inoue, D., & Yoshida, H. (2020) · Scientific Reports · doi:10.1038/s41598-020-58081-9 · Cited by 39
Two-parameter counter-diabatic driving in quantum annealing
Prielinger, L., Hartmann, A., Yamashiro, Y., Nishimura, K., Lechner, W., & Nishimori, H. (2021) · Physical Review Research · doi:10.1103/physrevresearch.3.013227 · Cited by 39 · cited 3×
“Adaptations to the standard QA mentioned in Section 2 comprise the utilization of time-dependent Hamiltonians [136], non-stoquastic Hamiltonians [62], transverse couplers [136], and counter-diabatic driving terms [111].”
MethodThe Useful Quantum Computing Techniques for Artificial Intelligence Engineers
Choi, J., Oh, S., & Kim, J. (2020) · 2020 International Conference on Information Networking (ICOIN) · doi:10.1109/icoin48656.2020.9016555 · Cited by 39 · cited 1×
“The most prominent problem formulations for CO on quantum computers are the Ising-model [189] and the equivalent Quadratic Unconstrained Binary Optimization (QUBO) model [53, 150, 173].”
MethodHamilton, C. S., Kruse, R., Sansoni, L., Barkhofen, S., Silberhorn, C., & Jex, I. (2017) · Conference on Lasers and Electro-Optics · doi:10.1364/cleo_qels.2017.ftu1f.2 · Cited by 39
Solving Large Maximum Clique Problems on a Quantum Annealer
Pelofske, E., Hahn, G., & Djidjev, H. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-14082-3_11 · Cited by 38 · cited 2×
“Further problem-specific decomposition methods have been proposed for the item listing problem [102] and the Max-Clique problem [110].”
MethodA QUBO Formulation of Minimum Multicut Problem Instances in Trees for D-Wave Quantum Annealers
Cruz-Santos, W., Venegas-Andraca, S. E., & Lanzagorta, M. O. (2019) · Scientific Reports · doi:10.1038/s41598-019-53585-5 · Cited by 37 · cited 1×
“…the graph coloring problem [126], the k-community detection problem [101], the Maximum Independent Set problem [148], the Minimum Multicut problem [34], the most frequent itemset problem [103], consensus clustering [32], the online advertisement allocation problem [135], traffic signal…”
BackgroundYarkoni, S., Plaat, A., & Bäck, T. (2018) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2018.8477865 · Cited by 37
Garden optimization problems for benchmarking quantum annealers
Calaza, C. D. G., Willsch, D., & Michielsen, K. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03226-6 · Cited by 36 · cited 1×
“Hybrid quantum-classical solvers have been applied to the garden optimization problem [25] and traffic optimization [67].”
MethodLower bounds on circuit depth of the quantum approximate optimization algorithm
Herrman, R., Ostrowski, J., Humble, T. S., & Siopsis, G. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03001-7 · Cited by 35 · cited 1×
“However, a lower bound for the required circuit depth has been theoretically derived and found to be the chromatic index of the problem graph plus one [64].”
BackgroundLodewijks, B. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.08043 · Cited by 35 · cited 1×
“Some of these known direct mappings stated by Lucas [199] have been improved and novel ones have been introduced by Lodewijks [91], including bin packing and partitioning problems.”
BackgroundComparison of QAOA with Quantum and Simulated Annealing
Streif, M., & Leib, M. (2019) · arXiv · doi:10.48550/arxiv.1901.01903 · Cited by 35 · cited 3×
“Comparison to QAOA QAOA is preferable when the energy landscape shows high and broad walls [130].”
BackgroundInfluentialAutomated quantum programming via reinforcement learning for combinatorial optimizationPreprint
McKiernan, K. A., Davis, E., Alam, M. S., & Rigetti, C. T. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.08054 · Cited by 33 · cited 7×
“…Bender’s decompostition [26], C-QUBO-LS / U-QUBO-LS [90], Problem-class specific decomposition [2] Problem-specific: QLS [124], Multilevel approach [139], Adapted Louvain algorithm [74] Quantum Alternating Operator Ansatz [114], and for program generation and architecture search [88, 97, 151, 152].”
BackgroundMethodInfluentialSolving Multi-Coloring Combinatorial Optimization Problems Using Hybrid Quantum AlgorithmsPreprint
Oh, Y.-H., Mohammadbagherpoor, H., Dreher, P., Singh, A., Yu, X., & Rindos, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.00595 · Cited by 33 · cited 2×
“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].”
MethodAlam, M., Ash-Saki, A., & Ghosh, S. (2019) · arXiv · doi:10.48550/arxiv.1907.09631 · Cited by 33 · cited 3×
“Thus, as an example, the optimal depth as a tradeoff between ansatz accuracy and error rates has been found to be p=1 and p=3, respectively [5, 60].”
BackgroundTowards Real Time Multi-robot Routing using Quantum Computing Technologies
Clark, J., West, T., Zammit, J. P., Guo, X., Mason, L., & Russell, D. (2019) · International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia) · doi:10.1145/3293320.3293333 · Cited by 33
On Quadratization of Pseudo-Boolean Functions
Boros, E., & Gruber, A. (2014) · arXiv · doi:10.48550/arxiv.1404.6538 · Cited by 32 · cited 1×
“The potentially large overhead in the number of variables lead to the development of several methods for degree reduction (e.g., References [160, 167, 168, 180, 188]), which are explained and compared in References [53, 62, 135, 218].”
MethodHybrid quantum annealing via molecular dynamics
Irie, H., Liang, H., Doi, T., Gongyo, S., & Hatsuda, T. (2021) · Scientific Reports · doi:10.1038/s41598-021-87676-z · Cited by 32 · cited 3×
“These approaches include the combination of QA with Simulated Annealing (SA) [38] and with a molecular dynamics algorithm [72], which serves as a preconditioner for QA.”
BackgroundMethodMarquezino, F. D. L., Portugal, R., & Lavor, C. (2019) · SpringerBriefs in computer science · doi:10.1007/978-3-030-19066-8 · Cited by 31
Schedule path optimization for adiabatic quantum computing and optimization
Zeng, L., Zhang, J., & Sarovar, M. (2016) · Journal of Physics A: Mathematical and Theoretical · doi:10.1088/1751-8113/49/16/165305 · Cited by 31
Optimizing the optimizer: decomposition techniques for quantum annealing
Bass, G., Henderson, M., Heath, J., & Dulny, J. S. (2021) · Quantum Machine Intelligence · doi:10.1007/s42484-021-00039-9 · Cited by 30 · 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].”
BackgroundMapping graph coloring to quantum annealing
SILVA, C. V. D., Aguiar, A., Lima, P. M. V., & Dutra, I. (2020) · Quantum Machine Intelligence · doi:10.1007/s42484-020-00028-4 · Cited by 30 · cited 1×
“In this sense, QUBO formulations for the graph coloring problem [126], the k-community detection problem [101], the Maximum Independent Set problem [148], the Minimum Multicut problem [34], the most frequent itemset problem [103], consensus clustering [32], the online advertisement allocation…”
BackgroundToward Quantum Gate-Model Heuristics for Real-World Planning Problems
Stollenwerk, T., Hadfield, S., & Wang, Z. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3030609 · Cited by 29 · cited 3×
“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].”
BackgroundMethodCombinatorial Optimization on Gate Model Quantum Computers: A Survey
Zahedinejad, E., & Zaribafiyan, A. (2017) · arXiv · doi:10.48550/arxiv.1708.05294 · Cited by 29 · cited 5×
“Neglecting the irrelevant constant, they are thus different representations of the same underlying NP-complete problem [221].”
BackgroundMethodInfluentialReview on Quantum Walk Algorithm
Zhou, W. (2021) · Journal of Physics Conference Series · doi:10.1088/1742-6596/1748/3/032022 · Cited by 28 · cited 1×
“Quantum Monte Carlo [221], quantum walk [225], and quantum machine learning [224] denote topics where quantum versions of classical approaches are developed that may be applied, among others, to CO problems, but are not associated with traditional CO approaches.”
BackgroundMax-independent set and the quantum alternating operator ansatz
Saleem, Z. H. (2020) · International Journal of Quantum Information · doi:10.1142/s0219749920500112 · Cited by 28 · cited 1×
“The Maximum Independent Set problem has been tackled with the Quantum Alternating Operator Ansatz [119].”
MethodQuantum Scheduling for Millimeter-Wave Observation Satellite Constellation
Kim, J., Kwak, Y., Jung, S., & Kim, J. (2021) · IEEE VTS Asia Pacific Wireless Communications Symposium (APWCS) · doi:10.1109/apwcs50173.2021.9548770 · Cited by 28
Hard combinatorial problems and minor embeddings on lattice graphs
Lucas, A. (2019) · Quantum Information Processing · doi:10.1007/s11128-019-2323-5 · Cited by 26 · cited 1×
“However, for most efficient quantum resource utilization, the type of utilized hardware should be already considered in the step of problem formulation as suggested by Lucas [93].”
Quadratization of symmetric pseudo-Boolean functions
Anthony, M., Boros, E., Crama, Y., & Gruber, A. (2016) · Discrete Applied Mathematics · doi:10.1016/j.dam.2016.01.001 · Cited by 26
Exploring network structure, dynamics, and function using NetworkX
Hagberg, A. A. (2024) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · Cited by 25
Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm DesignPreprint
Huang, C., Szegedy, M., Zhang, F., Gao, X., Chen, J., & Shi, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.02559 · Cited by 25 · cited 1×
“Standard QAOA has been applied to: the cluster head selection problem [28], the wireless scheduling problem [29], the vehicle routing problem [14], multi-coloring graph problems [104], the graph isomorphism problem [66], and a satellite scheduling problem [128].”
MethodZhu, L., Tang, H. L., Barron, G. S., et al. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.10258 · Cited by 25
Evolving objective function for improved variational quantum optimization
Kolotouros, I., & Wallden, P. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.023225 · Cited by 24 · cited 5×
“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.”
MethodInfluentialReinforcement-Learning-Based Variational Quantum Circuits Optimization for Combinatorial Problems
Khairy, S., Shaydulin, R., Cincio, L., Alexeev, Y., & Balaprakash, P. (2019) · arXiv · doi:10.48550/arxiv.1911.04574 · Cited by 21
Assessing Solution Quality of 3SAT on a Quantum Annealing Platform
Gabor, T., Zielinski, S., Feld, S., Roch, C., Seidel, C., Neukart, F., Galter, I., Mauerer, W., & Linnhoff-Popien, C. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-14082-3_3 · Cited by 21 · cited 2×
“In contrast to classical complete algorithms, increasing problem hardness causes a loss of precision instead of detrimental solution times [49].”
BackgroundDomino, K., Koniorczyk, M., Krawiec, K., Jałowiecki, K., & Gardas, B. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.08227 · Cited by 21 · cited 1×
“…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 [106].”
BackgroundApproximating the quantum approximate optimization algorithm with digital-analog interactions
Headley, D., Müller, T., Martin, A., Solano, E., Sanz, M., & Wilhelm, F. K. (2020) · arXiv · doi:10.48550/arxiv.2002.12215 · Cited by 21
Leveraging special-purpose hardware for local search heuristics
Liu, X., Ushijima‐Mwesigwa, H., Mandal, A., Upadhyay, S., Safro, I., & Roy, A. (2022) · Computational Optimization and Applications · doi:10.1007/s10589-022-00354-2 · Cited by 20 · cited 3×
“…[102, 107, 110] Any QUBO-solver Problem-agnostic: ADMM [50, 61, 149], Branch & Price [133], Bender’s decompostition [26], C-QUBO-LS / U-QUBO-LS [90], Problem-class specific decomposition [2] Problem-specific: QLS [124], Multilevel approach [139], Adapted Louvain algorithm [74] Quantum…”
BackgroundMethodInfluentialOsaba, E., Villar-Rodriguez, E., Oregi, I., & Moreno-Fernandez-de-Leceta, A. (2021) · Proceedings of the Genetic and Evolutionary Computation Conference Companion · doi:10.1145/3449726.3463123 · Cited by 20 · cited 1×
“Regarding problem decomposition, an alternative to qbsolv is represented by the quantum tabu algorithm [109] and its extended version [108], which perform similar to qbsolv in terms of solu-tion quality but require less QA resources.”
MethodEnergy-Efficient Cluster Head Selection via Quantum Approximate Optimization
Choi, J., Oh, S., & Kim, J. (2020) · Electronics · doi:10.3390/electronics9101669 · Cited by 20 · cited 1×
“Standard QAOA has been applied to: the cluster head selection problem [28], the wireless scheduling problem [29], the vehicle routing problem [14], multi-coloring graph problems [104], the graph isomorphism problem [66], and a satellite scheduling problem [128].”
MethodCharacterization of QUBO reformulations for the maximum k-colorable subgraph problem
Quintero, R. A., Bernal, D. E., Terlaky, T., & Zuluaga, L. F. (2022) · Quantum Information Processing · doi:10.1007/s11128-022-03421-z · Cited by 20 · 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…”
BackgroundQED driven QAOA for network-flow optimization
Zhang, Y., Zhang, R., & Potter, A. C. (2021) · Quantum · doi:10.22331/q-2021-07-27-510 · Cited by 19 · cited 3×
“Several other approaches have been identified where the ansatz adaptations happen as a secondary effect, e.g., References [36, 48, 82, 131, 153].”
BackgroundMethodTomesh, T., Allen, N., Dilley, D., & Saleem, Z. H. (2024) · Quantum · doi:10.22331/q-2024-10-04-1493 · Cited by 19 · cited 1×
“Thus, these operations must be decomposed into operations natively supported by the target NISQ devices before execution [217].”
MethodBharti, K. (2020) · arXiv · doi:10.48550/arxiv.2009.11001 · Cited by 19 · cited 3×
“Within the gate-model domain, a further distinction can be made between VQAs, Grover-based approaches [52, 118], and other gate-based approaches that have been mentioned above, e.g., References [15, 16, 24, 94].”
BackgroundMethodIsing-Based Consensus Clustering on Specialized Hardware
Cohen, E., Mandal, A., Ushijima‐Mwesigwa, H., & Roy, A. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-44584-3_9 · Cited by 19 · cited 1×
“…[101], the Maximum Independent Set problem [148], the Minimum Multicut problem [34], the most frequent itemset problem [103], consensus clustering [32], the online advertisement allocation problem [135], traffic signal optimization on a square lattice [70], the Multi-depot Capacitated Vehicle…”
BackgroundGarden optimization problems for benchmarking quantum annealers
Gonzalez Calaza, C. D., Willsch, D., & Michielsen, K. F. L. (2021) · RWTH Publications (RWTH Aachen) · doi:10.18154/rwth-2021-09173 · Cited by 18
Glover, F., Kochenberger, G. A., Ma, M., et al. (2020) · 4OR · doi:10.1007/s10288-020-00464-9 · Cited by 16
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.