Theorem 1.5 — Pauli relative distance , strictness criterion and monotonicity
OpenRelDecoding.Supplement.theorem_1_5operator-algebrasp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-informationrelative-decoding
Let and , , be signed Pauli generators (, ), let , and let be a unital -homomorphism on with . Let and over , the Hamming weight, , (empty minima ), and the intrinsic relative distance of (Definition 4.1). Then
- ;
- ;
- ;
- if , then
- for every subspace with (in particular the kernel of any compatible source ), .
The theorem says that relative decoding absorbs the relations already present in the source: its distance is at least the ordinary distance of the target relation code, and strictly larger exactly when every shortest target relation is inherited. This is what can enlarge the transduction window beyond the ordinary-decoding window .
Differences from the source:
- generalization: (21) for compatible source choices A′ with kernels K_A ⊆ K_{A′} ⊆ K_B → clause 5 for every subspace K′ with K_A ≤ K′ ≤ K_B; reason: the kernel of every compatible source is such a subspace, so the Lean clause specializes to (21); App. B.1 shows every such K′ is realized
- 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: 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
- encoding: distances in ℕ₀ ∪ {+∞}, empty minimum +∞ → values in ℕ∞ defined by sInf, sInf ∅ = ⊤; reason: Lean convention; same 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_CutRankSched_Pauli import Definitions.Def_StabTestMem_weyl import Definitions.Def_RelDecoding_Supplement_labelKer import Definitions.Def_RelDecoding_Supplement_coordDist import Definitions.Def_RelDecoding_Supplement_pauliGen set_option autoImplicit false
Formal statement
namespace RelDecoding.Supplement
open QAlgorithms RelDecoding
/-- **Theorem 1.5 (Relative decoding has higher distance).** For signed Pauli generators
`aᵢ = ηᵢᴬ P_{n_A}(wᵢ)`, `bᵢ = ηᵢᴮ P_{n_B}(vᵢ)` and a unital ∗-homomorphism `π : A → B` with
`π(aᵢ) = bᵢ`, write `K_A = ker A`, `K_B = ker B` over `F₂`, `d_{A→B} = min{|c| : c ∈ K_B \ K_A}` and
`d_B = min{|c| : 0 ≠ c ∈ K_B}`. Then
1. `d_rel = d_{A→B}` (19);
2. `d_{A→B} ≥ d_B` (19);
3. `K_A = {0} ⟹ d_{A→B} = d_B` (19);
4. if `d_B < ∞`, then `d_{A→B} > d_B ⟺ {c ∈ K_B : |c| = d_B} ⊆ K_A` (20);
5. for kernels `K_A ⊆ K_{A′} ⊆ K_B`, `d_{A→B} ≤ d_{A′→B}` (21).
Shang, Stilck França, *From Simple Sources to Quantum Advantage: Homomorphic Polynomial
Transduction via Relative Decoding*, arXiv:2609.35101 (held version, sha256 d2be7859…),
Theorem 1.5, p.9 (body version Proposition 4.8, p.25; setting §4.4.1, pp.23–24).
**Formalization Note.** `P_n` is the published `StabTestMem.weyl` (Hermitian convention
`i^{x·z}X^xZ^z`, integer exponent) on `Qubits n = Fin n → Bool`; `A = genAlg a`; `π` maps into
`Matrix (Qubits n_B) (Qubits n_B) ℂ` with `π (gen a i) = b i` (its range is `B`), the setting of the
published `relDist`. All distances lie in `ℕ∞` with empty minimum `⊤`. Clause 5 is stated for every
subspace `K′` with `K_A ⊆ K′ ⊆ K_B` (App. B.1 realizes each as the kernel of a compatible source). -/
theorem theorem_1_5 {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) →⋆ₐ[ℂ] Matrix (Qubits nB) (Qubits nB) ℂ)
(hπ : ∀ i, π (gen (pauliGen ηA wA) i) = pauliGen ηB wB i) :
relDist (pauliGen ηA wA) π = coordDist (pauliKer wA) (pauliKer wB) ∧
ordDist (pauliKer wB) ≤ coordDist (pauliKer wA) (pauliKer wB) ∧
(pauliKer wA = ⊥ → coordDist (pauliKer wA) (pauliKer wB) = ordDist (pauliKer wB)) ∧
(ordDist (pauliKer wB) < ⊤ →
(ordDist (pauliKer wB) < coordDist (pauliKer wA) (pauliKer wB) ↔
{c | c ∈ pauliKer wB ∧ (hammingNorm c : ℕ∞) = ordDist (pauliKer wB)} ⊆
(pauliKer wA : Set (Fin s → ZMod 2)))) ∧
(∀ K' : Submodule (ZMod 2) (Fin s → ZMod 2), pauliKer wA ≤ K' → K' ≤ pauliKer wB →
coordDist (pauliKer wA) (pauliKer wB) ≤ coordDist K' (pauliKer wB)) := 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 1.5, p.9 (pdf_page 9); body version Proposition 4.8, p.25; setting §4.4.1, eqs. (75)–(88), (93), pp.23–24