Theorem 4.4 — exact random-bit semantics of the finite sampler
ProvedCritWinSpin.LocalTM2.Compiled.sampler_retry_lawcritical-windowfinite-random-bitssamplerspin-systemstheorem-4-4
Fix a finite spin law , a scale , and , with alphabet size at most . For a positive-dimensional input on which preprocessing selects the critical branch, let be its prescribed random-bit budget, its prescribed number of trials, and its concrete one-trial word law. Then the decoded output of the compiled machine has exactly the law
The retry operation returns the first successful value from independent trials, or failure if all fail. This equality connects the actual finite random-bit program in Theorem 4.4 to the distribution used by its approximation proof.
Preamble
import Definitions.Def_CritWinSpin_SamplerNumericalData import Definitions.Def_CritWinSpin_SamplerMachine open QAlgorithms.Complexity QAlgorithms.LocalHamiltonian QuantumPRC open CritWinSpin CritWinSpin.LocalTM2.Compiled open CritWinSpin.Implementation CritWinSpin.Implementation.PreprocessPSD open CritWinSpin.Implementation.SamplerDataFacts set_option autoImplicit false
Formal statement
namespace CritWinSpin.LocalTM2.Compiled
theorem sampler_retry_law {N : ℕ} (S : SpinLaw) (C : ℕ) (I : Inst N) (m : ℕ)
(hC : 2 ≤ C) (hm : 1 ≤ m) (hqC : (alphabet S).length ≤ C)
(hN : 0 < N) (hin : preInside S C (encodedInput I.1)=true) :
let F := criticalCoins S C (encodedInput I.1,m)
outLaw (criticalWindowMachine S C) (tupleCode [encInst I,encBin m]) (decConfig S N) =
FiniteRetry.retry (trialWordLaw S C (sampleEulerData S C I m F)
(samplerStepCount S C (sampleReference I m F))) (trials S C I m) := by sorry
end CritWinSpin.LocalTM2.Compiled
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). Exact finite-random-bit implementation and retry semantics of the sampler.