Scalable Determination of Penalization Weights for Constrained Optimizations on Approximate Solvers

Quantum Physics [Submitted on 2 Apr 2026] Scalable Determination of Penalization Weights for Constrained Optimizations on Approximate Solvers Edoardo Alessandroni, Sergi Ramos-Calderer, Michel Krispin, Fritz Schinkel, Stefan Walter, Martin Kliesch, Leandro Aolita, Ingo Roth Quadratic unconstrained binary optimization (QUBO) provides problem formulations for various computational problems that can be solved with dedicated QUBO solvers, which can be based on classical or quantum computation. A common approach to constrained combinatorial optimization problems is to enforce the constraints in the QUBO formulation by adding penalization terms. Penalization introduces an additional hyperparameter that significantly affects the solver's efficacy: the relative weight between the objective terms and the penalization terms. We develop a pre-computation strategy for determining penalization weights with provable guarantees for Gibbs solvers and polynomial complexity for broad problem classes. Experiments across diverse problems and solver architectures, including large-scale instances on Fujitsu's Digital Annealer, show robust performance and order-of-magnitude speedups over existing heuristics. Comments: 20 pages, 8 figures Subjects: Quantum Physics (quant-ph) Cite as: arXiv:2604.02416 [quant-ph]   (or arXiv:2604.02416v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2604.02416 Focus to learn more Submission history From: Edoardo Alessandroni [view email] [v1] Thu, 2 Apr 2026 18:00:02 UTC (2,130 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-04 References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)