op_159_css_ccz_no_code_s_one
For 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 CCZ code.
Statement
theorem op_159_css_ccz_no_code_s_one (n : ℕ)
(K : Matrix (Fin 3) (Fin n) (ZMod 2)) (S : Matrix (Fin 1) (Fin n) (ZMod 2)) :
¬ css_quasi_transversal_ccz_code n 1 K S- Source
- arXiv:2610.09341 Sec. 4.2
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- css_z_distance_ge_three_iff_colsA CSS quantum code specified by a k by n logical X-operator matrix K and an s by n X-stabilizer matrix S over ZMod 2 has Z-distance at…
- css_z_distance_ge_threeA CSS quantum code specified by a k by n logical X-operator matrix K and an s by n X-stabilizer matrix S over ZMod 2 has Z-distance at…
- campbell_howard_conditionsThe nine Campbell-Howard conditions for a logical X-matrix K of 3 rows and an X-stabilizer matrix S of s rows over ZMod 2: the logical…
- Used by 1
- op_159_css_ccz_stabilizer_rank_ge_twoFor 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,…
Read back from the Lean
For every natural number $n$, every $3 \times n$ matrix $K$ over $\mathbb{Z}/2\mathbb{Z}$, and every $1 \times n$ matrix $S$ over $\mathbb{Z}/2\mathbb{Z}$, $(K, S)$ is not a CSS quasi-transversal CCZ code with parameters $n$ and $s = 1$. That is, $K$ and $S$ cannot simultaneously satisfy both the CSS $Z$-distance $\ge 3$ condition and the Campbell–Howard conditions.
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 proof proceeds by contradiction. If such a CSS code existed, its Z-distance would be at least 3, which implies that the columns of the logical matrix K are completely determined by the columns of the stabilizer matrix S: zero columns of S force zero columns of K, and duplicate columns of S force duplicate columns of K. Since S has rank s = 1, its columns have only two possible values (0 or 1), so every column of K is either zero or equal to a fixed column vector v. In all cases, the triple product of logical operators ∑ j, K 0 j * K 1 j * K 2 j factors through the stabilizer sum ∑ j, S 0 j = 0 and must vanish, directly contradicting the Campbell-Howard condition that requires this sum to equal 1.
Any vector in (ZMod 2)¹ whose single coordinate is 0 is the zero vector.
Since the index type Fin 1 contains only 0, a vector f : Fin 1 → ZMod 2 with f 0 = 0 evaluates to 0 everywhere and is therefore 0 by function extensionality.
have fin1_eq_zero : ∀ (f : Fin 1 → ZMod 2), f 0 = 0 → f = 0 := by intro f h ext ⟨i, hi⟩ have : i = 0 := by omega subst this exact h
Two vectors in (ZMod 2)¹ that agree at index 0 are equal.
Since 0 is the only index in Fin 1, any two functions f, g : Fin 1 → ZMod 2 agreeing at 0 agree on their entire domain, so f = g by function extensionality.
have fin1_eq : ∀ (f g : Fin 1 → ZMod 2), f 0 = g 0 → f = g := by intro f g h ext ⟨i, hi⟩ have : i = 0 := by omega subst this exact h
Assume for contradiction that a code exists, extracting the column-dependence conditions from the distance bound and the stabilizer condition ∑ j, S 0 j = 0.
Assume (K, S) forms a CSS quasi-transversal CCZ code. Applying css_z_distance_ge_three_iff_cols to the distance condition provides two column-dependency properties: any column j with Sᵀ j = 0 must have Kᵀ j = 0, and any distinct columns i ≠ j with Sᵀ i = Sᵀ j must have Kᵀ i = Kᵀ j. From the Campbell-Howard conditions, the triple product satisfies ∑ j, K 0 j * K 1 j * K 2 j = 1 and the single stabilizer generator satisfies ∑ j, S 0 j = 0.
uses
css_z_distance_ge_three_iff_colsintro ⟨hdist, hCH⟩ rcases (css_z_distance_ge_three_iff_cols K S).mp hdist with ⟨hzero, heq⟩ rcases hCH with ⟨_, _, hK3, _, _, _, hS1, _, _⟩ have hS1_0 : ∑ j : Fin n, S 0 j = 0 := hS1 0
Every element x ∈ ZMod 2 satisfies x³ = x and is either 0 or 1. automation
In ZMod 2, the only elements are 0 and 1, both of which satisfy x * x * x = x and x = 0 ∨ x = 1. Both statements are verified by exhaustive case checking via decide.
have hz_cube : ∀ x : ZMod 2, x * x * x = x := by decide have hz_cases : ∀ x : ZMod 2, x = 0 ∨ x = 1 := by decide
Split into cases on whether S has any non-zero entry, fixing a column j₀ with S 0 j₀ = 1 and setting v = Kᵀ j₀ in the positive case.
We branch on whether there exists some index j₀ such that S 0 j₀ = 1. In the positive branch, we fix such a witness j₀ and define v as column j₀ of K.
by_cases hex : ∃ j0 : Fin n, S 0 j0 = 1 · rcases hex with ⟨j0, hj0⟩ set v := K.transpose j0
In the positive case, every entry of K factors as K i j = v i * S 0 j.
For any column j, S 0 j is either 0 or 1. If S 0 j = 0, then column j of S is zero by fin1_eq_zero, so column j of K is zero by distance, giving K i j = 0 = v i * 0 using congr_fun and mul_zero. If S 0 j = 1, column j of S equals column j₀ of S by fin1_eq and Matrix.transpose_apply; whether j = j₀ or j ≠ j₀, the distance condition forces Kᵀ j = v, giving K i j = v i = v i * 1 using congr_fun and mul_one.
uses
congr_fun,Matrix.transpose_apply,mul_one,mul_zerohave hK : ∀ (i : Fin 3) (j : Fin n), K i j = v i * S 0 j := by intro i j rcases hz_cases (S 0 j) with hs0 | hs1 · have : S.transpose j = 0 := fin1_eq_zero (S.transpose j) hs0 have : K.transpose j = 0 := hzero j this have : K i j = 0 := congr_fun this i rw [this, hs0, mul_zero] · have hSeq : S.transpose j = S.transpose j0 := fin1_eq (S.transpose j) (S.transpose j0) (by rw [Matrix.transpose_apply, Matrix.transpose_apply, hs1, hj0]) have hKeq : K.transpose j = v := by by_cases hjj : j = j0 · rw [hjj] · exact heq j j0 hjj hSeq have : K i j = v i := congr_fun hKeq i rw [this, hs1, mul_one]
The term-by-term product of the three logical operators simplifies to K 0 j * K 1 j * K 2 j = (v 0 * v 1 * v 2) * S 0 j.
Substituting K i j = v i * S 0 j for i = 0, 1, 2 into the product yields (v 0 * S 0 j) * (v 1 * S 0 j) * (v 2 * S 0 j) = (v 0 * v 1 * v 2) * (S 0 j)³ by ring arithmetic. Because (S 0 j)³ = S 0 j in ZMod 2, this reduces to (v 0 * v 1 * v 2) * S 0 j.
have hterm : ∀ j : Fin n, K 0 j * K 1 j * K 2 j = (v 0 * v 1 * v 2) * S 0 j := by intro j rw [hK 0 j, hK 1 j, hK 2 j] have : (v 0 * S 0 j) * (v 1 * S 0 j) * (v 2 * S 0 j) = (v 0 * v 1 * v 2) * (S 0 j * S 0 j * S 0 j) := by ring rw [this, hz_cube]
Summing over all columns gives 0, contradicting the condition that the sum is 1. automation
Distributing the sum over columns using Finset.mul_sum factors the sum as (v 0 * v 1 * v 2) * ∑ j, S 0 j. Because the stabilizer sum is zero, multiplying by zero via mul_zero shows the whole sum is 0. Substituting this into the Campbell-Howard condition yields 0 = 1, which decide refutes to close this branch.
uses
Finset.mul_sum,mul_zerohave hsum : (∑ j : Fin n, K 0 j * K 1 j * K 2 j) = (v 0 * v 1 * v 2) * ∑ j : Fin n, S 0 j := by simp_rw [hterm] rw [← Finset.mul_sum] rw [hS1_0, mul_zero] at hsum rw [hsum] at hK3 revert hK3; decide
In the negative case where no entry of S is 1, row 0 of K is identically zero.
Since no column has S 0 j = 1, every S 0 j must equal 0 (ruling out 1 via False.elim). Thus every column of S is zero by fin1_eq_zero, which by the distance condition implies every column of K is zero. Applying congr_fun shows K 0 j = 0 for every j.
uses
False.elim,congr_fun· have hKzero : ∀ j : Fin n, K 0 j = 0 := by intro j have hs : S 0 j = 0 := by rcases hz_cases (S 0 j) with h0 | h1 · exact h0 · exact False.elim (hex ⟨j, h1⟩) have : S.transpose j = 0 := fin1_eq_zero (S.transpose j) hs have : K.transpose j = 0 := hzero j this exact congr_fun this 0
The sum over all columns vanishes, yielding a contradiction in the second branch. automation
Because K 0 j = 0 for every column j, each summand K 0 j * K 1 j * K 2 j is zero by zero_mul. The sum of zeroes across all columns is 0 by Finset.sum_const_zero. Substituting 0 into the Campbell-Howard condition gives 0 = 1, which decide refutes.
uses
zero_mul,Finset.sum_const_zerohave hsum : (∑ j : Fin n, K 0 j * K 1 j * K 2 j) = 0 := by have : (fun j : Fin n => K 0 j * K 1 j * K 2 j) = (fun _ => 0) := by ext j rw [hKzero j, zero_mul, zero_mul] rw [this, Finset.sum_const_zero] rw [hsum] at hK3 revert hK3; decide
css_z_distance_ge_three_iff_cols- A CSS code has Z-distance at least 3 if and only if zero columns of the stabilizer matrix S correspond to zero columns of K, and identical columns of S at distinct indices correspond to identical columns of K.
congr_fun- Equal functions take equal values at any argument: if f = g, then f a = g a.
mul_zero- Multiplying any element by zero on the right gives zero: a * 0 = 0.
Matrix.transpose_apply- Entry (i, j) of the transpose of matrix M is entry (j, i) of M.
mul_one- Multiplying any element by one on the right leaves it unchanged: a * 1 = a.
Finset.mul_sum- Multiplication distributes over finite sums: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
False.elim- From a contradiction (False), any proposition follows (ex falso quodlibet).
zero_mul- Multiplying any element by zero on the left gives zero: 0 * a = 0.
Finset.sum_const_zero- The sum of the constant zero function over any finite set is zero: ∑ _x ∈ s, 0 = 0.
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.
/-- No CSS code with 3 logical qubits and quasi-transversal CCZ exists at stabilizer rank s = 1. -/theorem op_159_css_ccz_no_code_s_one (n : ℕ) (K : Matrix (Fin 3) (Fin n) (ZMod 2)) (S : Matrix (Fin 1) (Fin n) (ZMod 2)) : ¬ css_quasi_transversal_ccz_code n 1 K S := by have fin1_eq_zero : ∀ (f : Fin 1 → ZMod 2), f 0 = 0 → f = 0 := by intro f h ext ⟨i, hi⟩ have : i = 0 := by omega subst this exact h have fin1_eq : ∀ (f g : Fin 1 → ZMod 2), f 0 = g 0 → f = g := by intro f g h ext ⟨i, hi⟩ have : i = 0 := by omega subst this exact h intro ⟨hdist, hCH⟩ rcases (css_z_distance_ge_three_iff_cols K S).mp hdist with ⟨hzero, heq⟩ rcases hCH with ⟨_, _, hK3, _, _, _, hS1, _, _⟩ have hS1_0 : ∑ j : Fin n, S 0 j = 0 := hS1 0 have hz_cube : ∀ x : ZMod 2, x * x * x = x := by decide have hz_cases : ∀ x : ZMod 2, x = 0 ∨ x = 1 := by decide by_cases hex : ∃ j0 : Fin n, S 0 j0 = 1 · rcases hex with ⟨j0, hj0⟩ set v := K.transpose j0 have hK : ∀ (i : Fin 3) (j : Fin n), K i j = v i * S 0 j := by intro i j rcases hz_cases (S 0 j) with hs0 | hs1 · have : S.transpose j = 0 := fin1_eq_zero (S.transpose j) hs0 have : K.transpose j = 0 := hzero j this have : K i j = 0 := congr_fun this i rw [this, hs0, mul_zero] · have hSeq : S.transpose j = S.transpose j0 := fin1_eq (S.transpose j) (S.transpose j0) (by rw [Matrix.transpose_apply, Matrix.transpose_apply, hs1, hj0]) have hKeq : K.transpose j = v := by by_cases hjj : j = j0 · rw [hjj] · exact heq j j0 hjj hSeq have : K i j = v i := congr_fun hKeq i rw [this, hs1, mul_one] have hterm : ∀ j : Fin n, K 0 j * K 1 j * K 2 j = (v 0 * v 1 * v 2) * S 0 j := by intro j rw [hK 0 j, hK 1 j, hK 2 j] have : (v 0 * S 0 j) * (v 1 * S 0 j) * (v 2 * S 0 j) = (v 0 * v 1 * v 2) * (S 0 j * S 0 j * S 0 j) := by ring rw [this, hz_cube] have hsum : (∑ j : Fin n, K 0 j * K 1 j * K 2 j) = (v 0 * v 1 * v 2) * ∑ j : Fin n, S 0 j := by simp_rw [hterm] rw [← Finset.mul_sum] rw [hS1_0, mul_zero] at hsum rw [hsum] at hK3 revert hK3; decide · have hKzero : ∀ j : Fin n, K 0 j = 0 := by intro j have hs : S 0 j = 0 := by rcases hz_cases (S 0 j) with h0 | h1 · exact h0 · exact False.elim (hex ⟨j, h1⟩) have : S.transpose j = 0 := fin1_eq_zero (S.transpose j) hs have : K.transpose j = 0 := hzero j this exact congr_fun this 0 have hsum : (∑ j : Fin n, K 0 j * K 1 j * K 2 j) = 0 := by have : (fun j : Fin n => K 0 j * K 1 j * K 2 j) = (fun _ => 0) := by ext j rw [hKzero j, zero_mul, zero_mul] rw [this, Finset.sum_const_zero] rw [hsum] at hK3 revert hK3; decide