On good encodings for quantum annealer and digital optimization solvers
Open accessThe DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
Abstract
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Figures



Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“HQA (Leap Hybrid solver), developed by D-Wave systems, also decomposes large QUBO into smaller subproblems wellsuited for QA ' s QPU, and then aggregates the results 27,44 .”
From Quantum annealing for combinatorial optimization: a benchmarking study (2025) · cites this paper as [44]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Quantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056
Quantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
On the computational complexity of Ising spin glass models
Barahona, F. (1982) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/15/10/028 · Cited by 1,306
Bertsimas, D., & Tsitsiklis, J. (1993) · Statistical Science · doi:10.1214/ss/1177011077 · Cited by 1,284
Colloquium : Quantum annealing and analog quantum computation
Das, A., & Chakrabarti, B. K. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1061 · Cited by 700
The unconstrained binary quadratic programming problem: a survey
Kochenberger, G., Hao, J.-K., Glover, F., Lewis, M., Lü, Z., Wang, H., & Wang, Y. (2014) · Journal of Combinatorial Optimization · doi:10.1007/s10878-014-9734-0 · Cited by 473
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
Research works printed but not linked: 1
- Apolloni, B., Cesa-Bianchi, N. & De Falco, D. A numerical implementation of “quantum annealing”. In Stochastic Processes, Physics and Geometry: Proceedings of the Ascona-Locarno Conference, 97–111 (1990).
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
“We use D-Wave Systems ’ quantum annealer (Advantage 4.1) to solve the problems using QA, and we set the number of reads for QA to 1000 with a total annealing time of 20 μ s.”
InfluentialA Review on Quantum Machine Learning in Applied Systems and Engineering
Hong, Y.-Y., & Lopez, D. J. D. (2025) · IEEE Access · doi:10.1109/access.2025.3599147 · Cited by 32
Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem
Ohno, K., Shirai, T., & Togawa, N. (2024) · IEEE Access · doi:10.1109/access.2024.3425711 · Cited by 15
Benchmarking quantum annealing with maximum cardinality matching problems
Vert, D., Willsch, M., Yenilen, B., Sirdey, R., Louise, S., & Michielsen, K. F. L. (2024) · Frontiers in Computer Science · doi:10.3389/fcomp.2024.1286057 · Cited by 10
Li, J., Li, Z., Yao, L., Wang, K., Li, J., Lu, Y., & Hu, C. (2024) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2024.2358045 · Cited by 9
Metadata
- Authors
- Ceselli, A., & Premoli, M.
- Affiliations
- University of Milan (IT)
- Corresponding author
- Premoli, Marco
- Venue
- Scientific Reports
- Published
- 2023-04-06
- Volume
- 13
- Issue
- 1
- Pages
- 5628-5628
- ISSN
- 2045-2322 (ISSN-L)
- PMC
- PMC10079660
- OpenAlex
- W4362670141
- Cited by
- 10
- References
- 38
- Citations by year
- 2026: 2 · 2025: 3 · 2024: 5
- FWCI
- 0.94
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- cc-by
- creativecommons.org/licenses/by/4.0 (tdm)
- creativecommons.org/licenses/by/4.0 (vor)
- Locations
- Scientific Reports (publishedVersion, cc-by)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- Archivio Istituzionale della Ricerca (Universita Degli Studi Di Milano) (submittedVersion, other-oa)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- Funders
- Quantum Blockchain Technologies (CTE_INT21ACESE_01)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- quantum annealing, QUBO encoding, D-Wave Advantage, combinatorial optimization, Ising model, variable fixing, QUBO
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: On good encodings for quantum annealer and digital optimization solvers. https://app.cochat.ai/papers/10.1038/s41598-023-32232-0
- The paper
- Ceselli, A., & Premoli, M. (2023). On good encodings for quantum annealer and digital optimization solvers. Scientific Reports. https://doi.org/10.1038/s41598-023-32232-0
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.