Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.7 — ai↦bia_i\mapsto b_iai​↦bi​ extends to a ∗*∗-homomorphism iff ATJnAA=BTJnBBA^{\mathsf T}J_{n_A}A=B^{\mathsf T}J_{n_B}BATJnA​​A=BTJnB​​B, KA⊆KBK_A\subseteq K_BKA​⊆KB​, ζA=ζB\zeta_A=\zeta_BζA​=ζB​ on KAK_AKA​

Open
RelDecoding.Supplement.theorem_4_7

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

operator-algebrasp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationrelative-decoding

Let ai=ηiAPnA(wi)a_i=\eta_i^AP_{n_A}(w_i)ai​=ηiA​PnA​​(wi​) and bi=ηiBPnB(vi)b_i=\eta_i^BP_{n_B}(v_i)bi​=ηiB​PnB​​(vi​), i=1,…,si=1,\dots,si=1,…,s, be signed Pauli generators (ηiL∈{±1}\eta_i^L\in\{\pm1\}ηiL​∈{±1}, wi∈F22nAw_i\in\mathbb F_2^{2n_A}wi​∈F22nA​​, vi∈F22nBv_i\in\mathbb F_2^{2n_B}vi​∈F22nB​​, Pn(x,z)=ix⋅zXxZzP_n(x,z)=i^{x\cdot z}X^xZ^zPn​(x,z)=ix⋅zXxZz), with algebras A=C∗(I,a1,…,as)\mathcal A=C^*(I,a_1,\dots,a_s)A=C∗(I,a1​,…,as​), B=C∗(I,b1,…,bs)\mathcal B=C^*(I,b_1,\dots,b_s)B=C∗(I,b1​,…,bs​), label matrices A=[w1⋯ws]A=[w_1\cdots w_s]A=[w1​⋯ws​], B=[v1⋯vs]B=[v_1\cdots v_s]B=[v1​⋯vs​], relation codes KA=ker⁡AK_A=\ker AKA​=kerA, KB=ker⁡BK_B=\ker BKB​=kerB over F2\mathbb F_2F2​, and ordered products WL(c)=a1c1⋯ascsW_L(c)=a_1^{c_1}\cdots a_s^{c_s}WL​(c)=a1c1​​⋯ascs​​ (resp. bbb), so that WL(c)=ζL(c)IW_L(c)=\zeta_L(c)IWL​(c)=ζL​(c)I for c∈KLc\in K_Lc∈KL​. Then the termwise assignment ai↦bia_i\mapsto b_iai​↦bi​ extends to a unital ∗*∗-homomorphism π:A→B\pi:\mathcal A\to\mathcal Bπ:A→B if and only if

ATJnAA=BTJnBB,KA⊆KB,ζA(c)=ζB(c)  (c∈KA),A^{\mathsf T}J_{n_A}A=B^{\mathsf T}J_{n_B}B,\qquad K_A\subseteq K_B,\qquad\zeta_A(c)=\zeta_B(c)\ \ (c\in K_A),ATJnA​​A=BTJnB​​B,KA​⊆KB​,ζA​(c)=ζB​(c)  (c∈KA​),

where Jn=(0InIn0)J_n=\begin{pmatrix}0&I_n\\I_n&0\end{pmatrix}Jn​=(0In​​In​0​).

The three conditions are: matching pairwise commutation and anticommutation, every scalar relation of the source terms is a relation of the target terms, and these relations carry the same phase. The homomorphism then transports every Hamiltonian polynomial, π(p(HA))=p(HB)\pi(p(H_A))=p(H_B)π(p(HA​))=p(HB​).

Differences from the source:

  • encoding: aᵢ = ηᵢᴬ P_{n_A}(wᵢ), P_n(x, z) = i^{x·z}X^xZ^z with integer exponent x·z, ηᵢᴸ ∈ {±1}, wᵢ ∈ F₂^{2n_A} → pauliGen ηA wA i = ((ηA i : ℤ) : ℂ) • StabTestMem.weyl (wA i) on Qubits n = Fin n → Bool, ηA i ∈ ℤˣ, labels CutRankSched.Pauli n = (Fin n → ZMod 2) × (Fin n → ZMod 2); the label matrix has rows x then z (Fin n ⊕ Fin n); reason: the published StabTestMem.weyl is the Hermitian Pauli i^{x·z}X^xZ^z with the integer exponent; ℤˣ = {±1}; same operators and labels
  • encoding: unital ∗-homomorphism π : 𝒜 → ℬ between A = C∗(I_A, a) and B = C∗(I_B, b) → π : genAlg a →⋆ₐ[ℂ] genAlg b (generated ∗-subalgebras of the matrix algebras) with π (gen a i) = gen b i; reason: in finite dimension the generated ∗-subalgebra is the generated C∗-algebra (App. E, p.85)
  • encoding: ζ_A(c) = ζ_B(c) for c ∈ K_A, where W_L(c) = ζ_L(c) I for c ∈ K_L → ∀ c ∈ K_A, ∀ ζ : ℂ, W_A(c) = ζ • 1 → W_B(c) = ζ • 1; reason: for c ∈ K_A the word W_A(c) is scalar, so ζ_A(c) is the unique ζ with W_A(c) = ζI (the matrix algebras are nonzero); the implication then says W_B(c) = ζ_A(c)I, i.e. ζ_B(c) = ζ_A(c)
Preamble
import Mathlib
import Definitions.Def_RelDecoding_markedSpace
import Definitions.Def_CutRankSched_Pauli
import Definitions.Def_StabTestMem_weyl
import Definitions.Def_RelDecoding_Supplement_labelKer
import Definitions.Def_RelDecoding_Supplement_pauliGen

set_option autoImplicit false
open scoped Matrix
Formal statement
namespace RelDecoding.Supplement

open QAlgorithms RelDecoding

/-- **Theorem 4.7 (Pauli homomorphism criterion).** For signed Pauli generators
`aᵢ = ηᵢᴬ P_{n_A}(wᵢ)`, `bᵢ = ηᵢᴮ P_{n_B}(vᵢ)` with label matrices `A = [w₁ ⋯ w_s]`,
`B = [v₁ ⋯ v_s]`, kernels `K_A`, `K_B` over `F₂` and ordered products `W_L(c) = a₁^{c₁}⋯a_s^{c_s}`
(`= ζ_L(c) I` for `c ∈ K_L`), the termwise assignment `aᵢ ↦ bᵢ` extends to a unital
∗-homomorphism `π : A → B` exactly when
`AᵀJ_{n_A}A = BᵀJ_{n_B}B`, `K_A ⊆ K_B`, `ζ_A(c) = ζ_B(c)` (`c ∈ K_A`) (85), with
`J_n = [[0, I_n], [I_n, 0]]` (86).

Shang, Stilck França, *From Simple Sources to Quantum Advantage: Homomorphic Polynomial
Transduction via Relative Decoding*, arXiv:2609.35101 (held version, sha256 d2be7859…),
Theorem 4.7, pp.23–24 (= Theorem 1.4, p.9; proof Proposition E.2, pp.86–87).

**Formalization Note.** `P_n` is the published `StabTestMem.weyl`; `A = genAlg a`, `B = genAlg b`
(generated ∗-subalgebras, equal to the generated C∗-algebras in finite dimension). The phase
condition is encoded as: for `c ∈ K_A`, `W_A(c) = ζI_A` implies `W_B(c) = ζI_B`; since every
`W_A(c)`, `c ∈ K_A`, is scalar and the matrices are nonzero (dimension `2^n ≥ 1`), this is
`ζ_A(c) = ζ_B(c)`. The ordered product uses the representatives `cᵢ ∈ {0, 1}`. -/
theorem theorem_4_7 {nA nB s : ℕ} (wA : Fin s → CutRankSched.Pauli nA) (ηA : Fin s → ℤˣ)
    (wB : Fin s → CutRankSched.Pauli nB) (ηB : Fin s → ℤˣ) :
    (∃ π : genAlg (pauliGen ηA wA) →⋆ₐ[ℂ] genAlg (pauliGen ηB wB),
        ∀ i, π (gen (pauliGen ηA wA) i) = gen (pauliGen ηB wB) i) ↔
      ((pauliLabelMatrix wA)ᵀ * symplecticJ nA * pauliLabelMatrix wA =
          (pauliLabelMatrix wB)ᵀ * symplecticJ nB * pauliLabelMatrix wB ∧
        pauliKer wA ≤ pauliKer wB ∧
        ∀ c ∈ pauliKer wA, ∀ ζ : ℂ, orderedProd (pauliGen ηA wA) c = ζ • 1 →
          orderedProd (pauliGen ηB wB) c = ζ • 1) := by sorry

end RelDecoding.Supplement
Source
Shang, Stilck França, From Simple Sources to Quantum Advantage: Homomorphic Polynomial Transduction via Relative Decoding, arXiv:2609.35101 (held version, sha256 d2be7859…), Theorem 4.7, pp.23–24 (pdf_pages 23–24); = Theorem 1.4, p.9; proof Proposition E.2, pp.86–87

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