Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for On the universality of SnS_nSn​-equivariant kkk-body gates

Definition
QAlgorithms_Papers_Independent_Intakenext100_P38

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

The objects the formalized statements of On the universality of SnS_nSn​-equivariant kkk-body gates (arXiv:2303.00728) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • labelPauli: Adapter to the frozen, standard-Y Pauli matrices (PDF p.10, A1).
  • axisCount: Number of occurrences of an axis in a word (PDF pp.5,10).
  • symmetricPauli: PDF pp.5,10, Definitions 3/5: sum of DISTINCT words with the specified counts. Overfull counts give the empty sum. This is neither an average nor a permutation sum.
  • symmetricUnitaryAlgebra: PDF p.3, (10): real skew-Hermitian commutant. The displayed set is itself already a real subspace; taking its span supplies the ambient submodule interface.
  • specialSymmetricAlgebra: PDF p.3, (11): total trace zero, as opposed to independently traceless blocks.
  • algebraCenter: PDF p.4, (16): intrinsic center, without using the sought C-basis theorem. The commuting subset is a real subspace.
  • centerlessSymmetricAlgebra: PDF p.3, (12): derived algebra of the compact skew commutant. For a compact reductive algebra, this intrinsic construction is the independently traceless multiplicity-block algebra. No coefficient constraint is built into this definition.
  • generatedSkewLie: PDF p.2, (2): Mathlib real Lie closure for an arbitrary Hermitian generator set. The accepted Support50.P30.dynamicalLie instead fixes its three normalized generators, so it cannot represent arbitrary G or the higher-body families.
  • generators1: PDF p.4, (21): the single collective-X generator.
  • generators1XY: PDF p.4, (22): the collective X,Y generators.
  • generators2: PDF pp.4–5, (23): the unnormalized Hermitian two-body generator set.
  • generatorsK: PDF p.6, (36): collectives X,Y and every all-Z weight from 2 through k.
  • g2
  • gK
  • levelTriples: Finite simplex at level m, including all boundary faces (PDF pp.5,10).
  • centralWeight: PDF p.5, (28): real factorial coefficient, cast BEFORE division.
  • centralElement: PDF pp.5,11, (28)/(B2): the Hermitian central candidate C_mu; C_0=I.
  • centralSpan: PDF pp.6,20: the nonidentity central directions available through order 2r.
  • coefficientCombination: PDF pp.5–6, (30)/(33): the full skew combination of real Pauli coefficients.
  • centralCoefficient: PDF p.5, (31): the weighted central coefficient at level 2mu.
  • IsSemiUniversal: PDF p.4, Definition 2: independent special-unitary control of every block.
  • IsEquivariantlyUniversal: PDF p.4, Definition 2 (15): exact equivariant universality up to one global phase. The frozen QAlgorithms.IsUniversal instead concerns approximation by circuits over a gate set on all register sizes; it is a different predicate.
  • CentralProjector: PDF pp.3–4: Hermitian central projections of the actual equivariant algebra. Minimal nonzero such projections are the canonical isotypic sectors.
  • IsCentralSector: PDF pp.3–4: a single isotypic sector, specified without a chosen Schur frame.
  • IsSubspaceControllable: PDF p.4, (13): every individual sector image contains its full special unitary algebra. E times the derived commutant is the repeated su(m_lambda) action on that sector. The existential M can depend on E and B, so this is individual control and does not impose simultaneous independent block control.
  • pauliDegreeSpace: PDF p.6, Corollary 1: sums of Pauli terms of support at most k. A collective generator need not have a common set of k supported wires.
  • rotationCommutant: PDF p.11, (B3)/(B5): skew commutant of all collective U(2) rotations.
  • permutationImage: PDF pp.11–12: corrected meaning of S_n in (B3). Printed real span of iR(pi) is not skew for general permutations; use the skew part of the COMPLEX permutation group-algebra image, as required by the proof.
  • transpositionClass: PDF p.12, Definition 6: involutions with exactly 2mu moved points are precisely products of mu disjoint transpositions. The remaining points are fixed.
  • transpositionSum: PDF p.12, (B7): sum over distinct permutations in the transposition class.
  • transpositionPauliExpansion: PDF p.12, (B12) corrected by p.13, (B17)–(B18): explicit four-index sum.
  • transpositionCentralExpansion: PDF p.12, (B13): triangular expansion in the C-prefix.
  • axisRelabel: PDF p.15, Lemma 4: coefficient permutation on the FULL Pauli-word basis, fixing I. This complex-linear map is not asserted to be a unitary conjugation.
  • appendixPauli: PDF p.21, Note G changes BOTH Y to -Y and P to iP.
  • correctionA: PDF p.22, (G4): the computed A, not an arbitrary input.
  • correctionB: PDF p.22, (G5): the computed B.
  • correctionC: PDF p.22, (G6): the computed C. Scalars use real subtraction.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_QECC
import Definitions.Def_QAlgorithms_Defs_GradientMethods
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P30

/-!
Statements from Kazi, Larocca and Cerezo, arXiv:2303.00728v2.
All spans and Lie closures are over the reals unless explicitly marked complex.
Paper-local definitions implement this paper only; matching accepted interfaces are imported. Compilation is pending batch handoff.
-/

noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P38

open scoped BigOperators

open QAlgorithms.Papers.Independent.Support50.P30
  (QnnOperator qubitPermutationMatrix PermutationEquivariant)

attribute [local instance] LieRing.ofAssociativeRing

/-- Adapter to the frozen, standard-Y Pauli matrices (PDF p.10, A1). -/
def labelPauli : (Option (Fin 3)) → Stabilizer.Pauli
  | none => .I
  | some j => if j = 0 then .X else if j = 1 then .Y else .Z

/-- Number of occurrences of an axis in a word (PDF pp.5,10). -/
def axisCount {n : ℕ} (w : Fin n → (Option (Fin 3))) (a : Fin 3) : ℕ :=
  (Finset.univ.filter fun j => w j = some a).card

/-- PDF pp.5,10, Definitions 3/5: sum of DISTINCT words with the specified counts.
Overfull counts give the empty sum. This is neither an average nor a permutation sum. -/
def symmetricPauli (n x y z : ℕ) : QnnOperator n :=
  ∑ w ∈ (Finset.univ : Finset (Fin n → (Option (Fin 3)))).filter
    (fun w => axisCount w 0 = x ∧ axisCount w 1 = y ∧ axisCount w 2 = z),
    pauliOps (fun j => labelPauli (w j))

/-- PDF p.3, (10): real skew-Hermitian commutant. The displayed set is itself
already a real subspace; taking its span supplies the ambient submodule interface. -/
def symmetricUnitaryAlgebra (n : ℕ) : Submodule ℝ (QnnOperator n) :=
  Submodule.span ℝ {A | A.conjTranspose = -A ∧ PermutationEquivariant A}

/-- PDF p.3, (11): total trace zero, as opposed to independently traceless blocks. -/
def specialSymmetricAlgebra (n : ℕ) : Submodule ℝ (QnnOperator n) :=
  Submodule.span ℝ {A | A ∈ symmetricUnitaryAlgebra n ∧ Matrix.trace A = 0}

/-- PDF p.4, (16): intrinsic center, without using the sought C-basis theorem.
The commuting subset is a real subspace. -/
def algebraCenter {n : ℕ} (g : Submodule ℝ (QnnOperator n)) : Submodule ℝ (QnnOperator n) :=
  Submodule.span ℝ {A | A ∈ g ∧ ∀ B ∈ g, A * B = B * A}

/-- PDF p.3, (12): derived algebra of the compact skew commutant. For a compact
reductive algebra, this intrinsic construction is the independently traceless
multiplicity-block algebra. No coefficient constraint is built into this definition. -/
def centerlessSymmetricAlgebra (n : ℕ) : Submodule ℝ (QnnOperator n) :=
  Submodule.span ℝ {M | ∃ A ∈ symmetricUnitaryAlgebra n,
    ∃ B ∈ symmetricUnitaryAlgebra n, M = A * B - B * A}

/-- PDF p.2, (2): Mathlib real Lie closure for an arbitrary Hermitian generator set.
The accepted Support50.P30.dynamicalLie instead fixes its three normalized
generators, so it cannot represent arbitrary G or the higher-body families. -/
def generatedSkewLie {n : ℕ} (G : Set (QnnOperator n)) : LieSubalgebra ℝ (QnnOperator n) :=
  LieSubalgebra.lieSpan ℝ (QnnOperator n) ((fun H => Complex.I • H) '' G)

/-- PDF p.4, (21): the single collective-X generator. -/
def generators1 (n : ℕ) : Set (QnnOperator n) := {symmetricPauli n 1 0 0}

/-- PDF p.4, (22): the collective X,Y generators. -/
def generators1XY (n : ℕ) : Set (QnnOperator n) :=
  {symmetricPauli n 1 0 0, symmetricPauli n 0 1 0}

/-- PDF pp.4–5, (23): the unnormalized Hermitian two-body generator set. -/
def generators2 (n : ℕ) : Set (QnnOperator n) :=
  {symmetricPauli n 1 0 0, symmetricPauli n 0 1 0, symmetricPauli n 0 0 2}

/-- PDF p.6, (36): collectives X,Y and every all-Z weight from 2 through k. -/
def generatorsK (n k : ℕ) : Set (QnnOperator n) :=
  {symmetricPauli n 1 0 0, symmetricPauli n 0 1 0} ∪
    {H | ∃ j : ℕ, 2 ≤ j ∧ j ≤ k ∧ H = symmetricPauli n 0 0 j}

abbrev g2 (n : ℕ) := generatedSkewLie (generators2 n)

abbrev gK (n k : ℕ) := generatedSkewLie (generatorsK n k)

/-- Finite simplex at level m, including all boundary faces (PDF pp.5,10). -/
def levelTriples (m : ℕ) : Finset (ℕ × ℕ × ℕ) :=
  ((Finset.range (m + 1)) ×ˢ ((Finset.range (m + 1)) ×ˢ
    (Finset.range (m + 1)))).filter fun t => t.1 + t.2.1 + t.2.2 = m

/-- PDF p.5, (28): real factorial coefficient, cast BEFORE division. -/
def centralWeight (a b c : ℕ) : ℝ :=
  ((2 * a).factorial : ℝ) * ((2 * b).factorial : ℝ) * ((2 * c).factorial : ℝ) /
    ((a.factorial : ℝ) * (b.factorial : ℝ) * (c.factorial : ℝ))

/-- PDF pp.5,11, (28)/(B2): the Hermitian central candidate C_mu; C_0=I. -/
def centralElement (n mu : ℕ) : QnnOperator n :=
  ∑ t ∈ levelTriples mu, centralWeight t.1 t.2.1 t.2.2 •
    symmetricPauli n (2 * t.1) (2 * t.2.1) (2 * t.2.2)

/-- PDF pp.6,20: the nonidentity central directions available through order 2r. -/
def centralSpan (n r : ℕ) : Submodule ℝ (QnnOperator n) :=
  Submodule.span ℝ {A | ∃ mu : ℕ, 1 ≤ mu ∧ mu ≤ r ∧
    A = Complex.I • centralElement n mu}

/-- PDF pp.5–6, (30)/(33): the full skew combination of real Pauli coefficients. -/
def coefficientCombination (n : ℕ) (c : ℕ → ℕ → ℕ → ℝ) : QnnOperator n :=
  Complex.I • (∑ x ∈ Finset.range (n + 1), ∑ y ∈ Finset.range (n + 1),
    ∑ z ∈ Finset.range (n + 1),
      if x + y + z ≤ n then c x y z • symmetricPauli n x y z else 0)

/-- PDF p.5, (31): the weighted central coefficient at level 2mu. -/
def centralCoefficient (c : ℕ → ℕ → ℕ → ℝ) (mu : ℕ) : ℝ :=
  ∑ t ∈ levelTriples mu, c (2 * t.1) (2 * t.2.1) (2 * t.2.2) /
    ((t.1.factorial : ℝ) * (t.2.1.factorial : ℝ) * (t.2.2.factorial : ℝ))

/-- PDF p.4, Definition 2: independent special-unitary control of every block. -/
def IsSemiUniversal {n : ℕ} (g : Submodule ℝ (QnnOperator n)) : Prop :=
  centerlessSymmetricAlgebra n ≤ g ∧ g ≤ symmetricUnitaryAlgebra n

/-- PDF p.4, Definition 2 (15): exact equivariant universality up to one global phase.
The frozen QAlgorithms.IsUniversal instead concerns approximation by circuits
over a gate set on all register sizes; it is a different predicate. -/
def IsEquivariantlyUniversal {n : ℕ} (g : Submodule ℝ (QnnOperator n)) : Prop :=
  specialSymmetricAlgebra n ≤ g ∧ g ≤ symmetricUnitaryAlgebra n

/-- PDF pp.3–4: Hermitian central projections of the actual equivariant algebra.
Minimal nonzero such projections are the canonical isotypic sectors. -/
def CentralProjector (n : ℕ) (E : QnnOperator n) : Prop :=
  E.IsHermitian ∧ E * E = E ∧ PermutationEquivariant E ∧
    ∀ A ∈ symmetricUnitaryAlgebra n, E * A = A * E

/-- PDF pp.3–4: a single isotypic sector, specified without a chosen Schur frame. -/
def IsCentralSector (n : ℕ) (E : QnnOperator n) : Prop :=
  E ≠ 0 ∧ CentralProjector n E ∧
    ∀ F : QnnOperator n, CentralProjector n F → F * E = F → F = 0 ∨ F = E

/-- PDF p.4, (13): every individual sector image contains its full special
unitary algebra. E times the derived commutant is the repeated su(m_lambda)
action on that sector. The existential M can depend on E and B, so this is
individual control and does not impose simultaneous independent block control. -/
def IsSubspaceControllable {n : ℕ} (g : Submodule ℝ (QnnOperator n)) : Prop :=
  g ≤ symmetricUnitaryAlgebra n ∧
    ∀ E : QnnOperator n, IsCentralSector n E →
      ∀ B ∈ centerlessSymmetricAlgebra n, ∃ M ∈ g, E * M = E * B

/-- PDF p.6, Corollary 1: sums of Pauli terms of support at most k.
A collective generator need not have a common set of k supported wires. -/
def pauliDegreeSpace (n k : ℕ) : Submodule ℝ (QnnOperator n) :=
  Submodule.span ℝ {A | ∃ w : Fin n → (Option (Fin 3)),
    (Finset.univ.filter fun j => w j ≠ none).card ≤ k ∧ A = pauliOps (fun j => labelPauli (w j))}

/-- PDF p.11, (B3)/(B5): skew commutant of all collective U(2) rotations. -/
def rotationCommutant (n : ℕ) : Submodule ℝ (QnnOperator n) :=
  Submodule.span ℝ {A | A.conjTranspose = -A ∧
    ∀ U : Matrix.unitaryGroup Bool ℂ, A * piKron n (U : Matrix Bool Bool ℂ) = piKron n (U : Matrix Bool Bool ℂ) * A}

/-- PDF pp.11–12: corrected meaning of S_n in (B3).
Printed real span of iR(pi) is not skew for general permutations; use the skew
part of the COMPLEX permutation group-algebra image, as required by the proof. -/
def permutationImage (n : ℕ) : Submodule ℝ (QnnOperator n) :=
  Submodule.span ℝ {A | A.conjTranspose = -A ∧
    A ∈ Submodule.span ℂ (Set.range (qubitPermutationMatrix n))}

/-- PDF p.12, Definition 6: involutions with exactly 2mu moved points are
precisely products of mu disjoint transpositions. The remaining points are fixed. -/
def transpositionClass (n mu : ℕ) : Finset (Equiv.Perm (Fin n)) :=
  Finset.univ.filter fun pi => pi * pi = 1 ∧
    (Finset.univ.filter fun j => pi j ≠ j).card = 2 * mu

/-- PDF p.12, (B7): sum over distinct permutations in the transposition class. -/
def transpositionSum (n mu : ℕ) : QnnOperator n :=
  ∑ pi ∈ transpositionClass n mu, qubitPermutationMatrix n pi

/-- PDF p.12, (B12) corrected by p.13, (B17)–(B18): explicit four-index sum. -/
def transpositionPauliExpansion (n mu : ℕ) : QnnOperator n :=
  (((4 : ℝ) ^ mu)⁻¹ / (n - 2 * mu).factorial) •
    (∑ a ∈ Finset.range (mu + 1), ∑ b ∈ Finset.range (mu + 1),
      ∑ c ∈ Finset.range (mu + 1), ∑ f ∈ Finset.range (mu + 1),
        if a + b + c + f = mu then
          (centralWeight a b c * ((n - 2 * (mu - f)).factorial : ℝ) /
            (f.factorial : ℝ)) • symmetricPauli n (2 * a) (2 * b) (2 * c)
        else 0)

/-- PDF p.12, (B13): triangular expansion in the C-prefix. -/
def transpositionCentralExpansion (n mu : ℕ) : QnnOperator n :=
  (((4 : ℝ) ^ mu)⁻¹ / (n - 2 * mu).factorial) •
    ∑ j ∈ Finset.range (mu + 1),
      (((n - 2 * j).factorial : ℝ) / ((mu - j).factorial : ℝ)) • centralElement n j

/-- PDF p.15, Lemma 4: coefficient permutation on the FULL Pauli-word basis,
fixing I. This complex-linear map is not asserted to be a unitary conjugation. -/
def axisRelabel {n : ℕ} (sigma : Equiv.Perm (Fin 3)) (A : QnnOperator n) : QnnOperator n :=
  ∑ w : Fin n → (Option (Fin 3)),
    (Matrix.trace (pauliOps (fun j => labelPauli (w j)) * A) / (2 : ℂ) ^ n) •
      pauliOps (fun j => labelPauli (Option.map sigma (w j)))

/-- PDF p.21, Note G changes BOTH Y to -Y and P to iP. -/
def appendixPauli (n x y z : ℕ) : QnnOperator n :=
  Complex.I • (((-1 : ℝ) ^ y) • symmetricPauli n x y z)

/-- PDF p.22, (G4): the computed A, not an arbitrary input. -/
def correctionA (n k : ℕ) : QnnOperator n :=
  (-4 : ℝ) • appendixPauli n (k - 2) 2 0 +
    (2 * (k : ℝ)) • appendixPauli n k 0 0

/-- PDF p.22, (G5): the computed B. -/
def correctionB (n k : ℕ) : QnnOperator n :=
  (4 : ℝ) • appendixPauli n (k - 2) 0 2 -
    (2 * (k : ℝ)) • appendixPauli n k 0 0

/-- PDF p.22, (G6): the computed C. Scalars use real subtraction. -/
def correctionC (n k : ℕ) : QnnOperator n :=
  (-4 * ((k : ℝ) - 2)) • appendixPauli n (k - 2) 2 0 -
    (4 : ℝ) • appendixPauli n (k - 2) 0 2 +
    (2 * (k : ℝ) * ((k : ℝ) - 1)) • appendixPauli n k 0 0

/-- Structural sanity: a source generator enters the actual Lie closure. -/
example {n : ℕ} {G : Set (QnnOperator n)} {H : QnnOperator n} (h : H ∈ G) :
    Complex.I • H ∈ generatedSkewLie G :=
  LieSubalgebra.subset_lieSpan (Set.mem_image_of_mem _ h)

/-- Structural sanity: the zero-generator boundary has zero Lie closure. -/
example (n : ℕ) : generatedSkewLie (∅ : Set (QnnOperator n)) = ⊥ := by
  simp [generatedSkewLie, LieSubalgebra.span_empty]

/-- Scalar sanity: the three coefficients of C_1 are 2 (PDF p.5). -/
example : centralWeight 1 0 0 = 2 := by norm_num [centralWeight]

/-- Convention sanity: the local Y adapter is the frozen standard Pauli Y. -/
example : labelPauli (some 1) = Stabilizer.Pauli.Y := by
  norm_num [labelPauli]

/-- Convention sanity: Note G's odd-Y sign is negative. -/
example (n x z : ℕ) : appendixPauli n x 1 z =
    Complex.I • ((-1 : ℝ) • symmetricPauli n x 1 z) := by
  simp [appendixPauli]

/-- Sector sanity: the zero projection is explicitly excluded. -/
example (n : ℕ) : ¬ IsCentralSector n 0 := by
  intro h
  exact h.1 rfl

/-- Empty-register sanity: no word contains a nonidentity axis. -/
example (w : Fin 0 → (Option (Fin 3))) (a : Fin 3) : axisCount w a = 0 := by
  simp [axisCount]

/-- Simplex sanity: the zero level consists of exactly its origin. -/
example : levelTriples 0 = {(0, 0, 0)} := by
  norm_num [levelTriples]

/-- Central sanity: the zero coefficient constraint is exactly total trace zero. -/
example (c : ℕ → ℕ → ℕ → ℝ) : centralCoefficient c 0 = c 0 0 0 := by
  unfold centralCoefficient
  have hzero : levelTriples 0 = {(0, 0, 0)} := by
    norm_num [levelTriples]
  rw [hzero]
  norm_num

/-- Central normalization sanity: C_0 is the identity Pauli sum. -/
example (n : ℕ) : centralElement n 0 = symmetricPauli n 0 0 0 := by
  unfold centralElement
  have hzero : levelTriples 0 = {(0, 0, 0)} := by
    norm_num [levelTriples]
  rw [hzero]
  norm_num [centralWeight]

/-- Generator sanity: the original Hermitian ZZ sum is present without scaling. -/
example (n : ℕ) : symmetricPauli n 0 0 2 ∈ generators2 n := by
  simp [generators2]

/-- Tensor-power boundary sanity: U to the zeroth tensor power is scalar one. -/
example (U : Matrix.unitaryGroup Bool ℂ) (a b : Qubits 0) :
    piKron 0 (U : Matrix Bool Bool ℂ) a b = 1 := by
  simp [piKron]

end QAlgorithms.Papers.Independent.Intakenext100.P38
Source
On the universality of SnS_nSn​-equivariant kkk-body gates, arXiv:2303.00728v2, https://arxiv.org/abs/2303.00728v2
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

QAlgorithms.Papers.Independent.Intakenext100.P38.CentralProjector

For every natural number nnn and every complex matrix EEE indexed by nnn-bit strings, CentralProjector⁡(n,E)\operatorname{CentralProjector}(n,E)CentralProjector(n,E) means that E†=EE^\dagger=EE†=E, E2=EE^2=EE2=E, EPp=PpEEP_p=P_pEEPp​=Pp​E for every permutation ppp of the nnn sites, and EA=AEEA=AEEA=AE for every A∈AnA\in\mathcal A_nA∈An​. Here (Pp)x,y=1(P_p)_{x,y}=1(Pp​)x,y​=1 exactly when xj=yp−1(j)x_j=y_{p^{-1}(j)}xj​=yp−1(j)​ at every site, and is zero otherwise; An\mathcal A_nAn​ is the real linear span of all matrices BBB satisfying B†=−BB^\dagger=-BB†=−B and commuting with every PpP_pPp​. Nonzeroness is not required: both the zero matrix and the identity satisfy these conditions. The definition also applies to n=0n=0n=0, where the matrices have size one and the conditions permit precisely the scalar projectors zero and one.

QAlgorithms.Papers.Independent.Intakenext100.P38.IsCentralSector

For every natural number nnn and every complex matrix EEE indexed by nnn-bit strings, IsCentralSector⁡(n,E)\operatorname{IsCentralSector}(n,E)IsCentralSector(n,E) means that E≠0E\ne0E=0, E†=EE^\dagger=EE†=E, E2=EE^2=EE2=E, EEE commutes with every site-permutation matrix PpP_pPp​, and EEE commutes with every matrix in An\mathcal A_nAn​; moreover, every complex matrix FFF satisfying F†=FF^\dagger=FF†=F, F2=FF^2=FF2=F, commutation with every PpP_pPp​, commutation with every member of An\mathcal A_nAn​, and FE=FFE=FFE=F, must satisfy F=0F=0F=0 or F=EF=EF=E. Here (Pp)x,y(P_p)_{x,y}(Pp​)x,y​ is one exactly when xj=yp−1(j)x_j=y_{p^{-1}(j)}xj​=yp−1(j)​ for all sites jjj, and zero otherwise, and An\mathcal A_nAn​ is the real linear span of the skew-Hermitian matrices commuting with all these permutation matrices. The minimality condition quantifies only over projectors satisfying those commutation conditions and uses precisely the equation FE=FFE=FFE=F. The case n=0n=0n=0 is included, in which the sole such nonzero projector is the one-dimensional identity.

QAlgorithms.Papers.Independent.Intakenext100.P38.IsEquivariantlyUniversal

For every natural number nnn and every real linear subspace ggg of complex matrices indexed by nnn-bit strings, IsEquivariantlyUniversal⁡(g)\operatorname{IsEquivariantlyUniversal}(g)IsEquivariantlyUniversal(g) means

span⁡R{A∈An:tr⁡A=0} ⊆ g ⊆ An.\operatorname{span}_{\mathbb R}\{A\in\mathcal A_n:\operatorname{tr}A=0\} \ \subseteq\ g\ \subseteq\ \mathcal A_n.spanR​{A∈An​:trA=0} ⊆ g ⊆ An​.

Here An\mathcal A_nAn​ is the real linear span of all matrices AAA with A†=−AA^\dagger=-AA†=−A that commute with every site-permutation matrix PpP_pPp​, whose entry (Pp)x,y(P_p)_{x,y}(Pp​)x,y​ is one exactly when xj=yp−1(j)x_j=y_{p^{-1}(j)}xj​=yp−1(j)​ for all sites jjj, and zero otherwise. The trace condition is equality to zero as a complex number, and both inclusions permit equality. No separate assumption that ggg is closed under commutators is made. The case n=0n=0n=0 is included: the trace-zero generating set contributes only zero, and the upper space consists of purely imaginary scalar matrices.

QAlgorithms.Papers.Independent.Intakenext100.P38.IsSemiUniversal

For every natural number nnn and every real linear subspace ggg of the complex matrices indexed by nnn-bit strings, IsSemiUniversal⁡(g)\operatorname{IsSemiUniversal}(g)IsSemiUniversal(g) means

span⁡R{AB−BA:A,B∈An} ⊆ g ⊆ An,\operatorname{span}_{\mathbb R}\{AB-BA:A,B\in\mathcal A_n\} \ \subseteq\ g\ \subseteq\ \mathcal A_n,spanR​{AB−BA:A,B∈An​} ⊆ g ⊆ An​,

where An\mathcal A_nAn​ is the real linear span of all matrices AAA satisfying A†=−AA^\dagger=-AA†=−A and APp=PpAAP_p=P_pAAPp​=Pp​A for every permutation ppp of the nnn sites. The permutation matrix is defined by (Pp)x,y=1(P_p)_{x,y}=1(Pp​)x,y​=1 when xj=yp−1(j)x_j=y_{p^{-1}(j)}xj​=yp−1(j)​ for every site jjj, and is zero otherwise. Both inclusions are non-strict, and ggg is assumed only to be a real linear subspace; closure of ggg under commutators is not an additional hypothesis in this definition. The definition includes n=0n=0n=0, for which the left-hand span is zero and A0\mathcal A_0A0​ consists of purely imaginary scalar matrices.

QAlgorithms.Papers.Independent.Intakenext100.P38.IsSubspaceControllable

For any natural number nnn, including 000, let Qn={0,1}n\mathcal Q_n=\{0,1\}^nQn​={0,1}n, and let ggg be a real linear subspace of the complex matrices indexed by Qn\mathcal Q_nQn​. For a permutation ppp of the nnn positions, define Pp(x,y)=1P_p(x,y)=1Pp​(x,y)=1 if xj=yp−1(j)x_j=y_{p^{-1}(j)}xj​=yp−1(j)​ for every jjj, and 000 otherwise. Let s\mathfrak ss be the real span of all matrices AAA satisfying A†=−AA^\dagger=-AA†=−A and APp=PpAAP_p=P_pAAPp​=Pp​A for every ppp, and let d\mathfrak dd be the real span of all commutators AB−BAAB-BAAB−BA with A,B∈sA,B\in\mathfrak sA,B∈s. The predicate says that g⊆sg\subseteq\mathfrak sg⊆s and that, for every nonzero matrix EEE satisfying E†=EE^\dagger=EE†=E, E2=EE^2=EE2=E, EPp=PpEEP_p=P_pEEPp​=Pp​E for every ppp, and EA=AEEA=AEEA=AE for every A∈sA\in\mathfrak sA∈s, with the additional property that every matrix FFF satisfying these same four conditions and FE=FFE=FFE=F is either 000 or EEE, one has

∀B∈d,∃M∈g,EM=EB.\forall B\in\mathfrak d,\quad \exists M\in g,\quad EM=EB.∀B∈d,∃M∈g,EM=EB.

The matrix MMM may depend on both EEE and BBB; if there are no such nonzero matrices EEE, this quantified requirement is vacuous.

QAlgorithms.Papers.Independent.Intakenext100.P38.algebraCenter

For every natural number nnn and every real linear subspace ggg of the complex matrices indexed by nnn-bit strings, this defines

span⁡R{A∈g:∀B∈g, AB=BA}.\operatorname{span}_{\mathbb R} \{A\in g:\forall B\in g,\ AB=BA\}.spanR​{A∈g:∀B∈g, AB=BA}.

Thus its spanning matrices belong to ggg and commute with every matrix in ggg. There is no additional hypothesis that ggg is closed under multiplication or commutators; n=0n=0n=0 and g={0}g=\{0\}g={0} are included.

QAlgorithms.Papers.Independent.Intakenext100.P38.appendixPauli

For natural numbers n,x,y,zn,x,y,zn,x,y,z, let Sn(x,y,z)S_n(x,y,z)Sn​(x,y,z) be the sum of all tensor products on nnn positions having exactly xxx factors equal to the standard Pauli matrix XXX, yyy factors equal to YYY, and zzz factors equal to ZZZ, with identity factors elsewhere. This definition is the complex matrix

i(−1)ySn(x,y,z).i(-1)^yS_n(x,y,z).i(−1)ySn​(x,y,z).

The sum is zero when x+y+z>nx+y+z>nx+y+z>n. For n=0n=0n=0, it is iii as a 1×11\times11×1 matrix when x=y=z=0x=y=z=0x=y=z=0, and is zero otherwise.

QAlgorithms.Papers.Independent.Intakenext100.P38.axisCount

For every natural number nnn, every assignment w:{0,…,n−1}→{none,0,1,2}w:\{0,\ldots,n-1\}\to\{\mathrm{none},0,1,2\}w:{0,…,n−1}→{none,0,1,2}, and every a∈{0,1,2}a\in\{0,1,2\}a∈{0,1,2}, this defines the number of positions assigned the present label aaa:

axisCount⁡(w,a)=∣{j<n:w(j)=a}∣.\operatorname{axisCount}(w,a)=\bigl|\{j<n:w(j)=a\}\bigr|.axisCount(w,a)=​{j<n:w(j)=a}​.

Positions assigned none\mathrm{none}none are excluded. For n=0n=0n=0, the count is 000.

QAlgorithms.Papers.Independent.Intakenext100.P38.axisRelabel

For every natural number nnn, every permutation σ\sigmaσ of the three labels {0,1,2}\{0,1,2\}{0,1,2}, and every complex matrix AAA indexed by nnn-bit strings, define L(none)=IL(\mathrm{none})=IL(none)=I, L(0)=XL(0)=XL(0)=X, L(1)=YL(1)=YL(1)=Y, and L(2)=ZL(2)=ZL(2)=Z, where X,Y,ZX,Y,ZX,Y,Z are the standard Pauli matrices, and put Pw=⨂j=0n−1L(wj)P_w=\bigotimes_{j=0}^{n-1}L(w_j)Pw​=⨂j=0n−1​L(wj​). The definition is

∑w∈{none,0,1,2}ntr⁡(PwA)2n Pσ∗w,\sum_{w\in\{\mathrm{none},0,1,2\}^{n}} \frac{\operatorname{tr}(P_wA)}{2^n}\, P_{\sigma_*w},w∈{none,0,1,2}n∑​2ntr(Pw​A)​Pσ∗​w​,

where (σ∗w)j=none(\sigma_*w)_j=\mathrm{none}(σ∗​w)j​=none when wj=nonew_j=\mathrm{none}wj​=none and (σ∗w)j=σ(wj)(\sigma_*w)_j=\sigma(w_j)(σ∗​w)j​=σ(wj​) otherwise. In particular, identity factors remain identity factors, and the coefficient uses tr⁡(PwA)\operatorname{tr}(P_wA)tr(Pw​A) without a conjugate transpose. No Hermiticity or symmetry assumption is made on AAA. For n=0n=0n=0, the single empty tensor product is 111, and the definition returns AAA.

QAlgorithms.Papers.Independent.Intakenext100.P38.centerlessSymmetricAlgebra

For every natural number nnn, let An\mathcal A_nAn​ be the real linear span of all complex matrices indexed by nnn-bit strings that are skew-Hermitian and commute with every position-permutation matrix PpP_pPp​, where PpP_pPp​ sends the basis vector indexed by vvv to that indexed by v∘p−1v\circ p^{-1}v∘p−1. This defines the real linear span of all commutators of two members of that subspace:

span⁡R{AB−BA:A∈An, B∈An}.\operatorname{span}_{\mathbb R}\{AB-BA:A\in\mathcal A_n,\ B\in\mathcal A_n\}.spanR​{AB−BA:A∈An​, B∈An​}.

The definition includes n=0n=0n=0, when all such commutators are zero.

QAlgorithms.Papers.Independent.Intakenext100.P38.centralCoefficient

For every function c:N3→Rc:\mathbb N^3\to\mathbb Rc:N3→R and every natural number μ\muμ, the real number centralCoefficient⁡(c,μ)\operatorname{centralCoefficient}(c,\mu)centralCoefficient(c,μ) is

∑a,b,d∈Na+b+d=μc(2a,2b,2d)a! b! d!.\sum_{\substack{a,b,d\in\mathbb N\\a+b+d=\mu}} \frac{c(2a,2b,2d)}{a!\,b!\,d!}.a,b,d∈Na+b+d=μ​∑​a!b!d!c(2a,2b,2d)​.

All ordered triples of nonnegative integers summing to μ\muμ occur once, and every factorial denominator is nonzero. There are no restrictions on ccc, and no qubit-count parameter or degree cutoff is imposed. For μ=0\mu=0μ=0, the value is c(0,0,0)c(0,0,0)c(0,0,0).

QAlgorithms.Papers.Independent.Intakenext100.P38.centralElement

For every pair of natural numbers n,μn,\mun,μ, centralElement⁡(n,μ)\operatorname{centralElement}(n,\mu)centralElement(n,μ) is the complex matrix indexed by nnn-bit strings given by

∑a,b,c∈Na+b+c=μ(2a)! (2b)! (2c)!a! b! c! S2a,2b,2c.\sum_{\substack{a,b,c\in\mathbb N\\a+b+c=\mu}} \frac{(2a)!\,(2b)!\,(2c)!}{a!\,b!\,c!}\,S_{2a,2b,2c}.a,b,c∈Na+b+c=μ​∑​a!b!c!(2a)!(2b)!(2c)!​S2a,2b,2c​.

Here Sx,y,zS_{x,y,z}Sx,y,z​ sums all tensor products with exactly xxx factors X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), yyy factors Y=(0−ii0)Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix}Y=(0i​−i0​), zzz factors Z=diag⁡(1,−1)Z=\operatorname{diag}(1,-1)Z=diag(1,−1), and identity factors on the remaining sites, each assignment counted once. A sum with x+y+z>nx+y+z>nx+y+z>n is empty and equals zero. Thus this definition allows μ=0\mu=0μ=0, in which case it gives the identity matrix, including the one-dimensional identity when n=0n=0n=0; it gives zero whenever 2μ>n2\mu>n2μ>n.

QAlgorithms.Papers.Independent.Intakenext100.P38.centralSpan

For all natural numbers n,rn,rn,r, centralSpan⁡(n,r)\operatorname{centralSpan}(n,r)centralSpan(n,r) is the real linear span, inside the complex matrices indexed by nnn-bit strings, of

{i∑a,b,c∈Na+b+c=μ(2a)! (2b)! (2c)!a! b! c! S2a,2b,2c: μ∈N, 1≤μ≤r}.\left\{ i\sum_{\substack{a,b,c\in\mathbb N\\a+b+c=\mu}} \frac{(2a)!\,(2b)!\,(2c)!}{a!\,b!\,c!}\,S_{2a,2b,2c} :\ \mu\in\mathbb N,\ 1\le\mu\le r \right\}.⎩⎨⎧​ia,b,c∈Na+b+c=μ​∑​a!b!c!(2a)!(2b)!(2c)!​S2a,2b,2c​: μ∈N, 1≤μ≤r⎭⎬⎫​.

Here Sx,y,zS_{x,y,z}Sx,y,z​ is the sum, once per assignment, of tensor products with xxx factors X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), yyy factors Y=(0−ii0)Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix}Y=(0i​−i0​), zzz factors Z=diag⁡(1,−1)Z=\operatorname{diag}(1,-1)Z=diag(1,−1), and identities elsewhere. It is zero if x+y+z>nx+y+z>nx+y+z>n. The span consists of finite real linear combinations of the displayed generators. For r=0r=0r=0 the generating set is empty and the span is {0}\{0\}{0}; generators with 2μ>n2\mu>n2μ>n vanish, so the span is also {0}\{0\}{0} for n=0n=0n=0 or n=1n=1n=1.

QAlgorithms.Papers.Independent.Intakenext100.P38.centralWeight

For all natural numbers a,b,ca,b,ca,b,c, the real number centralWeight⁡(a,b,c)\operatorname{centralWeight}(a,b,c)centralWeight(a,b,c) is

(2a)! (2b)! (2c)!a! b! c!,\frac{(2a)!\,(2b)!\,(2c)!}{a!\,b!\,c!},a!b!c!(2a)!(2b)!(2c)!​,

with the factorials interpreted as real numbers in this quotient. Zero arguments are allowed, with 0!=10!=10!=1; consequently the denominator never vanishes, and centralWeight⁡(0,0,0)=1\operatorname{centralWeight}(0,0,0)=1centralWeight(0,0,0)=1.

QAlgorithms.Papers.Independent.Intakenext100.P38.coefficientCombination

For every natural number nnn and every function c:N3→Rc:\mathbb N^3\to\mathbb Rc:N3→R, coefficientCombination⁡(n,c)\operatorname{coefficientCombination}(n,c)coefficientCombination(n,c) is the complex matrix indexed by nnn-bit strings

i∑x,y,z∈Nx+y+z≤nc(x,y,z) Sx,y,z.i\sum_{\substack{x,y,z\in\mathbb N\\x+y+z\le n}}c(x,y,z)\,S_{x,y,z}.ix,y,z∈Nx+y+z≤n​∑​c(x,y,z)Sx,y,z​.

Here Sx,y,zS_{x,y,z}Sx,y,z​ sums, once each, all tensor products with exactly xxx factors X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), yyy factors Y=(0−ii0)Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix}Y=(0i​−i0​), zzz factors Z=diag⁡(1,−1)Z=\operatorname{diag}(1,-1)Z=diag(1,−1), and identity factors elsewhere. The coefficients are arbitrary real numbers; only those with x+y+z≤nx+y+z\le nx+y+z≤n are used. The term x=y=z=0x=y=z=0x=y=z=0 is included and equals c(0,0,0)c(0,0,0)c(0,0,0) times the identity before multiplication by iii. In particular, for n=0n=0n=0 the result is i c(0,0,0)i\,c(0,0,0)ic(0,0,0) times the one-dimensional identity.

QAlgorithms.Papers.Independent.Intakenext100.P38.correctionA

For natural numbers n,kn,kn,k, let Sn(x,y,z)S_n(x,y,z)Sn​(x,y,z) denote the sum of all tensor products of nnn identity or standard Pauli factors with exactly xxx factors XXX, yyy factors YYY, and zzz factors ZZZ. Writing r=max⁡{k−2,0}r=\max\{k-2,0\}r=max{k−2,0}, the definition is

i(−4Sn(r,2,0)+2kSn(k,0,0)).i\left(-4S_n(r,2,0)+2kS_n(k,0,0)\right).i(−4Sn​(r,2,0)+2kSn​(k,0,0)).

Each Sn(x,y,z)S_n(x,y,z)Sn​(x,y,z) is zero if x+y+z>nx+y+z>nx+y+z>n, and an empty tensor product is the identity. No assumption k≥2k\ge2k≥2 or k≤nk\le nk≤n is made: in particular, r=0r=0r=0 for k=0k=0k=0 or k=1k=1k=1, and the formula also applies when n=0n=0n=0.

QAlgorithms.Papers.Independent.Intakenext100.P38.correctionB

For natural numbers n,kn,kn,k, let Sn(x,y,z)S_n(x,y,z)Sn​(x,y,z) denote the sum of all tensor products of nnn identity or standard Pauli factors with exactly xxx factors XXX, yyy factors YYY, and zzz factors ZZZ. Writing r=max⁡{k−2,0}r=\max\{k-2,0\}r=max{k−2,0}, the definition is

i(4Sn(r,0,2)−2kSn(k,0,0)).i\left(4S_n(r,0,2)-2kS_n(k,0,0)\right).i(4Sn​(r,0,2)−2kSn​(k,0,0)).

Each Sn(x,y,z)S_n(x,y,z)Sn​(x,y,z) is zero if x+y+z>nx+y+z>nx+y+z>n, and an empty tensor product is the identity. There is no restriction k≥2k\ge2k≥2 or k≤nk\le nk≤n; for k=0k=0k=0 or k=1k=1k=1, the first argument rrr is zero, and n=0n=0n=0 is also included.

QAlgorithms.Papers.Independent.Intakenext100.P38.correctionC

For any natural numbers n,kn,kn,k, let Sn(x,y,z)S_n(x,y,z)Sn​(x,y,z) be the sum of all nnn-fold tensor products of the standard Pauli matrices and the identity having exactly xxx factors XXX, yyy factors YYY, and zzz factors ZZZ, with identity factors elsewhere. An empty sum is zero, so Sn(x,y,z)=0S_n(x,y,z)=0Sn​(x,y,z)=0 when x+y+z>nx+y+z>nx+y+z>n. The declaration defines the complex matrix on nnn-bit strings

correctionC⁡(n,k)=i[−4(k−2)Sn(k\dotminus2,2,0)−4Sn(k\dotminus2,0,2)+2k(k−1)Sn(k,0,0)],\operatorname{correctionC}(n,k) =i\Bigl[-4(k-2)S_n(k\mathbin{\dotminus}2,2,0) -4S_n(k\mathbin{\dotminus}2,0,2) +2k(k-1)S_n(k,0,0)\Bigr],correctionC(n,k)=i[−4(k−2)Sn​(k\dotminus2,2,0)−4Sn​(k\dotminus2,0,2)+2k(k−1)Sn​(k,0,0)],

where k\dotminus2=max⁡(k−2,0)k\mathbin{\dotminus}2=\max(k-2,0)k\dotminus2=max(k−2,0) is natural-number subtraction in the tensor-factor counts, while the occurrences of k−2k-2k−2 and k−1k-1k−1 in the scalar coefficients are subtraction in R\mathbb RR. There is no restriction on nnn or kkk; in particular, k=0,1k=0,1k=0,1 and n=0n=0n=0 are included.

QAlgorithms.Papers.Independent.Intakenext100.P38.g2

For every natural number nnn, including n=0n=0n=0, g2(n)g_2(n)g2​(n) is the smallest real Lie subalgebra of complex matrices indexed by nnn-bit strings containing iS1,0,0iS_{1,0,0}iS1,0,0​, iS0,1,0iS_{0,1,0}iS0,1,0​, and iS0,0,2iS_{0,0,2}iS0,0,2​, with Lie bracket [A,B]=AB−BA[A,B]=AB-BA[A,B]=AB−BA. Here Sx,y,zS_{x,y,z}Sx,y,z​ is the sum of all tensor products having XXX on exactly xxx sites, YYY on exactly yyy sites, ZZZ on exactly zzz sites, and the identity on every remaining site, each assignment occurring once, where

X=(0110),Y=(0−ii0),Z=(100−1).X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\qquad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.X=(01​10​),Y=(0i​−i0​),Z=(10​0−1​).

Thus “smallest” means closure under real linear combinations and commutators. A sum Sx,y,zS_{x,y,z}Sx,y,z​ is zero when x+y+z>nx+y+z>nx+y+z>n; in particular, the third generator is zero for n<2n<2n<2, and all three generators are zero for n=0n=0n=0.

QAlgorithms.Papers.Independent.Intakenext100.P38.gK

For all natural numbers n,kn,kn,k, gK(n,k)g_K(n,k)gK​(n,k) is the smallest real Lie subalgebra of complex matrices indexed by nnn-bit strings containing

iS1,0,0,iS0,1,0,iS0,0,jfor every natural number j with 2≤j≤k,iS_{1,0,0},\qquad iS_{0,1,0},\qquad iS_{0,0,j}\quad\text{for every natural number }j\text{ with }2\le j\le k,iS1,0,0​,iS0,1,0​,iS0,0,j​for every natural number j with 2≤j≤k,

where the Lie bracket is AB−BAAB-BAAB−BA. Here Sx,y,zS_{x,y,z}Sx,y,z​ sums, once each, all tensor products with exactly xxx factors X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), yyy factors Y=(0−ii0)Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix}Y=(0i​−i0​), zzz factors Z=diag⁡(1,−1)Z=\operatorname{diag}(1,-1)Z=diag(1,−1), and identity factors elsewhere. The generated algebra is closed under real linear combinations and commutators. When k=0k=0k=0 or k=1k=1k=1, there are no generators from the indexed family. Whenever x+y+z>nx+y+z>nx+y+z>n, the corresponding sum is zero, so the generators with j>nj>nj>n vanish; for n=0n=0n=0, the whole generated algebra is zero.

QAlgorithms.Papers.Independent.Intakenext100.P38.generatedSkewLie

For every natural number nnn and every set GGG of complex matrices indexed by nnn-bit strings, this defines the smallest real Lie subalgebra containing iHiHiH for every H∈GH\in GH∈G, with bracket [A,B]=AB−BA[A,B]=AB-BA[A,B]=AB−BA. Equivalently, it is the smallest real linear subspace containing these matrices and closed under commutators. The set GGG is arbitrary, with no Hermiticity hypothesis. An empty GGG generates the zero subalgebra, and n=0n=0n=0 is allowed.

QAlgorithms.Papers.Independent.Intakenext100.P38.generators1

For every natural number nnn, this defines the singleton set

{∑j=0n−1Xj},\left\{\sum_{j=0}^{n-1}X_j\right\},{j=0∑n−1​Xj​},

where XjX_jXj​ acts by X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​) on position jjj and by the identity on every other position, on the space indexed by nnn-bit strings. For n=0n=0n=0, the sum is zero, so the set is {0}\{0\}{0}.

QAlgorithms.Papers.Independent.Intakenext100.P38.generators1XY

For every natural number nnn, this defines the set

{∑j=0n−1Xj, ∑j=0n−1Yj},\left\{\sum_{j=0}^{n-1}X_j,\ \sum_{j=0}^{n-1}Y_j\right\},{j=0∑n−1​Xj​, j=0∑n−1​Yj​},

where XjX_jXj​ and YjY_jYj​ act respectively by X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​) and Y=(0−ii0)Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix}Y=(0i​−i0​) on position jjj, and by the identity elsewhere, on the space indexed by nnn-bit strings. These are set elements, so equal matrices are included only once. For n=0n=0n=0, both sums are zero and the set is {0}\{0\}{0}.

QAlgorithms.Papers.Independent.Intakenext100.P38.generators2

For every natural number nnn, this defines the set

{∑j=0n−1Xj,∑j=0n−1Yj,∑0≤j<ℓ<nZjZℓ},\left\{ \sum_{j=0}^{n-1}X_j,\quad \sum_{j=0}^{n-1}Y_j,\quad \sum_{0\le j<\ell<n}Z_jZ_\ell \right\},⎩⎨⎧​j=0∑n−1​Xj​,j=0∑n−1​Yj​,0≤j<ℓ<n∑​Zj​Zℓ​⎭⎬⎫​,

where a subscript indicates the position on which the corresponding single-qubit matrix acts, with identity on all other positions, and

X=(0110),Y=(0−ii0),Z=(100−1).X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\qquad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.X=(01​10​),Y=(0i​−i0​),Z=(10​0−1​).

The pair sum includes each two-element subset of positions once and is zero for n<2n<2n<2. Repeated matrices are identified because this is a set; in particular, for n=0n=0n=0 the set is {0}\{0\}{0}.

QAlgorithms.Papers.Independent.Intakenext100.P38.generatorsK

For arbitrary natural numbers nnn and kkk, this defines the set

{∑q=0n−1Xq, ∑q=0n−1Yq} ∪ {∑S⊆{0,…,n−1}∣S∣=j∏q∈SZq: j∈N, 2≤j≤k},\left\{\sum_{q=0}^{n-1}X_q,\ \sum_{q=0}^{n-1}Y_q\right\} \ \cup\ \left\{ \sum_{\substack{S\subseteq\{0,\ldots,n-1\}\\|S|=j}} \prod_{q\in S}Z_q :\ j\in\mathbb N,\ 2\le j\le k \right\},{q=0∑n−1​Xq​, q=0∑n−1​Yq​} ∪ ⎩⎨⎧​S⊆{0,…,n−1}∣S∣=j​∑​q∈S∏​Zq​: j∈N, 2≤j≤k⎭⎬⎫​,

where Xq,Yq,ZqX_q,Y_q,Z_qXq​,Yq​,Zq​ act on position qqq by X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), Y=(0−ii0)Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix}Y=(0i​−i0​), and Z=(100−1)Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}Z=(10​0−1​) respectively, and by identity elsewhere. For k<2k<2k<2, the second set is empty. A term indexed by j>nj>nj>n is the zero matrix because there are no jjj-element subsets. Repeated matrices are identified, and for n=0n=0n=0 the resulting set is {0}\{0\}{0}.

QAlgorithms.Papers.Independent.Intakenext100.P38.labelPauli

This defines a function from an optional index in {0,1,2}\{0,1,2\}{0,1,2} to a Pauli label: an absent index maps to III, while the indices 000, 111, and 222 map respectively to XXX, YYY, and ZZZ.

QAlgorithms.Papers.Independent.Intakenext100.P38.levelTriples

For every natural number mmm, levelTriples⁡(m)\operatorname{levelTriples}(m)levelTriples(m) is the finite set

{(a,b,c)∈N3:0≤a,b,c≤m, a+b+c=m}.\{(a,b,c)\in\mathbb N^3:0\le a,b,c\le m,\ a+b+c=m\}.{(a,b,c)∈N3:0≤a,b,c≤m, a+b+c=m}.

Each ordered triple appears once. In particular, zero coordinates are permitted, and levelTriples⁡(0)={(0,0,0)}\operatorname{levelTriples}(0)=\{(0,0,0)\}levelTriples(0)={(0,0,0)}.

QAlgorithms.Papers.Independent.Intakenext100.P38.pauliDegreeSpace

For any natural numbers n,kn,kn,k, this is the real linear span of the matrices

Pw=⨂j=0n−1L(wj),#{j:wj≠none}≤k,P_w=\bigotimes_{j=0}^{n-1}L(w_j), \qquad \#\{j:w_j\ne\mathrm{none}\}\le k,Pw​=j=0⨂n−1​L(wj​),#{j:wj​=none}≤k,

indexed by all assignments wj∈{none,0,1,2}w_j\in\{\mathrm{none},0,1,2\}wj​∈{none,0,1,2}, where L(none)=IL(\mathrm{none})=IL(none)=I, L(0)=XL(0)=XL(0)=X, L(1)=YL(1)=YL(1)=Y, and L(2)=ZL(2)=ZL(2)=Z, with X,Y,ZX,Y,ZX,Y,Z the standard Pauli matrices. Explicitly, (Pw)u,v=∏jL(wj)uj,vj(P_w)_{u,v}=\prod_j L(w_j)_{u_j,v_j}(Pw​)u,v​=∏j​L(wj​)uj​,vj​​ for bit strings u,v∈{0,1}nu,v\in\{0,1\}^nu,v∈{0,1}n. The spanning coefficients are real. For k=0k=0k=0 the space is the real span of the identity; for n=0n=0n=0 the empty tensor product is the 1×11\times11×1 identity. No restriction k≤nk\le nk≤n is imposed.

QAlgorithms.Papers.Independent.Intakenext100.P38.permutationImage

For every natural number nnn, define PpP_pPp​, for each permutation ppp of the nnn positions, by

(Pp)x,y={1,xj=yp−1(j) for every j,0,otherwise,x,y∈{0,1}n.(P_p)_{x,y}= \begin{cases} 1,&x_j=y_{p^{-1}(j)}\text{ for every }j,\\ 0,&\text{otherwise}, \end{cases} \qquad x,y\in\{0,1\}^n.(Pp​)x,y​={1,0,​xj​=yp−1(j)​ for every j,otherwise,​x,y∈{0,1}n.

The definition is the real linear span of all matrices AAA satisfying A†=−AA^\dagger=-AA†=−A that belong to the complex linear span of the matrices PpP_pPp​. Thus the inner span permits complex coefficients, while the outer span uses real coefficients. For n=0n=0n=0, the only permutation matrix is the 1×11\times11×1 identity, and the resulting space consists of purely imaginary scalars.

QAlgorithms.Papers.Independent.Intakenext100.P38.rotationCommutant

For every natural number nnn, this is the real linear span of all complex matrices AAA indexed by nnn-bit strings such that

A†=−AandA U⊗n=U⊗nAfor every complex unitary 2×2 matrix U.A^\dagger=-A \quad\text{and}\quad A\,U^{\otimes n}=U^{\otimes n}A \quad\text{for every complex unitary }2\times2\text{ matrix }U.A†=−AandAU⊗n=U⊗nAfor every complex unitary 2×2 matrix U.

Here (U⊗n)x,y=∏j=0n−1Uxj,yj(U^{\otimes n})_{x,y}=\prod_{j=0}^{n-1}U_{x_j,y_j}(U⊗n)x,y​=∏j=0n−1​Uxj​,yj​​, with bits ordered as 0,10,10,1. The quantifier ranges over all unitary UUU, with no determinant restriction. When n=0n=0n=0, the product is 111, so the commutation condition is automatic and the resulting space consists of the purely imaginary 1×11\times11×1 matrices.

QAlgorithms.Papers.Independent.Intakenext100.P38.specialSymmetricAlgebra

For every natural number nnn, let An\mathcal A_nAn​ be the real linear span of all complex matrices BBB indexed by nnn-bit strings satisfying B†=−BB^\dagger=-BB†=−B and commuting with every position-permutation matrix PpP_pPp​, where PpP_pPp​ sends the basis vector indexed by vvv to that indexed by v∘p−1v\circ p^{-1}v∘p−1. This defines

span⁡R{A∈An:tr⁡(A)=0}.\operatorname{span}_{\mathbb R}\{A\in\mathcal A_n:\operatorname{tr}(A)=0\}.spanR​{A∈An​:tr(A)=0}.

The trace equality is an equality in C\mathbb CC. The definition applies also to n=0n=0n=0.

QAlgorithms.Papers.Independent.Intakenext100.P38.symmetricPauli

For arbitrary natural numbers n,x,y,zn,x,y,zn,x,y,z, this defines a complex matrix indexed by nnn-bit strings as the sum of all tensor products of nnn single-qubit matrices having exactly xxx factors XXX, yyy factors YYY, zzz factors ZZZ, and identity factors at all remaining positions. In the basis ordered as false,true\mathrm{false},\mathrm{true}false,true, these matrices are

X=(0110),Y=(0−ii0),Z=(100−1).X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\qquad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.X=(01​10​),Y=(0i​−i0​),Z=(10​0−1​).

Each assignment of these factors to positions occurs once, with coefficient 111. If x+y+z>nx+y+z>nx+y+z>n, the sum is empty and gives the zero matrix. For n=0n=0n=0, it gives the 1×11\times11×1 identity when x=y=z=0x=y=z=0x=y=z=0, and zero otherwise.

QAlgorithms.Papers.Independent.Intakenext100.P38.symmetricUnitaryAlgebra

For every natural number nnn, this defines the real linear span of all complex matrices AAA indexed by nnn-bit strings such that A†=−AA^\dagger=-AA†=−A and APp=PpAAP_p=P_pAAPp​=Pp​A for every permutation ppp of the nnn positions. Here PpP_pPp​ is the permutation matrix sending the basis vector indexed by a bit string vvv to the basis vector indexed by v∘p−1v\circ p^{-1}v∘p−1. The definition includes n=0n=0n=0, when the matrices are 1×11\times11×1.

QAlgorithms.Papers.Independent.Intakenext100.P38.transpositionCentralExpansion

For natural numbers n,μn,\mun,μ, let Sn(x,y,z)S_n(x,y,z)Sn​(x,y,z) be the sum of all tensor products on nnn positions containing exactly xxx standard Pauli XXX factors, yyy Pauli YYY factors, and zzz Pauli ZZZ factors, with identity factors on the other positions, and with an empty sum interpreted as zero. With r+=max⁡{r,0}r_+=\max\{r,0\}r+​=max{r,0}, the definition is the matrix

4−μ(n−2μ)+!∑j=0μ(n−2j)+!(μ−j)!(∑a,b,c≥0a+b+c=j(2a)!(2b)!(2c)!a! b! c! Sn(2a,2b,2c)).\frac{4^{-\mu}}{(n-2\mu)_+!} \sum_{j=0}^{\mu} \frac{(n-2j)_+!}{(\mu-j)!} \left( \sum_{\substack{a,b,c\ge0\\a+b+c=j}} \frac{(2a)!(2b)!(2c)!}{a!\,b!\,c!}\, S_n(2a,2b,2c) \right).(n−2μ)+​!4−μ​j=0∑μ​(μ−j)!(n−2j)+​!​​a,b,c≥0a+b+c=j​∑​a!b!c!(2a)!(2b)!(2c)!​Sn​(2a,2b,2c)​.

The coefficients are real, and the matrices are indexed by nnn-bit strings. No inequality between nnn and 2μ2\mu2μ is required; subtraction in the factorial arguments is truncated at zero. The formula includes n=0n=0n=0 and μ=0\mu=0μ=0, using 0!=10!=10!=1 and the identity for an empty tensor product; when μ=0\mu=0μ=0 the result is the identity.

QAlgorithms.Papers.Independent.Intakenext100.P38.transpositionClass

For natural numbers n,μn,\mun,μ, this is the finite set of all permutations π\piπ of {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1} such that

π2=idand#{j:π(j)≠j}=2μ.\pi^2=\mathrm{id} \quad\text{and}\quad \#\{j:\pi(j)\ne j\}=2\mu.π2=idand#{j:π(j)=j}=2μ.

Equivalently, these permutations consist of exactly μ\muμ disjoint transpositions together with fixed points. The set is empty when 2μ>n2\mu>n2μ>n; when μ=0\mu=0μ=0, it contains exactly the identity, including when n=0n=0n=0.

QAlgorithms.Papers.Independent.Intakenext100.P38.transpositionPauliExpansion

For natural numbers n,μn,\mun,μ, let Sn(x,y,z)S_n(x,y,z)Sn​(x,y,z) denote the sum of all tensor products of nnn factors from the identity and the standard Pauli matrices X,Y,ZX,Y,ZX,Y,Z having exactly xxx factors XXX, yyy factors YYY, and zzz factors ZZZ, with identity factors elsewhere; this sum is zero if x+y+z>nx+y+z>nx+y+z>n. Writing r+=max⁡{r,0}r_+=\max\{r,0\}r+​=max{r,0} for integer expressions rrr, the definition is

4−μ(n−2μ)+!∑0≤a,b,c,f≤μa+b+c+f=μ(2a)!(2b)!(2c)!a! b! c! (n−2(μ−f))+!f! Sn(2a,2b,2c).\frac{4^{-\mu}}{(n-2\mu)_+!} \sum_{\substack{0\le a,b,c,f\le\mu\\a+b+c+f=\mu}} \frac{(2a)!(2b)!(2c)!}{a!\,b!\,c!}\, \frac{\bigl(n-2(\mu-f)\bigr)_+!}{f!}\, S_n(2a,2b,2c).(n−2μ)+​!4−μ​0≤a,b,c,f≤μa+b+c+f=μ​∑​a!b!c!(2a)!(2b)!(2c)!​f!(n−2(μ−f))+​!​Sn​(2a,2b,2c).

All coefficients are real scalars acting on complex matrices indexed by nnn-bit strings. There is no assumption 2μ≤n2\mu\le n2μ≤n: every natural-number subtraction is truncated at zero before taking the factorial, and 0!=10!=10!=1. Empty tensor products are 111, so the definition also applies to n=0n=0n=0; for μ=0\mu=0μ=0 it gives the identity.

QAlgorithms.Papers.Independent.Intakenext100.P38.transpositionSum

For natural numbers n,μn,\mun,μ, this is the complex matrix indexed by nnn-bit strings given by

Tn,μ=∑π2=id#{j:π(j)≠j}=2μPπ,(Pπ)x,y={1,xj=yπ−1(j) for every j,0,otherwise.T_{n,\mu}=\sum_{\substack{\pi^2=\mathrm{id}\\ \#\{j:\pi(j)\ne j\}=2\mu}}P_\pi, \qquad (P_\pi)_{x,y}= \begin{cases} 1,&x_j=y_{\pi^{-1}(j)}\text{ for every }j,\\ 0,&\text{otherwise}. \end{cases}Tn,μ​=π2=id#{j:π(j)=j}=2μ​∑​Pπ​,(Pπ​)x,y​={1,0,​xj​=yπ−1(j)​ for every j,otherwise.​

The sum ranges over permutations of the nnn positions. It is the zero matrix when 2μ>n2\mu>n2μ>n, and is the identity matrix when μ=0\mu=0μ=0, including the 1×11\times11×1 identity when n=0n=0n=0.

Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me