有限精度 TM2 sampler:以凸包损失 N∆s 计费的统一机器
OpenCritWinSpin.sampler_envelope_machinecomplexity-theorysamplingspin-systemstm2
设 是有限有理自旋字母表上的 GHS 单点分布, 为其临界阈值, 为 Lemma 4.2 的凸包损失。存在一台统一随机多栈图灵机 和仅依赖 的 ,使得对每个 、对称有理半正定实例 和整数 ,输入为实例编码与二进制精度参数 时,输出律与 Gibbs 律的总变差距离至多 ,其最坏情况时间 满足
这里 是实例编码位长。同一台机器还满足:对每个 ,若
则
是时间上界的分析参数,并非机器输入;机器由实例自身估计谱界。后一不等式保留原证明中由拒绝试验导致的凸包损失,尚未代入某个熵阶 。
这给出 Theorem 4.4 中公式 (24) 的第一种时间界及枚举分支的粗时间界,把 Langevin 收敛、有限精度实现和统一随机位数的构造与临界指数的实分析分开。
Formalization Note 采用与 Theorem 4.4 相同的 RandMachine、输入编码和输出 decoder。安全余量 给有理谱估计及矩阵分解留出误差;它比原算法中 的累计谱误差大。对于谱界低于 的输入,内部正则化引入的有界额外损失由指数中的 吸收。 时使用唯一空配置。结论中不出现熵阶假设,常数允许依赖固定单点分布。
已退役:保留原先草图,后续沿 CritWinSpin.p4c_4_4_tm2_sampler 继续证明。
Preamble
import Mathlib import Definitions.Def_IsingLTL_BeliefProp_TVDist import Definitions.Def_QAlgorithms_ClassicalBinaryEncoding import Definitions.Def_QuantumPRC_IsPolyFamily import Definitions.Def_CritWinSpin_encInst import Definitions.Def_CritWinSpin_RandMachine import Definitions.Def_CritWinSpin_Wpot open QAlgorithms.LocalHamiltonian QuantumPRC IsingLTL.BeliefProp set_option autoImplicit false
Formal statement
theorem CritWinSpin.sampler_envelope_machine (S : CritWinSpin.SpinLaw)
(hS : CritWinSpin.IsGHS S) :
∃ (M : CritWinSpin.RandMachine) (c : ℝ) (k : ℕ), 0 < c ∧
∀ (N : ℕ) (I : CritWinSpin.Inst N) (m : ℕ),
I.1.IsSymm → (CritWinSpin.castM I.1).PosSemidef → 5 ≤ m →
tvDist (CritWinSpin.outLaw M (tupleCode [CritWinSpin.encInst I, encBin m])
(CritWinSpin.decConfig S N))
(CritWinSpin.gibbsOpt S (CritWinSpin.castM I.1) (CritWinSpin.castV I.2)) ≤
1 / (m : ℝ) ∧
(M.time (tupleCode [CritWinSpin.encInst I, encBin m]) : ℝ) ≤
c * ((N : ℝ) + (CritWinSpin.bitLen I : ℝ) + (m : ℝ)) ^ k *
Real.exp (c * (N : ℝ)) ∧
∀ s : ℝ, CritWinSpin.tau S < s → s ≤ 2 * CritWinSpin.tau S + 1 →
((s - 1 / ((m : ℝ) * ((N : ℝ) + 1))) •
(1 : Matrix (Fin N) (Fin N) ℝ) - CritWinSpin.castM I.1).PosSemidef →
(M.time (tupleCode [CritWinSpin.encInst I, encBin m]) : ℝ) ≤
c * ((N : ℝ) + (CritWinSpin.bitLen I : ℝ) + (m : ℝ)) ^ k *
Real.exp (c * ((N : ℝ) * CritWinSpin.deltaS S s + 1)) := by sorrySource
Liu–Zhang–Ren, The Critical Window for Sampling and Learning-to-Sample in Spin Systems, STOC 2027 submission, manuscript SHA256 f77584dab87d9e6d0936a083a2e3d26476a91a9d73dc303674514a3257c0de95, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/943.pdf, printed pp.16–18 (PDF pp.17–19), §4.2 sampler, Theorem 4.4 eq. (24), first time bound poly·exp(O(K+1)); enumeration branch in proof, printed p.17. Margin reformulation derived from e=1/(8mN).