Theorem 5.2 — expected-value transfer:
OpenRelDecoding.Supplement.theorem_5_2operator-algebrasp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-informationrelative-decoding
Let , let be a unital -homomorphism with , let , let be the span of marked words of length at most , and let be the relative distance (Definition 4.1). Let be integers, and . If
then
- ;
- the target expectation , , satisfies
- for every guide family , with , the target Gram and objective matrices , equal the source matrices , .
So in the window the target variational problem over any guide space is computable from source data alone; with this gives the energy window .
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