Unbalanced penalization: a new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
Open accessThe DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
Abstract
Solving combinatorial optimization problems of the kind that can be codified by quadratic unconstrained binary optimization (QUBO) is a promising application of quantum computation. Some problems of this class suitable for practical applications such as the traveling salesman problem (TSP), the bin packing problem (BPP), or the knapsack problem (KP) have inequality constraints that require a particular cost function encoding. The common approach is the use of slack variables to represent the inequality constraints in the cost function. However, the use of slack variables considerably increases the number of qubits and operations required to solve these problems using quantum devices. In this work, we present an alternative method that does not require extra slack variables and consists of using an unbalanced penalization function to represent the inequality constraints in the QUBO. This function is characterized by larger penalization when the inequality constraint is not achieved than when it is. We evaluate our approach on the TSP, BPP, and KP, successfully encoding the optimal solution of the original optimization problem near the ground state cost Hamiltonian. Additionally, we employ D -Wave Advantage and D -Wave hybrid solvers to solve the BPP, surpassing the performance of the slack variables approach by achieving solutions for up to 29 items, whereas the slack variables approach only handles up to 11 items. This new approach can be used to solve combinatorial problems with inequality constraints with a reduced number of resources compared to the slack variables approach using quantum annealing or variational quantum algorithms.
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
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 cited source says what the claim attributes to it.
In the citing paper
“there is no guarantee that the optimal solution of the original problem is encoded in the ground state of the Hamiltonian (see also the discussion in ref. 39).”
From Toward a linear-ramp QAOA protocol: evidence of a scaling advantage in solving some combinatorial optimization problems (2025) · cites this paper as [39]
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
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 1×
“However, we are currently in a noisy intermediate-scale quantum (NISQ) stage and QPUs are restricted in terms of qubits number and circuit depth [6].”
BackgroundAlgorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713 · cited 1×
“de algorithms such as Shor’s algorithm [7, 8] remain unpractical to test on real quantum hardware.”
MethodPolynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Yang (2021) · doi:10.1038/s41598-020-79139-8 · Cited by 5,035
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 4×
“The method is suitable for VQA on gate-based quantum computers and QA on quantum annealers, which both require expressing the combinatorial optimization problems in terms of QUBOs.”
BackgroundInfluentialIsing formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512 · cited 2×
“In this formulation, the problem is given by subject to the set of constraints, n i =1 ,i (cid:54) = j n j =1 ,j (cid:54) = i i ∈ Q j (cid:54) = i,j ∈ Q where n is the number of cities (nodes), c ij is the distance between the cities i and j , x ij is a binary variable that represents if the path…”
BackgroundQuantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339 · cited 1×
“IV.”
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 · cited 1×
“IV.”
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789 · cited 1×
“Of the aforementioned VQA algorithms, the most studied for combinatorial optimization problems is the Quantum Approximate Optimization algorithm (QAOA) [16].”
BackgroundQuantum computing for finance: Overview and prospects
Orús, R., Mugel, S., & Lizaso, E. (2019) · Reviews in Physics · doi:10.1016/j.revip.2019.100028 · Cited by 668 · cited 1×
“Multiple approaches for solving combinatorial optimization problems using QAOA or QA can be found in the literature, for example, in logistics [22], finance [5, 23– 25], energy [26], communications [27], automotive industry [28], traffic signaling [29], among others.”
Method
Research works printed but not linked: 1
- Khairy, 2020, vol 34, p 2367
Cited by
Montañez-Barrera, J. A., & Michielsen, K. (2025) · npj Quantum Information · doi:10.1038/s41534-025-01082-1 · Cited by 34
“39).”
Self-citationVariational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture
Mastroianni, C., Plastina, F., Settino, J., & Vinci, A. (2024) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2024.3398410 · Cited by 32
“Moreover, because P best and P feas decrease with the size of the problem, coherently with the general idea proposed in [59], we define the Coefficients of Performance for the success and the feasible solution probabilities, respectively C best and C feas .”
BackgroundTransfer learning of optimal QAOA parameters in combinatorial optimization
Montañez-Barrera, J. A., Willsch, D., & Michielsen, K. (2025) · Quantum Information Processing · doi:10.1007/s11128-025-04743-4 · Cited by 19
“In Appendix A, we explain in detail the problems and the parameters used in this work.”
Self-citationQAL-BP: an augmented Lagrangian quantum approach for bin packing
Cellini, L., Macaluso, A., & Lombardi, M. (2024) · Scientific Reports · doi:10.1038/s41598-023-50540-3 · Cited by 28
Montañez-Barrera, J. A., van den Heuvel, P., Willsch, D., & Michielsen, K. F. L. (2023) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00067 · Cited by 24
“The unbalanced penalization [25] is a heuristic method for including inequality constraints as penalization terms in the QUBO formulation of combinatorial optimization problems.”
MethodSelf-citation
Metadata
- Authors
- Montañez-Barrera, J. A., Willsch, D., Maldonado-Romo, A., & Michielsen, K.
- Affiliations
- Forschungszentrum Jülich (DE)
- Instituto Politécnico Nacional (MX)
- Corresponding author
- Montañez-Barrera, J A
- Venue
- Quantum Science and Technology
- Publisher
- IOP Publishing
- Published
- 2024-04-01
- Volume
- 9
- Issue
- 2
- Pages
- 025022
- ISSN
- 2058-9565 (ISSN-L)
- OpenAlex
- W4392975768
- Cited by
- 57
- References
- 35
- Citations by year
- 2026: 15 · 2025: 27 · 2024: 10
- FWCI
- 7.62
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- cc-by
- creativecommons.org/licenses/by/4.0 (vor, 1 d)
- iopscience.iop.org/info/page/text-and-data-mining (tdm, 1 d)
- Locations
- Quantum Science and Technology (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Funders
- Federal Ministry of Education and Research (13N16149)
- Gauss Centre for Supercomputing
- German Federal Ministry of Culture and Science of the State of North Rhine-Westphalia
- 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
- inequality constraints, QUBO encoding, combinatorial optimization, slack variables, traveling salesman problem, bin packing, knapsack problem, quantum annealing, variational quantum algorithms, D-Wave Advantage
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: Unbalanced penalization: a new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms. https://app.cochat.ai/papers/10.1088/2058-9565/ad35e4
- The paper
- Montañez-Barrera, J. A., Willsch, D., Maldonado-Romo, A., & Michielsen, K. (2024). Unbalanced penalization: a new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms. Quantum Science and Technology. https://doi.org/10.1088/2058-9565/ad35e4
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.