AFTD Auto-Formalizing Theoretical Domains

error_subspaces_orthogonal

theoremverifiedimported Lean

Orthogonality of distinct error subspaces. Let $C \le \mathcal{H}_n$ be a code that is non-degenerate for $t$-error correction, and let $E, F$ be Pauli strings on $n$ qubits with weights $\mathrm{wt}(E) \le t$ and $\mathrm{wt}(F) \le t$ and $E \neq F$. Then the images $\hat{E}(C)$ and $\hat{F}(C)$ of $C$ under the corresponding Pauli operators are orthogonal subspaces of $\mathcal{H}_n$; that is, $\langle \hat{E}\,u,\, \hat{F}\,v\rangle = 0$ for all $u, v \in C$.

Statement

set_option linter.mathlibStandardSet false in
open scoped BigOperators in
open scoped Real in
open scoped Nat in
open scoped Classical in
open scoped Pointwise in
set_option maxRecDepth 4000 in
set_option synthInstance.maxHeartbeats 20000 in
set_option synthInstance.maxSize 128 in
set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Complex Matrix in
lemma error_subspaces_orthogonal {n t : ℕ} {C : Submodule ℂ (Hn n)}
    (h_nondeg : IsNondegenerate n C t)
    (E F : PauliString n) (hE : weight E ≤ t) (hF : weight F ≤ t) (h_neq : E ≠ F) :
    Submodule.IsOrtho (C.map (pauliOp E)) (C.map (pauliOp F))
Source
TCSlib, `error_subspaces_orthogonal`
Lean proof
By Allan Li, Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
What was changed in error_subspaces_orthogonal
--- TCSlib/ErrorCorrectingCodes/QuantumHamming.lean:271 (error_subspaces_orthogonal)
+++ as compiled here
@@ -1 +1,13 @@
+set_option linter.mathlibStandardSet false in
+open scoped BigOperators in
+open scoped Real in
+open scoped Nat in
+open scoped Classical in
+open scoped Pointwise in
+set_option maxRecDepth 4000 in
+set_option synthInstance.maxHeartbeats 20000 in
+set_option synthInstance.maxSize 128 in
+set_option relaxedAutoImplicit false in
+set_option autoImplicit false in
+open Complex Matrix in
 lemma error_subspaces_orthogonal {n t : ℕ} {C : Submodule ℂ (Hn n)}
@@ -12,3 +24,3 @@
         exact fun A x y => Finset.sum_comm.trans ( Finset.sum_congr rfl fun _ _ => Finset.sum_congr rfl fun _ _ => by ring );
-      convert h_adj ( pauliMatrix E ) x ( pauliOp F y ) using 1;
+      convert h_adj ( pauliMatrix E ) x ( pauliOp F y ) using 1 <;> rfl
     have h_adj_zero : (pauliOpAdjoint E (pauliOp F y)) = (pauliOpAdjoint E (pauliOp F (codeProj C y))) := by
@@ -21,3 +33,3 @@
           intro z hz; specialize hz x hx; simp_all +decide [dotProduct] ;
-          simpa [ mul_comm ] using congr_arg Star.star hz
+          simpa [ PiLp.inner_apply, mul_comm ] using congr_arg Star.star hz
         have h_split : (x ⬝ᵥ (star (Submodule.starProjection C y))) = (x ⬝ᵥ (star y)) - (x ⬝ᵥ (star (y - Submodule.starProjection C y))) := by
Verified
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 13
  • HnThe $n$-qubit Hilbert space $\mathcal{H}_n = \ell^2\!\bigl(\{0,1\}^n,\mathbb{C}\bigr)$, implemented as \texttt{EuclideanSpace ℂ (Fin n →…
  • IsNondegenerateA code is non-degenerate if it satisfies the Knill--Laflamme condition and additionally $P_C E^\dagger F P_C = 0$ whenever…
  • PauliStringA Pauli string of length $n$ is a function $p : \mathrm{Fin}\,n \to \mathrm{PauliBasis}$.
  • codeProjThe orthogonal projection of $\mathcal{H}_n$ onto a subspace $C$, viewed as an endomorphism $P_C : \mathcal{H}_n \to \mathcal{H}_n$.
  • codeProj_applyAction of the code projection. Let $C$ be a closed subspace of the $n$-qubit Hilbert space $\mathcal{H}_n$, and let…
  • codeProj_eq_self_of_memProjection onto a code fixes its own vectors. Let $C$ be a subspace of the $n$-qubit Hilbert space $\mathcal{H}_n$, and let…
  • pauliMatrixFor a Pauli string $p$ on $n$ qubits, the $2^n\times 2^n$ matrix obtained as the tensor product of the single-qubit Pauli matrices…
  • pauliOpFor $p \in \mathrm{PauliString}\,n$, the associated Pauli operator $\hat{p} : \mathcal{H}_n \to \mathcal{H}_n$.
  • pauliOpAdjointThe adjoint (Hermitian conjugate) $\hat{p}^\dagger : \mathcal{H}_n \to \mathcal{H}_n$ of the Pauli operator associated with a Pauli string…
  • weightThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
  • instFintypePauliStringinstFintypePauliString
  • instFiniteDimensionalComplexSubtypeHnMemSubmoduleinstFiniteDimensionalComplexSubtypeHnMemSubmodule
  • KnillLaflammeA subspace $C \le \mathcal{H}_n$ satisfies the Knill--Laflamme condition for $t$-error correction if for all Pauli strings $E,F$…
Used by 1
  • error_sphere_dimensionDimension of the error sphere of a non-degenerate code. Let $C \le \mathcal{H}_n$ be a code on $n$ qubits that is non-degenerate for $t$…

Lean source view module on GitHub

set_option linter.mathlibStandardSet false in
open scoped BigOperators in
open scoped Real in
open scoped Nat in
open scoped Classical in
open scoped Pointwise in
set_option maxRecDepth 4000 in
set_option synthInstance.maxHeartbeats 20000 in
set_option synthInstance.maxSize 128 in
set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Complex Matrix in
lemma error_subspaces_orthogonal {n t : ℕ} {C : Submodule ℂ (Hn n)}
    (h_nondeg : IsNondegenerate n C t)
    (E F : PauliString n) (hE : weight E ≤ t) (hF : weight F ≤ t) (h_neq : E ≠ F) :
    Submodule.IsOrtho (C.map (pauliOp E)) (C.map (pauliOp F)) := by

  have h_ortho : ∀ x y : Hn n, x ∈ C → y ∈ C → (pauliOp E x) ⬝ᵥ (star (pauliOp F y)) = 0 := by
    have := h_nondeg.2 E F hE hF h_neq;
    intro x y hx hy; replace this := congr_arg ( fun f => f y ) this; simp_all +decide ;
    have h_adj : (pauliOp E x) ⬝ᵥ (star (pauliOp F y)) = x ⬝ᵥ (star (pauliOpAdjoint E (pauliOp F y))) := by
      have h_adj : ∀ (A : Matrix (Fin n → Fin 2) (Fin n → Fin 2) ℂ) (x y : EuclideanSpace ℂ (Fin n → Fin 2)), (A.mulVec x) ⬝ᵥ (star y) = x ⬝ᵥ (star (A.conjTranspose.mulVec y)) := by
        simp +decide [ Matrix.mulVec, dotProduct, Finset.mul_sum _ _ _, mul_assoc, mul_comm, mul_left_comm ];
        exact fun A x y => Finset.sum_comm.trans ( Finset.sum_congr rfl fun _ _ => Finset.sum_congr rfl fun _ _ => by ring );
      convert h_adj ( pauliMatrix E ) x ( pauliOp F y ) using 1 <;> rfl
    have h_adj_zero : (pauliOpAdjoint E (pauliOp F y)) = (pauliOpAdjoint E (pauliOp F (codeProj C y))) := by
      rw [ codeProj_eq_self_of_mem hy ];
    have h_adj_zero : ∀ x y : Hn n, x ∈ C → (x ⬝ᵥ (star (codeProj C y))) = (x ⬝ᵥ (star y)) := by
      intro x y hx; rw [ codeProj_apply ] ; simp +decide [dotProduct] ;
      have h_adj_zero : ∀ x y : Hn n, x ∈ C → (x ⬝ᵥ (star (Submodule.starProjection C y))) = (x ⬝ᵥ (star y)) := by
        intro x y hx
        have h_perp : ∀ z ∈ Cᗮ, (x ⬝ᵥ (star z)) = 0 := by
          intro z hz; specialize hz x hx; simp_all +decide [dotProduct] ;
          simpa [ PiLp.inner_apply, mul_comm ] using congr_arg Star.star hz
        have h_split : (x ⬝ᵥ (star (Submodule.starProjection C y))) = (x ⬝ᵥ (star y)) - (x ⬝ᵥ (star (y - Submodule.starProjection C y))) := by
          simp +decide ;
        have h_mem : y - Submodule.starProjection C y ∈ Cᗮ :=
          Submodule.sub_starProjection_mem_orthogonal y
        have h_zero := h_perp _ h_mem
        simp only [WithLp.ofLp_sub] at h_zero
        rw [h_split, h_zero, sub_zero]
      exact h_adj_zero x y hx;
    specialize h_adj_zero x ( ( pauliOpAdjoint E ) ( ( pauliOp F ) ( codeProj C y ) ) ) hx; simp_all only [codeProj_apply,
      Submodule.coe_orthogonalProjection_apply, WithLp.ofLp_zero, star_zero, dotProduct_zero];
  intro x hx y hy;
  simp_all only [ne_eq, Submodule.mem_map]
  obtain ⟨w, h⟩ := hx
  obtain ⟨w_1, h_1⟩ := hy
  obtain ⟨left, right⟩ := h
  obtain ⟨left_1, right_1⟩ := h_1
  subst right right_1
  apply h_ortho
  · simp_all only
  · simp_all only;


  /-
   proof in hsort:
  - show the family `(C.map (pauliOp E))` is pairwise disjoint (inf = ⊥) via orthogonality
  - use finrank of supremum over pairwise disjoint finite family
  - show each `pauliOp E` restricts to a linear equiv on `C` (invertible/unitary), hence
    `finrank (C.map (pauliOp E)) = finrank C`
  -/
See it in the graphDiscuss this resultChallenge it