Theorem 5.1 (p.19, eqs. (26)–(27)) — bridge from waters_prime
OpenCritWinSpin.p7b_theorem_5_1_from_waters_primecritical-windowp2o-v1reductionspin-systems
Assuming the statement of waters_prime, the full conclusion of Theorem 5.1 (p.19, eqs. (26)–(27)) holds. This isolates the constructions of that section from the prerequisite estimate.
Preamble
import Mathlib import Definitions.Def_CritWinSpin_BinarySource open QAlgorithms.Complexity QuantumPRC set_option autoImplicit false
Formal statement
namespace CritWinSpin
/-- Bridge lemma for Theorem 5.1 (p.19, eqs. (26)–(27)): the target conclusion given waters_prime. -/
theorem p7b_theorem_5_1_from_waters_prime (hP : ∀ (F : BilinearFamily), ∀ d : ℕ, 1 ≤ d → ∀ desc, GenSupport F.gen d desc → (F.q desc).Prime) :
∃ C : ℝ, 0 < C ∧ ∀ F : BilinearFamily, ∃ circ : WatersCircuit F,
PolyBounded circ.n0 ∧ (∀ d, d ^ 2 ≤ circ.n0 d) ∧
(∃ evalF : Str → Str, CookPvsNP.PolyTimeComputable evalF ∧
∀ d, 1 ≤ d → ∀ desc, GenSupport F.gen d desc → ∀ (key : WatersKey F desc d)
(m : Fin d → Bool) (s₁ s₂ : ZMod (F.q desc)), IsValidSig key m s₁ s₂ →
evalF (tupleCode [pkCode F d desc key, List.ofFn m, F.encG desc s₁, F.encG desc s₂]) =
List.ofFn (circ.evalCfg d desc key m s₁ s₂)) ∧
(∀ d, 1 ≤ d → ∀ desc, GenSupport F.gen d desc → ∀ (key : WatersKey F desc d)
(m : Fin d → Bool) (s₁ s₂ : ZMod (F.q desc)), IsValidSig key m s₁ s₂ →
circ.psi d desc key (circ.evalCfg d desc key m s₁ s₂) = m) ∧
(∀ d, 1 ≤ d → ∀ desc, GenSupport F.gen d desc → ∀ (key : WatersKey F desc d)
(y : BinCfg (circ.n0 d)), circ.genLaw d desc key y = unifOn (circ.omega d desc key) y) ∧
SourceProps F circ.toSource C ∧
SourceProps F (hatSource circ.toSource) C ∧
(∀ d, 1 ≤ d → ∀ desc, GenSupport F.gen d desc → ∀ (key : WatersKey F desc d)
(y : BinCfg (circ.n0 d + 1)),
(1 / 2 : ℝ) * ∑ t : Bool, ∑ Y : BinCfg (circ.n0 d), unifOn (circ.omega d desc key) Y *
(if (Fin.cons t (fun i => t == Y i) : BinCfg (circ.n0 d + 1)) = y then (1 : ℝ) else 0) =
unifOn ((hatSource circ.toSource).omega d desc key) y) := 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 5.1 (p.19, eqs. (26)–(27))