pith. machine review for the scientific record. sign in

arxiv: 2604.02416 · v1 · submitted 2026-04-02 · 🪐 quant-ph

Recognition: no theorem link

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
Authors on Pith no claims yet

Pith reviewed 2026-05-13 21:11 UTC · model grok-4.3

classification 🪐 quant-ph
keywords QUBOpenalization weightsconstrained optimizationGibbs solverspre-computationapproximate solversDigital Annealer
0
0 comments X

The pith

Pre-computation determines penalization weights for QUBO problems with provable guarantees on approximate solvers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a strategy to select penalization weights in advance when turning constrained optimization problems into QUBO form. The right weights are essential because they determine whether the solver respects the constraints or returns invalid solutions. Their pre-computation approach provides guarantees when the solver approximates a Gibbs sampler and runs in polynomial time for many standard problem classes. Tests on varied instances, including large-scale runs on Fujitsu's Digital Annealer, demonstrate reliable results and large speedups compared with existing trial-and-error tuning methods.

Core claim

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.

What carries the argument

A pre-computation strategy that calculates suitable penalization weights from problem structure so that constraints remain enforced when an approximate solver is applied to the resulting QUBO.

If this is right

  • Solvers obtain feasible solutions more reliably without needing to tune weights during the solve.
  • Polynomial runtime allows the method to scale to large problem sizes.
  • The same pre-computed weights work across both classical and quantum-inspired solver hardware.
  • Order-of-magnitude reductions in total computation time are observed relative to heuristic tuning.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The pre-computation step could be embedded in automated pipelines that convert constrained problems to QUBO form.
  • The same logic may extend to penalty formulations outside the QUBO setting.
  • Further tests on problems with many overlapping constraints would clarify where the polynomial bound remains practical.

Load-bearing premise

The solver must behave sufficiently like a Gibbs sampler or the problem must belong to a class where the weight calculation stays polynomial.

What would settle it

Applying the pre-computed weights to a solver that deviates markedly from Gibbs sampling behavior and finding that constraint violations remain frequent would falsify the claimed guarantees.

Figures

Figures reproduced from arXiv: 2604.02416 by Edoardo Alessandroni, Fritz Schinkel, Ingo Roth, Leandro Aolita, Martin Kliesch, Michel Krispin, Sergi Ramos-Calderer, Stefan Walter.

Figure 1
Figure 1. Figure 1: The big-M problem for approximate solvers is to ensure by the choice of a penalization weight M that an approximate solver samples feasible solutions with probability at least η when given a QUBO reformulation of a constrained optimization problem. Optionally, one can additionally enforce the solutions to be below a certain energy threshold Ef . We assume that the output distribution of a solver is qualita… view at source ↗
Figure 2
Figure 2. Figure 2: Proportion of feasible solutions observed [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Effective success probability ηeff of an ideal Gibbs sampler (top rows) and simulated annealing (SA) (bottom rows) for sampling feasible points, using a QUBO reformulation with penalization weight M∗ calculated by Alg. 1 for different constrained optimization problems (colums, see Section B for details) and system sizes. For each solver, in the first row we only require feasibilty (Ef = ∞), while for the s… view at source ↗
Figure 4
Figure 4. Figure 4: Effective success probability ηeff of the Fujitsu Digital An￾nealer (version 3) as a function of the system size using penalizations weigths M∗ determined by Alg. 1. Structure of the figure is identical to [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Multiplicative speedup compared to binary search from direct bound, computed as log2 (Mℓ1 /M∗ ), as a function of the system size for the different benchmarked problems. Here M∗ is the output of Alg. 1 and Mℓ1 is a direct bound for M (see Theorem 5). Colors indicate different target probabilities ηr ∈ {0.25, 0.5, 0.75}, and marker shapes different temperatures T = β −1 . For MNPP, random TSP and PO, lines … view at source ↗
Figure 6
Figure 6. Figure 6: Output dependence on vcut. Algorithm output M∗ (top) and associated effective success probability ηeff (bottom) as functions of the hyperparameter vcut for the tested benchmarks, shown for small system sizes. In the bottom plots, the thin blue line denotes the required probability η and orange markers the effective success ηeff measured from an ideal Gibbs sampler. For MNPP and TSP, M∗ stabilizes already a… view at source ↗
Figure 7
Figure 7. Figure 7: Output dependence on Ef . Algorithm output M∗ (left) and success probability used for the output computation η (right) as functions of the input parameter Ef , for a small instance of MNPP (N, P = 9, 2), illustrating the parameter’s effect. Filled blue markers denote the region where the required probability η can be satisfied and thus the output M∗ is computed using the required η, while empty markers den… view at source ↗
Figure 8
Figure 8. Figure 8: Penalization degeneracies for the problems studied and stretched exponential fit. npen(v) is shown as a function of the violation v on a logarithmic scale for the benchmarked problems (from left to right, MNPP, TSP and PO) at a fixed problem size. The problem parameters were chosen such that each instance requires 255 bits; specifically, for MNPP N = 45, P = 5, for TSP nv = 25 and for PO N = 45, w = 5. Dot… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper develops a pre-computation strategy for determining penalization weights in QUBO formulations of constrained combinatorial optimization problems. It provides provable guarantees when the solver exactly samples from the Gibbs distribution and polynomial complexity for broad problem classes. Experiments on diverse problems and solver architectures, including large-scale instances on Fujitsu's Digital Annealer, report robust performance and order-of-magnitude speedups over existing heuristics.

Significance. If the central claim holds with the necessary extensions to approximate solvers, the work would be significant for practical deployment of QUBO hardware. Removing manual or heuristic penalty tuning while retaining formal performance assurances could improve reliability and speed for constrained problems on both classical and specialized solvers.

major comments (1)
  1. [Abstract and theoretical guarantees section] The abstract and introduction claim 'provable guarantees for Gibbs solvers' while reporting results on approximate solvers such as the Fujitsu Digital Annealer. The skeptic note and abstract indicate that the formal argument assumes exact sampling from exp(-H/T); no section supplies a quantitative bound on allowable deviation from the Gibbs measure that preserves dominance of the penalty term over infeasible states. This is load-bearing for the central claim because the experimental validation relies on the approximate hardware.

Simulated Author's Rebuttal

1 responses · 1 unresolved

We thank the referee for their careful reading and constructive feedback. Below we respond point-by-point to the major comment and outline the revisions we will make to clarify the scope of our results.

read point-by-point responses

  1. Referee: [Abstract and theoretical guarantees section] The abstract and introduction claim 'provable guarantees for Gibbs solvers' while reporting results on approximate solvers such as the Fujitsu Digital Annealer. The skeptic note and abstract indicate that the formal argument assumes exact sampling from exp(-H/T); no section supplies a quantitative bound on allowable deviation from the Gibbs measure that preserves dominance of the penalty term over infeasible states. This is load-bearing for the central claim because the experimental validation relies on the approximate hardware.

    Authors: We agree that the formal guarantees are derived under the assumption of exact sampling from the Gibbs distribution, as already noted in the abstract and skeptic note. The pre-computation strategy is designed to ensure that the penalty term dominates infeasible configurations with high probability when the solver exactly samples from exp(-H/T). For the approximate solvers used in the experiments (including the Fujitsu Digital Annealer), we report only empirical performance, which shows consistent success and order-of-magnitude speedups over heuristics across multiple problem classes and instance sizes. We acknowledge that the manuscript does not supply a quantitative bound on the allowable deviation from the exact Gibbs measure. We will revise the abstract, introduction, and add a new subsection in the theoretical section to explicitly separate the provable guarantees (exact Gibbs) from the empirical results (approximate hardware). We will also expand the discussion to address the practical implications and limitations when the solver deviates from the ideal distribution. revision: partial

standing simulated objections not resolved
  • A quantitative bound on the allowable deviation from the exact Gibbs measure that would still guarantee dominance of the penalty term

Circularity Check

0 steps flagged

Pre-computation strategy for penalization weights relies on external guarantees rather than self-referential fitting

full rationale

The paper develops a pre-computation strategy for penalization weights with provable guarantees specifically for exact Gibbs solvers and polynomial complexity for broad problem classes. This derivation is presented as independent mathematical construction rather than a fit to observed solver outputs or a self-definition. Experiments on approximate hardware (e.g., Digital Annealer) are reported as empirical validation separate from the core guarantees. No load-bearing self-citations, uniqueness theorems imported from the authors, or ansatzes smuggled via prior work are required for the central claim. The approach remains self-contained against external benchmarks, with any transfer gap to approximate solvers constituting a correctness issue rather than circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities can be identified from the provided text.

pith-pipeline@v0.9.0 · 5454 in / 994 out tokens · 36293 ms · 2026-05-13T21:11:53.895709+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

78 extracted references · 78 canonical work pages · 2 internal anchors

  1. [1]

    Abbas, A

    A. Abbas, A. Ambainis, B. Augustino, A. Bärtschi, H. Buhrman, C. Coffrin, G. Cortiana, V . Dunjko, D. J. Egger, B. G. Elmegreen, N. Franco, F. Fratini, B. Fuller, J. Gacon, C. Gonciulea, S. Gri- bling, S. Gupta, S. Hadfield, R. Heese, G. Kircher, T. Kleinert, T. Koch, G. Korpas, S. Lenk, J. Marecek, V . Markov, G. Mazzola, S. Mensa, N. Mohseni, G. Nannici...

    work page arXiv 2024

  2. [2]

    M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizin- sky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wil- son, and G. Rose, Quantum annealing with ma...

    work page 2011

  3. [3]

    E. J. Crosson and D. A. Lidar, Prospects for quantum enhance- ment with diabatic quantum annealing, Nat. Rev. Phys.3, 466 (2021), arXiv:2008.09913 [quant-ph]

    work page arXiv 2021

  4. [5]

    Inagaki, Y

    T. Inagaki, Y . Haribara, K. Igarashi, T. Sonobe, S. Tamate, T. Honjo, A. Marandi, P. L. McMahon, T. Umeki, K. Enbutsu, O. Tadanaga, H. Takenouchi, K. Aihara, K. ichi Kawarabayashi, K. Inoue, S. Utsunomiya, and H. Takesue, A coherent Ising ma- chine for 2000-node optimization problems, Science354, 603 (2016)

    work page 2000

  5. [6]

    Honjo, T

    T. Honjo, T. Sonobe, K. Inaba, T. Inagaki, T. Ikuta, Y . Ya- mada, T. Kazama, K. Enbutsu, T. Umeki, R. Kasahara, K. ichi Kawarabayashi, and H. Takesue, 100,000-spin coherent Ising machine, Science Advances7, eabh0952 (2021)

    work page 2021

  6. [7]

    M. Sao, H. Watanabe, Y . Musha, and A. Utsunomiya, Appli- cation of digital annealer for faster combinatorial optimization, Fujitsu Scientific and Technical Journal55, 45 (2019)

    work page 2019

  7. [8]

    Hideki Fukushima-Kimura, N

    B. Hideki Fukushima-Kimura, N. Kawamoto, E. Noda, and A. Sakai, Mathematical aspects of the Digital Annealer’s simu- lated annealing algorithm, arXiv:2303.08392 [math.OC] (2023)

    work page arXiv 2023

  8. [9]

    Okuyama, T

    T. Okuyama, T. Sonobe, K.-i. Kawarabayashi, and M. Yamaoka, Binary optimization by momentum annealing, Phys. Rev. E100, 012111 (2019)

    work page 2019

  9. [10]

    H. Goto, K. Tatsumura, and A. R. Dixon, Combinatorial op- timization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems, Science Advances5, eaav2372 (2019), https://www.science.org/doi/pdf/10.1126/sciadv.aav2372

    work page doi:10.1126/sciadv.aav2372 2019

  10. [11]

    Tatsumura, M

    K. Tatsumura, M. Yamasaki, and H. Goto, Scaling out Ising ma- chines using a multi-chip architecture for simulated bifurcation, Nature Electronics4, 208 (2021)

    work page 2021

  11. [12]

    Kochenberger, J.-K

    G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y . Wang, The unconstrained binary quadratic programming problem: a survey, Journal of Combinatorial Opti- mization28, 58 (2014)

    work page 2014

  12. [13]

    Ratke, List of qubo formulations, https://blog.xa0

    D. Ratke, List of qubo formulations, https://blog.xa0. de/post/List-of-QUBO-formulations/ (2021), blog post, accessed 2026-03-02. 9 Figure 5.Multiplicative speedup compared to binary search from direct bound,computed as log2(Mℓ1/M∗), as a function of the system size for the different benchmarked problems. Here M∗is the output of Alg. 1 and Mℓ1 is a direct...

    work page 2021

  13. [14]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, Science220, 671 (1983)

    work page 1983

  14. [15]

    Geman and D

    S. Geman and D. Geman, Stochastic relaxation, gibbs distribu- tions, and the bayesian restoration of images, IEEE Transactions on Pattern Analysis and Machine IntelligencePAMI-6, 721 (1984)

    work page 1984

  15. [16]

    R. J. Glauber, Time-dependent statistics of the ising model, Jour- nal of Mathematical Physics4, 294 (1963)

    work page 1963

  16. [17]

    W. K. Hastings, Monte carlo sampling methods using markov chains and their applications, Biometrika57, 97 (1970)

    work page 1970

  17. [18]

    Exchange Monte Carlo Method and Application to Spin Glass Simulations

    K. Hukushima and K. Nemoto, Exchange monte Carlo method and application to spin glass simulations, Journal of the Physical Society of Japan65, 1604 (1996), arXiv:cond-mat/9512035

    work page internal anchor Pith review Pith/arXiv arXiv 1996

  18. [19]

    Mossel and A

    E. Mossel and A. Sly, Exact thresholds for ising–gibbs samplers on general graphs, The Annals of Probability41, 10.1214/11- aop737 (2013)

    work page doi:10.1214/11- 2013

  19. [20]

    Siddique and H

    N. Siddique and H. Adeli, Simulated annealing, its variants and engineering applications, International Jour- nal on Artificial Intelligence Tools25, 1630001 (2016), https://doi.org/10.1142/S0218213016300015

    work page doi:10.1142/s0218213016300015 2016

  20. [21]

    Karabin and S

    M. Karabin and S. J. Stuart, Simulated annealing with adaptive cooling rates (2020), arXiv:2002.06124 [physics.chem-ph]

    work page arXiv 2020

  21. [22]

    Matsubara, H

    S. Matsubara, H. Tamura, M. Takatsu, D. Yoo, B. Vatankhahghadim, H. Yamasaki, T. Miyazawa, S. Tsukamoto, Y . Watanabe, K. Takemoto, and A. Sheikholeslami, Ising-model optimizer with parallel-trial bit-sieve engine, inComplex, Intelligent, and Software Intensive Systems, edited by L. Barolli and O. Terzo (Springer International Publishing, 2018) pp. 432–438

    work page 2018

  22. [23]

    H. M. Waidyasooriya, Y . Araki, and M. Hariyama, Acceler- ator architecture for simulated quantum annealing based on resource-utilization-aware scheduling and its implementation using opencl, in2018 International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS)(2018) pp. 335–340

    work page 2018

  23. [24]

    Matsubara, M

    S. Matsubara, M. Takatsu, T. Miyazawa, T. Shibasaki, Y . Watan- abe, K. Takemoto, and H. Tamura, Digital annealer for high- speed solving of combinatorial optimization problems and its applications, in2020 25th Asia and South Pacific Design Au- tomation Conference (ASP-DAC)(2020) pp. 667–672

    work page 2020

  24. [25]

    Kadowaki and H

    T. Kadowaki and H. Nishimori, Quantum annealing in the trans- verse ising model, Physical Review E58, 5355 (1998)

    work page 1998

  25. [26]

    Farhi, J

    E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem, Science292, 472 (2001)

    work page 2001

  26. [27]

    Rajak, S

    A. Rajak, S. Tomar, and S. Kumar, Quantum annealing: An overview, Philosophical Transactions of the Royal Society A 380, 20210417 (2022)

    work page 2022

  27. [28]

    Munoz-Bauza and D

    H. Munoz-Bauza and D. Lidar, Scaling advantage in approx- imate optimization with quantum annealing, Physical Review Letters134, 160601 (2025)

    work page 2025

  28. [29]

    A Quantum Approximate Optimization Algorithm

    E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  29. [30]

    Blekos, D

    K. Blekos, D. Brand, A. Ceschini, C.-H. Chou, R.-H. Li, K. Pandya, and A. Summer, A review on quantum approximate optimization algorithm and its variants, Physics Reports1068, 1 (2024)

    work page 2024

  30. [31]

    Cheng, Y .-Q

    L. Cheng, Y .-Q. Chen, S.-X. Zhang, and S. Zhang, Quantum approximate optimization via learning-based adaptive optimiza- tion, Communications Physics7, 83 (2024)

    work page 2024

  31. [32]

    Amosy, T

    O. Amosy, T. Danzig, O. Lev, and et al., Iteration-free quan- tum approximate optimization algorithm using neural networks, Quantum Machine Intelligence6, 38 (2024)

    work page 2024

  32. [33]

    Yanakiev, N

    N. Yanakiev, N. Mertig, C. K. Long, and D. R. M. Arvidsson- Shukur, Dynamic adaptive quantum approximate optimization algorithm for shallow, noise-resilient circuits, Physical Review A109, 032420 (2024)

    work page 2024

  33. [34]

    Gilks, S

    W. Gilks, S. Richardson, and D. Spiegelhalter, eds.,Markov Chain Monte Carlo in Practice(Chapman and Hall/CRC, Lon- don, 1996)

    work page 1996

  34. [35]

    Harwood, C

    S. Harwood, C. Gambella, D. Trenev, A. Simonetto, D. Bernal, and D. Greenberg, Formulating and solving routing problems on quantum computers, IEEE Transactions on Quantum Engineer- ing2, 1 (2021)

    work page 2021

  35. [36]

    I. D. Leonidas, A. Dukakis, B. Tan, and D. G. Angelakis, Qubit efficient quantum algorithms for the vehicle routing problem on noisy intermediate-scale quantum processors, Advanced Quan- tum Technologies7, 2300309 (2024)

    work page 2024

  36. [37]

    Qiskit documentation, Converters for quadratic programs - lin- earequalitytopenalty (2022)

    work page 2022

  37. [38]

    U. Azad, B. K. Behera, E. A. Ahmed, P. K. Panigrahi, and A. Farouk, Solving vehicle routing problem using quantum ap- proximate optimization algorithm, IEEE Transactions on Intelli- gent Transportation Systems24, 7564 (2023)

    work page 2023

  38. [39]

    Alessandroni, S

    E. Alessandroni, S. Ramos-Calderer, I. Roth, E. Traversi, L. Aolita,et al., Alleviating the quantum big-m problem, npj Quantum Information11, 10.1038/s41534-025-01067-0 (2025)

    work page doi:10.1038/s41534-025-01067-0 2025

  39. [40]

    G. Reinelt, Tsplib95 – a library of sample instances for the travelling salesman problem and related prob- 10 lems, http://comopt.ifi.uni-heidelberg.de/ software/TSPLIB95/(1991), accessed: 2025-10-22

    work page 1991

  40. [41]

    H. P. Williams,Model Building in Mathematical Programming, 5th ed. (Wiley, Chichester, UK, 2013)

    work page 2013

  41. [42]

    Glover, Improved linearization of nonlinear binary program- ming problems, Operations Research13, 111 (1965)

    F. Glover, Improved linearization of nonlinear binary program- ming problems, Operations Research13, 111 (1965)

    work page 1965

  42. [43]

    I. G. Rosenberg,Reduction of Bivalent Maximization Problems to the Quadratic Case, Research Memorandum RM-P-2470 (RAND Corporation, Santa Monica, CA, 1975)

    work page 1975

  43. [44]

    G. L. Nemhauser and L. A. Wolsey,Integer and Combinatorial Optimization(Wiley, New York, 1988)

    work page 1988

  44. [45]

    Metropolis, A

    N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, Equation of state calculations by fast computing machines, The Journal of Chemical Physics21, 1087 (1953)

    work page 1953

  45. [46]

    Nesterov and A

    Y . Nesterov and A. Nemirovskii,Interior-Point Polynomial Algo- rithms in Convex Programming, Studies in Applied Mathematics, V ol. 13 (Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994)

    work page 1994

  46. [47]

    Yurtsever, M

    A. Yurtsever, M. Udell, J. A. Tropp, and V . Cevher, Sketchy decisions: Convex low-rank matrix optimization with optimal storage, inProceedings of the 20th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, V ol. 54, edited by A. Singh and J. Zhu (PMLR, 2017) pp. 1188–1196

    work page 2017

  47. [48]

    R. L. Burden, J. D. Faires, and A. M. Burden,Numerical Analy- sis, 10th ed. (Cengage Learning, 2015)

    work page 2015

  48. [49]

    Díez-Valle, F

    P. Díez-Valle, F. J. Gómez-Ruiz, D. Porras, and J. J. García- Ripoll, Universal resources for qaoa and quantum annealing (2025), arXiv:2506.03241 [quant-ph]

    work page arXiv 2025

  49. [50]

    Oshiyama, S

    H. Oshiyama, S. Suzuki, and N. Shibata, Classical simulation and theory of quantum annealing in a thermal environment, Phys. Rev. Lett.128, 170502 (2022)

    work page 2022

  50. [51]

    C. F. CAIAFA and A. N. PROTO, Temperature es- timation in the two-dimensional ising model, Interna- tional Journal of Modern Physics C17, 29 (2006), https://doi.org/10.1142/S0129183106008856

    work page doi:10.1142/s0129183106008856 2006

  51. [52]

    Benedetti, J

    M. Benedetti, J. Realpe-Gómez, R. Biswas, and A. Perdomo- Ortiz, Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applica- tions in deep learning, Phys. Rev. A94, 022308 (2016)

    work page 2016

  52. [53]

    Hadfield, Z

    S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Algorithms 12, 34 (2019)

    work page 2019

  53. [54]

    Herman, R

    D. Herman, R. Shaydulin, Y . Sun, S. Chakrabarti, S. Hu, P. Minssen, A. Rattew, R. Yalovetzky, and M. Pistoia, Quantum zeno dynamics for constrained optimization, Communications Physics6, 219 (2023), arXiv:2209.15024 [quant-ph]

    work page arXiv 2023

  54. [55]

    Diez-Valle, J

    P. Diez-Valle, J. Luis-Hita, S. Hernandez-Santana, F. Martínez- Garcia, A. Diaz-Fernandez, E. Andres, J. Jose Garcia-Ripoll, E. Sanchez-Martinez, and D. Porras, Multiobjective variational quantum optimization for constrained problems: an application to cash handling, Quantum Science and Technology8, 045009 (2023)

    work page 2023

  55. [56]

    Bucher, J

    D. Bucher, J. Stein, S. Feld, and C. Linnhoff-Popien, Penalty- free approach to accelerating constrained quantum optimization, Phys. Rev. A112, 062605 (2025)

    work page 2025

  56. [57]

    Bucher, D

    D. Bucher, D. Porawski, M. Janetschek, J. Stein, C. O’Meara, G. Cortiana, and C. Linnhoff-Popien, Efficient qaoa architecture for solving multi-constrained optimization problems, in2025 IEEE International Conference on Quantum Computing and Engineering (QCE)(IEEE, 2025) p. 356–367

    work page 2025

  57. [58]

    Shirai and N

    T. Shirai and N. Togawa, Compressed space quantum approxi- mate optimization algorithm for constrained combinatorial opti- mization, IEEE Transactions on Quantum Engineering6, 1–14 (2025)

    work page 2025

  58. [59]

    B. Bakó, A. Glos, Ö. Salehi, and Z. Zimborás, Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs, Quantum9, 1663 (2025)

    work page 2025

  59. [60]

    Egginger, K

    S. Egginger, K. Kirova, S. Bruckner, S. Hillmich, and R. Kueng, A rigorous quantum framework for inequality-constrained and multi-objective binary optimization (2026), arXiv:2510.13983 [quant-ph]

    work page arXiv 2026

  60. [61]

    E. L. Schreiber, R. E. Korf, and M. D. Moffitt, Optimal multi- way number partitioning, J. ACM65, 10.1145/3184400 (2018)

    work page doi:10.1145/3184400 2018

  61. [62]

    Lucas, Ising formulations of many np problems, Frontiers in Physics2, 10.3389/fphy.2014.00005 (2014)

    A. Lucas, Ising formulations of many np problems, Frontiers in Physics2, 10.3389/fphy.2014.00005 (2014)

    work page doi:10.3389/fphy.2014.00005 2014

  62. [63]

    Korf, Objective functions for multi-way number partitioning

    R. Korf, Objective functions for multi-way number partitioning. (2010)

    work page 2010

  63. [64]

    Gent and T

    I. Gent and T. Walsh, Phase transitions and annealed theories: Number partitioning as a case study (1996) pp. 170–174, proc ECAI-96

    work page 1996

  64. [65]

    Matai, S

    R. Matai, S. Singh, and M. Mittal, Traveling salesman prob- lem: an overview of applications, formulations, and solution approaches (2010)

    work page 2010

  65. [66]

    Markowitz, Portfolio selection, The Journal of Finance7, 77 (1952)

    H. Markowitz, Portfolio selection, The Journal of Finance7, 77 (1952)

    work page 1952

  66. [67]

    Grant, T

    E. Grant, T. S. Humble, and B. Stump, Benchmarking quan- tum annealing controls with portfolio optimization, Phys. Rev. Applied15, 014012 (2021)

    work page 2021

  67. [68]

    Rosenberg, P

    G. Rosenberg, P. Haghnegahdar, P. Goddard, P. Carr, K. Wu, and M. L. de Prado, Solving the optimal trading trajectory problem using a quantum annealer, IEEE Journal of Selected Topics in Signal Processing10, 1053 (2016)

    work page 2016

  68. [69]

    M. R. Jerrum, L. G. Valiant, and V . V . Vazirani, Random gen- eration of combinatorial structures from a uniform distribution, Theoretical Computer Science43, 169 (1986)

    work page 1986

  69. [70]

    Jerrum,Counting, Sampling and Integrating: Algorithms and Complexity, Lectures in Mathematics ETH Zürich (Birkhäuser, 2003)

    M. Jerrum,Counting, Sampling and Integrating: Algorithms and Complexity, Lectures in Mathematics ETH Zürich (Birkhäuser, 2003)

    work page 2003

  70. [71]

    Vigoda, Approximately counting knapsack solutions and re- lated problems, Lecture notes, Georgia Institute of Technology (2014)

    E. Vigoda, Approximately counting knapsack solutions and re- lated problems, Lecture notes, Georgia Institute of Technology (2014)

    work page 2014

  71. [72]

    Pesant, C.-G

    G. Pesant, C.-G. Quimper, and A. Zanarini, Counting solutions of CSPs: A structural approach, inProceedings of the Twenty- Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)(2015) p. 337–343

    work page 2015

  72. [73]

    Boyd and L

    S. Boyd and L. Vandenberghe,Convex Optimization(Cambridge University Press, 2009). 11 Appendix A: Extended theoretical guarantee for the algorithm Theorem 2 establishes that the proposed algorithm returns a valueM∗that ensures anη-reformulation, Eq. (3) using infinite samplesNs→∞. We here establish that using an inverse polynomial number of samples in the...

    work page 2009

  73. [74]

    The Multiway Number Partitioning Problem (MNPP) is a generalization of this, with multiple subsets to partition the elements into

    MNPP The Number Partitioning Problem (NPP), an NP-hard combinatorial problem, aims at partitioning a set of numbers into two subsets as evenly as possible. The Multiway Number Partitioning Problem (MNPP) is a generalization of this, with multiple subsets to partition the elements into. Its applications range from distributed networking and computing, reso...

    work page

  74. [75]

    Given a connected graphG= (V,E) withnv =|V|vertices, where edgeei,j represents the cost of traveling from nodei to nodej, the goal is to find the cheapest Hamiltonian cycle, i.e

    TSP The Traveling Salesman Problem is a cornerstone of optimization problems, it is a NP-hard problem highly relevant both in theoretical computer science and for practical applications, such as logistics, circuit design, telecommunications [65]. Given a connected graphG= (V,E) withnv =|V|vertices, where edgeei,j represents the cost of traveling from node...

    work page

  75. [76]

    the problem of selecting a set of assets maximizing returns while minimizing risk

    PO For Portfolio Optimization we use the well-known Markovitz model [ 66–68], i.e. the problem of selecting a set of assets maximizing returns while minimizing risk. The problem specification requires a vectorµof expected returns of a set ofN assets, their covariance matrix Σ , a risk aversionγ >0, and a partition numberw defining the portfolio discretiza...

    work page 2020

  76. [77]

    Note that in the penalization term the rows contribute independently to the total error

    MNPP For a Multiway Number Partition Problem (MNPP) instance withN numbers to partition intoP partitions the penalization E(p)(x) = ∑N i=1(1−∑P p=1xi,p)2 enforces a feasible decision matrix [x]i,p to be right-stochastic, i.e., ∑P p=1xi,p = 1∀i, meaning that each row of the binary matrix contains exactly one 1. Note that in the penalization term the rows c...

    work page

  77. [78]

    The number of feasible points thus corresponds to the number of permutation matrices, hence npen(0) = nv(nv−1)...1 =nv!

    TSP For a Travelling Salesman Problem instance withnv vertices, the penalizationE(p)(x) = ∑nv i=1(1−∑nv t=1xt,i)2 + ∑nv t=1(1−∑nv i=1xt,i)2 enforces a feasible decision matrix [x]t,i to be stochastic, meaning that each rowandeach column must contain exactly a single 1. The number of feasible points thus corresponds to the number of permutation matrices, h...

    work page

  78. [79]

    The penalization is zero only for bitstrings x whose components sum up to 2w−1

    PO For a Portfolio Optimization instance withN stocks and partition numberw, the penalization energy isE(p)(x) = (∑N i=1xi− 2w + 1)2, where each component is an integer xi∈{0,...,2w−1}. The penalization is zero only for bitstrings x whose components sum up to 2w−1. Since E(p) is the square of an integer, non-zero configurations exist only for perfect-squa...

    work page