Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

An affine channel code from linear reconciliation of uniform inputs

Open
QAlgorithms.Papers.Independent.Intakenext100.P30.uniform_reconciliation_code

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

prove2quantum

Let UUU and CCC be finite vector spaces over the same field, let f:U→Cf:U\to Cf:U→C be a surjective linear compressor, and let DcD_cDc​ be a normalized POVM on the receiver output with outcomes in UUU for each c∈Cc\in Cc∈C. For a cq channel u↦ρYuu\mapsto\rho_Y^uu↦ρYu​, suppose the reconciliation error under the uniform input law is at most ε\varepsilonε, where ε≥0\varepsilon\ge0ε≥0. There exist a∈Ua\in Ua∈U and a normalized decoder with message alphabet M=ker⁡fM=\ker fM=kerf and encoder m↦a+mm\mapsto a+mm↦a+m such that

∣M∣=∣U∣∣C∣,1∣M∣∑m∈MPr⁡[m^≠m∣ρYa+m]≤ε.|M|=\frac{|U|}{|C|},\qquad \frac1{|M|}\sum_{m\in M}\Pr[\widehat m\ne m\mid\rho_Y^{a+m}]\le\varepsilon.∣M∣=∣C∣∣U∣​,∣M∣1​m∈M∑​Pr[m=m∣ρYa+m​]≤ε.

Thus a single affine fiber of the compressor supports a channel code of the indicated size. The source's construction, rather than an assumed good fiber, supplies this code.

All alphabets are finite and nonempty, and output Hilbert spaces are finite dimensional and nonzero. A classical–quantum channel assigns a positive semidefinite, trace-one matrix to each input. Encoders may use private randomness; decoders are normalized POVMs. Codes are fixed independently of the message, with no supplied shared key or entanglement. Logarithms and entropies are in bits.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P30
Formal statement
noncomputable section

open scoped BigOperators ComplexConjugate Matrix ComplexOrder

open Filter

namespace QAlgorithms.Papers.Independent.Intakenext100.P30

variable {X Y Z M U V A B C : Type*}

variable [Fintype X] [DecidableEq X] [Fintype Y] [DecidableEq Y]

variable [Fintype Z] [DecidableEq Z] [Fintype M] [DecidableEq M]

variable [Fintype U] [DecidableEq U] [Fintype V] [DecidableEq V]

variable [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]

variable [Fintype C] [DecidableEq C]

attribute [local instance] Classical.propDecidable

/-- Lemma 2, PDF pp.3–4, with three source corrections: the compression map is
onto its actual range; the encoder is the affine inclusion m ↦ a+m into a fiber;
the error conclusion is <= epsilon, matching the definition of epsilon-good.
No good fiber or resulting error bound is a hypothesis. -/
theorem uniform_reconciliation_code {K : Type*} [Field K]
    [AddCommGroup U] [Module K U] [AddCommGroup C] [Module K C] [Nonempty Y]
    (theta : U → Matrix Y Y ℂ) (hTheta : RRIsCq theta)
    (compress : U →ₗ[K] C) (honto : Function.Surjective compress)
    (decompress : C → U → Matrix Y Y ℂ) (hDec : ∀ c, IsPOVM (decompress c))
    (epsilon : ℝ) (he : 0 ≤ epsilon)
    (herror : rrReconciliationError theta compress decompress (rrUniform U) ≤ epsilon) :
    ∃ a : U, ∃ decoder : {u : U // compress u = 0} → Matrix Y Y ℂ,
      IsPOVM decoder ∧
      (Fintype.card {u : U // compress u = 0} : ℝ) =
        (Fintype.card U : ℝ) / (Fintype.card C : ℝ) ∧
      rrAffineCodeError theta compress a decoder ≤ epsilon := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P30

end
Source
Noisy channel coding via privacy amplification and information reconciliation, arXiv:1012.4814v2, PDF p. 3, Lemma 2: Channel Coding from Information Reconciliation of Uniform Inputs
Read-back

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

Let KKK be any field, let U,CU,CU,C be finite additive commutative groups equipped with KKK-module structures, and let YYY be a finite nonempty index type, with decidable equality where required. Suppose θ(u)∈CY×Y\theta(u)\in\mathbb C^{Y\times Y}θ(u)∈CY×Y is positive semidefinite with trace one for every u∈Uu\in Uu∈U, f:U→Cf:U\to Cf:U→C is a surjective KKK-linear map, and matrices Dc,uD_{c,u}Dc,u​ satisfy Dc,u⪰0D_{c,u}\succeq0Dc,u​⪰0 and ∑u∈UDc,u=IY\sum_{u\in U}D_{c,u}=I_Y∑u∈U​Dc,u​=IY​ for every c∈Cc\in Cc∈C. For every real ϵ≥0\epsilon\ge0ϵ≥0, if

1∣U∣∑u∈U[1−Re⁡tr⁡(Df(u),uθ(u))]≤ϵ,\frac1{|U|}\sum_{u\in U} \left[1-\operatorname{Re}\operatorname{tr}\bigl(D_{f(u),u}\theta(u)\bigr)\right]\le\epsilon,∣U∣1​u∈U∑​[1−Retr(Df(u),u​θ(u))]≤ϵ,

then there exist a∈Ua\in Ua∈U and matrices MvM_vMv​, indexed by v∈ker⁡fv\in\ker fv∈kerf, such that Mv⪰0M_v\succeq0Mv​⪰0, ∑v∈ker⁡fMv=IY\sum_{v\in\ker f}M_v=I_Y∑v∈kerf​Mv​=IY​,

∣ker⁡f∣=∣U∣∣C∣as an equality of real numbers,1∣ker⁡f∣∑v∈ker⁡f[1−Re⁡tr⁡(Mvθ(a+v))]≤ϵ.|\ker f|=\frac{|U|}{|C|} \quad\text{as an equality of real numbers}, \qquad \frac1{|\ker f|}\sum_{v\in\ker f} \left[1-\operatorname{Re}\operatorname{tr}\bigl(M_v\theta(a+v)\bigr)\right]\le\epsilon.∣kerf∣=∣C∣∣U∣​as an equality of real numbers,∣kerf∣1​v∈kerf∑​[1−Retr(Mv​θ(a+v))]≤ϵ.

The zero-dimensional or singleton module cases and ϵ=0\epsilon=0ϵ=0 are included.

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