AFTD Auto-Formalizing Theoretical Domains

op_159_css_ccz_no_code_s_one

theoremverified

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

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.

  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.

    lines 5–10

      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
  2. 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.

    lines 11–16

      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
  3. 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.

    lines 17–20

    uses css_z_distance_ge_three_iff_cols

      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
  4. 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.

    lines 21–22

      have hz_cube : ∀ x : ZMod 2, x * x * x = x := by decide
      have hz_cases : ∀ x : ZMod 2, x = 0 ∨ x = 1 := by decide
  5. 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.

    lines 23–25

      by_cases hex : ∃ j0 : Fin n, S 0 j0 = 1
      · rcases hex with ⟨j0, hj0⟩
        set v := K.transpose j0
  6. 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.

    lines 26–41

    uses congr_fun, Matrix.transpose_apply, mul_one, mul_zero

        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]
  7. 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.

    lines 42–46

        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]
  8. 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.

    lines 47–52

    uses Finset.mul_sum, mul_zero

        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
  9. 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.

    lines 53–61

    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
  10. 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.

    lines 62–68

    uses zero_mul, Finset.sum_const_zero

        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
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

/-- 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
See it in the graphDiscuss this resultChallenge it