Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.2 — expected-value transfer: 2D+r<drel⇒EB(π(OA);XA)=τA(XA∗OAXA)/τA(XA∗XA)2D+r<d_{\mathrm{rel}}\Rightarrow\mathcal E_B(\pi(O_A);X_A)=\tau_A(X_A^*O_AX_A)/\tau_A(X_A^*X_A)2D+r<drel​⇒EB​(π(OA​);XA​)=τA​(XA∗​OA​XA​)/τA​(XA∗​XA​)

Open
RelDecoding.Supplement.theorem_5_2

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

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

Let A=C∗(IA,a1,…,as)⊆B(HA)\mathcal A=C^*(I_A,a_1,\dots,a_s)\subseteq B(H_A)A=C∗(IA​,a1​,…,as​)⊆B(HA​), let π:A→B(HB)\pi:\mathcal A\to B(H_B)π:A→B(HB​) be a unital ∗*∗-homomorphism with π(ai)=bi\pi(a_i)=b_iπ(ai​)=bi​, let τL=Tr⁡/NL\tau_L=\operatorname{Tr}/N_LτL​=Tr/NL​, let FtA\mathcal F^A_tFtA​ be the span of marked words of length at most ttt, and let dreld_{\mathrm{rel}}drel​ be the relative distance (Definition 4.1). Let D,r≥0D,r\ge0D,r≥0 be integers, 0≠XA∈FDA0\ne X_A\in\mathcal F^A_D0=XA​∈FDA​ and OA=OA∗∈FrAO_A=O_A^*\in\mathcal F^A_rOA​=OA∗​∈FrA​. If

2D+r<drel,2D+r<d_{\mathrm{rel}},2D+r<drel​,

then

  1. π(XA)≠0\pi(X_A)\ne0π(XA​)=0;
  2. the target expectation EB(OB;XA)=τB(XB∗OBXB)/τB(XB∗XB)\mathcal E_B(O_B;X_A)=\tau_B(X_B^*O_BX_B)/\tau_B(X_B^*X_B)EB​(OB​;XA​)=τB​(XB∗​OB​XB​)/τB​(XB∗​XB​), XB=π(XA)X_B=\pi(X_A)XB​=π(XA​), satisfies
EB(π(OA);XA)=τA(XA∗OAXA)τA(XA∗XA);\mathcal E_B(\pi(O_A);X_A)=\frac{\tau_A(X_A^*O_AX_A)}{\tau_A(X_A^*X_A)};EB​(π(OA​);XA​)=τA​(XA∗​XA​)τA​(XA∗​OA​XA​)​;
  1. for every guide family F0,…,FR−1∈FDAF_0,\dots,F_{R-1}\in\mathcal F^A_DF0​,…,FR−1​∈FDA​, with Yj=π(Fj)Y_j=\pi(F_j)Yj​=π(Fj​), the target Gram and objective matrices (Gπ)ij=τB(Yi∗Yj)(G_\pi)_{ij}=\tau_B(Y_i^*Y_j)(Gπ​)ij​=τB​(Yi∗​Yj​), (Kπ)ij=τB(Yi∗π(OA)Yj)(K_\pi)_{ij}=\tau_B(Y_i^*\pi(O_A)Y_j)(Kπ​)ij​=τB​(Yi∗​π(OA​)Yj​) equal the source matrices (GA)ij=τA(Fi∗Fj)(G_A)_{ij}=\tau_A(F_i^*F_j)(GA​)ij​=τA​(Fi∗​Fj​), (KA)ij=τA(Fi∗OAFj)(K_A)_{ij}=\tau_A(F_i^*O_AF_j)(KA​)ij​=τA​(Fi∗​OA​Fj​).

So in the window 2D+r<drel2D+r<d_{\mathrm{rel}}2D+r<drel​ the target variational problem over any guide space WD⊆FDA\mathcal W_D\subseteq\mathcal F^A_DWD​⊆FDA​ is computable from source data alone; with OA=HA∈F1AO_A=H_A\in\mathcal F^A_1OA​=HA​∈F1A​ this gives the energy window 2D+1<drel2D+1<d_{\mathrm{rel}}2D+1<drel​.

Differences from the source:

  • generalization: Hilbert spaces H_A, H_B with N_L = dim H_L ≥ 1 (τ_L divides by N_L) → index types nA, nB may be empty, where Lean's x/0 = 0 gives τ_L ≡ 0; reason: covers only extra degenerate instances where the source's τ_L is undefined; on nonempty index types it is the source's statement verbatim
  • encoding: A = C∗(I_A, a₁,…,a_s) ⊆ B(H_A), π : A ↠ B unital ∗-homomorphism with π(aᵢ) = bᵢ → A = genAlg a = StarAlgebra.adjoin ℂ (Set.range a) in Matrix nA nA ℂ; π : genAlg a →⋆ₐ[ℂ] Matrix nB nB ℂ with π (gen a i) = b i; reason: in finite dimension the generated ∗-subalgebra is norm closed (App. E, p.85); the range of π is the ∗-subalgebra generated by the bᵢ, i.e. B; this is the setting of the published relDist
  • reading: 'Thus the source Gram and objective matrices determine the target variational problem on every W_D ⊆ 𝓕ᴬ_D' → for every finite family F : Fin R → A with F j ∈ 𝓕ᴬ_D, targetGram π F = sourceGram F and targetObjective π (π O_A) F = sourceObjective O_A F; reason: the proof of Theorem C.2 (p.73) makes the clause precise as these matrix identities, which determine the variational problem of Proposition 5.1
  • encoding: 𝓕ᴬ_t, d_rel ∈ ℕ₀ ∪ {+∞}, integers D, r ≥ 0 → markedSpace a t; relDist a π : ℕ∞; D r : ℕ with ((2 * D + r : ℕ) : ℕ∞) < relDist a π; reason: Lean convention; same spaces and values
Preamble
import Mathlib
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_NormalizedTrace
import Definitions.Def_RelDecoding_markedSpace
import Definitions.Def_RelDecoding_relDist
import Definitions.Def_RelDecoding_Supplement_targetExpectation

set_option autoImplicit false
Formal statement
namespace RelDecoding.Supplement

open LIDT.MIPStarRE.Quantum RelDecoding

/-- **Theorem 5.2 (Expected-value transfer under relative decoding).** Let `0 ≠ X_A ∈ 𝓕ᴬ_D` and
`O_A = O_A∗ ∈ 𝓕ᴬ_r`. If `2D + r < d_rel` (118), then `π(X_A) ≠ 0` and
`E_B(π(O_A); X_A) = τ_A(X_A∗O_AX_A) / τ_A(X_A∗X_A)` (119). Moreover (the "Thus" clause, made
precise in the proof of Theorem C.2): for every guide family `F₀, …, F_{R−1}` in `𝓕ᴬ_D`, the target
Gram and objective matrices `(G_π)_{ij} = τ_B(Y_i∗Y_j)`, `(K_π)_{ij} = τ_B(Y_i∗π(O_A)Y_j)`,
`Y_j = π(F_j)`, equal the source ones `(G_A)_{ij} = τ_A(F_i∗F_j)`, `(K_A)_{ij} = τ_A(F_i∗O_AF_j)`.

Shang, Stilck França, *From Simple Sources to Quantum Advantage: Homomorphic Polynomial
Transduction via Relative Decoding*, arXiv:2609.35101 (held version, sha256 d2be7859…),
Theorem 5.2, p.28 (= Theorem C.2, p.73, with proof; definitions eqs. (114)–(115), p.28).

**Formalization Note.** Setting of the published `relDist`: `A = genAlg a`, `π` a unital
∗-homomorphism into `Matrix nB nB ℂ` with `π (gen a i) = b i`, `τ_L = normalizedTrace`,
`𝓕ᴬ_t = markedSpace a t`, `d_rel ∈ ℕ∞`; `D, r : ℕ`. The index types may be empty (then `τ ≡ 0` by
Lean's `x / 0 = 0`; with `nB` empty `d_rel = 0` and the hypothesis fails, with `nA` empty no
`X_A ≠ 0` exists). -/
theorem theorem_5_2 {nA nB : Type*} [Fintype nA] [DecidableEq nA] [Fintype nB] [DecidableEq nB]
    {s : ℕ} (a : Fin s → Matrix nA nA ℂ) (b : Fin s → Matrix nB nB ℂ)
    (π : genAlg a →⋆ₐ[ℂ] Matrix nB nB ℂ) (hπ : ∀ i, π (gen a i) = b i) (D r : ℕ)
    (XA OA : genAlg a) (hX0 : XA ≠ 0) (hX : XA ∈ markedSpace a D) (hOsa : IsSelfAdjoint OA)
    (hO : OA ∈ markedSpace a r) (hd : ((2 * D + r : ℕ) : ℕ∞) < relDist a π) :
    π XA ≠ 0 ∧
      targetExpectation π (π OA) XA =
        normalizedTrace (star (XA : Matrix nA nA ℂ) * (OA : Matrix nA nA ℂ) * (XA : Matrix nA nA ℂ)) /
          normalizedTrace (star (XA : Matrix nA nA ℂ) * (XA : Matrix nA nA ℂ)) ∧
      ∀ (R : ℕ) (F : Fin R → genAlg a), (∀ j, F j ∈ markedSpace a D) →
        targetGram π F = sourceGram F ∧ targetObjective π (π OA) F = sourceObjective OA F := 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 5.2, p.28 (pdf_page 28); = Theorem C.2 with proof, p.73; definitions eqs. (114)–(115), p.28

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