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
Abstract
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.
AI Impact Assessments
(3 models)Scientific Impact Assessment
1. Core Contribution
This paper tackles a fundamental practical challenge in QUBO-based optimization: how to set the penalization weight *M* when converting constrained problems into unconstrained formulations for approximate solvers (simulated annealing, digital annealers, quantum annealers, QAOA). The key insight is that existing Big-M strategies are designed for exact solvers and systematically overestimate the penalty, degrading solution quality for approximate solvers that sample from thermal-like distributions.
The authors propose Algorithm 1, a pre-computation strategy that combines SDP relaxation bounds, uniform sampling over the feasible subspace, and analytically derived penalization degeneracies to compute three probability bounds—for low-energy feasible, high-energy feasible, and infeasible configurations. These are combined into a scalar function whose root yields the penalization weight *M* guaranteeing a target feasibility probability η. The approach is novel in explicitly incorporating the solver's degree of approximation (modeled via inverse temperature β of a Gibbs distribution) into the penalty determination.
2. Methodological Rigor
The theoretical foundations are sound. Theorem 2 provides a clean proof that Algorithm 1 yields an η-reformulation for exact Gibbs samplers in the infinite-sample limit with full degeneracy information. Theorem 4 extends this to finite samples, showing O(ε⁻²) samples suffice for an (η−ε)-reformulation. The complexity analysis is thorough, establishing polynomial runtime under reasonable assumptions (bounded entries, efficient feasible-space sampling, efficient penalization degeneracy computation).
The paper appropriately acknowledges that the Gibbs distribution is a *model* for practical solvers, not an exact description. The gap between theory and practice is addressed through extensive empirical validation across three problem classes (TSP, MNPP, PO), three solver types (exact Gibbs, simulated annealing, Fujitsu Digital Annealer v3), and system sizes up to ~4000 bits. The experimental design is well-structured, testing feasibility-only and optimality-constrained settings.
One methodological concern is the reliance on the Gibbs distribution assumption. While results on the Digital Annealer show the method works in practice (ηeff ≥ η consistently), the theoretical guarantee technically only holds for ideal Gibbs samplers. The paper is transparent about this, but a more formal characterization of robustness to distributional deviations would strengthen the contribution.
3. Potential Impact
Practical impact is significant. The Big-M problem is ubiquitous in QUBO-based optimization—every constrained problem converted to QUBO requires this hyperparameter. The demonstrated order-of-magnitude speedups (Figure 5, showing log₂(M_ℓ₁/M*) often exceeding 10) over naive binary search represent substantial savings in solver calls, which can be expensive for hardware accelerators and quantum devices.
Relevance to quantum computing: The paper explicitly positions itself as useful for quantum annealers and QAOA, where computational resources are scarce and each solver call is costly. The pre-computation strategy, running on classical hardware, is a natural fit for hybrid classical-quantum workflows. Recent work connecting quantum solvers to Gibbs samplers (refs [49-52]) provides a pathway for extending the theoretical guarantees.
Breadth of applicability: The framework handles any linearly constrained binary optimization, which encompasses a wide range of NP-hard problems through standard gadgets. The analytical derivation of penalization degeneracies for TSP, MNPP, and PO (Appendix I) is a useful reference contribution.
4. Timeliness & Relevance
This work is timely for several reasons: (a) dedicated QUBO hardware (digital annealers, quantum annealers) is increasingly deployed for real-world problems, making practical hyperparameter tuning critical; (b) the gap between theoretical QUBO formulations and practical solver performance is a recognized bottleneck; (c) the quantum optimization community specifically needs methods for managing penalization in unconstrained formulations. The paper builds on the authors' prior work [39] on alleviating the Big-M problem for exact solvers, extending it naturally to the approximate-solver regime.
5. Strengths & Limitations
Strengths:
Limitations:
Additional Observations
The paper's framing as a "pre-computation strategy" is strategically sound—it positions the method as complementary to, rather than competing with, existing solvers. The comparison metric (saved binary search iterations) is practical and convincing. The analytical penalization degeneracies exhibit sub-exponential scaling (Figure 8), which is an interesting structural observation about these problem classes that could have independent value.
The paper is well-written with clear exposition, though the density of notation and the extensive appendices may limit accessibility for practitioners. The connection to quantum computing, while motivating, remains prospective rather than demonstrated.
Generated Apr 6, 2026
Comparison History (43)
Paper 2 presents a fundamental breakthrough in experimental quantum physics by allowing the estimation of nonlinear quantum properties using only a single measurement setting. This drastically reduces the experimental overhead traditionally required. While Paper 1 offers a highly practical algorithmic improvement for combinatorial optimization solvers, Paper 2's methodological innovation solves a core bottleneck in quantum state characterization, offering deeper fundamental scientific impacts across quantum information science, many-body physics, and the evaluation of near-term quantum devices.
Paper 2 addresses a foundational bottleneck in Density Functional Theory (DFT), the primary computational tool in quantum chemistry and materials science. By achieving linear scaling for highly accurate, non-local machine-learned exchange-correlation functionals, it enables the simulation of strongly correlated systems at unprecedented scales. This has sweeping implications for drug discovery, materials design, and physics. While Paper 1 provides a valuable optimization for QUBO solvers, Paper 2's breakthrough in fundamental quantum chemical modeling promises a substantially broader and more transformative impact across multiple scientific disciplines.
Paper 2 likely has higher impact: it introduces a broadly applicable, experimentally demonstrated photonic-domain protocol that restores entanglement from solid-state emitters without temporal post-selection or detector-resolution constraints—key bottlenecks for scalable quantum networking. This is timely for integrated quantum photonics and could influence source engineering, quantum communication, and hardware architectures. Paper 1 is novel and useful for QUBO/annealing workflows with provable guarantees, but its impact is more specialized to optimization solver tuning and may be bounded by the adoption trajectory of QUBO/quantum-inspired hardware.
Paper 2 likely has higher scientific impact due to a clearer, more immediately actionable contribution: a scalable, theoretically grounded method for choosing penalty weights in QUBO constrained optimization, validated experimentally on diverse problems and hardware (including large-scale Digital Annealer runs). This targets a widely encountered bottleneck in both classical and quantum-inspired/quantum optimization with direct real-world applications and reproducibility. Paper 1 is highly novel and ambitious, but its claims (emergent spacetime/Einstien equations from detector inference) are speculative and harder to validate, which may limit near-term uptake despite potential long-term significance.
Paper 2 offers a broadly applicable, solver-agnostic method with provable guarantees and polynomial complexity for selecting penalty weights in constrained QUBO formulations—an important, ubiquitous bottleneck in both classical and quantum/annealing optimization workflows. It demonstrates robust gains across diverse problems and architectures (including large-scale Digital Annealer runs), suggesting immediate real-world utility and wide cross-domain impact (operations research, ML, quantum computing). Paper 1 is novel in physical stochastic neuron implementations, but impact is less immediate due to hardware complexity and currently limited evaluation scope (simple MNIST-scale models).
Paper 1 introduces a novel physical mechanism (phononic bath) for qubit reset, achieving a 1-2 orders of magnitude improvement in hardware fidelity. This addresses a critical bottleneck in superconducting quantum circuits, directly impacting quantum computing scalability. While Paper 2 offers a valuable algorithmic improvement for QUBO solvers, Paper 1 represents a fundamental experimental breakthrough with broader implications for the rapidly advancing field of quantum information science.
Paper 2 addresses a fundamental grand challenge in quantum technology—scalable quantum repeaters for a quantum internet. By proposing a scheme that corrects transmission loss without introducing logical errors and requiring orders of magnitude fewer qubits than photonic approaches, it offers a transformative leap for long-distance quantum communication. While Paper 1 provides a valuable optimization technique for near-term annealers, Paper 2's potential to enable medium-to-long-distance secure quantum networks represents a broader and more paradigm-shifting scientific impact across quantum computing, networking, and cryptography.
Paper 2 addresses a fundamental and broadly applicable problem in combinatorial optimization—determining penalization weights for QUBO formulations—with provable guarantees and demonstrated scalability across diverse problem classes and solver architectures. This has wide impact across quantum computing, classical optimization, and operations research. Paper 1 presents a practical but incremental engineering contribution combining existing QKD and PQC technologies using open-source tools. While useful for network security practitioners, it is more of a systems integration effort with narrower impact compared to Paper 2's theoretical and practical contributions to optimization methodology.
Paper 1 likely has higher impact due to a novel, hardware-calibrated QFT truncation scheme with a clear theoretical bound (TV-distance) linking circuit depth to error, and a strong timeliness for NISQ-era phase estimation—core to many quantum algorithms (simulation, chemistry, metrology). It also shows practical cross-platform gate-count reductions and an important “noise-truncation synergy,” suggesting near-term advantage. Paper 2 is valuable and broadly applicable to QUBO practice, but penalization-weight tuning is a more incremental area with narrower methodological novelty than a scalable QPE/QFT advance.
Paper 2 introduces a fundamentally new concept (dismagicker) that addresses a significant gap in quantum computing—the lack of tools for non-stabilizerness reduction analogous to disentanglers for entanglement. This bridges quantum resource theory with practical tensor network methods and quantum state preparation, potentially impacting both classical simulation and quantum computing. Paper 1, while practically useful for QUBO optimization with solid methodology, addresses a more incremental hyperparameter tuning problem. Paper 2's novelty, conceptual contribution, and broad applicability across quantum information science give it higher impact potential.