op_159_css_ccz_stabilizer_rank_ge_two
For any block length n, if a 3 by n logical matrix K and an s by n stabilizer matrix S over ZMod 2 form a CSS quasi-transversal CCZ code, then the stabilizer rank s is at least 2.
Statement
theorem op_159_css_ccz_stabilizer_rank_ge_two (n s : ℕ)
(K : Matrix (Fin 3) (Fin n) (ZMod 2)) (S : Matrix (Fin s) (Fin n) (ZMod 2))
(h : css_quasi_transversal_ccz_code n s K S) : 2 ≤ s- Related work
- arXiv:2610.09341 Prop. 4.3
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- css_quasi_transversal_ccz_codeA CSS quantum code of block length n specified by a 3 by n logical X-operator matrix K and an s by n X-stabilizer matrix S over ZMod 2 has…
- op_159_css_ccz_no_code_s_zeroFor any block length n, no 3 by n logical X-operator matrix K and 0 by n X-stabilizer matrix S over ZMod 2 form a CSS quasi-transversal…
- op_159_css_ccz_no_code_s_oneFor any block length n, no 3 by n logical X-operator matrix K and 1 by n X-stabilizer matrix S over ZMod 2 form a CSS quasi-transversal…
Read back from the Lean
For all natural numbers $n$ and $s$, and for all matrices $K \in \mathrm{Mat}_{3 \times n}(\mathbb{Z}/2\mathbb{Z})$ and $S \in \mathrm{Mat}_{s \times n}(\mathbb{Z}/2\mathbb{Z})$, if the pair $(K, S)$ forms a CSS quasi-transversal CCZ code (satisfying the CSS $Z$-distance at least 3 condition and the Campbell-Howard conditions), then $s \ge 2$ (the matrix $S$ has at least 2 rows).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by contradiction. If the stabilizer rank s were strictly less than 2, then s would have to be 0 or 1. Both possibilities are ruled out by prior non-existence results, which show that no CSS quasi-transversal CCZ code can have stabilizer rank 0 or 1.
Assume for contradiction that s < 2, reducing the problem to the cases s = 0 and s = 1.
We proceed by contradiction, assuming ¬(2 ≤ s). By linear arithmetic over ℕ, this implies s < 2. Because s is a natural number, an exhaustive case analysis on the interval [0, 2) leaves only two cases: s = 0 and s = 1.
by_contra hlt have hs : s < 2 := by omega interval_cases s
The case s = 0 is impossible.
The auxiliary theorem op_159_css_ccz_no_code_s_zero establishes that no CSS quasi-transversal CCZ code can have stabilizer rank 0, contradicting the hypothesis h.
uses
op_159_css_ccz_no_code_s_zero· exact op_159_css_ccz_no_code_s_zero n K S hThe case s = 1 is impossible, completing the proof.
Similarly, op_159_css_ccz_no_code_s_one proves that no CSS quasi-transversal CCZ code can have stabilizer rank 1, which again contradicts h and closes the final branch.
uses
op_159_css_ccz_no_code_s_one· exact op_159_css_ccz_no_code_s_one n K S h
op_159_css_ccz_no_code_s_zero- There is no CSS quasi-transversal CCZ code with stabilizer rank 0.
op_159_css_ccz_no_code_s_one- There is no CSS quasi-transversal CCZ code with stabilizer rank 1.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Any CSS code of block length n with 3 logical qubits, Z-distance at least 3, and quasi-transversal CCZ must have stabilizer rank s at least 2. -/theorem op_159_css_ccz_stabilizer_rank_ge_two (n s : ℕ) (K : Matrix (Fin 3) (Fin n) (ZMod 2)) (S : Matrix (Fin s) (Fin n) (ZMod 2)) (h : css_quasi_transversal_ccz_code n s K S) : 2 ≤ s := by by_contra hlt have hs : s < 2 := by omega interval_cases s · exact op_159_css_ccz_no_code_s_zero n K S h · exact op_159_css_ccz_no_code_s_one n K S h