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.”
MethodQuantum annealing: A new method for minimizing multidimensional functions
Finnila, A. B., Gomez, M. A., Sebenik, C., Stenson, C., & Doll, J. D. (1994) · Chemical Physics Letters · doi:10.1016/0009-2614(94)00117-0 · Cited by 644
Quantum 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 2×
“Even if it is still unclear whether QAOA will give any advantage compared with classical algorithms, its simplicity makes it of great interest for analytical and practical purposes [4].”
BackgroundManigrasso, J., Chillón, I., Genna, V., Vidossich, P., Somarowthu, S., Pyle, A. M., De Vivo, M., & Marcia, M. (2022) · Nature Communications · doi:10.1038/s41467-021-27699-2 · Cited by 498
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 · cited 1×
“There are three main reasons for this; first, many combinatorial optimization problems can be encoded in Hamiltonians, the ground state being the optimal solution of the problem [1, 2]; second, they are commonly hard to solve and have practical applications [3]; and third, the quantum algorithms to solve these problem…”
BackgroundQiskit/qiskit-metapackage: Qiskit 0.43.0
Gambetta, J., Treinish, M., Kassebaum, P., Rodríguez, D. M., De La Puente González, S., Hu, S., Javadi-Abhari, A., Azaustre, C., Pistoia, M., Scholten, T. L., et al. (2019) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.2573505 · Cited by 386
Quantum 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 2×
“Still, such an approach increments the number of qubits and connections needed to solve these problems.”
BackgroundMassively parallel quantum computer simulator
De Raedt, K., Michielsen, K., De Raedt, H., Trieu, B., Arnold, G., Richter, M., Lippert, T., Watanabe, H., & Ito, N. (2007) · Computer Physics Communications · doi:10.1016/j.cpc.2006.08.007 · Cited by 213
Self-citationQuantum stochastic optimization
Apolloni, B., Carvalho, C., & de Falco, D. (1989) · Stochastic Processes and their Applications · doi:10.1016/0304-4149(89)90040-9 · Cited by 207 · cited 1×
“Besides, quantum annealers, using the quantum annealing (QA) principle [11–13], are another quantum technology used to solve combinatorial optimization problems [14–16].”
MethodQuantum versus classical annealing of Ising spin glasses
Heim, B., Rønnow, T. F., Isakov, S. V., & Troyer, M. (2015) · Science · doi:10.1126/science.aaa4170 · Cited by 193 · cited 1×
“In this respect, QA shows some advantages under certain conditions compared to classical annealing [17–19].”
BackgroundXY 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
Benchmarking 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 1×
“Even if it is still unclear whether QAOA will give any advantage compared with other algorithms [21], its simplicity makes it of great interest for analytical and practical purposes [4].”
BackgroundSelf-citationMugel, S., Kuchkovsky, C., Sánchez, E., Fernández-Lorenzo, S., Luis-Hita, J., Lizaso, E., & Orús, R. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.013006 · Cited by 124 · 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.”
MethodMassively parallel quantum computer simulator, eleven years later
De Raedt, H., Jin, F., Willsch, D., Willsch, M., Yoshioka, N., Ito, N., Yuan, S., & Michielsen, K. (2019) · Computer Physics Communications · doi:10.1016/j.cpc.2018.11.005 · Cited by 123 · cited 1×
“[32, 33] in its GPU-accelerated version [34].”
Self-citationLearning 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 1×
“For example, on gate-base QPUs, Variational Quantum Algorithms (VQA) [9] thanks to their short depth and resistance to noise are applicable even with the above limitations [10].”
BackgroundBenchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
Willsch, D., Willsch, M., Gonzalez Calaza, C. D., Jin, F., De Raedt, H., Svensson, M., & Michielsen, K. (2022) · Quantum Information Processing · doi:10.1007/s11128-022-03476-y · Cited by 114 · cited 1×
“Besides, quantum annealers, using the quantum annealing (QA) principle [11–13], are another quantum technology used to solve combinatorial optimization problems [14–16].”
MethodSelf-citationBenchmarking 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
Self-citationPenalty and partitioning techniques to improve performance of QUBO solvers
Verma, A., & Lewis, M. W. (2020) · Discrete Optimization · doi:10.1016/j.disopt.2020.100594 · Cited by 107 · cited 1×
“The slack variable, S , is an auxiliary variable that makes a penalization term vanish when the inequality constraint is achieved, Therefore, when Eq.”
BackgroundBreaking 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 · cited 1×
“There are three main reasons for this; first, many combinatorial optimization problems can be encoded in Hamiltonians, the ground state being the optimal solution of the problem [1, 2]; second, they are commonly hard to solve and have practical applications [3]; and third, the quantum algorithms to solve these problem…”
BackgroundGPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
Willsch, D., Willsch, M., Jin, F., Michielsen, K. F. L., & Raedt, H. A. D. (2022) · Computer Physics Communications · doi:10.1016/j.cpc.2022.108411 · Cited by 67
Self-citationQuantum Computing: Towards Industry Reference Problems
Luckow, A., Klepsch, J., & Pichlmeier, J. (2021) · Digitale Welt · doi:10.1007/s42354-021-0335-7 · Cited by 66 · cited 1×
“[23], traffic signal [24], among others.”
An introduction to quantum annealing
de Falco, D., & Tamascelli, D. (2011) · RAIRO - Theoretical Informatics and Applications · doi:10.1051/ita/2011013 · Cited by 64 · cited 1×
“Besides, quantum annealers, using the quantum annealing (QA) principle, are another quantum technology used to solve combinatorial optimization problems [11, 12].”
MethodConstrained quantum optimization for extractive summarization on a trapped-ion quantum computer
Niroula, P., Shaydulin, R., Yalovetzky, R., Minssen, P., Herman, D., Hu, S., & Pistoia, M. (2022) · Scientific Reports · doi:10.1038/s41598-022-20853-w · Cited by 59 · cited 2×
“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.”
BackgroundMethodUrgelles, H., Picazo-Martínez, P., García‐Roger, D., & Monserrat, J. F. (2022) · Sensors · doi:10.3390/s22197570 · Cited by 44 · 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.”
MethodOn the emerging potential of quantum annealing hardware for combinatorial optimization
Tasseff, B., Albash, T., Morrell, Z., Vuffray, M., Lokhov, A. Y., Misra, S., & Coffrin, C. (2024) · Journal of Heuristics · doi:10.1007/s10732-024-09530-5 · Cited by 42 · cited 1×
“In this respect, QA shows some advantages under certain conditions compared to classical annealing [17–19].”
BackgroundAn Application of Quantum Annealing Computing to Seismic Inversion
Souza, A. M., Martins, E. O., Roditi, I., Sá, N., Sarthour, R. S., & Oliveira, I. S. (2022) · Frontiers in Physics · doi:10.3389/fphy.2021.748285 · Cited by 38
Multi-qubit correction for quantum annealers
Ayanzadeh, R., Dorband, J. E., Halem, M., & Finin, T. (2021) · Scientific Reports · doi:10.1038/s41598-021-95482-w · Cited by 34 · cited 1×
“Besides, quantum annealers, using the quantum annealing (QA) principle, are another quantum technology used to solve combinatorial optimization problems [11, 12].”
MethodGlover, F., Kochenberger, G. A., Ma, M., & Du, Y. (2022) · Annals of Operations Research · doi:10.1007/s10479-022-04695-3 · Cited by 30 · cited 1×
“In this new heuristic encoding method, inequality constraints are encoded using an unbalanced penalization formula.”
MethodJUWELS Booster – A Supercomputer for Large-Scale AI Research
Kesselheim, S., Herten, A., Krajsek, K., Ebert, J., Jitsev, J., Cherti, M., Langguth, M., Gong, B., Stadtler, S., Mozaffari, A., et al. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-90539-2_31 · Cited by 23
George Dantzig’s contributions to integer programming
Grötschel, M., & Nemhauser, G. L. (2008) · Discrete Optimization · doi:10.1016/j.disopt.2007.08.003 · Cited by 19
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
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.