AFTD Auto-Formalizing Theoretical Domains

op_159_css_ccz_no_code_s_zero

theoremverified

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

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.

  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.

    lines 5–9

    uses css_quasi_transversal_ccz_code, css_z_distance_ge_three_iff_cols

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

    lines 10–11

      have hS : ∀ j : Fin n, S.transpose j = 0 := fun j => by
        funext i; exact i.elim0
  3. 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.

    lines 12–14

    uses congrFun

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

    lines 15–20

    uses Finset.sum_eq_zero

      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
  5. 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`.

    lines 21–22

    uses zero_ne_one

      rw [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.

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