Theorem 4.3 — Failure of stable algorithms
OpenDQIShattered.Supplement.theorem_4_3decoded-quantum-interferometrygibbs-samplingglauber-dynamicsp2o-gran-per-chapterp2o-plan-paperp2o-v1random-xorsatshatteringspin-glass
There is an such that, for every , some has the following property. For every , real , and satisfying
there exists , independent of . If is a family of probability-law-valued samplers that is -stable under replacement of one independently sampled clause for a fixed , then
Differences from the source:
- reading: is sufficiently small → Lean states and quantifies every ; reason: this is the standard uniform meaning of “sufficiently small”
- encoding: is -stable for an independent of → Lean represents as one dependent sampler family and places the fixed before the universal quantifier over ; reason: this preserves the source's quantifier order
Preamble
import Mathlib import Definitions.Def_DQIShattered_Supplement_Framework
Formal statement
namespace DQIShattered
namespace Supplement
/-- **Theorem 4.3 (Failure of stable algorithms).**
Zhou, Shutty, Sellke, Jordan, arXiv:2609.40345, held version sha256 0c7f6fdf…,
p.18.
There is a positive meaning of 'sufficiently small' such that, for every eligible `ε`, all
sufficiently large `k`, every `D ≥ k`, and every `β` in (4.4), there is a constant
`ι_* = ι_*(k,D,β,ε) > 0`, independent of `N`. Any distribution-valued sampler family which is
`ι`-stable for one fixed `ι ∈ (0,ι_*]` has strictly positive asymptotic lower normalized-
Wasserstein error from the Gibbs measure. -/
theorem theorem_4_3 :
∃ ε₀ : ℝ, 0 < ε₀ ∧ ∀ ε : ℝ, 0 < ε → ε < ε₀ →
∃ k₀ : ℕ, 3 ≤ k₀ ∧ ∀ k : ℕ, k₀ ≤ k →
∀ D : ℝ, (k : ℝ) ≤ D → ∀ β : ℝ, InHardRange k D ε β →
StableObstruction k D β := by sorry
end Supplement
end DQIShattered
Source
Zhou, Shutty, Sellke, Jordan, Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry, arXiv:2609.40345 (held version sha256 0c7f6fdf…), Theorem 4.3, p.18, eq. (4.4)