betaFeedback

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 N=1000N=1000, even the largest family-median bound restricts the potentially improving binary configurations to less than 10−14410^{-144} of the full configuration space, while the largest upper bound on the corresponding Haar volume is of order 10−49910^{-499}.

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

H(x)=−∑i<jJijxixj−∑ihixi,xi∈{±1}.(1)H(x) = -\sum_{i<j} J_{ij}x_i x_j - \sum_i h_i x_i, \qquad x_i \in\{\pm1\}. \tag*{(1)}

Here NN is the number of variables, the coupling matrix J∈RN×NJ \in\mathbb{R}^{N \times N} is real symmetric with zero diagonal, and h∈RNh \in\mathbb{R}^{N} are the local fields. The global minimisers of HH 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 UU of a returned configuration, such a relaxation gives the rigorous interval

L≤Egs≤U.(2)L \le E_{\mathrm{gs}} \le U. \tag*{(2)}

The interval quantifies how much improvement is energetically possible, but not whether potential improvements occupy half the state space or one configuration in 2N2^N.

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-kk-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 xs∈{±1}Nx^s \in\{\pm1\}^N with energy E=H(xs)E = H(x^s) we consider

CB(E,Δ)=#{x∈{±1}N:H(x)≤E−Δ}.(3)C_{\mathrm{B}}(E,\Delta) = \#\{x \in\{\pm1\}^N : H(x) \le E - \Delta\}. \tag*{(3)}

For a fixed returned state xsx^s, we use the shorthand C(Δ):=CB(H(xs),Δ)C(\Delta) := C_{\mathrm{B}}(H(x^s),\Delta). Thus C(Δ)C(\Delta) counts all configurations that match or improve upon xsx^s by at least Δ\Delta. For Δ=0\Delta= 0 the count includes xsx^s and any degenerate configuration, in particular −xs-x^s if hi=0h_i = 0. The case Δ>0\Delta> 0 is relevant if one is interested in the number of solutions offering a substantial improvement. Since

D(xs):=#{x:H(x)≥H(xs)}≥2N−C(0),(4)D(x^s) := \#\{x : H(x) \ge H(x^s)\} \ge2^N - C(0), \tag*{(4)}

an upper bound on C(0)C(0) gives a lower bound on the domination number D(xs)D(x^s) of the returned state xsx^s, 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 xsx^s only through H(xs)H(x^s), 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 N=1000N = 1000 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 ii is represented by a continuous phase θi∈T:=[0,2π)\theta_i \in\mathbb{T} := [0, 2\pi). We assume identical natural frequencies and work in a frame rotating at their common frequency. For couplings JijJ_{ij}, fields hih_i, and fixed locking strength κ\kappa, the deterministic dynamics are generated by the Lyapunov function

Eκ(θ)=−∑i<jJijcos⁡(θi−θj)−∑ihicos⁡θi−κ2∑icos⁡2θi.(5)\mathcal{E}_{\kappa}(\theta) = - \sum_{i<j} J_{ij}\cos(\theta_i-\theta_j) - \sum_i h_i\cos\theta_i - \frac{\kappa}{2}\sum_i\cos2\theta_i. \tag*{(5)}

The first term describes XY interactions, where positive JijJ_{ij} favours equal phases, while negative JijJ_{ij} favours a phase difference of π\pi. The field hih_i couples oscillator ii to a fixed phase reference, favouring 00 for hi>0h_i > 0 and π\pi for hi<0h_i < 0.

The second-harmonic term connects the continuous XY model to binary Ising spins. For κ>0\kappa> 0, it favours θi∈{0,π}\theta_i \in\{0,\pi\}, which encode xi=+1x_i = +1 and xi=−1x_i = -1, respectively. When h=0h = 0, this locking reduces the global U(1)U(1) phase symmetry to a twofold symmetry. At the exact binary configurations, cos⁡(θi−θj)=xixj\cos(\theta_i-\theta_j) = x_i x_j, cos⁡θi=xi\cos\theta_i = x_i, and cos⁡2θi=1\cos2\theta_i = 1, giving

Eκ(x)=H(x)−Nκ2,(6)\mathcal{E}_{\kappa}(x) = H(x) - \frac{N\kappa}{2}, \tag*{(6)}

for H(x)H(x) 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 00 and π\pi, equivalently setting xi=sign⁡(cos⁡θi)x_i = \operatorname{sign}(\cos\theta_i).

After rescaling the phase-relaxation time, we model the solver trajectories by deterministic gradient descent on the phase-energy landscape,

θ˙i=−∂Eκ(t)∂θi=−∑j≠iJijsin⁡(θi−θj)−hisin⁡θi−κ(t)sin⁡2θi,(7)\begin{aligned} \dot{\theta}_i = -\frac{\partial\mathcal{E}_{\kappa}(t)}{\partial\theta_i} \\ &= -\sum_{j\ne i} J_{ij}\sin(\theta_i-\theta_j) - h_i\sin\theta_i - \kappa(t)\sin2\theta_i, \tag*{(7)} \end{aligned}

where κ(t)\kappa(t) is the applied locking schedule. At fixed κ\kappa, the chain rule gives

dEκdt=∑i∂Eκ∂θiθ˙i=−∑i(∂Eκ∂θi)2≤0,(8)\frac{d\mathcal{E}_{\kappa}}{dt} = \sum_i \frac{\partial\mathcal{E}_{\kappa}}{\partial\theta_i}\dot{\theta}_i = -\sum_i\left(\frac{\partial\mathcal{E}_{\kappa}}{\partial\theta_i}\right)^2 \le0, \tag*{(8)}

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 (J,h,κ)(J,h,\kappa) and returned state are specified.

Previous work reports that the best performance is obtained by gradually increasing the locking strength κ\kappa [32, 33]. Following this strategy, our runs begin with an unlocked XY exploration and then ramp κ(t)\kappa(t). If at the end of the run we look for a binary readout we apply xis=sign⁡(cos⁡θis)x_i^s = \operatorname{sign}(\cos\theta_i^s) to the final state θ\theta. 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 θs∈TN\theta^s \in\mathbb{T}^N with energy Eκ=Eκ(θs)E_\kappa= \mathcal{E}_\kappa(\theta^s). 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

Cκ(Eκ,Δ)=μH{θ∈TN:Eκ(θ)≤Eκ−Δ}.(9)C_\kappa(E_\kappa,\Delta) = \mu_{\mathrm{H}}\left\{\theta\in\mathbb{T}^N : \mathcal{E}_\kappa(\theta) \le E_\kappa-\Delta\right\}. \tag*{(9)}

where μH\mu_{\mathrm{H}} is the normalised Haar measure on TN\mathbb{T}^N and κ\kappa is the locking strength at readout. This judges the machine in its own landscape. Because Eκ\mathcal{E}_\kappa changes with κ\kappa, volumes taken at different κ\kappa are not comparable, so we report CκC_\kappa only at the realised κ\kappa. At κ=0\kappa=0 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

xis=sign⁡(cos⁡θis),(10)x_i^s = \operatorname{sign}(\cos\theta_i^s), \tag*{(10)}

with sign⁡(0)=+1\operatorname{sign}(0)=+1. The resulting bit string is assessed by the count C(Δ)C(\Delta) of Eq. (3), the number of Ising configurations whose energy lies at least Δ\Delta below H(xs)H(x^s). Once xsx^s, JJ and hh are fixed, C(Δ)C(\Delta) does not depend on κ\kappa. The locking schedule affects it only through which bit string the machine delivers.

The following sections derive rigorous upper bounds C^(Δ)\widehat{C}(\Delta) on the binary count and C^κ(Eκ,Δ)\widehat{C}_\kappa(E_\kappa,\Delta) 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

Eκ⋆=min⁡θ∈TNEκ(θ),E_\kappa^\star= \min_{\theta\in\mathbb{T}^N} \mathcal{E}_\kappa(\theta),

the energy of a realised configuration provides an upper bound UκU_\kappa on Eκ⋆E_\kappa^\star. A lower bound follows by expressing the quadratic phase energy with a matrix variable. Let ci=cos⁡θic_i=\cos\theta_i, si=sin⁡θis_i=\sin\theta_i, and

v=(1,c1,…,cN,s1,…,sN)⊤.v=(1,c_1,\ldots,c_N,s_1,\ldots,s_N)^\top.

The matrix Y=vv⊤Y=vv^\top is positive semidefinite and satisfies

Y00=1,Ycici+Ysisi=1,i=1,…,N.(11)Y_{00}=1,\qquad Y_{c_i c_i}+Y_{s_i s_i}=1,\quad i=1,\ldots,N. \tag*{(11)}

Furthermore, the energy is linear in the entries of YY:

Eκ(Y)=−∑i<jJij(Ycicj+Ysisj)−∑ihiY0ci−κ2∑i(Ycici−Ysisi).(12)\mathcal{E}_\kappa(Y)=-\sum_{i<j}J_{ij}(Y_{c_i c_j}+Y_{s_i s_j}) -\sum_i h_iY_{0c_i}-\frac{\kappa}{2}\sum_i(Y_{c_i c_i}-Y_{s_i s_i}). \tag*{(12)}

The optimisation problem for the optimal energy then reads

Eκ⋆=min⁡YEκ(Y)E_\kappa^\star=\min_Y\mathcal{E}_\kappa(Y)
subject toY⪰0,rank⁡Y=1,\text{subject to}\quad Y\succeq0,\qquad\operatorname{rank}Y=1,
Y00=1,Y_{00}=1,
Ycici+Ysisi=1,i=1,…,N.(13)Y_{c_i c_i}+Y_{s_i s_i}=1,\quad i=1,\ldots,N. \tag*{(13)}

Dropping the nonconvex rank-one constraint yields a semidefinite programme (SDP) [34], whose optimal value ℓκ,1\ell_{\kappa,1} satisfies ℓκ,1≤Eκ⋆\ell_{\kappa,1}\le E_\kappa^\star. 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 vB=(1,x)⊤v_{\mathrm{B}}=(1,x)^\top and minimise

H(Y)=−∑i<jJijYij−∑ihiY0i(14)H(Y)=-\sum_{i<j}J_{ij}Y_{ij}-\sum_i h_iY_{0i} \tag*{(14)}

over Y⪰0Y\succeq0 with Yii=1Y_{ii}=1 for i=0,…,Ni=0,\ldots,N. The binary and phase PSD matrices therefore have dimensions N+1N+1 and 2N+12N+1, respectively, with N+1N+1 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 Lκ,1≤ℓκ,1L_{\kappa,1}\le\ell_{\kappa,1} 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

Lκ,1≤Eκ⋆≤Uκ.(15)L_{\kappa,1}\le E_\kappa^\star\le U_\kappa. \tag*{(15)}

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 EE, which we denote by CB(E)≡CB(E,0)C_{\mathrm{B}}(E) \equiv C_{\mathrm{B}}(E,0), which is defined in Eq. (3).

The idea is to introduce a probabilistic interpretation and describe CB(E)C_{\mathrm{B}}(E) 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 XX be a random variable uniformly distributed on {±1}N\{\pm1\}^{N}. For any parameter choice β>0\beta> 0, the probability of H(X)≤EH(X) \le E is equivalent to e−βH(X)≥e−βEe^{-\beta H(X)} \ge e^{-\beta E}. Applying Markov’s inequality to the nonnegative random variable e−βH(X)e^{-\beta H(X)} therefore gives the exponential bound:

CB(E)=2NP[H(X)≤E]≤2NeβEEX[e−βH(X)].(16)\begin{aligned} C_{\mathrm{B}}(E) &= 2^{N}\mathbb{P}[H(X) \le E] \\ &\le2^{N}e^{\beta E}\mathbb{E}_{X}\left[e^{-\beta H(X)}\right]. \tag*{(16)} \end{aligned}

The same bound holds trivially for β=0\beta= 0. Thus any upper bound

B(β)≥log⁡EX[e−βH(X)](17)B(\beta) \ge\log\mathbb{E}_{X}\left[e^{-\beta H(X)}\right] \tag*{(17)}

implies

CB(E)≤exp⁡(Nlog⁡2+βE+B(β)),(18)C_{\mathrm{B}}(E) \le\exp(N\log2 + \beta E + B(\beta)), \tag*{(18)}

Here log⁡\log denotes the natural logarithm.

While the above bound is valid for all β\beta, its choice affects the tightness of the bound. Hence, in our implementation, we optimise over a given parameter range. If the exponent Nlog⁡2+βE+B(β)N\log2 + \beta E + B(\beta) is negative for any admissible β\beta, the corresponding upper bound on CB(E)C_{\mathrm{B}}(E) is strictly less than one and hence certifies that no states with energy below EE exist.

Recursively bounding the partition function

For uniform binary spins, the exponential moment is the normalised Ising partition function:

EX[e−βH(X)]=2−NZB(β),\mathbb{E}_{X}\left[e^{-\beta H(X)}\right] = 2^{-N}Z_{\mathrm{B}}(\beta),
ZB(β)=∑x∈{±1}Ne−βH(x).(19)Z_{\mathrm{B}}(\beta) = \sum_{x\in\{\pm1\}^{N}} e^{-\beta H(x)}. \tag*{(19)}

Thus Eq. (16) becomes CB(E)≤eβEZB(β)C_{\mathrm{B}}(E) \le e^{\beta E}Z_{\mathrm{B}}(\beta). 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 β\beta or the energy threshold EE. 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 ii to the energy as −xibi-x_i b_i, with

bi=hi+∑j≠iJijxj,(20)b_i = h_i + \sum_{j\ne i} J_{ij}x_j, \tag*{(20)}

the normalised sum over xix_i contributes

12∑xi=±1eβxibi=cosh⁡(βbi)(21)\frac{1}{2}\sum_{x_i=\pm1} e^{\beta x_i b_i} = \cosh(\beta b_i) \tag*{(21)}

to the partition function. Exactly eliminating one spin therefore adds log⁡cosh⁡(βbi)\log\cosh(\beta b_i) 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 cc,

log⁡cosh⁡z≤cz2+d(c)with\log\cosh z \le cz^2 + d(c)\quad\text{with}
d(c)=sup⁡z∈R{log⁡cosh⁡z−cz2},0≤c≤12.(22)d(c) = \sup_{z\in\mathbb{R}}\{\log\cosh z-cz^2\},\qquad0\le c\le\frac{1}{2}. \tag*{(22)}

We evaluate d(c)d(c) by rigorously enclosing its maximiser and the resulting supremum, with d(1/2)=0d(1/2)=0.

At each elimination step, the emerging cosh factor is bounded by a quadratic contribution. Defining γ:=2cβ\gamma:= 2c\beta where cc is the curvature of the quadratic bound and β\beta is the Chernoff parameter, the terms involving the remaining spins are absorbed into the reduced Ising model SN×N→S(N−1)×(N−1)\mathbb{S}^{N\times N}\to\mathbb{S}^{(N-1)\times(N-1)} through the updates:

Jjk←Jjk+γvjvk,j<k,j,k≠i,hj←hj+γhivj,j≠i.(23)\begin{aligned} J_{jk} &\leftarrow J_{jk}+\gamma v_jv_k, && j<k,\quad j,k\ne i,\\ h_j &\leftarrow h_j+\gamma h_i v_j, && j\ne i. \tag*{(23)} \end{aligned}

where v=J−i,iv = J_{-i,i} contains the current couplings to the spin being eliminated.

The bounded error shifts the bound at each elimination step by

cβ2(hi2+∥v∥22)+d(c).(24)c\beta^{2}\left(h_i^{2}+\lVert v\rVert_{2}^{2}\right)+d(c). \tag*{(24)}

We use a common curvature cc across all elimination steps, which gives a fixed parameter γ\gamma, and eliminating N−1N-1 spins produces the contribution

S(γ)=∑eliminated i(hi2+∥J−i,i∥22),(25)S(\gamma)=\sum_{\text{eliminated }i}\left(h_i^{2}+\lVert J_{-i,i}\rVert_{2}^{2}\right), \tag*{(25)}

where each term is evaluated immediately before eliminating ii. Together with the final spin’s field hf(γ)h_f(\gamma), the quantity S(γ)S(\gamma) forms the stored profile. Summing over the final spin exactly yields the final partition function bound

BB(γ,c)=γ24cS(γ)+(N−1)d(c)+log⁡cosh⁡(γhf(γ)2c).(26)B_{\mathrm{B}}(\gamma,c)=\frac{\gamma^{2}}{4c}S(\gamma)+(N-1)d(c) +\log\cosh\left(\frac{\gamma h_f(\gamma)}{2c}\right). \tag*{(26)}

For every γ>0\gamma>0 and 0<c≤1/20<c\leq1/2, this expression bounds the logarithm of the normalised partition function at β=γ/(2c)\beta=\gamma/(2c). The stored quantities S(γ)S(\gamma) and hf(γ)h_f(\gamma) depend only on γ\gamma; the remaining dependence on cc is explicit. Consequently,

log⁡EX[e−βH(X)]≤BB(γ,c),β=γ2c.(27)\log\mathbb{E}_{X}\left[e^{-\beta H(X)}\right]\leq B_{\mathrm{B}}(\gamma,c),\qquad\beta=\frac{\gamma}{2c}. \tag*{(27)}

The elimination order affects tightness but not validity. We greedily eliminate the spin with the smallest current hi2+∥J−i,i∥22h_i^{2}+\lVert J_{-i,i}\rVert_{2}^{2}, minimising the immediate quadratic contribution.

Numerically, for each γ\gamma in a finite grid Γ⊂(0,∞)\Gamma\subset(0,\infty), we therefore perform one elimination recursion and store the resulting profile. Once the profiles have been computed for all γ∈Γ\gamma\in\Gamma, each threshold EE requires only scalar optimisation over cc and comparison across the stored profiles. For each profile, we minimise the full Chernoff exponent γE/(2c)+BB(γ,c)\gamma E/(2c)+B_{\mathrm{B}}(\gamma,c), rather than BB(γ,c)B_{\mathrm{B}}(\gamma,c) alone. Selecting the smallest result across γ∈Γ\gamma\in\Gamma gives

CB(E)≤exp⁡[Nlog⁡2+min⁡γ∈Γinf⁡0<c≤1/2{γE2c+BB(γ,c)}].(28)C_{\mathrm{B}}(E)\leq \exp\left[N\log2+\min_{\gamma\in\Gamma}\inf_{0<c\leq1/2} \left\{\frac{\gamma E}{2c}+B_{\mathrm{B}}(\gamma,c)\right\}\right]. \tag*{(28)}

The optimal choice of cc and the selected γ\gamma can therefore depend on EE, while the stored profiles are reused unchanged. The trivial bound CB(E)≤2NC_{\mathrm{B}}(E)\leq2^{N} is also included.

Using a common curvature sacrifices the freedom to choose a separate cic_i at every step, but makes the matrix recursion (23) depend only on γ\gamma. With step-dependent curvatures, changing an early cic_i generally changes all subsequent couplings and requires repeating the recursion. For G=∣Γ∣G=|\Gamma| values of γ\gamma, the implementation for a dense interaction graph requires O(GN3)O(GN^{3}) time and O(N2)O(N^{2}) 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 EkE_k. We denote this normalised phase-space volume by Ck(Ek)≡Ck(Ek,0)C_k(E_k)\equiv C_k(E_k,0), as defined in Eq. (9). Here, the uniform binary measure is replaced by the normalised Haar measure μH\mu_{\mathrm{H}} on the torus, with dμH(θ)=(2π)−Ndθ\mathrm{d}\mu_{\mathrm{H}}(\theta)=(2\pi)^{-N}\mathrm{d}\theta. Thus, 0≤Ck(Ek)≤10\leq C_k(E_k)\leq1, 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 β>0\beta>0, the event Ek(θ)≤Ek\mathcal{E}_k(\theta)\leq E_k is equivalent to e−βEk(θ)≥e−βEke^{-\beta\mathcal{E}_k(\theta)}\geq e^{-\beta E_k}. Applying Markov’s inequality under μH\mu_{\mathrm{H}} therefore gives

Ck(Ek)≤eβEkMT(β),C_k(E_k)\leq e^{\beta E_k}M_{\mathrm{T}}(\beta),
MT(β)=∫TNe−βEk(θ) dμH(θ).(29)M_{\mathrm{T}}(\beta)=\int_{\mathbb{T}^{N}}e^{-\beta\mathcal{E}_k(\theta)}\,\mathrm{d}\mu_{\mathrm{H}}(\theta). \tag*{(29)}

The bound also holds for β=0\beta=0. Here MTM_{\mathrm{T}} 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 log⁡MT\log M_{\mathrm{T}}. 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

Ai=hi+∑j≠iJije−iθj,βAi=re−iϕ,λ=βκ2.(30)A_i=h_i+\sum_{j\neq i}J_{ij}e^{-i\theta_j},\qquad\beta A_i=re^{-i\phi},\qquad\lambda=\frac{\beta\kappa}{2}. \tag*{(30)}

Keeping the remaining phases fixed, exact integration over phase ii produces the factor

Fλ(r,ϕ)=∫02πeλcos⁡(2θ)+rcos⁡(θ−ϕ)dθ2π.(31)F_{\lambda}(r,\phi)=\int_{0}^{2\pi}e^{\lambda\cos(2\theta)+r\cos(\theta-\phi)}\frac{\mathrm{d}\theta}{2\pi}. \tag*{(31)}

As in the binary case, the resulting marginal energy would change its structure by exactly eliminating a variable. To obtain a quadratic bound in ∣Ai∣\lvert A_i\rvert that preserves the pairwise structure during elimination, we proceed in two steps. We first bound the emerging factor independently of the local-field orientation ϕ\phi. Using the Fourier-Bessel expansion [47],

Fλ(r,ϕ)=I0(λ)I0(r)+2∑m≥1Im(λ)I2m(r)cos⁡(2mϕ),(32)F_{\lambda}(r,\phi)=I_0(\lambda)I_0(r)+2\sum_{m\geq1}I_m(\lambda)I_{2m}(r)\cos(2m\phi), \tag*{(32)}

where ImI_m is the modified Bessel function of the first kind of order mm. For λ≥0\lambda\geq0, the coefficients are nonnegative, giving the orientation-independent upper bound

Fλ(r,ϕ)≤Fλ(r,0)=:Fλ(r).(33)F_{\lambda}(r,\phi)\leq F_{\lambda}(r,0)=:F_{\lambda}(r). \tag*{(33)}

Exact elimination adds log⁡Fλ(r,ϕ)\log F_{\lambda}(r,\phi) to the exponent, generally introducing higher-order interactions. To preserve the pairwise structure, we hence further bound it by a quadratic function of r=β∣Ai∣r=\beta|A_i|. Define

dλT(c):=sup⁡r≥0{log⁡Fλ(r)−cr2},c>0.(34)d_{\lambda}^{\mathrm{T}}(c):=\sup_{r\geq0}\{\log F_{\lambda}(r)-cr^2\},\qquad c>0. \tag*{(34)}

Then

log⁡Fλ(r,ϕ)≤cr2+dλT(c).(35)\log F_{\lambda}(r,\phi)\leq cr^2+d_{\lambda}^{\mathrm{T}}(c). \tag*{(35)}

For each fixed pair (λ,c)(\lambda,c), the envelope offset is defined by a one-dimensional maximisation over r≥0r\geq0. It is finite, as Fλ(r)≤eλ+rF_{\lambda}(r)\leq e^{\lambda+r} implies dλT(c)≤λ+1/(4c)d_{\lambda}^{\mathrm{T}}(c)\leq\lambda+1/(4c). This maximisation is distinct from the subsequent minimisation of the Chernoff exponent over cc.

Writing v=J−i,iv=J_{-i,i}, the squared local field satisfies

∣Ai∣2=hi2+∥v∥22+2hi∑jvjcos⁡θj+2∑j<kvjvkcos⁡(θj−θk).(36)|A_i|^2=h_i^2+\lVert v\rVert_2^2+2h_i\sum_jv_j\cos\theta_j+2\sum_{j<k}v_jv_k\cos(\theta_j-\theta_k). \tag*{(36)}

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 cc and γ=2cβ\gamma=2c\beta, elimination therefore gives the same coupling and field updates as Eq. (23), with d(c)d(c) replaced by dλT(c)d_{\lambda}^{\mathrm{T}}(c).

These updates depend only on γ\gamma. We therefore choose a finite grid Γ⊂(0,∞)\Gamma\subset(0,\infty) and perform one elimination recursion for each γ∈Γ\gamma\in\Gamma. For each recursion, we store the sum S(γ)=∑eliminated i(hi2+∥J−i,i∥22)S(\gamma)=\sum_{\mathrm{eliminated}\ i}(h_i^2+\lVert J_{-i,i}\rVert_2^2), evaluated using the current fields and couplings, and the final field hf(γ)h_f(\gamma). Together, these quantities define a profile that can be reused.

For a prescribed locking strength κ≥0\kappa\geq0 and energy threshold EκE_\kappa, we then optimise the Chernoff exponent over c>0c>0 at each fixed γ\gamma. In our numerical implementation, we evaluate a finite curvature grid and retain the smallest certified upper bound over all evaluated (γ,c)(\gamma,c) pairs. The parameters β=γ/(2c)\beta=\gamma/(2c) and λ=γκ/(4c)\lambda=\gamma\kappa/(4c) are determined by cc and are not optimised independently.

Applying the envelope to the first N−1N-1 phases and integrating the final phase exactly gives

BT(γ,c,κ)=γ24cS(γ)+(N−1)dλT(c)+log⁡Fλ(γ∣hf(γ)∣2c),λ=γκ4c,(37)B_{\mathrm{T}}(\gamma,c,\kappa)=\frac{\gamma^2}{4c}S(\gamma)+(N-1)d_{\lambda}^{\mathrm{T}}(c)+\log F_{\lambda}\left(\frac{\gamma|h_f(\gamma)|}{2c}\right),\qquad\lambda=\frac{\gamma\kappa}{4c}, \tag*{(37)}

such that, for κ≥0\kappa\geq0 and γ,c>0\gamma,c>0,

log⁡MT(γ2c)≤BT(γ,c,κ).(38)\log M_{\mathrm{T}}\left(\frac{\gamma}{2c}\right)\leq B_{\mathrm{T}}(\gamma,c,\kappa). \tag*{(38)}

Combining this with Eq. (29), minimising the full Chernoff exponent over c>0c>0, and selecting the smallest result across γ∈Γ\gamma\in\Gamma yields

Cκ(Eκ)≤min⁡{1,exp⁡[min⁡γ∈Γinf⁡c>0{γEκ2c+BT(γ,c,κ)}]}.(39)C_{\kappa}(E_{\kappa})\leq\min\left\{1,\exp\left[\min_{\gamma\in\Gamma}\inf_{c>0}\left\{\frac{\gamma E_{\kappa}}{2c}+B_{\mathrm{T}}(\gamma,c,\kappa)\right\}\right]\right\}. \tag*{(39)}

The continuous envelope is well defined for every c>0c>0. Changing cc also changes λ=γκ/(4c)\lambda=\gamma\kappa/(4c), so the scalar envelope must be evaluated at the corresponding (λ,c)(\lambda,c). When κ=0\kappa=0, F0(r)=I0(r)F_0(r)=I_0(r); for κ>0\kappa>0, the second-harmonic term enters through FλF_{\lambda} and dλT(c)d_{\lambda}^{\mathrm{T}}(c). Appendix A describes the certified evaluation of FλF_{\lambda} and dλTd_{\lambda}^{\mathrm{T}}. 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

Bex(β)=log⁡[Ee−βH(X)].(40)B_{\mathrm{ex}}(\beta)=\log\left[\mathbb{E}e^{-\beta H(X)}\right]. \tag*{(40)}

denote the exact uniform log-partition function and define

ℓZ(E)=N+1log⁡2inf⁡β≥0{βE+Bex(β)},\ell_Z(E)=N+\frac{1}{\log2}\inf_{\beta\geq0}\{\beta E+B_{\mathrm{ex}}(\beta)\},
ℓ^(E)=N+1log⁡2inf⁡β≥0{βE+B(β)}.(41)\widehat{\ell}(E)=N+\frac{1}{\log2}\inf_{\beta\geq0}\{\beta E+B(\beta)\}. \tag*{(41)}

If CB(E)>0C_B(E)>0 and ℓ(E)=log⁡2CB(E)\ell(E)=\log_2 C_B(E), then

ℓ^(E)−ℓ(E)=ℓZ(E)−ℓ(E)⏟Chernoff relaxation+ℓ^(E)−ℓZ(E)⏟log-partition approximation.(42)\widehat{\ell}(E)-\ell(E)=\underbrace{\ell_Z(E)-\ell(E)}_{\text{Chernoff relaxation}}+\underbrace{\widehat{\ell}(E)-\ell_Z(E)}_{\text{log-partition approximation}}. \tag*{(42)}

Both terms are nonnegative. The first term is present even if the partition function is known exactly, so improving the partition-function bound BB can reduce only the second.

At intermediate percentiles there is no reason for the Chernoff bound to be exact. Indeed, if E≥E[H(X)]E \ge\mathbb{E}[H(X)], convexity makes β=0\beta= 0 optimal, so even the exact partition function returns only the trivial bound CB(E)≤2NC_B(E) \le2^N.

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 E=EgsE = E_{\mathrm{gs}}, then

lim⁡β→∞[N+βEgs+Bex(β)log⁡2]=log⁡2#{x:H(x)=Egs}.(43)\lim_{\beta\to\infty}\left[N+\frac{\beta E_{\mathrm{gs}}+B_{\mathrm{ex}}(\beta)}{\log2}\right]=\log_2\#\{x:H(x)=E_{\mathrm{gs}}\}. \tag*{(43)}

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 pp, the relative sampling error scales as (Mp)−1/2(Mp)^{-1/2} for MM 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

O(x)=o0+aTx+12xTKx,(44)O(x)=o_0+a^{\mathsf T}x+\frac{1}{2}x^{\mathsf T}Kx, \tag*{(44)}

where o0∈Ro_0 \in\mathbb{R}, a∈RNa \in\mathbb{R}^N, and K=KT∈RN×NK=K^{\mathsf T}\in\mathbb{R}^{N\times N}. Useful observables could be magnetisation, cut imbalance, or the overlap (xs)Tx(x^s)^{\mathsf T}x with a trial state xsx^s. In particular, overlap bounds can reveal how many spins must change to obtain a better solution. For binary spins, the Hamming distance dH(x,xs)d_H(x,x^s) between two configurations counts the differing spins and satisfies dH(x,xs)=12[N−(xs)Tx]d_H(x,x^s)=\frac{1}{2}[N-(x^s)^{\mathsf T}x]. Thus, ruling out improving solutions with overlap greater than qq proves that every improving solution must differ from xsx^s in at least (N−q)/2(N-q)/2 spins. To quantify the ranges of said observables within a given low-energy subspace, one is interested in computing

Omax⁡(E)=max⁡x O(x)O_{\max}(E)=\max_x\ O(x)
s.t.H(x)≤E,\text{s.t.}\quad H(x)\le E,
xi2=1,i=1,…,N.(45)x_i^2=1,\quad i=1,\ldots,N. \tag*{(45)}

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 Y=(1,x)(1,x)TY=(1,x)(1,x)^{\mathsf T}, the energy and observable become linear in the matrix entries:

H(Y)=−∑i<jJijYij−∑ihiY0i,O(Y)=o0Y00+∑iaiY0i+12∑i,jKijYij.(46)\begin{aligned} H(Y)&=-\sum_{i<j}J_{ij}Y_{ij}-\sum_i h_iY_{0i},\\ O(Y)&=o_0Y_{00}+\sum_i a_iY_{0i}+\frac{1}{2}\sum_{i,j}K_{ij}Y_{ij}. \tag*{(46)} \end{aligned}

The matrix satisfies Y⪰0Y\succeq0, Yii=1Y_{ii}=1, and rank Y=1Y=1. Dropping the rank-one constraint gives the SDP

ω1(E)=max⁡YO(Y)\omega_1(E)=\max_Y\quad O(Y)
subject toY⪰0,Yii=1,i=0,…,N,\text{subject to}\quad Y\succeq0,\quad Y_{ii}=1,\quad i=0,\ldots,N,
H(Y)≤EY00.(47)H(Y)\le EY_{00}. \tag*{(47)}

Every binary configuration satisfying H(x)≤EH(x)\le E produces a feasible matrix, so Omax⁡(E)≤ω1(E)O_{\max}(E)\le\omega_1(E). This SDP is the first level of the corresponding constrained moment-sum-of-squares hierarchy [34, 35]. For continuous observables quadratic in (cos⁡θ,sin⁡θ)(\cos\theta,\sin\theta), the same matrix rewrite gives

ωκ,1T(E)=max⁡YO(Y)\omega_{\kappa,1}^{\mathsf T}(E)=\max_Y\quad O(Y)
subject toY⪰0,Y00=1,\text{subject to}\quad Y\succeq0,\quad Y_{00}=1,
Ycici+Ysisi=1,i=1,…,N,Y_{c_i c_i}+Y_{s_i s_i}=1,\quad i=1,\ldots,N,
Eκ(Y)≤EY00.(48)\mathcal{E}_{\kappa}(Y)\le EY_{00}. \tag*{(48)}

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 oo, define the joint count

CO(E,o)=#{x:H(x)≤E, O(x)≥o}.(49)C_O(E,o)=\#\{x:H(x)\le E,\ O(x)\ge o\}. \tag*{(49)}

For every β,μ≥0\beta,\mu\ge0, as with the energy count, we apply the Chernoff bound with the uniform base measure and the statistics (H,O)(H,O),

CO(E,o)≤2NeβE−μoEexp⁡[−βH(X)+μO(X)].(50)C_O(E,o)\le2^N e^{\beta E-\mu o}\mathbb{E}\exp[-\beta H(X)+\mu O(X)]. \tag*{(50)}

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 β\beta and μ\mu act as multipliers for the inequalities H(x)≤EH(x)\le E and O(x)≥oO(x)\ge o, respectively. For β>0\beta>0, the resulting weight can be written as

e−βH(x)+μO(x)=e−β[H(x)−tO(x)],t=μ/β.(51)e^{-\beta H(x)+\mu O(x)}=e^{-\beta[H(x)-tO(x)]},\qquad t=\mu/\beta. \tag*{(51)}

This has the form of a generalised Gibbs ensemble, where tt represents the thermodynamic conjugate to the observable OO [54]. In particular, when OO represents the particle number, tt 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 β>0\beta>0, the tilted exponent −βH(x)+μO(x)-\beta H(x)+\mu O(x) remains quadratic. Since xi2=1x_i^2=1, its Ising parameters are obtained through

Jij↦Jij+μβKij (i<j),h↦h+μβa,(52)J_{ij}\mapsto J_{ij}+\frac{\mu}{\beta}K_{ij}\ (i<j),\qquad h\mapsto h+\frac{\mu}{\beta}a, \tag*{(52)}

retaining zero diagonal for JJ and adding the constant μ(o0+12tr⁡K)\mu(o_0+\frac{1}{2}\operatorname{tr}K) 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 B^O(β,μ)\widehat{B}_O(\beta,\mu) bound log⁡Eexp⁡[−βH(X)+μO(X)]\log\mathbb{E}\exp[-\beta H(X)+\mu O(X)] from above. (50) then gives

CO(E,o)≤exp⁡[Nlog⁡2+βE+B^O(β,μ)−μo].(53)C_O(E,o)\le\exp\left[N\log2+\beta E+\widehat{B}_O(\beta,\mu)-\mu o\right]. \tag*{(53)}

For μ>0\mu>0, the right-hand side is below one whenever

o>Nlog⁡2+βE+B^O(β,μ)μ.o>\frac{N\log2+\beta E+\widehat{B}_O(\beta,\mu)}{\mu}.

Since CO(E,o)C_O(E,o) is an integer, no configuration can satisfy both constraints at such a threshold. Hence, for a nonempty energy sublevel set,

Omax⁡(E)≤Nlog⁡2+βE+B^O(β,μ)μ.(54)O_{\max}(E)\le\frac{N\log2+\beta E+\widehat{B}_O(\beta,\mu)}{\mu}. \tag*{(54)}

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 O(x)=(xs)TxO(x)=(x^s)^\mathsf{T}x, the same count certificate gives a meaningful flip requirement. Set EΔ=H(xs)−ΔE_\Delta=H(x^s)-\Delta, with Δ>0\Delta>0, and define

rcert(Δ)=max⁡({0}∪{r∈{0,…,N}:C^O(EΔ,N−2r)<1}).(55)r_{\mathrm{cert}}(\Delta)=\max\left(\{0\}\cup\left\{r\in\{0,\ldots,N\}:\widehat{C}_O(E_\Delta,N-2r)<1\right\}\right). \tag*{(55)}

Every state achieving the prescribed improvement must then differ from xsx^s in more than rcertr_{\mathrm{cert}} spins. The baseline radius zero follows from Δ>0\Delta>0; rcert=Nr_{\mathrm{cert}}=N 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 ∑iaicos⁡θi\sum_i a_i\cos\theta_i shifts hh, a pair correlation shifts JJ, and the binarity observable

Obin(θ)=∑icos⁡2θi(56)O_{\mathrm{bin}}(\theta)=\sum_i\cos2\theta_i \tag*{(56)}

simply replaces λ\lambda by λ+μ\lambda+\mu 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 N=250N=250–10001000. 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 cc, with β=γ/(2c)\beta=\gamma/(2c) and additional scalar optimisation in the binary count case. Observable certificates additionally use a fixed grid of tilts t=μ/βt=\mu/\beta. 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 Jij∼N(0,(N−1)−1)J_{ij} \sim\mathcal{N}(0,(N-1)^{-1}), bimodal SK couplings Jij=±(N−1)−1/2J_{ij} = \pm(N-1)^{-1/2} with equal probability, and Gaussian SK couplings with independent fields hi∼N(0,0.32)h_i \sim\mathcal{N}(0,0.3^2) [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 wij=∣gij∣/N−1w_{ij} = |g_{ij}|/\sqrt{N-1} for gij∼N(0,1)g_{ij} \sim\mathcal{N}(0,1). The Max-2-SAT instances contain 8N8N clauses with uniformly selected distinct variables, independent literal signs, and weights drawn uniformly from [0.5,1.5]/8[0.5,1.5]/\sqrt{8}.

For binary instances at N=18N = 18, 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 N=10N = 10, a pilot sample of 10610^6 independent Haar configurations selects energy thresholds at prescribed lower-tail fractions. A fresh sample of 2×1062 \times10^6 configurations estimates the sublevel volumes, with 95% Clopper-Pearson confidence intervals [50]. To assess the error introduced by the Chernoff bound, we also estimate pZ(E)=inf⁡β≥0eβEEμH[e−βκ(θ)]p_Z(E) = \inf_{\beta\ge0} e^{\beta E}\mathbb{E}_{\mu_H}[e^{-\beta\kappa(\theta)}]. We select β\beta using a separate pilot of 2192^{19} configurations, then evaluate the exponential moment at fixed β\beta using eight independent batches of 2182^{18} 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 Egs=min⁡xH(x)E_{\mathrm{gs}} = \min_x H(x), the Chernoff bound computed from the exact partition function is as expected tight.

thresholdreference fractionChernoffcertificate
Binary, N=18N = 18
ground level7.63×10−67.63 \times10^{-6}7.63×10−67.63 \times10^{-6}4.35×10−44.35 \times10^{-4}
0.1% rank1.01×10−31.01 \times10^{-3}6.80×10−36.80 \times10^{-3}1.43×10−21.43 \times10^{-2}
1% rank1.00×10−21.00 \times10^{-2}6.08×10−26.08 \times10^{-2}7.72×10−27.72 \times10^{-2}
10% rank1.00×10−11.00 \times10^{-1}4.32×10−14.32 \times10^{-1}4.63×10−14.63 \times10^{-1}
Continuous, N=10N = 10, κ=0\kappa= 0
0.1% target(9.91×10−4)†(9.91 \times10^{-4})^\dagger(6.33×10−3)†(6.33 \times10^{-3})^\dagger1.14×10−21.14 \times10^{-2}
1% target(1.00×10−2)†(1.00 \times10^{-2})^\dagger(6.05×10−2)†(6.05 \times10^{-2})^\dagger7.41×10−27.41 \times10^{-2}
10% target(1.00×10−1)†(1.00 \times10^{-1})^\dagger(4.33×10−1)†(4.33 \times10^{-1})^\dagger4.63×10−14.63 \times10^{-1}
Continuous, N=10N = 10, κ=0.4\kappa= 0.4
0.1% target(9.96×10−4)†(9.96 \times10^{-4})^\dagger(7.50×10−3)†(7.50 \times10^{-3})^\dagger1.88×10−21.88 \times10^{-2}
1% target(1.00×10−2)†(1.00 \times10^{-2})^\dagger(6.47×10−2)†(6.47 \times10^{-2})^\dagger9.09×10−29.09 \times10^{-2}
10% target(1.00×10−1)†(1.00 \times10^{-1})^\dagger(4.37×10−1)†(4.37 \times10^{-1})^\dagger4.73×10−14.73 \times10^{-1}

Table I. Median reference fractions and certified bounds. Binary rows use five families and ten seeds per family (N=18N = 18, 50 instances); continuous rows use three native XY ensembles and ten seeds per ensemble (N=10N = 10, 30 instances per κ\kappa). Binary reference fractions are exact, and binary Chernoff values use the exact partition function. Continuous reference fractions are Monte Carlo estimates, marked †\dagger; 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 N=18N = 18. 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 N=10N = 10. 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 2×1062 \times10^{6} 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 N=1000N = 1000 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 N∈{250,500,750,1000}N \in\{250, 500, 750, 1000\} 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 TN\mathbb{T}^N. 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 κ=1.2\kappa= 1.2. We row every final phase configuration and select the readout with the lowest Ising energy.

At the returned energy H(xs)H(x^s), the binary certificate gives an upper bound C^B\widehat{C}_{\mathrm{B}} on the number of configurations satisfying H(x)≤H(xs)H(x) \le H(x^s). To compare different system sizes, we report the binary count rate, r^B=min⁡{1,log⁡2C^B/N}\widehat{r}_{\mathrm{B}} = \min\{1,\log_2 \widehat{C}_{\mathrm{B}}/N\}. This normalisation accounts for the exponential growth of the binary state space: a value r^B\widehat{r}_{\mathrm{B}} certifies at most 2Nr^B2^{N\widehat{r}_{\mathrm{B}}} configurations, or a remaining fraction of at most 2−N(1−r^B)2^{-N(1-\widehat{r}_{\mathrm{B}})}. A rate of zero

Figure 2. Large binary benchmarks. (a) Binary count rate r^B\hat r_{\mathrm{B}} 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 NN. 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 xsx^{s} is the unique ground state, whereas a rate of one gives no improvement over the trivial bound of 2N2^{N} configurations. Since xsx^{s} is itself counted, C^B<2\hat C_{\mathrm{B}} < 2 proves that xsx^{s} is the unique ground state; for h=0h = 0, the count is even, and C^B<4\hat C_{\mathrm{B}} < 4 proves that xsx^{s} and −xs-x^{s} are the only ground states.

At N=1000N = 1000, the largest family-median value of r^B\hat r_{\mathrm{B}} is about 0.52 [Fig. 2(a)]. For an instance with r^B≤0.52\hat r_{\mathrm{B}} \le0.52, at most a fraction 2−0.48N2^{-0.48N} 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 d=1d = 1 provides this interval. Its median width grows from 0.160

per spin at N=250N = 250 to 0.214 at $N = 1000 [Fig. 2(b)]. The width U−L=(U−Egs)+(Egs−L)U - L = (U - E_{\mathrm{gs}}) + (E_{\mathrm{gs}} - L) combines the suboptimality of the returned state with the slack of the relaxation. For zero-field Gaussian SK with our normalisation Jij∼N(0,(N−1)−1)J_{ij} \sim\mathcal{N}(0,(N-1)^{-1}), the optimal first-order SDP value, denoted here by ℓf\ell_{\mathrm{f}}, satisfies ℓf/N→−1\ell_{\mathrm{f}}/N \to-1 [57], while Egs/N→−P∗E_{\mathrm{gs}}/N \to-P_{*} with P∗≃0.7632P_{*} \simeq0.7632 [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 (N−1)−1(N-1)^{-1} differs from the standard N−1N^{-1} convention by an energy scaling factor N/(N−1)→1\sqrt{N/(N-1)} \to1, leaving both limits unchanged. Hence, a nonzero window per spin persists even for an optimal readout in the above scenario.

Improvement curves At N=1000N = 1000, we vary the required improvement Δ\Delta 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 r^B(Δ)\hat r_{\mathrm{B}}(\Delta) against the improvement per spin Δ/N\Delta/N, using 51 equally spaced thresholds spanning 0≤Δ/N≤0.250 \le\Delta/N \le0.25. At zero improvement, the medians and seed ranges reproduce the N=1000N = 1000 large-instance results. We additionally provide the energy lower bound by the SDP. For each instance, the SDP energy lower bound L1L_1 gives an upper limit ΔSDPUB:=H(xs)−L1\Delta^{\mathrm{UB}}_{\mathrm{SDP}} := H(x^{s}) - L_1 on the achievable improvement: no configuration can satisfy H(x)≤H(xs)−ΔH(x) \le H(x^{s}) - \Delta when Δ>ΔSDPUB\Delta> \Delta^{\mathrm{UB}}_{\mathrm{SDP}}. 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 N=1000N = 1000 for all five families, plotted against the required improvement per spin Δ/N\Delta/N. 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 ΔSDPUB/N\Delta^{\mathrm{UB}}_{\mathrm{SDP}}/N, 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 r^B(Δ)=max⁡{0,min⁡{1,log⁡2C^(Δ)/N}}\hat{r}_{\mathrm{B}}(\Delta) = \max\{0,\min\{1,\log_{2}\widehat{C}(\Delta)/N\}\}. Empty events are certified when the untruncated bound satisfies C^(Δ)<1\widehat{C}(\Delta) < 1.

Native continuous states

For continuous optimisation we keep κ=0\kappa= 0 throughout the evolution and select the final configuration with the lowest XY energy E0(θs)\mathcal{E}_0(\theta^{s}). The continuous certificate bounds the normalised Haar volume (9) at Δ=0\Delta= 0, 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 q^T=p^T1/N\widehat{q}_{\mathrm{T}} = \widehat{p}_{\mathrm{T}}^{1/N},

Figure 4. Large native continuous benchmarks, with κ=0\kappa= 0. (a) Per-spin Haar-volume bound q^T\widehat{q}_{\mathrm{T}} 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 NN. 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

p^T=min⁡{1,C^0(E0(θs),0)}.(57)\widehat{p}_{\mathrm{T}} = \min\left\{1,\widehat{C}_0\left(\mathcal{E}_0(\theta^{s}),0\right)\right\}. \tag*{(57)}

Figure 4(a) shows these bounds for the three native XY ensembles. Among the 30 instances at N=1000N = 1000, the least restrictive bound is q^T≃0.317\widehat{q}_{\mathrm{T}} \simeq0.317, a Haar-volume bound of order 10−49910^{-499}. 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 N=250N = 250 to 0.089 at N=1000N = 1000 [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 M/N=N−1∑ixiM/N = N^{-1}\sum_i x_i.

At N=16N = 16, we enumerate all binary configurations for ten instances from each of the five families. For each instance, we fix the energy cutoff EE at its tenth percentile and compare exact and certified counts satisfying both H≤EH \le E and the magnetisation bound M/N≥mM/N \ge m, where m∈{0,0.125,0.25,0.375,0.5,0.625,0.75}m \in\{0, 0.125, 0.25, 0.375, 0.5, 0.625, 0.75\}. Dividing both counts by 2162^{16} 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 C^O(E,Nm)<1\hat{C}_{O}(E,Nm) < 1, 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 mm. 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 mm. 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,

Figure 5. Observable-resolved certificates. (a) Exact versus certified joint fractions at N=16N = 16, with each instance’s energy cutoff fixed at its tenth energy percentile. Both axes show fractions of all binary configurations satisfying H≤EH \le E and M/N≥mM/N \ge m. 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 N=250N = 250 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).

R~^B,O(m)=max⁡{0,min⁡{1,log⁡2C^O(E,Nm)/N}}(58)\hat{\tilde{R}}_{B,O}(m) = \max\left\{0,\min\left\{1,\log_2 \hat{C}_{O}(E,Nm)/N\right\}\right\} \tag*{(58)}

where O(x)=M(x)=∑ixiO(x) = M(x) = \sum_i x_i and the observable constraint is M(x)/N≥mM(x)/N \ge m. 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 C^O(E,Nm)<1\hat{C}_{O}(E,Nm) < 1.

At N=250N = 250, 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 O=MO = M, o=Nmo = Nm, and μ=βt\mu= \beta t. We divide the resulting observable bound by NN and retain the smallest upper endpoint over the evaluated parameter choices with t>0t > 0, including the physical bound M/N≤1M/N \le1. 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 N=1000N = 1000. 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 10−810^{-8}. 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 ii, let J,hJ,h denote the current stored coefficients, v=J−i,iv = J_{-i,i}, and J^,h^\hat{J},\hat{h} the stored coefficients after the update. Define

δJjk(i)=J^jk−(Jjk+γvjvk),δhj(i)=h^j−(hj+γhivj),(59)\begin{aligned} \delta J_{jk}^{(i)} &= \hat{J}_{jk} - (J_{jk} + \gamma v_jv_k), \\ \delta h_j^{(i)} &= \hat{h}_j - (h_j + \gamma h_i v_j), \tag*{(59)} \end{aligned}

where the expressions in parentheses are evaluated exactly from the current stored coefficients. We compute an upper bound

εi≥∑j<kj,k≠i∣δJjk(i)∣+∑j≠i∣δhj(i)∣.\varepsilon_i \ge\sum_{\substack{j<k\\j,k\ne i}} |\delta J^{(i)}_{jk}|+\sum_{j\ne i}|\delta h^{(i)}_j|.

Since spin and cosine factors have modulus at most one, we add β∑iεi\beta\sum_i\varepsilon_i to the log-partition bound. Squared terms in S(γ)S(\gamma) are enclosed from above. For linear observable bounds, we similarly enclose the difference δhobs\delta h^{\mathrm{obs}} between the stored tilted field and the exact shift h+(μ/β)ah+(\mu/\beta)a in (52), adding β∑j∣δhjobs∣\beta\sum_j|\delta h^{\mathrm{obs}}_j| to the log-partition bound.

Rounding in β=γ/(2c)\beta=\gamma/(2c) may break the identity 2cβ=γ2c\beta=\gamma used in the elimination updates. We therefore evaluate the envelope using the effective curvature ceff=γ/(2β)c_{\mathrm{eff}}=\gamma/(2\beta). Since the envelope offset decreases with curvature, we use a lower enclosure of ceffc_{\mathrm{eff}} for the offset and an upper enclosure of ceffβ2=βγ/2c_{\mathrm{eff}}\beta^2=\beta\gamma/2 for the quadratic coefficient. Rounding in λ=βκ/2\lambda=\beta\kappa/2 changes log⁡Fλ\log F_\lambda by at most the error in λ\lambda, since ∣∂λlog⁡Fλ∣≤1|\partial_\lambda\log F_\lambda|\le1. We include this error in the upper bound.

Scalar envelopes. For the binary envelope, we enclose the positive solution of tanh⁡z=2cz\tanh z=2cz by interval bisection and evaluate log⁡cosh⁡z−cz2\log\cosh z-cz^2 over the resulting interval to bound d(c)d(c) from above. For c≥1/2c\ge1/2, we use d(c)=0d(c)=0.

For the continuous envelope, to preserve an upper bound after truncation of the Fourier-Bessel function FλF_\lambda (32), we explicitly bound the omitted positive tail at order KK. The power series for ImI_m[47] gives

Im(λ)=∑j≥0qm+2jj!(m+j)!≤qmm!eq2/(m+1),q=λ/2.(60)I_m(\lambda)=\sum_{j\ge0}\frac{q^{m+2j}}{j!(m+j)!}\le\frac{q^m}{m!}e^{q^2/(m+1)}, \qquad q=\lambda/2. \tag*{(60)}

Using I2m(r)≤I0(r)I_{2m}(r)\le I_0(r) and bounding successive terms of ∑m>Kqm/m!\sum_{m>K}q^m/m! by the ratio q/(K+2)q/(K+2), the omitted positive tail satisfies

TK:=2∑m>KIm(λ)I2m(r)≤2I0(r)qK+1eq2/(K+2)(K+1)![1−q/(K+2)],0≤q<K+2.(61)\begin{aligned} T_K&:=2\sum_{m>K}I_m(\lambda)I_{2m}(r)\\ &\le\frac{2I_0(r)q^{K+1}e^{q^2/(K+2)}}{(K+1)!\left[1-q/(K+2)\right]},\\ &\qquad0\le q<K+2. \tag*{(61)} \end{aligned}

This tail upper bound is added to the truncated sum before taking the logarithm. For λ=0\lambda=0, F0(r)=I0(r)F_0(r)=I_0(r) is evaluated directly. The maximum of f(r)=log⁡Fλ(r)−cr2f(r)=\log F_\lambda(r)-cr^2 lies in [0,(2c)−1][0,(2c)^{-1}]. Adaptive subdivision uses f′′≥−2cf''\ge-2c and hence

sup⁡r∈[a,b]f(r)≤max⁡{f(a),f(b)}+c(b−a)24(62)\sup_{r\in[a,b]}f(r)\le\max\{f(a),f(b)\}+\frac{c(b-a)^2}{4} \tag*{(62)}

to produce a global upper enclosure on the partition integral.

SDP and final bounds. Write the relaxation as minimising tr⁡(QY)\operatorname{tr}(QY) over its feasible matrices YY. 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 y=(y0,…,yN)y=(y_0,\ldots,y_N), define

DB(y)=diag⁡(y0,y1,…,yN)D_{\mathrm{B}}(y)=\operatorname{diag}(y_0,y_1,\ldots,y_N)

for binary spins, and

DT(y)=diag⁡(y0,y1,…,yN,y1,…,yN)D_{\mathrm{T}}(y)=\operatorname{diag}(y_0,y_1,\ldots,y_N,y_1,\ldots,y_N)

for continuous phases, with the ordering (1,c,s)(1,c,s). A dual candidate provides a lower bound only if its slack matrix S=Q−D(y)S=Q-D(y) 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 τ\tau we compute an approximate Cholesky factor RR of S−τIS-\tau I and rigorously enclose the residual:

∥S−τI−RTR∥∞≤ρ.\lVert S-\tau I-R^{\mathsf T}R\rVert_\infty\le\rho.

The enclosure accounts for all rounding errors in all matrix operations involved. Here ∥⋅∥∞\lVert\cdot\rVert_\infty is the maximum absolute row sum. Because RTR⪰(τ−ρ)IR^{\mathsf T}R\succeq(\tau-\rho)I. Consequently, for every feasible Y⪰0Y\succeq0,

tr⁡(SY)≥(τ−ρ)tr⁡Y.\operatorname{tr}(SY)\ge(\tau-\rho)\operatorname{tr}Y.

The normalisation constraints give tr⁡(D(y)Y)=∑i=0Nyi\operatorname{tr}(D(y)Y)=\sum_{i=0}^{N}y_i. Using Q=D(y)+SQ=D(y)+S and tr⁡Y=N+1\operatorname{tr}Y=N+1, we therefore obtain

tr⁡(QY)≥∑i=0Nyi+(N+1)(τ−ρ)=:L,\operatorname{tr}(QY)\ge\sum_{i=0}^{N}y_i+(N+1)(\tau-\rho)=:L,

as a certified lower energy bound, where we evaluate the expression using outward rounding toward a lower bound.

For magnetisation, we minimise −O(x)=−aTx-O(x)=-a^{\mathsf T}x subject to H(x)≤EH(x)\le E. The energy constraint introduces a nonnegative dual multiplier λ\lambda, giving the slack

S=Q−O+λ(QH−Ee0e0T)−DB(y).S=Q_{-O}+\lambda(Q_H-Ee_0e_0^{\mathsf T})-D_{\mathrm{B}}(y).

Here QHQ_H and Q−OQ_{-O} represent H(x)H(x) and −O(x)-O(x) under the lifting Y0=(1,x)(1,x)TY_0=(1,x)(1,x)^{\mathsf T}, and e0e_0 selects the constant moment Y00=1Y_{00}=1. Applying the same correction to the dual slack as in the energy case gives a certified lower bound on −O(x)-O(x). 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 γ=g/s(J,h)\gamma= g/s(J,h), where

s(J,h)=max⁡{10−12,∥J∥F2+∥h∥22N},s(J,h)=\max\left\{10^{-12},\sqrt{\frac{\lVert J\rVert_{F}^{2}+\lVert h\rVert_{2}^{2}}{N}}\right\},

g∈{0.08,0.15,0.30,0.60,0.90,1.20}g \in\{0.08,0.15,0.30,0.60,0.90,1.20\}.

For binary counts, we first evaluate the bound at ten equally spaced values of the curvature cc between 0.06 and 0.50. We also minimise the bound numerically over c∈[0.04,0.50]c \in[0.04,0.50] using a bounded scalar optimiser, with an absolute tolerance of 2×10−72 \times10^{-7} in cc and a maximum of 80 iterations. We retain the smallest bound obtained.

Continuous volumes use only

c∈{0.06,0.08,0.11,0.15,0.20,0.25,0.30,0.40,0.50},c \in\{0.06,0.08,0.11,0.15,0.20,0.25,0.30,0.40,0.50\},

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 (J,h+ta)(J,h+ta) at

t∈{0,0.15,0.30,0.60,1.0,1.5},t \in\{0,0.15,0.30,0.60,1.0,1.5\},

where aa is the magnetisation weight vector. For each tilt, we choose

γ=gs(J,h+ta),g∈{0.15,0.30,0.60,0.90},\gamma=\frac{g}{s(J,h+ta)}, \qquad g \in\{0.15,0.30,0.60,0.90\},

using the scale function ss defined above. We evaluate eight equally spaced curvatures in [0.08,0.50][0.08,0.50], 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 10−810^{-8}. No solver time limit is imposed. The binary and full phase SDPs are solved separately.

Computational cost

For GG profiles and dense coupling matrix, construction requires O(GN3)O(GN^{3}) time and O(N2)O(N^{2}) working memory. Once constructed, the profiles are reused across different energy thresholds, which require only scalar calculations. In a representative Gaussian SK run at N=1000N=1000 (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. [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. [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. [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. [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. [5]K. P. Kalinin and N. G. Berloff, Global optimization of spin Hamiltonians with gain-dissipative systems, Scientific Reports 8, 17791 (2018).
  6. [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. [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. [8]A. Lucas, Ising formulations of many NP problems, Frontiers in Physics 2, 5 (2014).DOI
  9. [9]E. Boros and P. L. Hammer, Pseudo-Boolean optimization, Discrete Applied Mathematics 123, 155 (2002).DOI
  10. [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. [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. [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. [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. [14]G. Gutin, A. Vainshtein, and A. Yeo, Domination analysis of combinatorial optimization problems, Discrete Applied Mathematics 129, 513 (2003).DOI
  15. [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. [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. [17]N. Alon, G. Gutin, and M. Krivelevich, Algorithms with large domination ratio, Journal of Algorithms 50, 118 (2004).DOI
  18. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [30]S. Steinenberger, Max-Cut via Kuramoto-type oscillators, SIAM Journal on Applied Dynamical Systems 22, 730 (2023).
  31. [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. [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. [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. [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. [35]J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization 11, 796 (2001).DOI
  36. [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. [37]MOSEK ApS, MOSEK Optimizer API for Julia, Version 11.0 (2025).
  38. [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. [39]L. A. Goldberg and M. Jerrum, The complexity of ferromagnetic Ising with local fields, Combinatorics, Probability and Computing 16, 43 (2007).DOI
  40. [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. [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. [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. [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. [44]R. Dechter and I. Rish, Mini-buckets: A general scheme for bounded inference, Journal of the ACM 50, 107 (2003).
  45. [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. [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. [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. [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. [49]S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence (Oxford University Press, 2013).
  50. [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. [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. [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. [53]H. Touchette, The large deviation approach to statistical mechanics, Physics Reports 478, 1 (2009).DOI
  54. [54]E. T. Jaynes, Information theory and statistical mechanics, Physical Review 106, 620 (1957).DOI
  55. [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. [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. [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. [58]A. Dembo, A. Montanari, and S. Sen, Extremal cuts of sparse random graphs (2015), arXiv:1503.03923 [math.PR].DOI
  59. [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. [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. [61]F. Johansson, Arb: Efficient arbitrary-precision midpoint-radius interval arithmetic, IEEE Transactions on Computers 66, 1281 (2017).arxiv.org/abs/1611.02831

Paper details

vlnc:W_nuq939b8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 12

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT 6 Astra, Claude Opus 5.5

View statement
Looking for related papers…
Contents