stabilizer_subspace_finrank_eq_two_pow
Let $k \le n$ and let $g_1, \dots, g_{n-k}$ be $n$-qubit Pauli operators $g_l = \varepsilon_l P_l$ with signs $\varepsilon_l \in \{1, -1\}$ and $P_l$ tensor products of $I, X, Y, Z$, which pairwise commute and are independent in the sense that no product of a nonempty subfamily of the $g_l$ is a scalar multiple of the identity (equivalently, the abelian group $S$ they generate has $2^{n-k}$ elements and does not contain $-I$). Then the stabilized subspace $\{\psi \in \mathbb{C}^{2^n} : g_l \psi = \psi \text{ for all } l\}$ (which equals $\{\psi : s\psi = \psi\ \forall s \in S\}$) has complex dimension $2^k$.
Statement
theorem stabilizer_subspace_finrank_eq_two_pow (n k : ℕ) (hk : k ≤ n) (p : Fin (n - k) → PauliString n) (ε : Fin (n - k) → ℂ) (hε : ∀ l, ε l = 1 ∨ ε l = -1) (hcomm : ∀ l l', Commute (pauliMatrix (p l)) (pauliMatrix (p l'))) (hind : ∀ b : Fin (n - k) → Bool, b ≠ (fun _ => false) → ∀ c : ℂ, ((List.finRange (n - k)).map (fun l => if b l then ε l • pauliMatrix (p l) else 1)).prod ≠ c • 1) : Module.finrank ℂ (⨅ l, LinearMap.ker (ε l • pauliOp (p l) - LinearMap.id) : Submodule ℂ (Hn n)) = 2 ^ k
- Formalizes
- arXiv:2610.37807 Lemma 10. Lean differs: S is given by its n-k generators (signs ±1, since -I is not in S every element squares to I), independence and -I not in S are stated together as 'no nonempty product of generators is a scalar matrix', and stab(S) is the common +1 eigenspace of the generators.
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- pauliOpFor $p \in \mathrm{PauliString}\,n$, the associated Pauli operator $\hat{p} : \mathcal{H}_n \to \mathcal{H}_n$.
- 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…
- PauliStringA Pauli string of length $n$ is a function $p : \mathrm{Fin}\,n \to \mathrm{PauliBasis}$.
- HnThe $n$-qubit Hilbert space $\mathcal{H}_n = \ell^2\!\bigl(\{0,1\}^n,\mathbb{C}\bigr)$, implemented as \texttt{EuclideanSpace ℂ (Fin n →…
- PauliBasisThe four Pauli basis elements $\{I,X,Y,Z\}$, represented as an inductive type.
- tr_pauli_of_ne_oneIf a Pauli string on $n$ qubits contains at least one non-identity single-qubit Pauli operator, then its tensor-product matrix has trace…
- instFiniteDimensionalComplexSubtypeHnMemSubmoduleinstFiniteDimensionalComplexSubtypeHnMemSubmodule
- sigmaIThe $2\times 2$ identity matrix over $\mathbb{C}$, i.e.\ the Pauli operator $I$.
- PauliBasis.toMatrixMaps each Pauli basis element $\{I,X,Y,Z\}$ to its corresponding $2\times 2$ matrix $\{\sigma_I,\sigma_X,\sigma_Y,\sigma_Z\}$.
- sigmaXThe bit-flip Pauli matrix $X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ over $\mathbb{C}$.
- sigmaYThe bit-phase-flip Pauli matrix $Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$ over $\mathbb{C}$.
- sigmaZThe phase-flip Pauli matrix $Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$ over $\mathbb{C}$.
Read back from the Lean
For any natural numbers $n$ and $k$ with $k \le n$, given a family of $n - k$ Pauli strings $p : \mathrm{Fin}(n - k) \to \mathrm{PauliString}(n)$ and a family of complex scalars $\varepsilon : \mathrm{Fin}(n - k) \to \mathbb{C}$ such that:
1. For every $l \in \mathrm{Fin}(n - k)$, $\varepsilon(l) = 1$ or $\varepsilon(l) = -1$;
2. For all $l, l' \in \mathrm{Fin}(n - k)$, the Pauli matrices $\mathrm{pauliMatrix}(p(l))$ and $\mathrm{pauliMatrix}(p(l'))$ commute;
3. For every non-identically-false boolean vector $b : \mathrm{Fin}(n - k) \to \mathrm{Bool}$ and every scalar $c \in \mathbb{C}$, the ordered product over $l \in [0, \dots, n - k - 1]$ (given by List.finRange (n - k)) of $(\text{if } b(l) \text{ then } \varepsilon(l) \cdot \mathrm{pauliMatrix}(p(l)) \text{ else } 1)$ is not equal to the scalar matrix $c \cdot I$;
then the complex dimension (Module.finrank ℂ) of the joint $+1$-eigenspace $\bigcap_{l \in \mathrm{Fin}(n - k)} \ker(\varepsilon(l) \cdot \mathrm{pauliOp}(p(l)) - \mathrm{id})$ in $H_n(n)$ is equal to $2^k$.
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
To determine the complex dimension of the stabilizer subspace of an independent abelian group generated by n - k Pauli operators, the proof constructs the projector Pr = ∏_{l=0}^{n-k-1} (1/2)(I + g_l) onto the joint +1-eigenspace. Expanding this product yields an average over all 2^{n-k} elements of the generated abelian group. By the algebraic independence of the generators, every non-trivial group element corresponds to a non-identity Pauli string and therefore has trace zero, leaving only the identity operator whose trace is 2^n. Because the dimension of the image of a projection operator equals its trace, the dimension of the stabilized subspace is 2^{-(n-k)} · 2^n = 2^k.
The product of any two single-qubit Pauli matrices is a complex scalar multiple of a Pauli matrix. automation
Exhaustive case analysis across all 16 pairs of Pauli basis matrices (I, X, Y, Z), verified by entrywise evaluation.
cases a <;> cases b · exact ⟨1, .I, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .X, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .Y, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .Z, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .X, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .I, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨Complex.I, .Z, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨-Complex.I, .Y, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .Y, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨-Complex.I, .Z, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .I, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨Complex.I, .X, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .Z, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨Complex.I, .Y, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨-Complex.I, .X, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .I, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩
The product of two n-qubit Pauli matrices is a complex scalar multiple of an n-qubit Pauli matrix.
Pointwise application of single-qubit multiplication on each factor; distributing the product across tensor components via Fintype.prod_sum shows that the global matrix product matches the tensor product of the component products scaled by the product of scalar factors.
uses
pauliBasis_toMatrix_mul_exists_smul,Fintype.prod_sumchoose cf rf hf using fun k => pauliBasis_toMatrix_mul_exists_smul (p k) (q k) refine ⟨∏ k, cf k, rf, ?_⟩ ext i l simp only [Matrix.mul_apply, pauliMatrix, Matrix.smul_apply, smul_eq_mul] simp_rw [← Finset.prod_mul_distrib] have h1 := (Fintype.prod_sum (fun (k : Fin n) (x : Fin 2) => (p k).toMatrix (i k) x * (q k).toMatrix x (l k))).symm rw [h1] refine Finset.prod_congr rfl fun k _ => ?_ have := congrFun (congrFun (hf k) (i k)) (l k) simp only [Matrix.mul_apply, Matrix.smul_apply, smul_eq_mul] at this exact this
The n-qubit Pauli matrix for the all-identity string is the identity matrix.
Each single-qubit identity matrix is the Kronecker delta. Its n-fold tensor product at entry (i, j) is the product of Kronecker deltas over all qubit positions, which is 1 if i = j and contains a zero factor (so vanishes by Finset.prod_eq_zero) if i ≠ j.
uses
Finset.prod_eq_zero,Finset.mem_univhave hI : ∀ x y : Fin 2, sigmaI x y = if x = y then 1 else 0 := by intro x y; fin_cases x <;> fin_cases y <;> simp [sigmaI] ext i j simp only [pauliMatrix, PauliBasis.toMatrix, Matrix.one_apply, hI] by_cases hij : i = j · subst hij; simp · rw [if_neg hij] obtain ⟨k, hk⟩ : ∃ k, i k ≠ j k := by by_contra h; push Not at h; exact hij (funext h) exact Finset.prod_eq_zero (Finset.mem_univ k) (by simp [hk])
Every n-qubit Pauli matrix squares to the identity matrix.
Each single-qubit Pauli matrix squares to the 2 × 2 identity matrix. Distributing matrix multiplication across the tensor factors with Fintype.prod_sum proves that the square of any n-qubit Pauli matrix equals the all-identity Pauli matrix, which is 1.
uses
pauliMatrix_identity_string_eq_one,Fintype.prod_sumhave hsq : ∀ a : PauliBasis, a.toMatrix * a.toMatrix = 1 := by intro a; cases a <;> (ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]) rw [← pauliMatrix_identity_string_eq_one n] ext i l simp only [Matrix.mul_apply, pauliMatrix] simp_rw [← Finset.prod_mul_distrib] rw [(Fintype.prod_sum (fun (k : Fin n) (x : Fin 2) => (p k).toMatrix (i k) x * (p k).toMatrix x (l k))).symm] refine Finset.prod_congr rfl fun k _ => ?_ have := congrFun (congrFun (hsq (p k)) (i k)) (l k) simp only [Matrix.mul_apply] at this rw [this] have hI : ∀ x y : Fin 2, sigmaI x y = if x = y then 1 else 0 := by intro x y; fin_cases x <;> fin_cases y <;> simp [sigmaI] simp [PauliBasis.toMatrix, hI, Matrix.one_apply]
The product ∏_{l=0}^{N-1} (1 + A_l) expands into the sum over all boolean vectors b of the products of terms with b(l) = true.
Induction on the number of factors N. At each step, the product with (1 + A_0) splits into two sums corresponding to b(0) = false and b(0) = true, matching the summation over boolean functions.
uses
List.finRange_succ,Fintype.sum_boolinduction N with | zero => simp | succ N ih => rw [List.finRange_succ, List.map_cons, List.prod_cons, List.map_map] have ih' := ih (fun l => Af l.succ) simp only [Function.comp_def] at ih' ⊢ rw [ih', ← (Fin.consEquiv (fun _ => Bool)).sum_comp, Fintype.sum_prod_type, Fintype.sum_bool] simp only [Fin.consEquiv, Equiv.coe_fn_mk, Fin.cons_zero, Fin.cons_succ, if_true, Bool.false_eq_true, if_false, List.map_cons, List.prod_cons, List.map_map, Function.comp_def, one_mul] rw [add_mul, one_mul, Finset.mul_sum, add_comm]
Factoring a scalar c out of each term in a product of length L pulls out a factor of c^L.
Straightforward induction on the list L, applying associativity and commutation of scalar and ring multiplication.
uses
List.map_cons,List.prod_cons,smul_mul_smul_comminduction L with | nil => simp | cons a L ih => rw [List.map_cons, List.prod_cons, ih, List.map_cons, List.prod_cons, smul_mul_smul_comm, List.length_cons, pow_succ, mul_comm]
The signed generators G_l = ε_l P_l pairwise commute and square to 1, and the operators E_l = (1/2)(1 + G_l) are commuting idempotent projectors.
Since ε_l ∈ {±1} and P_l^2 = 1, G_l^2 = 1. The pairwise commutation of the Pauli matrices transfers to G_l and then to E_l. Expanding E_l^2 = (1/4)(1 + 2 G_l + G_l^2) = (1/2)(1 + G_l) = E_l confirms idempotence.
uses
pauliMatrix_mul_self_eq_one,Commute.smul_left,Commute.smul_rightclassical set G : Fin (n - k) → Matrix (Fin n → Fin 2) (Fin n → Fin 2) ℂ := fun l => ε l • pauliMatrix (p l) with hG have hε2 : ∀ l, ε l * ε l = 1 := by intro l; rcases hε l with h | h <;> rw [h] <;> norm_num have hGG : ∀ l, G l * G l = 1 := by intro l; simp only [hG, smul_mul_smul_comm, pauliMatrix_mul_self_eq_one, hε2, one_smul] have hGc : ∀ l l', Commute (G l) (G l') := fun l l' => ((hcomm l l').smul_left _).smul_right _ set E : Fin (n - k) → Matrix (Fin n → Fin 2) (Fin n → Fin 2) ℂ := fun l => (1/2 : ℂ) • (1 + G l) with hE have hGE : ∀ l, G l * E l = E l := by intro l; simp only [hE, Matrix.mul_smul, Matrix.mul_add, Matrix.mul_one, hGG, add_comm] have hEE : ∀ l, E l * E l = E l := by intro l have : E l * E l = (1/2 : ℂ) • (E l + G l * E l) := by conv_lhs => rw [show E l = (1/2 : ℂ) • (1 + G l) from rfl] rw [Matrix.smul_mul, Matrix.add_mul, Matrix.one_mul] rw [this, hGE, ← two_smul ℂ (E l), smul_smul]; norm_num have hEc : ∀ l l', Commute (E l) (E l') := by intro l l' exact (((Commute.one_left _).add_left ((Commute.one_right _).add_right (hGc l l'))).smul_left _).smul_right _
Any sub-product of the projectors E_l is idempotent, and its +1-eigenspace is precisely the joint +1-eigenspace of the corresponding generators G_l.
By list induction: commuting idempotents multiply to an idempotent. A vector v satisfies (∏_{l ∈ L} E_l) v = v if and only if each individual generator satisfies G_l v = v.
uses
Commute.list_prod_right,mulVec_mulVechave hlist : ∀ L : List (Fin (n - k)), ((L.map E).prod * (L.map E).prod = (L.map E).prod) ∧ ∀ v : (Fin n → Fin 2) → ℂ, ((L.map E).prod *ᵥ v = v ↔ ∀ l ∈ L, G l *ᵥ v = v) := by intro L induction L with | nil => simp | cons a L ih => obtain ⟨ih1, ih2⟩ := ih have hc : Commute (E a) (L.map E).prod := Commute.list_prod_right _ _ (by intro x hx; obtain ⟨l, -, rfl⟩ := List.mem_map.mp hx; exact hEc a l) simp only [List.map_cons, List.prod_cons] set P := (L.map E).prod refine ⟨?_, fun v => ⟨fun hv => ?_, fun hv => ?_⟩⟩ · calc E a * P * (E a * P) = E a * (P * E a) * P := by simp only [mul_assoc] _ = E a * (E a * P) * P := by rw [hc.eq] _ = (E a * E a) * (P * P) := by simp only [mul_assoc] _ = E a * P := by rw [hEE, ih1] · have hEv : E a *ᵥ v = v := by have : E a *ᵥ ((E a * P) *ᵥ v) = (E a * P) *ᵥ v := by rw [mulVec_mulVec, ← mul_assoc, hEE] rwa [hv] at this have hPv : P *ᵥ v = v := by have : P *ᵥ ((E a * P) *ᵥ v) = (E a * P) *ᵥ v := by rw [mulVec_mulVec, ← mul_assoc, ← hc.eq, mul_assoc, ih1] rwa [hv] at this intro l hl rcases List.mem_cons.mp hl with rfl | hl · have : G l *ᵥ (E l *ᵥ v) = E l *ᵥ v := by rw [mulVec_mulVec, hGE] rwa [hEv] at this · exact (ih2 v).mp hPv l hl · have hPv : P *ᵥ v = v := (ih2 v).mpr (fun l hl => hv l (List.mem_cons_of_mem _ hl)) have hEv : E a *ᵥ v = v := by have hGv := hv a List.mem_cons_self rw [hE] simp only [Matrix.smul_mulVec, Matrix.add_mulVec, Matrix.one_mulVec, hGv] rw [← two_smul ℂ v, smul_smul]; norm_num rw [← mulVec_mulVec, hPv, hEv]
Every non-empty product of generators is a scalar multiple of a Pauli matrix and has trace zero.
By multiplicative closure of Pauli strings, any subset product of generators equals c • pauliMatrix r. If r is not the identity string, its trace is zero by tr_pauli_of_ne_one. If r were the identity string, the product would be c • 1, contradicting the hypothesis that the generators are independent.
uses
pauliMatrix_mul_exists_smul,pauliMatrix_identity_string_eq_one,tr_pauli_of_ne_one,trace_smulset Pr := ((List.finRange (n - k)).map E).prod with hPrdef have hclose : ∀ (b : Fin (n - k) → Bool) (L : List (Fin (n - k))), ∃ c : ℂ, ∃ r : PauliString n, (L.map (fun l => if b l then G l else 1)).prod = c • pauliMatrix r := by intro b L induction L with | nil => exact ⟨1, fun _ => PauliBasis.I, by simp [pauliMatrix_identity_string_eq_one]⟩ | cons a L ih => obtain ⟨c, r, h⟩ := ih obtain ⟨c', r', h'⟩ : ∃ c' : ℂ, ∃ r' : PauliString n, (if b a then G a else 1) = c' • pauliMatrix r' := by by_cases hb : b a · exact ⟨ε a, p a, by simp [hb, hG]⟩ · exact ⟨1, fun _ => PauliBasis.I, by simp [hb, pauliMatrix_identity_string_eq_one]⟩ obtain ⟨c'', r'', h''⟩ := pauliMatrix_mul_exists_smul r' r refine ⟨c' * c * c'', r'', ?_⟩ rw [List.map_cons, List.prod_cons, h, h', smul_mul_smul_comm, h'', smul_smul] have htr0 : ∀ b : Fin (n - k) → Bool, b ≠ (fun _ => false) → (((List.finRange (n - k)).map (fun l => if b l then G l else 1)).prod).trace = 0 := by intro b hb obtain ⟨c, r, h⟩ := hclose b (List.finRange (n - k)) by_cases hr : ∃ i, r i ≠ PauliBasis.I · rw [h, trace_smul, tr_pauli_of_ne_one n r hr, smul_zero] · push Not at hr have hr' : r = fun _ => PauliBasis.I := funext hr exact absurd (by rw [h, hr', pauliMatrix_identity_string_eq_one]) (hind b hb c)
The total projector Pr = ∏_{l=0}^{n-k-1} E_l has trace 2^k.
Expanding Pr gives (1/2)^{n-k} times the sum over all 2^{n-k} boolean vectors b of the products of generators. Every term with b ≠ 0 is traceless, leaving only the all-false term whose value is the 2^n × 2^n identity matrix with trace 2^n. Thus the trace is 2^{-(n-k)} · 2^n = 2^k.
uses
list_prod_map_smul_eq_pow_smul,list_prod_map_one_add_eq_sum,trace_sum,Finset.sum_eq_single,trace_onehave hPr : Pr = (1/2 : ℂ) ^ (n - k) • ∑ b : Fin (n - k) → Bool, ((List.finRange (n - k)).map (fun l => if b l then G l else 1)).prod := by rw [hPrdef, show ((List.finRange (n - k)).map E) = (List.finRange (n - k)).map (fun l => (1/2 : ℂ) • (1 + G l)) from rfl, list_prod_map_smul_eq_pow_smul, List.length_finRange, list_prod_map_one_add_eq_sum] have htrace : Pr.trace = 2 ^ k := by rw [hPr, trace_smul, trace_sum, Finset.sum_eq_single (fun _ => false)] · simp only [Bool.false_eq_true, if_false] rw [List.map_const', List.prod_replicate, one_pow, trace_one] simp only [Fintype.card_fun, Fintype.card_fin, smul_eq_mul] have : (2 : ℂ) ^ n = 2 ^ k * 2 ^ (n - k) := by rw [← pow_add]; congr 1; omega push_cast rw [this, one_div, inv_pow]; field_simp · intro b _ hb; exact htr0 b hb · simp
The linear map of Pr is an idempotent projection onto the stabilized subspace, so the dimension of the subspace is 2^k.
The subspace ⨅_l ker(g_l - id) consists of all vectors fixed by every G_l, which are exactly the vectors fixed by the idempotent operator Pr. Hence Matrix.toEuclideanLin Pr is a projection onto this subspace, and its trace (which equals the matrix trace 2^k) equals the dimension of the subspace.
uses
Matrix.toEuclideanLin_eq_toLin_orthonormal,LinearMap.trace_eq_matrix_trace,LinearMap.toMatrix_toLin,WithLp.ofLp_injectivehave hPP : Pr * Pr = Pr := (hlist (List.finRange (n - k))).1 have hPfix : ∀ v, Pr *ᵥ v = v ↔ ∀ l, G l *ᵥ v = v := by intro v rw [show Pr = ((List.finRange (n - k)).map E).prod from rfl, (hlist _).2 v] simp have hmemV : ∀ v : Hn n, v ∈ (⨅ l, LinearMap.ker (ε l • pauliOp (p l) - LinearMap.id) : Submodule ℂ (Hn n)) ↔ ∀ l, G l *ᵥ (WithLp.ofLp v) = WithLp.ofLp v := by intro v simp only [Submodule.mem_iInf, LinearMap.mem_ker, LinearMap.sub_apply, LinearMap.smul_apply, LinearMap.id_apply, sub_eq_zero] refine forall_congr' fun l => ?_ have e : ε l • pauliOp (p l) v = WithLp.toLp 2 (G l *ᵥ WithLp.ofLp v) := by simp [pauliOp, hG, Matrix.smul_mulVec] rfl rw [e] constructor · intro h; have := congrArg WithLp.ofLp h; simpa using this · intro h; rw [h] have hproj : LinearMap.IsProj (⨅ l, LinearMap.ker (ε l • pauliOp (p l) - LinearMap.id) : Submodule ℂ (Hn n)) (Matrix.toEuclideanLin Pr) := by constructor · intro x rw [hmemV] have : Pr *ᵥ (Pr *ᵥ WithLp.ofLp x) = Pr *ᵥ WithLp.ofLp x := by rw [mulVec_mulVec, hPP] simpa [Matrix.toEuclideanLin] using (hPfix _).mp this · intro x hx rw [hmemV] at hx have := (hPfix (WithLp.ofLp x)).mpr hx apply WithLp.ofLp_injective simpa [Matrix.toEuclideanLin] using this have htr := hproj.trace have hlin : LinearMap.trace ℂ (Hn n) (Matrix.toEuclideanLin Pr) = Pr.trace := by rw [Matrix.toEuclideanLin_eq_toLin_orthonormal, LinearMap.trace_eq_matrix_trace ℂ (EuclideanSpace.basisFun _ ℂ).toBasis, LinearMap.toMatrix_toLin] rw [hlin, htrace] at htr exact_mod_cast htr.symm
The main theorem stabilizer_subspace_finrank_eq_two_pow holds.
Directly applies the auxiliary theorem stabilizer_subspace_finrank_eq_two_pow_aux with the provided parameters and hypotheses.
uses
stabilizer_subspace_finrank_eq_two_pow_auxexact stabilizer_subspace_finrank_eq_two_pow_aux n k hk p ε hε hcomm hind
pauliBasis_toMatrix_mul_exists_smul- The product of any two single-qubit Pauli matrices is a complex scalar multiple of a Pauli matrix.
Fintype.prod_sum- Distributing a product of sums over a finite index set into a sum of products over function spaces.
Finset.prod_eq_zero- A product over a finset is zero if at least one factor is zero.
Finset.mem_univ- Every element of a finite type belongs to its universal finset Finset.univ.
pauliMatrix_identity_string_eq_one- The Pauli matrix corresponding to the all-identity Pauli string is the identity matrix.
List.finRange_succ- The list of indices in Fin (n+1) decomposes into 0 followed by the successor-mapped indices of Fin n.
Fintype.sum_bool- Summing a function over Bool equals its value at true plus its value at false.
List.map_cons- Mapping a function over a cons-cell applies the function to the head and maps over the tail.
List.prod_cons- The product of elements in a cons-cell is the head multiplied by the product of the tail.
smul_mul_smul_comm- Scalar multiplications distribute and commute across multiplication: (a • b) * (c • d) = (a * c) • (b * d).
pauliMatrix_mul_self_eq_one- The square of any n-qubit Pauli matrix is the identity matrix.
Commute.smul_left- If a and b commute, then any scalar multiple of a commutes with b.
Commute.smul_right- If a and b commute, then a commutes with any scalar multiple of b.
Commute.list_prod_right- If an element commutes with every element in a list, it commutes with the product of the list.
mulVec_mulVec- Matrix-vector multiplication associates with matrix multiplication: M *ᵥ (N *ᵥ v) = (M * N) *ᵥ v.
pauliMatrix_mul_exists_smul- The product of two n-qubit Pauli matrices is a scalar multiple of an n-qubit Pauli matrix.
tr_pauli_of_ne_one- An n-qubit Pauli matrix has trace zero if at least one qubit operator is not the identity.
trace_smul- The trace of a scalar multiple of a matrix is the scalar times the trace of the matrix.
list_prod_map_smul_eq_pow_smul- Factoring a scalar c out of every element in a list of length L scales the product by c^L.
list_prod_map_one_add_eq_sum- Expanding the product of (1 + A_l) over a list gives the sum over all boolean indicator vectors of products of chosen factors.
trace_sum- The trace of a finite sum of matrices is the sum of their individual traces.
Finset.sum_eq_single- A finite sum collapses to a single term if all other terms are zero.
trace_one- The trace of the identity matrix equals the dimension of the underlying index type.
Matrix.toEuclideanLin_eq_toLin_orthonormal- The linear map on EuclideanSpace represented by a matrix coincides with the linear map with respect to the standard orthonormal basis.
LinearMap.trace_eq_matrix_trace- The trace of a linear endomorphism equals the trace of its representing matrix in any basis.
LinearMap.toMatrix_toLin- The matrix representation of the linear map constructed from a matrix M recovers M.
WithLp.ofLp_injective- The conversion function WithLp.ofLp between an Lp space and its underlying function type is injective.
stabilizer_subspace_finrank_eq_two_pow_aux- The core auxiliary theorem establishing that the joint +1-eigenspace of the commuting independent Pauli operators has dimension 2^k.
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.
open Matrix intheorem pauliBasis_toMatrix_mul_exists_smul (a b : PauliBasis) : ∃ c : ℂ, ∃ r : PauliBasis, a.toMatrix * b.toMatrix = c • r.toMatrix := by cases a <;> cases b · exact ⟨1, .I, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .X, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .Y, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .Z, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .X, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .I, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨Complex.I, .Z, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨-Complex.I, .Y, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .Y, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨-Complex.I, .Z, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .I, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨Complex.I, .X, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .Z, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨Complex.I, .Y, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨-Complex.I, .X, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩ · exact ⟨1, .I, by ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]⟩open Matrix intheorem pauliMatrix_mul_exists_smul {n : ℕ} (p q : PauliString n) : ∃ c : ℂ, ∃ r : PauliString n, pauliMatrix p * pauliMatrix q = c • pauliMatrix r := by choose cf rf hf using fun k => pauliBasis_toMatrix_mul_exists_smul (p k) (q k) refine ⟨∏ k, cf k, rf, ?_⟩ ext i l simp only [Matrix.mul_apply, pauliMatrix, Matrix.smul_apply, smul_eq_mul] simp_rw [← Finset.prod_mul_distrib] have h1 := (Fintype.prod_sum (fun (k : Fin n) (x : Fin 2) => (p k).toMatrix (i k) x * (q k).toMatrix x (l k))).symm rw [h1] refine Finset.prod_congr rfl fun k _ => ?_ have := congrFun (congrFun (hf k) (i k)) (l k) simp only [Matrix.mul_apply, Matrix.smul_apply, smul_eq_mul] at this exact thisopen Matrix intheorem pauliMatrix_identity_string_eq_one (n : ℕ) : pauliMatrix (fun _ : Fin n => PauliBasis.I) = 1 := by have hI : ∀ x y : Fin 2, sigmaI x y = if x = y then 1 else 0 := by intro x y; fin_cases x <;> fin_cases y <;> simp [sigmaI] ext i j simp only [pauliMatrix, PauliBasis.toMatrix, Matrix.one_apply, hI] by_cases hij : i = j · subst hij; simp · rw [if_neg hij] obtain ⟨k, hk⟩ : ∃ k, i k ≠ j k := by by_contra h; push Not at h; exact hij (funext h) exact Finset.prod_eq_zero (Finset.mem_univ k) (by simp [hk])open Matrix intheorem pauliMatrix_mul_self_eq_one {n : ℕ} (p : PauliString n) : pauliMatrix p * pauliMatrix p = 1 := by have hsq : ∀ a : PauliBasis, a.toMatrix * a.toMatrix = 1 := by intro a; cases a <;> (ext i j; fin_cases i <;> fin_cases j <;> simp [PauliBasis.toMatrix, sigmaI, sigmaX, sigmaY, sigmaZ]) rw [← pauliMatrix_identity_string_eq_one n] ext i l simp only [Matrix.mul_apply, pauliMatrix] simp_rw [← Finset.prod_mul_distrib] rw [(Fintype.prod_sum (fun (k : Fin n) (x : Fin 2) => (p k).toMatrix (i k) x * (p k).toMatrix x (l k))).symm] refine Finset.prod_congr rfl fun k _ => ?_ have := congrFun (congrFun (hsq (p k)) (i k)) (l k) simp only [Matrix.mul_apply] at this rw [this] have hI : ∀ x y : Fin 2, sigmaI x y = if x = y then 1 else 0 := by intro x y; fin_cases x <;> fin_cases y <;> simp [sigmaI] simp [PauliBasis.toMatrix, hI, Matrix.one_apply]theorem list_prod_map_one_add_eq_sum {R : Type*} [Ring R] (N : ℕ) (Af : Fin N → R) : ((List.finRange N).map (fun l => 1 + Af l)).prod = ∑ b : Fin N → Bool, ((List.finRange N).map (fun l => if b l then Af l else 1)).prod := by induction N with | zero => simp | succ N ih => rw [List.finRange_succ, List.map_cons, List.prod_cons, List.map_map] have ih' := ih (fun l => Af l.succ) simp only [Function.comp_def] at ih' ⊢ rw [ih', ← (Fin.consEquiv (fun _ => Bool)).sum_comp, Fintype.sum_prod_type, Fintype.sum_bool] simp only [Fin.consEquiv, Equiv.coe_fn_mk, Fin.cons_zero, Fin.cons_succ, if_true, Bool.false_eq_true, if_false, List.map_cons, List.prod_cons, List.map_map, Function.comp_def, one_mul] rw [add_mul, one_mul, Finset.mul_sum, add_comm]theorem list_prod_map_smul_eq_pow_smul {R : Type*} [Ring R] {ι : Type*} (L : List ι) (c : ℂ) [Algebra ℂ R] (Af : ι → R) : (L.map (fun l => c • Af l)).prod = c ^ L.length • (L.map Af).prod := by induction L with | nil => simp | cons a L ih => rw [List.map_cons, List.prod_cons, ih, List.map_cons, List.prod_cons, smul_mul_smul_comm, List.length_cons, pow_succ, mul_comm]open Matrix intheorem stabilizer_subspace_finrank_eq_two_pow_aux (n k : ℕ) (hk : k ≤ n) (p : Fin (n - k) → PauliString n) (ε : Fin (n - k) → ℂ) (hε : ∀ l, ε l = 1 ∨ ε l = -1) (hcomm : ∀ l l', Commute (pauliMatrix (p l)) (pauliMatrix (p l'))) (hind : ∀ b : Fin (n - k) → Bool, b ≠ (fun _ => false) → ∀ c : ℂ, ((List.finRange (n - k)).map (fun l => if b l then ε l • pauliMatrix (p l) else 1)).prod ≠ c • 1) : Module.finrank ℂ (⨅ l, LinearMap.ker (ε l • pauliOp (p l) - LinearMap.id) : Submodule ℂ (Hn n)) = 2 ^ k := by classical set G : Fin (n - k) → Matrix (Fin n → Fin 2) (Fin n → Fin 2) ℂ := fun l => ε l • pauliMatrix (p l) with hG have hε2 : ∀ l, ε l * ε l = 1 := by intro l; rcases hε l with h | h <;> rw [h] <;> norm_num have hGG : ∀ l, G l * G l = 1 := by intro l; simp only [hG, smul_mul_smul_comm, pauliMatrix_mul_self_eq_one, hε2, one_smul] have hGc : ∀ l l', Commute (G l) (G l') := fun l l' => ((hcomm l l').smul_left _).smul_right _ set E : Fin (n - k) → Matrix (Fin n → Fin 2) (Fin n → Fin 2) ℂ := fun l => (1/2 : ℂ) • (1 + G l) with hE have hGE : ∀ l, G l * E l = E l := by intro l; simp only [hE, Matrix.mul_smul, Matrix.mul_add, Matrix.mul_one, hGG, add_comm] have hEE : ∀ l, E l * E l = E l := by intro l have : E l * E l = (1/2 : ℂ) • (E l + G l * E l) := by conv_lhs => rw [show E l = (1/2 : ℂ) • (1 + G l) from rfl] rw [Matrix.smul_mul, Matrix.add_mul, Matrix.one_mul] rw [this, hGE, ← two_smul ℂ (E l), smul_smul]; norm_num have hEc : ∀ l l', Commute (E l) (E l') := by intro l l' exact (((Commute.one_left _).add_left ((Commute.one_right _).add_right (hGc l l'))).smul_left _).smul_right _ have hlist : ∀ L : List (Fin (n - k)), ((L.map E).prod * (L.map E).prod = (L.map E).prod) ∧ ∀ v : (Fin n → Fin 2) → ℂ, ((L.map E).prod *ᵥ v = v ↔ ∀ l ∈ L, G l *ᵥ v = v) := by intro L induction L with | nil => simp | cons a L ih => obtain ⟨ih1, ih2⟩ := ih have hc : Commute (E a) (L.map E).prod := Commute.list_prod_right _ _ (by intro x hx; obtain ⟨l, -, rfl⟩ := List.mem_map.mp hx; exact hEc a l) simp only [List.map_cons, List.prod_cons] set P := (L.map E).prod refine ⟨?_, fun v => ⟨fun hv => ?_, fun hv => ?_⟩⟩ · calc E a * P * (E a * P) = E a * (P * E a) * P := by simp only [mul_assoc] _ = E a * (E a * P) * P := by rw [hc.eq] _ = (E a * E a) * (P * P) := by simp only [mul_assoc] _ = E a * P := by rw [hEE, ih1] · have hEv : E a *ᵥ v = v := by have : E a *ᵥ ((E a * P) *ᵥ v) = (E a * P) *ᵥ v := by rw [mulVec_mulVec, ← mul_assoc, hEE] rwa [hv] at this have hPv : P *ᵥ v = v := by have : P *ᵥ ((E a * P) *ᵥ v) = (E a * P) *ᵥ v := by rw [mulVec_mulVec, ← mul_assoc, ← hc.eq, mul_assoc, ih1] rwa [hv] at this intro l hl rcases List.mem_cons.mp hl with rfl | hl · have : G l *ᵥ (E l *ᵥ v) = E l *ᵥ v := by rw [mulVec_mulVec, hGE] rwa [hEv] at this · exact (ih2 v).mp hPv l hl · have hPv : P *ᵥ v = v := (ih2 v).mpr (fun l hl => hv l (List.mem_cons_of_mem _ hl)) have hEv : E a *ᵥ v = v := by have hGv := hv a List.mem_cons_self rw [hE] simp only [Matrix.smul_mulVec, Matrix.add_mulVec, Matrix.one_mulVec, hGv] rw [← two_smul ℂ v, smul_smul]; norm_num rw [← mulVec_mulVec, hPv, hEv] set Pr := ((List.finRange (n - k)).map E).prod with hPrdef have hclose : ∀ (b : Fin (n - k) → Bool) (L : List (Fin (n - k))), ∃ c : ℂ, ∃ r : PauliString n, (L.map (fun l => if b l then G l else 1)).prod = c • pauliMatrix r := by intro b L induction L with | nil => exact ⟨1, fun _ => PauliBasis.I, by simp [pauliMatrix_identity_string_eq_one]⟩ | cons a L ih => obtain ⟨c, r, h⟩ := ih obtain ⟨c', r', h'⟩ : ∃ c' : ℂ, ∃ r' : PauliString n, (if b a then G a else 1) = c' • pauliMatrix r' := by by_cases hb : b a · exact ⟨ε a, p a, by simp [hb, hG]⟩ · exact ⟨1, fun _ => PauliBasis.I, by simp [hb, pauliMatrix_identity_string_eq_one]⟩ obtain ⟨c'', r'', h''⟩ := pauliMatrix_mul_exists_smul r' r refine ⟨c' * c * c'', r'', ?_⟩ rw [List.map_cons, List.prod_cons, h, h', smul_mul_smul_comm, h'', smul_smul] have htr0 : ∀ b : Fin (n - k) → Bool, b ≠ (fun _ => false) → (((List.finRange (n - k)).map (fun l => if b l then G l else 1)).prod).trace = 0 := by intro b hb obtain ⟨c, r, h⟩ := hclose b (List.finRange (n - k)) by_cases hr : ∃ i, r i ≠ PauliBasis.I · rw [h, trace_smul, tr_pauli_of_ne_one n r hr, smul_zero] · push Not at hr have hr' : r = fun _ => PauliBasis.I := funext hr exact absurd (by rw [h, hr', pauliMatrix_identity_string_eq_one]) (hind b hb c) have hPr : Pr = (1/2 : ℂ) ^ (n - k) • ∑ b : Fin (n - k) → Bool, ((List.finRange (n - k)).map (fun l => if b l then G l else 1)).prod := by rw [hPrdef, show ((List.finRange (n - k)).map E) = (List.finRange (n - k)).map (fun l => (1/2 : ℂ) • (1 + G l)) from rfl, list_prod_map_smul_eq_pow_smul, List.length_finRange, list_prod_map_one_add_eq_sum] have htrace : Pr.trace = 2 ^ k := by rw [hPr, trace_smul, trace_sum, Finset.sum_eq_single (fun _ => false)] · simp only [Bool.false_eq_true, if_false] rw [List.map_const', List.prod_replicate, one_pow, trace_one] simp only [Fintype.card_fun, Fintype.card_fin, smul_eq_mul] have : (2 : ℂ) ^ n = 2 ^ k * 2 ^ (n - k) := by rw [← pow_add]; congr 1; omega push_cast rw [this, one_div, inv_pow]; field_simp · intro b _ hb; exact htr0 b hb · simp have hPP : Pr * Pr = Pr := (hlist (List.finRange (n - k))).1 have hPfix : ∀ v, Pr *ᵥ v = v ↔ ∀ l, G l *ᵥ v = v := by intro v rw [show Pr = ((List.finRange (n - k)).map E).prod from rfl, (hlist _).2 v] simp have hmemV : ∀ v : Hn n, v ∈ (⨅ l, LinearMap.ker (ε l • pauliOp (p l) - LinearMap.id) : Submodule ℂ (Hn n)) ↔ ∀ l, G l *ᵥ (WithLp.ofLp v) = WithLp.ofLp v := by intro v simp only [Submodule.mem_iInf, LinearMap.mem_ker, LinearMap.sub_apply, LinearMap.smul_apply, LinearMap.id_apply, sub_eq_zero] refine forall_congr' fun l => ?_ have e : ε l • pauliOp (p l) v = WithLp.toLp 2 (G l *ᵥ WithLp.ofLp v) := by simp [pauliOp, hG, Matrix.smul_mulVec] rfl rw [e] constructor · intro h; have := congrArg WithLp.ofLp h; simpa using this · intro h; rw [h] have hproj : LinearMap.IsProj (⨅ l, LinearMap.ker (ε l • pauliOp (p l) - LinearMap.id) : Submodule ℂ (Hn n)) (Matrix.toEuclideanLin Pr) := by constructor · intro x rw [hmemV] have : Pr *ᵥ (Pr *ᵥ WithLp.ofLp x) = Pr *ᵥ WithLp.ofLp x := by rw [mulVec_mulVec, hPP] simpa [Matrix.toEuclideanLin] using (hPfix _).mp this · intro x hx rw [hmemV] at hx have := (hPfix (WithLp.ofLp x)).mpr hx apply WithLp.ofLp_injective simpa [Matrix.toEuclideanLin] using this have htr := hproj.trace have hlin : LinearMap.trace ℂ (Hn n) (Matrix.toEuclideanLin Pr) = Pr.trace := by rw [Matrix.toEuclideanLin_eq_toLin_orthonormal, LinearMap.trace_eq_matrix_trace ℂ (EuclideanSpace.basisFun _ ℂ).toBasis, LinearMap.toMatrix_toLin] rw [hlin, htrace] at htr exact_mod_cast htr.symmtheorem stabilizer_subspace_finrank_eq_two_pow (n k : ℕ) (hk : k ≤ n) (p : Fin (n - k) → PauliString n) (ε : Fin (n - k) → ℂ) (hε : ∀ l, ε l = 1 ∨ ε l = -1) (hcomm : ∀ l l', Commute (pauliMatrix (p l)) (pauliMatrix (p l'))) (hind : ∀ b : Fin (n - k) → Bool, b ≠ (fun _ => false) → ∀ c : ℂ, ((List.finRange (n - k)).map (fun l => if b l then ε l • pauliMatrix (p l) else 1)).prod ≠ c • 1) : Module.finrank ℂ (⨅ l, LinearMap.ker (ε l • pauliOp (p l) - LinearMap.id) : Submodule ℂ (Hn n)) = 2 ^ k := by exact stabilizer_subspace_finrank_eq_two_pow_aux n k hk p ε hε hcomm hind