WorksMathematics
Quantifying the remaining search space in analogue optimisation
Abstract
Benchmarking analogue optimisers requires certifying not only how close a returned energy is to the optimum, but also how many better configurations may remain. Semidefinite relaxations provide rigorous bounds on the ground-state energy and selected observables, yet reveal little about the size of this residual search space. We introduce a deterministic, instance-specific upper bound on the number of binary configurations whose energies improve upon a returned state by a prescribed margin. Combined with a semidefinite energy interval, this yields a complementary certificate of both the magnitude and multiplicity of any possible improvement. To judge an analogue optimiser's native performance, we provide a generalisation of the framework to obtain bounds on the Haar volume of the remaining continuous phase-space. To further characterise the remaining search space, we extend our bounds to resolve regions in configuration space in both the binary and continuous setting. Our approach couples a variational-Chernoff reduction with an elimination bound of the resulting partition function. Comparisons with exact enumeration and independent Haar sampling are consistent with the bounds on small instances. In numerical experiments at , even the largest family-median bound restricts the potentially improving binary configurations to less than of the full configuration space, while the largest upper bound on the corresponding Haar volume is of order .
Introduction
Many binary optimisation problems, including Max-Cut and Max-2-SAT, can be mapped to the continuous dynamics of oscillator networks, coherent Ising machines, annealers, and other physical optimisers [1, 2, 3, 4, 5, 6, 7]. Finding the solution to the problem translates to the global minimisers of
Here is the number of variables, the coupling matrix is real symmetric with zero diagonal, and are the local fields. The global minimisers of encode optimal solutions to the original problem, while nonglobal local minima represent metastable candidate solutions [8, 9].
However, in the relevant regime, exactly computing the ground-state energy against which the returned state should be judged, often is computationally intractable. Most benchmarking protocols compare attained objectives, success frequencies, or time to a target [10, 11, 12]. These quantities are indispensable for comparing devices, but none certifies how far a particular output is from the unknown optimum.
Baccari et al. addressed this logical gap for quantum optimisers by computing certified lower bounds on the ground-state energy [13]. Combined with the energy of a returned configuration, such a relaxation gives the rigorous interval
The interval quantifies how much improvement is energetically possible, but not whether potential improvements occupy half the state space or one configuration in .
Benchmarking a solution by how many solutions it beats is an established idea in combinatorial optimisation. Domination analysis rates a heuristic by the number of solutions it is guaranteed to be better than [14, 15, 16]. For Max-Cut and Max--SAT, polynomial algorithms with a constant domination ratio exist [17], and related results cover Boolean quadratic programs [18]. Instance-specific dominance certificates have also been constructed for heuristic outputs of TSP and MaxSAT instances [19]. Motivated by this viewpoint, for a returned binary state with energy we consider
For a fixed returned state , we use the shorthand . Thus counts all configurations that match or improve upon by at least . For the count includes and any degenerate configuration, in particular if . The case is relevant if one is interested in the number of solutions offering a substantial improvement. Since
an upper bound on gives a lower bound on the domination number of the returned state , that is the number of states with energy as least as large as the trial state.
Density-of-states methods estimate the population of each energy level [20, 21] but do not give one-sided bounds. Hashing-based model counters give bounds that hold with a prescribed probability, but require many calls to an exact solver [22, 23]. Jain et al. derive deterministic upper bounds on the number of feasible solutions of binary integer programs [24]. An objective cutoff can be added to such a program as a constraint, but the method targets small structured programs rather than dense quadratic objectives. Related hardware work enumerates solutions under assumptions on sampling fairness and energy ordering [25]. Another approach bounds satisfiability densities by concentration inequalities whose sensitivity constants come from an annealer, so the bound is valid only if the annealer finds the true maxima [26]. What we are interested in here: a deterministic upper bound on the number of configurations better than the returned state, that applies to the continuous phase states in which oscillator machines compute. We seek bounds that are valid for an arbitrary dense instance where for a fixed instance the count depends on only through , independently of how that state was found.
We derive a deterministic upper bound of this kind from variational Chernoff bounds [27] combined with partition-function bounds [28]. We express the improving fraction as an event probability under a uniform reference measure. Bounding this probability certifies the improving count independently of the optimiser’s sampling or search procedure.
The remainder of the paper first introduces the phase-oscillator model and semidefinite energy certificates. We then derive configuration-count bounds using an elimination procedure related to that of Jaakkola-Jordan [28], with curvature profiles reused across energy thresholds, and extend the framework to continuous phases while preserving pairwise elimination. We show how the resulting count and volume bounds can be combined with energy intervals and observable constraints, to further resolve the remaining search space. Finally, we assess the tightness of the bounds against exact enumeration and independent Haar sampling, evaluate their scaling on dense random instances and NP-hard encodings with up to variables, and discuss limitations and extensions.
Phase-based oscillator model and benchmark questions
Phase dynamics and locking
Following standard phase-based descriptions of oscillator Ising machines [4, 29, 30], we model the analogue solver as a Kuramoto network with second-harmonic injection locking. Related phase-reduced descriptions also arise in gain-dissipative photonic networks, including coupled lasers and nonequilibrium condensates [5, 31].
Oscillator is represented by a continuous phase . We assume identical natural frequencies and work in a frame rotating at their common frequency. For couplings , fields , and fixed locking strength , the deterministic dynamics are generated by the Lyapunov function
The first term describes XY interactions, where positive favours equal phases, while negative favours a phase difference of . The field couples oscillator to a fixed phase reference, favouring for and for .
The second-harmonic term connects the continuous XY model to binary Ising spins. For , it favours , which encode and , respectively. When , this locking reduces the global phase symmetry to a twofold symmetry. At the exact binary configurations, , , and , giving
for from Eq. (1). Thus, locking reshapes the continuous energy landscape while leaving the ordering of binary configurations unchanged. At finite locking strength, we obtain a binary state by rounding each phase to the nearer of and , equivalently setting .
After rescaling the phase-relaxation time, we model the solver trajectories by deterministic gradient descent on the phase-energy landscape,
where is the applied locking schedule. At fixed , the chain rule gives
so the dynamics decrease the programmed phase energy. Here, experimental noise such as gain imbalance, detuning, and other hardware effects would modify the trajectory, but not the certificates once the realised and returned state are specified.
Previous work reports that the best performance is obtained by gradually increasing the locking strength [32, 33]. Following this strategy, our runs begin with an unlocked XY exploration and then ramp . If at the end of the run we look for a binary readout we apply to the final state . This schedule allows the interaction energy to relax before strong locking drives the phases towards binary states.
Returned state and benchmark questions
An analogue run returns a measured phase configuration with energy . We judge it by two questions: one about the continuous landscape the machine actually navigates in, and one about the binary Ising problem encoded.
In the native setting, the dominance question we aim to answer is: How much of phase space is better than the returned state? We measure this by the volume
where is the normalised Haar measure on and is the locking strength at readout. This judges the machine in its own landscape. Because changes with , volumes taken at different are not comparable, so we report only at the realised . At the landscape is the XY objective itself.
On the other hand, we are interested in the number of logical states that improve upon the returned decoded solution. In that case we ask: How many different bit strings are better than the delivered answer? The phases are read out as
with . The resulting bit string is assessed by the count of Eq. (3), the number of Ising configurations whose energy lies at least below . Once , and are fixed, does not depend on . The locking schedule affects it only through which bit string the machine delivers.
The following sections derive rigorous upper bounds on the binary count and on the normalised continuous volume.
Lower bound for the energy
Before bounding the remaining search space, we obtain a lower bound on the optimal energy which can be used complementarily for benchmarking solvers. Writing
the energy of a realised configuration provides an upper bound on . A lower bound follows by expressing the quadratic phase energy with a matrix variable. Let , , and
The matrix is positive semidefinite and satisfies
Furthermore, the energy is linear in the entries of :
The optimisation problem for the optimal energy then reads
Dropping the nonconvex rank-one constraint yields a semidefinite programme (SDP) [34], whose optimal value satisfies . As the resulting matrices need not correspond to individual phase configurations due to potentially larger ranks, this yields a lower bound to the original minimisation problem.
For binary optimisation problems, we instead write and minimise
over with for . The binary and phase PSD matrices therefore have dimensions and , respectively, with scalar normalisation constraints in either case.
These elementary relaxations coincide with the first level of the Lasserre moment-sum-of-squares hierarchy [34, 35]. Higher relaxation orders introduce higher-degree moments and additional constraints, giving a systematic sequence of tighter bounds that converges to the original solution in the binary and toric scenarios considered here. We use only the first level and construct its matrix constraints explicitly in JuMP [36], solving them with MOSEK [37].
The numerical solver output is converted into a certified lower bound by the certification procedure described in Appendix § 1.9. Together with an outward-rounded upper evaluation of the returned energy, this gives the certified interval
The binary energy interval is obtained in the same way.
Counting states below an energy threshold
Chernoff reduction
We are now going to describe how variational Chernoff bounds on event probabilities [27] can be used to obtain bounds on the number of states below a given energy threshold. We are interested in the number of states with energy at most , which we denote by , which is defined in Eq. (3).
The idea is to introduce a probabilistic interpretation and describe as the expectation value of a random variable, and then to apply Markov’s inequality to obtain a tractable quantity. This converts the counting problem into a log-partition-function bound, for which tractable variational upper bounds have been developed [38].
Let be a random variable uniformly distributed on . For any parameter choice , the probability of is equivalent to . Applying Markov’s inequality to the nonnegative random variable therefore gives the exponential bound:
The same bound holds trivially for . Thus any upper bound
implies
Here denotes the natural logarithm.
While the above bound is valid for all , its choice affects the tightness of the bound. Hence, in our implementation, we optimise over a given parameter range. If the exponent is negative for any admissible , the corresponding upper bound on is strictly less than one and hence certifies that no states with energy below exist.
Recursively bounding the partition function
For uniform binary spins, the exponential moment is the normalised Ising partition function:
Thus Eq. (16) becomes . Exact evaluation is intractable in general [39, 40], motivating tractable upper bounds on the log-partition function [38, 41]. Several methods provide rigorous upper bounds on Ising partition functions, including tree-reweighted and log-determinant relaxations [38, 41], convex and entropy-based bounds [42, 43], and approximate elimination schemes [44, 45].
Any rigorous upper bound on the partition function can be inserted into the Chernoff construction to obtain a valid bound on the remaining configurations; the choice of bound affects the tightness and computational cost of the resulting certificate. Here we adopt the recursive quadratic bound of Jaakkola and Jordan [28, 46]. Its explicit recursive updates apply to dense coupling matrices. The parametrisation developed below allows the results of these updates to be reused when varying the Chernoff parameter or the energy threshold . In particular, different returned configurations of the same problem instance can be assessed without repeating the recursive elimination for each configuration. These properties motivate our implementation choice, without implying that this bound is uniformly tighter or faster than the alternatives.
The idea is to compute the expectation value by recursively eliminating single spins, summing over one spin while keeping the remaining spins fixed, and repeating this process. Writing the contribution of spin to the energy as , with
the normalised sum over contributes
to the partition function. Exactly eliminating one spin therefore adds to the exponent, generally introducing interactions beyond the quadratic Ising form. To preserve the original form of the Hamiltonian, to be able to work recursively, Jaakkola and Jordan bound this term by a quadratic envelope with parametrised curvature ,
We evaluate by rigorously enclosing its maximiser and the resulting supremum, with .
At each elimination step, the emerging cosh factor is bounded by a quadratic contribution. Defining where is the curvature of the quadratic bound and is the Chernoff parameter, the terms involving the remaining spins are absorbed into the reduced Ising model through the updates:
where contains the current couplings to the spin being eliminated.
The bounded error shifts the bound at each elimination step by
We use a common curvature across all elimination steps, which gives a fixed parameter , and eliminating spins produces the contribution
where each term is evaluated immediately before eliminating . Together with the final spin’s field , the quantity forms the stored profile. Summing over the final spin exactly yields the final partition function bound
For every and , this expression bounds the logarithm of the normalised partition function at . The stored quantities and depend only on ; the remaining dependence on is explicit. Consequently,
The elimination order affects tightness but not validity. We greedily eliminate the spin with the smallest current , minimising the immediate quadratic contribution.
Numerically, for each in a finite grid , we therefore perform one elimination recursion and store the resulting profile. Once the profiles have been computed for all , each threshold requires only scalar optimisation over and comparison across the stored profiles. For each profile, we minimise the full Chernoff exponent , rather than alone. Selecting the smallest result across gives
The optimal choice of and the selected can therefore depend on , while the stored profiles are reused unchanged. The trivial bound is also included.
Using a common curvature sacrifices the freedom to choose a separate at every step, but makes the matrix recursion (23) depend only on . With step-dependent curvatures, changing an early generally changes all subsequent couplings and requires repeating the recursion. For values of , the implementation for a dense interaction graph requires time and working memory, plus storage for the profiles.
As the above discussion holds in exact arithmetic, numerical errors have to be accounted for when manipulating floating-point numbers. Appendix § 1.9 describes this numerical error control while Appendix § 1.10 specifies the parameter grids, numerical searches, and measured runtimes and memory usage for the numerical section.
Extension to continuous phase space
We now generalise the discrete procedure to bound the volume of continuous phase configurations with energy below . We denote this normalised phase-space volume by , as defined in Eq. (9). Here, the uniform binary measure is replaced by the normalised Haar measure on the torus, with . Thus, , and the volume has the same probabilistic interpretation as the normalised binary count. To bound this volume, we extend the binary elimination procedure to the corresponding continuous partition integral.
For , the event is equivalent to . Applying Markov’s inequality under therefore gives
The bound also holds for . Here is the continuous partition integral with respect to the normalised Haar measure, replacing the normalised binary partition sum. Our task is consequently to upper-bound . As in the binary case, we integrate out one variable at a time and bound the resulting factor by a quadratic envelope that preserves the pairwise model.
For the current complex local field, write
Keeping the remaining phases fixed, exact integration over phase produces the factor
As in the binary case, the resulting marginal energy would change its structure by exactly eliminating a variable. To obtain a quadratic bound in that preserves the pairwise structure during elimination, we proceed in two steps. We first bound the emerging factor independently of the local-field orientation . Using the Fourier-Bessel expansion [47],
where is the modified Bessel function of the first kind of order . For , the coefficients are nonnegative, giving the orientation-independent upper bound
Exact elimination adds to the exponent, generally introducing higher-order interactions. To preserve the pairwise structure, we hence further bound it by a quadratic function of . Define
Then
For each fixed pair , the envelope offset is defined by a one-dimensional maximisation over . It is finite, as implies . This maximisation is distinct from the subsequent minimisation of the Chernoff exponent over .
Writing , the squared local field satisfies
Hence the quadratic envelope adds only constant, field, and pairwise terms when a spin is eliminated and preserves the structure recursively. With a common curvature and , elimination therefore gives the same coupling and field updates as Eq. (23), with replaced by .
These updates depend only on . We therefore choose a finite grid and perform one elimination recursion for each . For each recursion, we store the sum , evaluated using the current fields and couplings, and the final field . Together, these quantities define a profile that can be reused.
For a prescribed locking strength and energy threshold , we then optimise the Chernoff exponent over at each fixed . In our numerical implementation, we evaluate a finite curvature grid and retain the smallest certified upper bound over all evaluated pairs. The parameters and are determined by and are not optimised independently.
Applying the envelope to the first phases and integrating the final phase exactly gives
such that, for and ,
Combining this with Eq. (29), minimising the full Chernoff exponent over , and selecting the smallest result across yields
The continuous envelope is well defined for every . Changing also changes , so the scalar envelope must be evaluated at the corresponding . When , ; for , the second-harmonic term enters through and . Appendix A describes the certified evaluation of and . Our numerical implementation searches a finite curvature grid, as specified together with the tolerances in Appendix B.
Tightness of the relaxations
Combining the Chernoff bound (16) with the elimination bound (27) (and similarly for (38)) introduces two distinct sources of looseness. To separate them, let
denote the exact uniform log-partition function and define
If and , then
Both terms are nonnegative. The first term is present even if the partition function is known exactly, so improving the partition-function bound can reduce only the second.
At intermediate percentiles there is no reason for the Chernoff bound to be exact. Indeed, if , convexity makes optimal, so even the exact partition function returns only the trivial bound .
In general, the Chernoff bound is well suited to the extreme low-energy tail. Under standard large-deviation regularity assumptions, optimisation of the exact log-partition function recovers the leading exponential decay rate of the tail (e.g. the low-energy part of the spectrum), although not generally its finite-size prefactor [48, 49]. At the binary optimum the bound becomes exact: if , then
Thus the Chernoff relaxation can dominate the error at moderate energy ranks, whereas the quality of the partition-function approximation becomes increasingly important in the deepest tail.
This focus on the low-energy tail also matches the practical role of the certificate. For typical or high-energy thresholds, the corresponding state fraction is not rare and can be estimated directly by uniform sampling, with standard binomial confidence intervals [50]. If the target fraction is , the relative sampling error scales as for independent samples; direct sampling therefore becomes costly precisely when the better-than-threshold states are rare. More elaborate sequential Monte Carlo methods can address some rare-event regimes [51], but require an additional sampling construction. We therefore use deterministic certificates for the rare, best-energy part of the landscape, while ordinary sampling remains available for its well-populated bulk.
The continuous phase-volume certificate admits the same separation between Chernoff slack and partition-integral slack, with normalised Haar measure replacing the uniform binary measure. Its target is a volume rather than a count: isolated continuous minima have zero Haar volume, so the binary ground-state degeneracy identity from Eq. (43) does not carry over. The tightness of the continuous certificate, including the additional slack from recursive elimination, is assessed numerically here.
Observable certificates
Besides the energy gap and the number of states, analysing the structure of an energy subspace could yield meaningful operational information. We’re aiming to resolve the remaining search space along observables of the form
where , , and . Useful observables could be magnetisation, cut imbalance, or the overlap with a trial state . In particular, overlap bounds can reveal how many spins must change to obtain a better solution. For binary spins, the Hamming distance between two configurations counts the differing spins and satisfies . Thus, ruling out improving solutions with overlap greater than proves that every improving solution must differ from in at least spins. To quantify the ranges of said observables within a given low-energy subspace, one is interested in computing
Following Wang et al. [52], we use a semidefinite relaxation with an energy upper bound to bound an observable within a given energy sublevel set. Writing , the energy and observable become linear in the matrix entries:
The matrix satisfies , , and rank . Dropping the rank-one constraint gives the SDP
Every binary configuration satisfying produces a feasible matrix, so . This SDP is the first level of the corresponding constrained moment-sum-of-squares hierarchy [34, 35]. For continuous observables quadratic in , the same matrix rewrite gives
Every admissible phase configuration yields a feasible matrix, so this SDP provides an upper bound to the observable within the continuous energy sublevel set. In our implementation we construct the observable SDP with JuMP [36] and solve it using MOSEK [37]. The reported upper bounds are obtained by certifying the numerical dual solution of the problem, as described in Appendix § 1.9.
Counting with an observable constraint
Solving the constrained moment relaxation for Problem (45) certifies that no state in the energy sublevel set exceeds the observable bound. However, it does not say how many states have a specified observable value or how that population changes as the threshold is varied. These questions are the primary purpose of the observable-resolved count we introduce here, first in the binary and then in the continuous case.
For a threshold value , define the joint count
For every , as with the energy count, we apply the Chernoff bound with the uniform base measure and the statistics ,
The elimination remains applicable provided that the observable preserves the pairwise Ising form.
The joint Chernoff bound can be interpreted as an exponential Lagrangian relaxation of the energy and observable constraints [53]. The nonnegative parameters and act as multipliers for the inequalities and , respectively. For , the resulting weight can be written as
This has the form of a generalised Gibbs ensemble, where represents the thermodynamic conjugate to the observable [54]. In particular, when represents the particle number, plays the role of a chemical potential in the grand-canonical ensemble. For other observables such as magnetisation, it can be interpreted as an auxiliary field favouring configurations with larger observable values.
For , the tilted exponent remains quadratic. Since , its Ising parameters are obtained through
retaining zero diagonal for and adding the constant to the exponent. Several observables can be combined with nonnegative multipliers, at the cost of a higher-dimensional scalar search.
For binary states, the joint certificate also yields an upper bound on the observable throughout the energy sublevel set. Let bound from above. (50) then gives
For , the right-hand side is below one whenever
Since is an integer, no configuration can satisfy both constraints at such a threshold. Hence, for a nonempty energy sublevel set,
We retain the smallest bound over the evaluated parameter choices. Thus the observable bound follows directly from the same count certificate, independently of any grid of observable thresholds. Exclusion holds strictly above this bound; equality alone does not certify emptiness.
For the overlap , the same count certificate gives a meaningful flip requirement. Set , with , and define
Every state achieving the prescribed improvement must then differ from in more than spins. The baseline radius zero follows from ; excludes the improvement globally.
In the continuous scenario, for observables already present in the oscillator energy Eq. (5), the unconstrained bound construction can be adapted similarly to the binary case. A phase magnetisation term shifts , a pair correlation shifts , and the binarity observable
simply replaces by in Eqs. (31)–(37). This gives a volume upper bound on phases that are simultaneously low in energy and highly locked.
Numerical evaluation
We evaluate the certificates against exact binary counts and independently sampled continuous sublevel volumes, then apply the certification workflow to simulated analogue-solver outputs at –. Finally, we test observable-resolved counts and compare the resulting observable bounds with a dedicated SDP. The first-order moment relaxations for energy and observable certification are constructed in JuMP and solved with MOSEK [37].
Certificate parameters. We evaluate a small, fixed grid of elimination parameters adapted to the coefficient scale of each instance, and reuse the resulting profiles across energy thresholds. For each profile, we optimise over the curvature , with and additional scalar optimisation in the binary count case. Observable certificates additionally use a fixed grid of tilts . We retain the smallest validated upper bound among the evaluated candidates and the trivial bound. Numerical error control is described in Appendix A. The parameter grids and search settings are specified in Appendix B.
Reference checks and looseness
We consider five instance families. The spin-glass controls are Gaussian Sherrington–Kirkpatrick (SK) couplings , bimodal SK couplings with equal probability, and Gaussian SK couplings with independent fields [55]. The other two families are direct quadratic encodings of weighted Max-Cut and weighted Max-2-SAT [8, 56]. The Max-Cut instances are complete graphs with for . The Max-2-SAT instances contain clauses with uniformly selected distinct variables, independent literal signs, and weights drawn uniformly from .
For binary instances at , exhaustive enumeration gives both the exact sublevel fractions and the partition function. This separates the Chernoff relaxation from the additional quadratic-elimination error.
For continuous instances at , a pilot sample of independent Haar configurations selects energy thresholds at prescribed lower-tail fractions. A fresh sample of configurations estimates the sublevel volumes, with 95% Clopper-Pearson confidence intervals [50]. To assess the error introduced by the Chernoff bound, we also estimate . We select using a separate pilot of configurations, then evaluate the exponential moment at fixed using eight independent batches of configurations. Variation across blocks estimates sampling uncertainty. Note that these Chernoff estimates are diagnostic and do not constitute rigorous bounds.
We observe no violations of the certified upper bounds in either reference check Figure 1. The certificates substantially restrict the state space, although they remain loose relative to the reference fractions. Table I separates the two sources of slack in Eq. (42). At the binary tenth-percentile threshold, the Chernoff step dominates the looseness. At the ground-state threshold , the Chernoff bound computed from the exact partition function is as expected tight.
| threshold | reference fraction | Chernoff | certificate |
| Binary, | |||
| ground level | |||
| 0.1% rank | |||
| 1% rank | |||
| 10% rank | |||
| Continuous, , | |||
| 0.1% target | |||
| 1% target | |||
| 10% target | |||
| Continuous, , | |||
| 0.1% target | |||
| 1% target | |||
| 10% target |
Table I. Median reference fractions and certified bounds. Binary rows use five families and ten seeds per family (, 50 instances); continuous rows use three native XY ensembles and ten seeds per ensemble (, 30 instances per ). Binary reference fractions are exact, and binary Chernoff values use the exact partition function. Continuous reference fractions are Monte Carlo estimates, marked ; separate Chernoff estimates are not reported. The certificate column contains deterministic upper bounds obtained using quadratic elimination.
Figure 1. Calibration against independent references. (a) Exact binary fractions and certified fractions at . For each family and exact-rank threshold, markers show the medians over ten seeds and bands show the interquartile range of the certified fraction. (b) Haar-volume estimates and certified phase fractions at . Each curve displays the median over ten seeds. Markers show medians and bands show interquartile ranges. Horizontal error bars span the medians of the lower and upper endpoints of the per-instance 95% binomial intervals obtained from fresh samples. The diagonal denotes exact equality. Thresholds are fixed by exact rank in (a) and by an independent pilot in (b).
Large instances
We next assess the certificates on dense simulated instances with up to variables, where we assess binary readouts and native continuous states separately. In both cases, the analogue solver selects a candidate energy, and the certificate bounds the state space below that energy. We consider system sizes and ten instance seeds per family. The binary benchmarks use the five families defined above; continuous benchmarks comprise the three corresponding native XY ensembles: Gaussian couplings, bimodal couplings, and Gaussian couplings with random fields.
For each instance, the analogue solver evolves from 64 independent initial phase configurations drawn uniformly from . Each trajectory evolves deterministically for dimensionless time 60 using 3000 forward-Euler steps of size 0.02. The locking protocol and candidate selection depend on the benchmark, as described below.
Binary readouts
For binary optimisation, the locking strength remains zero for the first 35% of the evolution and then increases linearly to . We row every final phase configuration and select the readout with the lowest Ising energy.
At the returned energy , the binary certificate gives an upper bound on the number of configurations satisfying . To compare different system sizes, we report the binary count rate, . This normalisation accounts for the exponential growth of the binary state space: a value certifies at most configurations, or a remaining fraction of at most . A rate of zero
Figure 2. Large binary benchmarks. (a) Binary count rate at the selected binary readout. Lines show medians over ten instance seeds per family and size; bands show the full seed range. (b) Gaps between the returned Ising energies and their SDP lower bounds, divided by . The line shows the median over all five families and ten seeds per family, giving 50 instances at each size; the band shows the full range.
certifies that is the unique ground state, whereas a rate of one gives no improvement over the trivial bound of configurations. Since is itself counted, proves that is the unique ground state; for , the count is even, and proves that and are the only ground states.
At , the largest family-median value of is about 0.52 [Fig. 2(a)]. For an instance with , at most a fraction of all binary configurations match or improve on the returned state. Exponentially many such configurations may remain, and a small count rate does not by itself imply a small energy gap.
The SDP lower bound at relaxation order provides this interval. Its median width grows from 0.160
per spin at to 0.214 at $N = 1000 [Fig. 2(b)]. The width combines the suboptimality of the returned state with the slack of the relaxation. For zero-field Gaussian SK with our normalisation , the optimal first-order SDP value, denoted here by , satisfies [57], while with [58]. Hence, there is an analytical gap between the first order relaxation and the binary optimum which persists even if the analogue solver converged to the global optimum. Our variance differs from the standard convention by an energy scaling factor , leaving both limits unchanged. Hence, a nonzero window per spin persists even for an optimal readout in the above scenario.
Improvement curves At , we vary the required improvement for ten instances of each family, reusing the returned binary states and certificate settings of the experiments above.
Figure 3 shows the binary count rate against the improvement per spin , using 51 equally spaced thresholds spanning . At zero improvement, the medians and seed ranges reproduce the large-instance results. We additionally provide the energy lower bound by the SDP. For each instance, the SDP energy lower bound gives an upper limit on the achievable improvement: no configuration can satisfy when . The SDP lower bound identifies the improvement beyond which no configuration can exist, whereas the count certificate may still return a nonzero upper bound on the number of states in this region. Together, the two certificates bound both the number of configurations achieving a prescribed improvement and the maximum improvement that is possible.
Figure 3. Improvement curves at for all five families, plotted against the required improvement per spin . Thin curves show individual instances; solid curves and shaded bands show the median and full range over ten seeds. Colour-matched dashed vertical lines mark the median of the SDP-derived improvement upper bounds , and vertical bands span its full range over the ten seeds. The curves show the count certificate separately from this SDP exclusion, using the displayed rate . Empty events are certified when the untruncated bound satisfies .
Native continuous states
For continuous optimisation we keep throughout the evolution and select the final configuration with the lowest XY energy . The continuous certificate bounds the normalised Haar volume (9) at , that is, the probability that a uniformly sampled phase configuration matches or improves the returned energy. It is not an attraction-basin volume or a success probability of the optimiser. To compare system sizes, we report ,
Figure 4. Large native continuous benchmarks, with . (a) Per-spin Haar-volume bound at the returned XY energy. Lines show medians over ten seeds per ensemble and size; bands show the full seed range. (b) Gaps between the returned XY energies and their SDP lower bounds, divided by . The line shows the median over three ensembles and ten seeds per ensemble, giving 30 instances at each size; the band shows the full range.
with
Figure 4(a) shows these bounds for the three native XY ensembles. Among the 30 instances at , the least restrictive bound is , a Haar-volume bound of order . As in the binary case this does not show that the returned state is optimal. The SDP energy interval again complements the volume bound, with median width growing from 0.052 per spin at to 0.089 at [Fig. 4(b)].
Observable-resolved counts
Observable-resolved certificates bound how many states satisfy both an energy cutoff and an observable constraint and can hence reveal additional information about the remaining search space. We test this extension using the signed magnetisation .
At , we enumerate all binary configurations for ten instances from each of the five families. For each instance, we fix the energy cutoff at its tenth percentile and compare exact and certified counts satisfying both and the magnetisation bound , where . Dividing both counts by gives the exact and certified joint fractions plotted in Figure 5a. The resulting 350 instance-threshold comparisons include 41 cases with no configuration satisfying both constraints. The certificate proves emptiness in 10 of these cases, with , yielding an observable bound on the energy subspace. All 41 zero-count cases are omitted from the logarithmic axes, leaving 309 points in the figure. Each point represents one instance-threshold pair, coloured by . For each colour, the diamond’s horizontal coordinate is the median exact fraction and its vertical coordinate is the median certified bound across the displayed instances. These medians are taken separately at fixed . All points lie above the equality line, consistent with the bound on every tested instance.
Figure 5(b) shows the logarithmic joint count bound per spin,
(a)
(b)
Figure 5. Observable-resolved certificates. (a) Exact versus certified joint fractions at , with each instance’s energy cutoff fixed at its tenth energy percentile. Both axes show fractions of all binary configurations satisfying and . Colours identify the signed magnetisation thresholds listed in the legend. Circles represent individual instances; diamonds give the coordinate-wise medians of the same-colour points. The dashed line denotes equality. (b) Certified magnetisation profile at for Gaussian SK. Thin curves show individual instances, and the blue line and band show the median and full range over ten instances. Vertical lines show the median count-derived and SDP range bounds, and the corresponding shaded vertical regions show their full ranges over the same ten instances. The count-derived range is obtained from Eq. (54).
where and the observable constraint is . Smaller values indicate tighter bounds on the number of low-energy configurations with large magnetisation. For display, negative rates are set to zero; empty events are identified from the untruncated bound .
At , we evaluate the joint-count bounds at the energy of the returned binary state. We obtain the count-derived magnetisation bound from Eq. (54), with , , and . We divide the resulting observable bound by and retain the smallest upper endpoint over the evaluated parameter choices with , including the physical bound . This uses the same candidates as the joint-count curves but is independent of the plotted magnetisation grid. The median count-derived bound over the ten instances is 0.677, compared with 0.524 for the SDP.
Although the SDP gives a tighter magnetisation bound, the joint-count curves additionally quantify how many low-energy configurations may remain above each magnetisation threshold. They therefore provide information about the population of the energy sublevel set beyond its extremal observable values.
Discussion and outlook
The main contribution of this work is an end-to-end certificate that provides information about the remaining state-space in analogue optimisation. The SDP interval bounds how much improvement remains energetically possible, while the count or volume curve bounds how many states can realise each improvement. We develop tailored methods for bounding the remaining discrete local space as well as the remaining native phase-space. To scale our procedure to experimentally relevant system sizes, we combine Chernoff reductions with controlled partition function bounds by Jaakkola and Jordan which we extend to the continuous scenario. To further characterise the remaining state space, we extend the above certificates to observable-resolved regions therein.
Exact enumeration and independent phase sampling validate the implementation, and the dense tests show that both quantities remain easily computable up to . At this size the binary as well as the continuous certificate can certifiably exclude an exponentially large state space. The observable-resolved counts also give non-trivial statements about the remaining state space and, for binary states, can certify that no configurations satisfy the given constraints. The developed framework therefore offers a complementary work to extremal SDPs, which only certify an interval in which the optimum lives but do not offer access to the count of the states with certain qualities.
The practical relevance of our work is as a calibration layer around an optimiser. Each algorithmic or physical output can be mapped to a certified energy interval and improvement curve. These paired quantities can be used to compare integration times, noise levels, locking schedules, or hardware configurations. They complement success probability and time-to-target measurements by asking a different question: after a state has been returned, how much of the search space can still contain a prescribed improvement?
The numerical results also reveal limitations. At ordinary percentiles, uniform sampling can estimate the state fraction directly and more tightly with binomial confidence intervals [50]; the deterministic certificate is most useful in the rare low-energy tail, where such events are difficult to observe. However, even there, an upper bound may still leave exponentially many states.
The next step is therefore to further tighten the certificate. Possible routes could be to improve the current bound especially improving the hyperparameter optimisation or to compare alternative rigorous partition-function bounds. The preferred choice may depend on the instance structure, the energy range of interest, and the number of threshold queries. Such comparisons could improve the trade-off between certificate tightness and computational cost. For problems mapped to an Ising Hamiltonian, constraint-aware elimination and conditioning hierarchies could tighten the reference space. Higher-order interactions and multistate variables would extend the framework beyond quadratic binary models [59, 60].
Acknowledgements
The authors thank Victor Magron for useful discussions. The authors acknowledge the use of GPT 6 Astra and Claude Opus 5.5 for assistance with brainstorming ideas, code development, and language improvement in the final manuscript. The final content, analysis, mathematical results, and conclusions remain the sole responsibility of the authors.
J.N. acknowledges the support from the EPSRC through PhD studentship EP/W524633/1.
Y.N. acknowledges support by European Union’s HORIZON–MSCA-2023-DN-JD programme under the Horizon Europe (HORIZON) Marie Skłodowska-Curie Actions, grant agreement 101120296 (TENORS), the Government of Spain (Severo Ochoa CEX2019-000910-S, FUNQIP and NextGeneration EU PRTR-C17.I1) and European Union (QSNP, 101114043 and PASQUanS2.1, 101113690), Fundació Cellex, Fundació Mir-Puig, and Generalitat de Catalunya (CERCA program).
N.G.B. acknowledges the support from the HORIZON EIC Pathfinder Challenges project HEISINGBERG (grant 101114978), the Weizmann–UK Make Connection grant (grant 142568), and the EPSRC UK Multidisciplinary Centre for Neuromorphic Computing (grant UKRI982).
Code Availability
The numerical implementation of the count and SDP certificates is publicly available under https://github.com/jonaeg/StateSpaceCountCertificate.
Numerical certification
The discussion on how to obtain bounds on the state count, in the binary as well as in the continuous setting applies in exact arithmetic. When performing the algorithm on a computer using floating-point arithmetic, one hence has to take into account the finite-precision when obtaining rigorous bounds.
Computed scalar floating-point quantities are enclosed rigorously using Arb [61] through python-flint with at least 160-bit precision. Array calculations use double precision, with explicit rounding-error bounds included in the certificates. The SDP solver uses primal-feasibility, dual-feasibility, and relative-gap tolerances of . These tolerances control the numerical search, To certify numerical values we bound the residual errors of each returned candidate, as described below.
Elimination errors. We first describe how to bound the errors which accumulate through the elimination bound to the partition function. At the step eliminating spin , let denote the current stored coefficients, , and the stored coefficients after the update. Define
where the expressions in parentheses are evaluated exactly from the current stored coefficients. We compute an upper bound
Since spin and cosine factors have modulus at most one, we add to the log-partition bound. Squared terms in are enclosed from above. For linear observable bounds, we similarly enclose the difference between the stored tilted field and the exact shift in (52), adding to the log-partition bound.
Rounding in may break the identity used in the elimination updates. We therefore evaluate the envelope using the effective curvature . Since the envelope offset decreases with curvature, we use a lower enclosure of for the offset and an upper enclosure of for the quadratic coefficient. Rounding in changes by at most the error in , since . We include this error in the upper bound.
Scalar envelopes. For the binary envelope, we enclose the positive solution of by interval bisection and evaluate over the resulting interval to bound from above. For , we use .
For the continuous envelope, to preserve an upper bound after truncation of the Fourier-Bessel function (32), we explicitly bound the omitted positive tail at order . The power series for [47] gives
Using and bounding successive terms of by the ratio , the omitted positive tail satisfies
This tail upper bound is added to the truncated sum before taking the logarithm. For , is evaluated directly. The maximum of lies in . Adaptive subdivision uses and hence
to produce a global upper enclosure on the partition integral.
SDP and final bounds. Write the relaxation as minimising over its feasible matrices . Each SDP minimisation problem has an associated dual problem, whose feasible solutions provide lower bounds on the original problem’s optimal value. For a numerical dual solution , define
for binary spins, and
for continuous phases, with the ordering . A dual candidate provides a lower bound only if its slack matrix is positive semidefinite. Numerical solver output may violate this condition slightly, so we bound the violation and correct the reported objective.
For an adequate repair factor we compute an approximate Cholesky factor of and rigorously enclose the residual:
The enclosure accounts for all rounding errors in all matrix operations involved. Here is the maximum absolute row sum. Because . Consequently, for every feasible ,
The normalisation constraints give . Using and , we therefore obtain
as a certified lower energy bound, where we evaluate the expression using outward rounding toward a lower bound.
For magnetisation, we minimise subject to . The energy constraint introduces a nonnegative dual multiplier , giving the slack
Here and represent and under the lifting , and selects the constant moment . Applying the same correction to the dual slack as in the energy case gives a certified lower bound on . Its negative, rounded upward, is the reported observable upper bound.
Numerical settings and computational cost
We now elaborate on the numerical settings used in our computations and computational cost associated with our procedure.
Parameter choices
We set , where
.
For binary counts, we first evaluate the bound at ten equally spaced values of the curvature between 0.06 and 0.50. We also minimise the bound numerically over using a bounded scalar optimiser, with an absolute tolerance of in and a maximum of 80 iterations. We retain the smallest bound obtained.
Continuous volumes use only
without local minimisation. For each threshold, we retain the smallest enclosed Chernoff exponent among the evaluated candidates, including the trivial bound.
For magnetisation bounds, we evaluate the tilted models at
where is the magnetisation weight vector. For each tilt, we choose
using the scale function defined above. We evaluate eight equally spaced curvatures in , without local refinement.
SDP calculation
The first-order moment SDPs are constructed explicitly in JuMP and solved using MOSEK, with one solver thread and primal-feasibility, dual-feasibility, and relative-gap tolerances of . No solver time limit is imposed. The binary and full phase SDPs are solved separately.
Computational cost
For profiles and dense coupling matrix, construction requires time and working memory. Once constructed, the profiles are reused across different energy thresholds, which require only scalar calculations. In a representative Gaussian SK run at (seed 1) on an Apple MacBook Pro (M4 Pro, 24 GiB RAM), using one thread each for BLAS and MOSEK, profile construction took 240 s. Additional binary and continuous threshold queries averaged 0.028 s and 0.00013 s, respectively. The binary SDP calculation, including Julia startup, took 10.9 s, followed by 0.42 s for residual validation. The separate full phase SDP calculation took 30.9 s using the already running Julia worker, followed by 4.81 s for residual validation. Peak sampled process-tree memory across these stages was approximately 2.75 GiB. These are single representative measurements.
References
References
- [1]Y. Yamamoto, K. Aihara, T. Leleu, K.-i. Kawarabayashi, S. Kako, M. Fejer, K. Inoue, and H. Takesue, Coherent Ising machines—optical neural networks operating at the quantum limit, npj Quantum Information 3, 49 (2017).DOI
- [2]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.-i. Kawarabayashi, K. Inoue, S. Utsunomiya, and H. Takesue, A coherent Ising machine for 2000-node optimization problems, Science 354, 603 (2016).pubmed.ncbi.nlm.nih.gov/27811271
- [3]P. L. McMahon, A. Marandi, Y. Haribara, R. Hamelry, C. Langrock, S. Tamate, T. Inagaki, H. Takesue, S. Utsunomiya, K. Aihara, R. L. Byer, M. M. Fejer, H. Mabuchi, and Y. Yamamoto, A fully programmable 100-spin coherent Ising machine with all-to-all connections, Science 354, 614 (2016).
- [4]T. Wang and J. Roychowdhury, OIM: Oscillator-based Ising machines for solving combinatorial optimisation problems, in Unconventional Computation and Natural Computation, Lecture Notes in Computer Science, Vol. 11493 (Springer, 2019) pp. 232–256.arxiv.org/abs/1903.07163
- [5]K. P. Kalinin and N. G. Berloff, Global optimization of spin Hamiltonians with gain-dissipative systems, Scientific Reports 8, 17791 (2018).
- [6]H. Goto, K. Endo, M. Suzuki, Y. Sakai, T. Kanao, Y. Hamakawa, R. Hidaka, M. Yamasaki, and K. Tatsumura, High-performance combinatorial optimization based on classical mechanics, Science Advances 7, eabe7953 (2021).DOI
- [7]N. Mohsen, P. L. McMahon, and T. Byrnes, Ising machines as hardware solvers of combinatorial optimization problems, Nature Reviews Physics 4, 363 (2022).
- [8]A. Lucas, Ising formulations of many NP problems, Frontiers in Physics 2, 5 (2014).DOI
- [9]E. Boros and P. L. Hammer, Pseudo-Boolean optimization, Discrete Applied Mathematics 123, 155 (2002).DOI
- [10]J. King, S. Yarkoni, M. M. Nevison, J. P. Hilton, and C. C. McGeoch, Benchmarking a quantum annealing processor with the time-to-target metric, arXiv:1508.05087 (2015).arxiv.org/abs/1508.05087
- [11]R. Hamerly, T. Inagaki, P. L. McMahon, D. Venturelli, A. Marandi, T. Onodera, E. Ng, C. Langrock, K. Inaba, T. Honjo, K. Enbutsu, T. Umeki, R. Kasahara, S. Utsunomiya, S. Kako, K.-i. Kawarabayashi, R. L. Byer, M. M. Fejer, H. Mabuchi, D. Englund, E. Rieffel, H. Takesue, and Y. Yamamoto, Experimental investigation of performance differences between coherent Ising machines and quantum annealer, Science Advances 5, eaau0823 (2019).
- [12]D. E. Bernal Neira, R. Brown, P. Sathe, F. Wudarski, M. Pavone, E. G. Rieffel, and D. Venturelli, Benchmarking the operation of quantum heuristics and Ising machines: scoring parameter setting strategies on optimization applications, Quantum Machine Intelligence 7, 86 (2025).arxiv.org/abs/2402.10255
- [13]F. Baccari, C. Cologn, P. Wittek, and A. Acín, Verifying the output of quantum optimizers with ground-state energy lower bounds, Physical Review Research 2, 043163 (2020).DOI
- [14]G. Gutin, A. Vainshtein, and A. Yeo, Domination analysis of combinatorial optimization problems, Discrete Applied Mathematics 129, 513 (2003).DOI
- [15]G. Gutin and A. Yeo, Domination analysis of combinatorial optimization algorithms and problems, in Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications, Operations Research/Computer Science Interfaces Series, Vol. 34, edited by M. C. Golumbic and I. B.-A. Hartman (Springer, Boston, 2005) pp. 145–171.DOI
- [16]D. Berend, S. S. Skiena, and Y. Twitto, Combinatorial dominance guarantees for heuristic algorithms, Discrete Mathematics & Theoretical Computer Science Proceedings, 79 (2007).DOI
- [17]N. Alon, G. Gutin, and M. Krivelevich, Algorithms with large domination ratio, Journal of Algorithms 50, 118 (2004).DOI
- [18]A. P. Punnen, P. Sripratak, and D. Karapetyan, Domination analysis of algorithms for bipartite Boolean quadratic programs, in Fundamentals of Computation Theory (FCT 2013), Lecture Notes in Computer Science, Vol. 8070 (Springer, 2013) pp. 271–282.DOI
- [19]D. Berend, S. S. Skiena, and Y. Twitto, Dominance certificates for combinatorial optimization problems, in Optimization Problems in Graph Theory, Springer Optimization and Its Applications, Vol. 139, edited by B. Golden-gorin (Springer, 2018) pp. 107–122.DOI
- [20]F. Wang and D. P. Landau, Efficient, multiple-range random walk algorithm to calculate the density of states, Physical Review Letters 86, 2050 (2001).
- [21]S. Ermon, C. P. Gomes, and B. Selman, Computing the density of states of Boolean formulas, in Principles and Practice of Constraint Programming (CP 2010), Lecture Notes in Computer Science, Vol. 6308 (Springer, 2010) pp. 38–52.DOI
- [22]C. P. Gomes, A. Sabharwal, and B. Selman, Model counting: a new strategy for obtaining good bounds, in Proceedings of the 21st AAAI Conference on Artificial Intelligence (2006) pp. 54–61.
- [23]S. Ermon, C. P. Gomes, A. Sabharwal, and B. Selman, Taming the curse of dimensionality: discrete integration by hashing and optimization, in Proceedings of the 30th International Conference on Machine Learning, PMLR, Vol. 28 (2013) pp. 334–342.arxiv.org/abs/1302.6677
- [24]S. Jain, S. Kadioglu, and M. Sellmann, Upper bounds on the number of solutions of binary integer programs, in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, Vol. 6140 (Springer, 2010) pp. 203–218.DOI
- [25]Y. Mizuno, M. Ali, and T. Komatsuzaki, Enumeration algorithms for combinatorial problems using Ising machines: When should we stop exploring energy landscapes?, arXiv preprint arXiv:2412.00284 (2024).arxiv.org/abs/2412.00284
- [26]T. Sahai, A. Mishra, J. M. Pasini, and S. Jha, Estimating the density of states of Boolean satisfiability problems on classical and quantum computing platforms, in Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34 (2020) pp. 1627–1635.arxiv.org/abs/1910.13088
- [27]R. Pavikumar and J. Lafferty, Variational Chernoff bounds for graphical models, in Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (UAI) (2004) pp. 462–469.
- [28]T. S. Jaakkola and M. I. Jordan, Recursive algorithms for approximating probabilities in graphical models, in Advances in Neural Information Processing Systems 9 (1996) pp. 487–493.
- [29]M. Erementchouk, A. Shukla, and P. Mazumder, On computational capabilities of Ising machines based on nonlinear oscillators, Physica D: Nonlinear Phenomena 437, 133334 (2022).DOI
- [30]S. Steinenberger, Max-Cut via Kuramoto-type oscillators, SIAM Journal on Applied Dynamical Systems 22, 730 (2023).
- [31]K. P. Kalinin and N. G. Berloff, Simulating Ising and n-state planar Potts models and external fields with nonequilibrium condensates, Physical Review Letters 121, 235302 (2018).DOI
- [32]M. Farasat, E. M. H. E. B. Ekanayake, and N. Shukla, Spin freezing in oscillator Ising machines: When second-harmonic injection impedes computation, Physical Review Applied 25, 034038 (2026).
- [33]M. Farasat and N. Shukla, Astroid spinodal boundary in phase-based Ising machines (2026), arXiv:2607.26213 [physics.comp-ph].arxiv.org/abs/2607.26213
- [34]M. Laurent, Sums of squares, moment matrices and optimization over polynomials, in Emerging Applications of Algebraic Geometry, The IMA Volumes in Mathematics and its Applications, Vol. 149, edited by M. Putinar and S. Sullivant (Springer, New York, 2009) pp. 157–270.
- [35]J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization 11, 796 (2001).DOI
- [36]M. Lubin, O. Dowson, J. Dias Garcia, J. Huchette, B. Legat, and J. P. Vielma, JuMP 1.0: Recent improvements to a modeling language for mathematical optimization, Mathematical Programming Computation 10.1007/s12532-023-00239-3 (2023).arxiv.org/abs/2206.03866
- [37]MOSEK ApS, MOSEK Optimizer API for Julia, Version 11.0 (2025).
- [38]M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky, A new class of upper bounds on the log partition function, IEEE Transactions on Information Theory 51, 2313 (2005).
- [39]L. A. Goldberg and M. Jerrum, The complexity of ferromagnetic Ising with local fields, Combinatorics, Probability and Computing 16, 43 (2007).DOI
- [40]S. A. Nagy, R. Paredes, J. M. Dudek, L. Dueñas-Osorio, and M. Y. Vardi, Ising model partition-function computation as a weighted counting problem, Physical Review E 109, 055301 (2024).DOI
- [41]M. J. Wainwright and M. I. Jordan, Log-determinant relaxation for approximate inference in discrete Markov random fields, IEEE Transactions on Signal Processing 54, 2099 (2006).DOI
- [42]L. El Ghaoui and A. Gueye, A convex upper bound on the log-partition function for binary distributions, in Advances in Neural Information Processing Systems 21 (2008) pp. 409–416.
- [43]E. Beyler and F. Bach, Variational inference on the Boolean hypercube with the quantum entropy, in Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 258 (2025) pp. 1153–1161.arxiv.org/abs/2411.03759
- [44]R. Dechter and I. Rish, Mini-buckets: A general scheme for bounded inference, Journal of the ACM 50, 107 (2003).
- [45]Q. Liu and A. T. Ihler, Bounding the partition function using Hölder’s inequality, in Proceedings of the 28th International Conference on Machine Learning (2011) pp. 849–856.
- [46]M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul, An introduction to variational methods for graphical models, Machine Learning 37, 183 (1999).
- [47]NIST Digital Library of Mathematical Functions, Modified bessel functions: Generating function and associated series, DLMF, Sec. 10.35 (2026), accessed 1 October 2026.
- [48]H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, The Annals of Mathematical Statistics 23, 493 (1952).DOI
- [49]S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence (Oxford University Press, 2013).
- [50]C. J. Clopper and E. S. Pearson, The use of confidence or fiducial limits illustrated in the case of the binomial, Biometrika 26, 404 (1934).DOI
- [51]P. Del Moral, A. Doucet, and A. Jasra, Sequential Monte Carlo samplers, Journal of the Royal Statistical Society: Series B 68, 411 (2006).
- [52]J. Wang, J. Surace, I. Frérot, B. Legat, M.-O. Renou, V. Magron, and A. Acín, Certifying ground-state properties of many-body systems, Physical Review X 14, 031006 (2024).DOI
- [53]H. Touchette, The large deviation approach to statistical mechanics, Physics Reports 478, 1 (2009).DOI
- [54]E. T. Jaynes, Information theory and statistical mechanics, Physical Review 106, 620 (1957).DOI
- [55]A. Crisanti and T. Rizzo, Analysis of the ∞-replica symmetry breaking solution of the Sherrington-Kirkpatrick model, Physical Review E 65, 046137 (2002).pubmed.ncbi.nlm.nih.gov/12005956
- [56]M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM 42, 1115 (1995).DOI
- [57]A. Montanari and S. Sen, Semidefinite programs on sparse random graphs and their application to community detection (2015), arXiv:1504.05910 [cs.DM].arxiv.org/abs/1504.05910
- [58]A. Dembo, A. Montanari, and S. Sen, Extremal cuts of sparse random graphs (2015), arXiv:1503.03923 [math.PR].DOI
- [59]C. Bybee, D. Kleyko, D. E. Nikonov, A. Khosrowshahi, B. A. Olshausen, and F. T. Sommer, Efficient optimization with higher-order Ising machines, Nature Communications 14, 6033 (2023).DOI
- [60]Y. Cheng and Z. Lin, From Ising to Potts: Physics-inspired Potts machines of coupled oscillators for low-energy sampling and combinatorial optimization, arXiv preprint arXiv:2507.18379 10.48550/arXiv.2507.18379 (2025).arxiv.org/abs/2507.18379
- [61]F. Johansson, Arb: Efficient arbitrary-precision midpoint-radius interval arithmetic, IEEE Transactions on Computers 66, 1281 (2017).arxiv.org/abs/1611.02831





