Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem A.2 — full addressable Tanner transformation

Open
QuantumCupGates644.ConstantWeight.Supplement.theorem_A_2

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-error-correctionquantum-information

Use the graph, field, r≥2, degree Δ≥2, r local systems and extendable set M of §3.1. Instead of Equation (9), assume an extra local system F^(0), with M extendable for its Tanner code, and

im⁡Fv(0)∗im⁡Fv(1)∗⋯∗im⁡Fv(r−1)⊆im⁡Fv(r).\operatorname{im}\mathcal F^{(0)}_v*\operatorname{im}\mathcal F^{(1)}_v*\cdots*\operatorname{im}\mathcal F^{(r-1)}_v\subseteq\operatorname{im}\mathcal F^{(r)}_v.imFv(0)​∗imFv(1)​∗⋯∗imFv(r−1)​⊆imFv(r)​.

The actual subsystems of Equation (12) support addressable C^(r−1)Z gates with sparsity at most (4Δ)^{r²} and yield at least |M|^r. Logical representatives are chosen once, before all a∈F^s; the resulting logical tensor is the diagonal with coefficients a. Over finite fields the weighted physical trace-phase action is also required.

Under distance and decoder premises only for j=1,…,r, the same subsystems are valid and satisfy

wlocal≤rΔ2,dX≥d(r),dZ≥(2/Δ)r−1∏j<rd(j),ρQ=min⁡{∏j<rρ(j)/Δr−1,ρ(r)}.w_{\mathrm{local}}\le r\Delta^2,\quad d_X\ge d^{(r)},\quad d_Z\ge(2/\Delta)^{r-1}\prod_{j<r}d^{(j)},\quad\rho_Q=\min\{\prod_{j<r}\rho^{(j)}/\Delta^{r-1},\rho^{(r)}\}.wlocal​≤rΔ2,dX​≥d(r),dZ​≥(2/Δ)r−1j<r∏​d(j),ρQ​=min{j<r∏​ρ(j)/Δr−1,ρ(r)}.

Their clock is c_r(T+Δ+|V(Γ)|+1)^{k_r r}, uniformly over the field, graph, systems and inputs. No Equation (9), all-ones condition on F^(0), extra quantum control block, or decoder assumption for F^(0) is inserted.

Differences from the source:

  • encoding: one-based finite coordinate sets and quotient logical spaces → Fin labels and full-preimage logical subspaces; reason: the relabellings are bijective and the published CSS convention represents the same quotients
  • encoding: radius-min{∏ρ^(j)/Δ^(r−1),ρ^(r)} time-poly(Δ,|V|)^r decoding → nonnegative radii, strict error inequalities, and c(T+Δ+|V|+1)^(kr) elementary-operation bounds; reason: c and k depend only on fixed r and precede every graph, field, system and constituent clock T; polynomial constituent clocks specialize to the printed bound
  • generalization: finite directed graphs → finite edge-labelled loopless directed graphs, also allowing parallel edges; reason: the proof uses incidence and total incident degree only; simple source graphs are included without changing any bound
  • generalization: integer minimum-distance parameters → nonnegative real lower bounds for constituent-code distances; reason: substituting the source minimum distances recovers both source bounds; the displayed nonnegative distance expressions are monotone in these lower bounds
Preamble
import Definitions.Def_QuantumCupGates644_ConstantWeight_Supplement_cup
import Definitions.Def_QuantumCupGates644_ConstantWeight_Supplement_decoder
Formal statement
namespace QuantumCupGates644.ConstantWeight.Supplement
open scoped BigOperators
open Classical

theorem theorem_A_2 :
    ∀ r : ℕ, 2 ≤ r → ∃ c k : ℕ, 0 < c ∧ 0 < k ∧
    ∀ (F : Type) [Field F] (G : Graph) (Δ : ℕ), 2 ≤ Δ →
    ∀ (S : Fin r → LocalSystem F G), G.DegreeAtMost Δ →
      (G.LeftToRight ∨ (2 : F) = 0) →
    ∀ (M : Finset (Fin G.ne)), Extendable S M →
    ∀ (S₀ : LocalSystem F G), IsExtendable S₀.tanner M → AddressMultiplication S S₀ →
      AlgebraicAddressable (productSubsystem S) ((4*Δ)^(r^2)) (M.card^r) ∧
      (∀ [Fintype F] (p : ℕ) [Fact p.Prime] [Algebra (ZMod p) F],
        PhysicalAddressable p (productSubsystem S) ((4*Δ)^(r^2)) (M.card^r)) ∧
      ∀ (d ρ : Fin r → NNReal) (T : ℕ),
        (∀ j, DistanceAtLeast (S j).tanner (d j)) →
        (∀ j, DecodesClassical (S j).tanner (ρ j) T) →
        ∀ i, (productSubsystem S i).Valid ∧
          SourceLocality S i (r * (Δ : ℝ)^2) ∧
          (productSubsystem S i).XDistanceAtLeast (xDistanceBound d) ∧
          (productSubsystem S i).ZDistanceAtLeast (zDistanceBound d Δ) ∧
          DecodesQuantum (productSubsystem S i) (radius (fun j => ρ j) Δ)
            (quantumClock c k r Δ G.nv T) := by sorry

end QuantumCupGates644.ConstantWeight.Supplement
Source
Louis Golowich, Itzhak Tamo, Guanyu Zhu, STOC 2027 submission #644 (October 2026); canonical source.pdf, SHA-256 4f5444723e907920327c3fb5432396e702dbb3d8f705e0deeb5bf9b833e17439; Theorem A.2, printed/PDF p.36

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me