Claim 3.8 — subsystem decoder
OpenQuantumCupGates644.ConstantWeight.Supplement.claim_3_8Let Γ be a finite directed graph of total incident degree at most Δ≥2, let F be a field, and let r≥2. Assume Γ is oriented from one bipartition class to the other, or F has characteristic two. Let be the chosen local systems. Let M⊆E(Γ) be extendable for the first r−1 Tanner codes, and assume their local Schur product lies in the rth local image. The codes Q^(i) and protected spaces L^(i) are the actual cyclic tensor construction and Equation (12).
Suppose each classical Tanner code has a radius-ρ^(j) decoder, with elementary-operation clock at most T. There are positive integer constants c_r,k_r, independent of Γ, F, the systems and the received words, such that each selected subsystem has a strict-radius decoder with
Consequently polynomial classical clocks give the paper's polynomial quantum clock. X and Z errors each satisfy the displayed strict radius.
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
import Definitions.Def_QuantumCupGates644_ConstantWeight_Supplement_decoder
namespace QuantumCupGates644.ConstantWeight.Supplement
open scoped BigOperators
open Classical
theorem claim_3_8 :
∀ 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 → Multiplication S →
∀ (ρ : Fin r → NNReal) (T : ℕ),
(∀ j, DecodesClassical (S j).tanner (ρ j) T) →
∀ i, DecodesQuantum (productSubsystem S i) (radius (fun j => ρ j) Δ)
(quantumClock c k r Δ G.nv T) := by sorry
end QuantumCupGates644.ConstantWeight.Supplement