op_159_css_ccz_no_code_s_zero
For 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 CCZ code.
Statement
theorem op_159_css_ccz_no_code_s_zero (n : ℕ)
(K : Matrix (Fin 3) (Fin n) (ZMod 2)) (S : Matrix (Fin 0) (Fin n) (ZMod 2)) :
¬ css_quasi_transversal_ccz_code n 0 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…
- 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…
- 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…
- 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$ with entries in $\mathbb{Z}/2\mathbb{Z}$, and every $0 \times n$ matrix $S$ with entries in $\mathbb{Z}/2\mathbb{Z}$, $(K, S)$ is not a CSS quasi-transversal CCZ code of length $n$ with $s = 0$ (that is, ¬ css_quasi_transversal_ccz_code n 0 K S).
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: suppose a CSS quasi-transversal CCZ code exists with stabilizer rank s = 0. Because the stabilizer matrix S has 0 rows, all its column vectors are trivially zero. By the column characterization of the Z-distance condition (d_Z ≥ 3), every column of the logical operator matrix K must also be zero. Consequently, the Campbell-Howard cubic sum ∑_j K_{0,j} K_{1,j} K_{2,j} evaluates to 0, contradicting the code requirement that this sum equals 1.
Assuming a CSS quasi-transversal CCZ code exists at s = 0, any column where the stabilizer is zero must also have a zero logical column.
We assume for contradiction that (K, S) forms a CSS quasi-transversal CCZ code. Unfolding the definition reveals that the Z-distance must be at least 3 and the Campbell-Howard conditions must hold. Characterizing the distance condition via column vectors using `css_z_distance_ge_three_iff_cols` gives that whenever a column of S is zero, the corresponding column of K must also be zero.
uses
css_quasi_transversal_ccz_code,css_z_distance_ge_three_iff_colsintro h rw [css_quasi_transversal_ccz_code] at h obtain ⟨hz, hch⟩ := h rw [css_z_distance_ge_three_iff_cols] at hz obtain ⟨hz1, hz2⟩ := hz
Every column of S is zero.
Since S has 0 rows (its row indices belong to the empty type `Fin 0`), any column vector S.transpose j is indexed by `Fin 0`. By function extensionality and elimination on the empty index (`Fin.elim0`), each column vector is vacuously 0.
have hS : ∀ j : Fin n, S.transpose j = 0 := fun j => by funext i; exact i.elim0
Every entry of K is zero.
For every column j, since S.transpose j = 0, the first distance condition implies that K.transpose j = 0. Applying `congrFun` to evaluate this zero vector at each row index i shows that K i j = 0 for all i and j.
uses
congrFunhave hK : ∀ (i : Fin 3) (j : Fin n), K i j = 0 := fun i j => by have h' := congrFun (hz1 j (hS j)) i simpa using h'
The Campbell-Howard cubic sum of entries of K evaluates to 0, contradicting the requirement that it equals 1.
One of the Campbell-Howard conditions requires the triple sum ∑ j, K 0 j * K 1 j * K 2 j = 1. However, since all entries of K are zero, every term in the sum is 0 * 0 * 0 = 0. By `Finset.sum_eq_zero`, the entire sum is 0.
uses
Finset.sum_eq_zeroobtain ⟨_, _, h3, _⟩ := hch have hsum : (∑ j, K 0 j * K 1 j * K 2 j) = 0 := by apply Finset.sum_eq_zero intro j _ rw [hK 0 j, hK 1 j, hK 2 j] ring
A contradiction is derived, proving no such code can exist.
Substituting the value 0 for the sum into the Campbell-Howard condition gives 0 = 1, which contradicts `zero_ne_one`.
uses
zero_ne_onerw [hsum] at h3 exact zero_ne_one h3
css_quasi_transversal_ccz_code- The definition stating that a pair of matrices (K, S) forms a CSS quasi-transversal CCZ code if it has Z-distance at least 3 and satisfies the Campbell-Howard conditions.
css_z_distance_ge_three_iff_cols- A CSS code has Z-distance at least 3 if and only if every column where S is zero has K zero, and any two distinct columns where S agrees must also have K agree.
congrFun- If two functions are equal, their values at any given input are equal.
Finset.sum_eq_zero- A finite sum is zero if every term in the sum is zero.
zero_ne_one- Zero is not equal to one.
- At stabilizer rank s = 0, the matrix S has 0 rows, which is represented formally by row indices in Fin 0. Because Fin 0 is empty, any column vector of S is vacuously the zero vector.
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 = 0. -/theorem op_159_css_ccz_no_code_s_zero (n : ℕ) (K : Matrix (Fin 3) (Fin n) (ZMod 2)) (S : Matrix (Fin 0) (Fin n) (ZMod 2)) : ¬ css_quasi_transversal_ccz_code n 0 K S := by intro h rw [css_quasi_transversal_ccz_code] at h obtain ⟨hz, hch⟩ := h rw [css_z_distance_ge_three_iff_cols] at hz obtain ⟨hz1, hz2⟩ := hz have hS : ∀ j : Fin n, S.transpose j = 0 := fun j => by funext i; exact i.elim0 have hK : ∀ (i : Fin 3) (j : Fin n), K i j = 0 := fun i j => by have h' := congrFun (hz1 j (hS j)) i simpa using h' obtain ⟨_, _, h3, _⟩ := hch have hsum : (∑ j, K 0 j * K 1 j * K 2 j) = 0 := by apply Finset.sum_eq_zero intro j _ rw [hK 0 j, hK 1 j, hK 2 j] ring rw [hsum] at h3 exact zero_ne_one h3