Theorem 1.1(ii) — CDH-hardness of learning-to-sample at
OpenCritWinSpin.theorem_1_1_iicomplexity-theorycryptographylearning-to-samplep2o-v1spin-systems
Let be a single-site GHS distribution of type , with and .
There is a constant such that for every and every bilinear group family satisfying the CDH assumption, there is a PPT family of instances with on sites, , satisfying for all
such that for every PPT algorithm and every polynomially bounded ,
Here and are the sample-extension and sample-amplification errors of Definition 2.2, and is encoded as . The family is chosen independently of and ; the constant is chosen before and the bilinear family. The paper proves this clause from the binary Ising source (Theorem 5.1), the gadget reduction (Theorem 6.3) and the CDH reduction (Theorem 7.2).
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_BilinearFamily import Definitions.Def_CritWinSpin_errExt open QAlgorithms.LocalHamiltonian QuantumPRC OWFLocalDesc IsingLTL.BeliefProp set_option autoImplicit false
Formal statement
namespace CritWinSpin
/-- **Theorem 1.1(ii), CDH-hardness of learning-to-sample in the critical window**
(Liu–Zhang–Ren, *The Critical Window for Sampling and Learning-to-Sample in Spin Systems*,
STOC 2027 submission, manuscript sha256 f77584da…, pp.2–3, eq. (3); Definition 2.2, p.9;
Assumption 2.3, p.10).
Let `ρ` be a single-site GHS distribution of type `p ≥ 2`, `τ = (Var_ρ X)^{-1}`,
`d_p = (p − 1)/p`. There is `C_ρ > 0` such that for every `ε ∈ (0, d_p)` and every bilinear
group family satisfying CDH there is a PPT family of instances with `h = 0` on `N(d)` sites,
`d ≤ N(d) = poly(d)`, satisfying (3), such that for every PPT `A` and polynomially bounded
`k ≥ 1`, both `E_ext(A; k)` and `E_amp(A; k)` are at least `1 − negl(N)`.
The family is chosen before `A` and `k`. In the paper this is proved by the binary Ising source
of Theorem 5.1, the gadget reduction of Theorem 6.3 and the CDH reduction of Theorem 7.2. -/
theorem theorem_1_1_ii (S : SpinLaw) (p : ℕ) (hS : IsGHS S) (hp : IsTypeP S p) :
(∃ Cρ : ℝ, 0 < Cρ ∧ ∀ ε : ℝ, 0 < ε → ε < dExp p → ∀ F : BilinearFamily, CDH F →
∃ (Fam : PPT) (Nf : ℕ → ℕ),
(∀ d, d ≤ Nf d) ∧ PolyBounded Nf ∧
(∀ d, 1 ≤ d → ∀ ω : Fin (Fam.coins.eval (unary d).length) → Bool,
∃ I : Inst (Nf d), Fam.alg (tupleCode [List.ofFn ω, unary d]) = encInst I ∧
I.1.IsSymm ∧ I.2 = 0 ∧ (castM I.1).PosSemidef ∧
((tau S * (1 + (Nf d : ℝ) ^ (-dExp p + ε))) •
(1 : Matrix (Fin (Nf d)) (Fin (Nf d)) ℝ) - castM I.1).PosSemidef ∧
width (castM I.1) (castV I.2) ≤ Cρ) ∧
∀ (A : PPT) (k : ℕ → ℕ), (∀ d, 1 ≤ k d) → PolyBounded k →
(∀ c : ℕ, ∃ d₀ : ℕ, ∀ d ≥ d₀,
1 - errExt S (famLaw Fam (Nf d) d) A (k d) ≤ 1 / (Nf d : ℝ) ^ c) ∧
(∀ c : ℕ, ∃ d₀ : ℕ, ∀ d ≥ d₀,
1 - errAmp S (famLaw Fam (Nf d) d) A (k d) ≤ 1 / (Nf d : ℝ) ^ c)) := by sorry
end CritWinSpin
Source
Liu, Zhang, Ren, The Critical Window for Sampling and Learning-to-Sample in Spin Systems, STOC 2027 submission (manuscript sha256 f77584da…), Theorem 1.1(ii), pp.2–3, eq. (3); Definition 2.2, p.9; Assumption 2.3, p.10; Theorems 5.1, 6.3, 7.2