Theorem 4.4 — running time of the finite sampler
ProvedCritWinSpin.Implementation.SamplerRuntime.criticalWindowMachine_timecritical-windowsamplerspin-systemstheorem-4-4
Let be a GHS spin law of type , and choose the numerical scale to satisfy the stated scale and integration bounds. The concrete sampler has constants and such that, for every rational instance with
its running time is at most
Here is the encoded instance length. The machine and the constants are fixed before . This is the running-time part of the sampler construction in Theorem 4.4.
Preamble
import Definitions.Def_CritWinSpin_SamplerMachine import Definitions.Def_CritWinSpin_encInst open QAlgorithms.Complexity QAlgorithms.LocalHamiltonian QuantumPRC open CritWinSpin CritWinSpin.LocalTM2.Compiled open CritWinSpin.Implementation.PreprocessIntegral set_option autoImplicit false
Formal statement
namespace CritWinSpin.Implementation.SamplerRuntime
theorem criticalWindowMachine_time (S : SpinLaw) (p : ℕ) (hS : IsGHS S) (hp : IsTypeP S p)
(C : ℕ) (hC8 : 8 ≤ C) (hC : 1000 * (fixedScale S : ℝ) ≤ (C : ℝ))
(hPrecision : 1000 * integrationConstant S ≤ (C : ℝ)) :
∃ (Ctime : ℝ) (k : ℕ), 0 < Ctime ∧ ∀ (N : ℕ) (I : Inst N) (m : ℕ) (δ : ℝ),
I.1.IsSymm → (castM I.1).PosSemidef → 0 ≤ δ →
((tau S*(1+δ)) • (1 : Matrix (Fin N) (Fin N) ℝ)-castM I.1).PosSemidef → 5 ≤ m →
((criticalWindowMachine S C).time (tupleCode [encInst I, encBin m]) : ℝ) ≤
Ctime * ((N : ℝ) + bitLen I + m) ^ k *
Real.exp (Ctime * N * δ ^ ((p : ℝ) / ((p : ℝ)-1))) := by sorry
end CritWinSpin.Implementation.SamplerRuntime
Source
Liu–Zhang–Ren, The Critical Window for Sampling and Learning-to-Sample in Spin Systems, STOC 2027 submission (manuscript sha256 f77584da…), Theorem 4.4, p.17, equation (24). Running-time component of the concrete sampler.