CoChat

On good encodings for quantum annealer and digital optimization solvers

Open access
Ceselli, Alberto, Premoli, Marco · 2023 · Scientific Reports

The 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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1038/s41598-023-32232-0

Cites

39 of 39 references verified0 citation errors · 0 not checkable

Statistics

Figures

Figure 1 Schema of the QUBO-based heuristic framework to solve constrained combinatorial optimization problems.
Figure 1 Schema of the QUBO-based heuristic framework to solve constrained combinatorial optimization problems.CC BY · PubMed Central
Figure 2 Scatter plots of execution time (on y-axis) and the relative difference between the objective function value zs resulting from a solver s and the minimum among all solvers (on x-axis), i.e., |(zs-mins^(′)∈solverszs^(′))/(mins^(′)∈solverszs^(′))| . Values are averaged on all instances. randam + Gurobi D-Wave × SA Gurobi 1sec.
Figure 2 Scatter plots of execution time (on y-axis) and the relative difference between the objective function value zs resulting from a solver s and the minimum among all solvers (on x-axis), i.e., |(zs-mins^(′)∈solverszs^(′))/(mins^(′)∈solverszs^(′))| . Values are averaged on all instances. randam + Gurobi D-Wave × SA Gurobi 1sec.CC BY · PubMed Central
Figure 3 Comparison of Π(S) values of different sorting methods. From left to right: the sorting by increasing value of the potential gain measure (4), the sorting by increasing average variable values in SA solutions over repeated starts, and the sorting by increasing average values in D-wave samples. Orange bars represent median values, which in details are 0.039 for the potential gain measure (4), 0.089 for SA-binary, 0.068 for SA-unary, 0.106 for SA-linear, 0.311 for SA-qubo-card, 0.182 for D-Wave-binary, 0.044 for D-Wave-qubo-card and 0.087 for D-Wave-linear.
Figure 3 Comparison of Π(S) values of different sorting methods. From left to right: the sorting by increasing value of the potential gain measure (4), the sorting by increasing average variable values in SA solutions over repeated starts, and the sorting by increasing average values in D-wave samples. Orange bars represent median values, which in details are 0.039 for the potential gain measure (4), 0.089 for SA-binary, 0.068 for SA-unary, 0.106 for SA-linear, 0.311 for SA-qubo-card, 0.182 for D-Wave-binary, 0.044 for D-Wave-qubo-card and 0.087 for D-Wave-linear.CC BY · PubMed Central

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.

A few free checks a day · papers already verified open instantly · results are public

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?

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

Show all 39 references

Research works printed but not linked: 1

  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

See all 16

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)
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
Licence
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.