Lemma 7.1 (p.26, eq. (39)) — bridge from theorem_5_1
ProvedCritWinSpin.p7b_lemma_7_1_from_theorem_5_1critical-windowp2o-v1reductionspin-systems
Assuming the statement of Theorem 5.1 (p.19, eqs. (26)–(27)), the full conclusion of Lemma 7.1 (p.26, eq. (39)) holds. This isolates the constructions of that section from the prerequisite estimate.
Preamble
import Mathlib import Definitions.Def_CritWinSpin_Lhat import Definitions.Def_CritWinSpin_BinarySource set_option autoImplicit false open QAlgorithms.Complexity QuantumPRC
Formal statement
namespace CritWinSpin
open Classical in
/-- Bridge lemma for Lemma 7.1 (p.26, eq. (39)): the target conclusion given Theorem 5.1 (p.19, eqs. (26)–(27)). -/
theorem p7b_lemma_7_1_from_theorem_5_1 (S : SpinLaw) {n r d k T : ℕ} (Ω : Finset (BinCfg n)) (Ψ : BinCfg n → Fin d → Bool)
(hΨ : ∀ m₀ : Fin d → Bool, ∑ y, unifOn Ω y * (if Ψ y = m₀ then (1 : ℝ) else 0) = 1 / (2 : ℝ) ^ d)
(κ : BinCfg n → Option (Config S (Fin n × Fin r)) → ℝ)
(hκ₀ : ∀ y o, 0 ≤ κ y o) (hκ₁ : ∀ y, ∑ o, κ y o = 1)
(Al : (Fin k → Config S (Fin n × Fin r)) → Option (Fin (k + 1) → Config S (Fin n × Fin r)) → ℝ)
(hAl₀ : ∀ X o, 0 ≤ Al X o) (hAl₁ : ∀ X, ∑ o, Al X o = 1) (i : Fin T) (hP : ∃ 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)) :
∑ Fs : Fin T → BinCfg n, prodLaw (unifOn Ω) Fs *
∑ ω : Fin T → Option (Config S (Fin n × Fin r)), (∏ t, κ (Fs t) (ω t)) *
(match lhatRun k ω with
| none => 0
| some R =>
∑ X' : Fin (k + 1) → Config S (Fin n × Fin r), Al (fun j => (R j).2) (some X') *
(if PassEv Ω Ψ X' ∧ (∀ j, (R j).1 ≠ i) ∧
mStar Ψ (fun j => (R j).2) X' = some (Ψ (Fs i)) then (1 : ℝ) else 0)) ≤
1 / (2 : ℝ) ^ d := 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…), Lemma 7.1 (p.26, eq. (39))