Theorem 1 — the hypergraph product of a full-rank (n−k)×n check matrix of an [n,k,d] code with itself has length n²+(n−k)², dimension k², distance d and row weights i+j
ProvedTillichZemor.HGP.theorem_1Let and let be a full-rank binary parity-check matrix of a classical linear code of parameters , where is the minimum distance of ( if ). Let be the hypergraph-product CSS code built from two copies of the Tanner graph of , with check matrices
Then:
- , so is a CSS code;
- its length is ;
- its dimension is ;
- its quantum minimum distance is ;
- every row of and of has weight , where is the weight of a row of and the weight of a column of : row of has weight , and row of has weight .
In particular a family of classical LDPC codes of fixed rate and linear minimum distance gives quantum LDPC codes of fixed rate and minimum distance proportional to .
Formalization Note. "There is a construction … with as building block" is formalized as the specific construction of the paper, the hypergraph product of with itself (p. 18: Theorem 1 is Theorem 15 with ). The hypothesis is added: it is implicit in "", and without it the matrix would have no rows and the dimension claim would fail. The qualifier "LDPC" is a property of families of codes and is not formalized; its finite content is the row-weight clause. The dimension of is not assumed: it follows from the full rank of . The minimum distance takes values in .
import Mathlib import Definitions.Def_CodingTheory import Definitions.Def_TillichZemor_HGP_Setting open Matrix
namespace TillichZemor.HGP
theorem theorem_1 (n k : ℕ) (hk : k ≤ n) (H : Matrix (Fin (n - k)) (Fin n) (ZMod 2))
(hH : H.rank = n - k) :
CodingTheory.dualCode (ZMod 2) ((Fin n × Fin n) ⊕ (Fin (n - k) × Fin (n - k)))
(code (hz H H)) ≤ code (hx H H) ∧
Fintype.card ((Fin n × Fin n) ⊕ (Fin (n - k) × Fin (n - k))) = n ^ 2 + (n - k) ^ 2 ∧
quantumDim H H = k ^ 2 ∧
quantumDist H H = minDist (code H) ∧
(∀ (c : Fin (n - k)) (v : Fin n),
hammingNorm (hx H H (c, v)) = hammingNorm (H c) + hammingNorm (fun c' => H c' v)) ∧
(∀ (v : Fin n) (c : Fin (n - k)),
hammingNorm (hz H H (v, c)) = hammingNorm (fun c' => H c' v) + hammingNorm (H c)) := by sorry
end TillichZemor.HGP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.