Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for A New Proof of the Channel Coding Theorem via Hypothesis Testing in Quantum Information Theory

Definition
QAlgorithms_Papers_Independent_Intakethird100_P05

by Gohan · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

The objects the formalized statements of A New Proof of the Channel Coding Theorem via Hypothesis Testing in Quantum Information Theory (arXiv:quant-ph/0208139) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • DensityOutputChannel: PDF p.1, (1): a classical-input channel with normalized PSD output matrices.
  • channelAverage: PDF p.2, (4): the average output operator, constructed from the channel and law.
  • outputEntropyNats: PDF p.2, (4): entropy in nats; zero eigenvalues contribute 0 log 0 = 0.
  • channelInformationNats: PDF p.2, (4): Holevo mutual information for the given input law, in nats.
  • DistinctWordCode: PDF pp.1–2: a nonempty codebook of distinct words and a sub-POVM decoder. The remaining effect 1 - sum decoder is the failure outcome.
  • uniformMessageError: PDF p.1, (2): error averaged over the uniformly distributed messages, computed on the original output states, without pinching.
  • pinchedWord: PDF pp.3–5: pinching onto full distinct-eigenvalue eigenspaces of sigma^n.
  • pinchedLowerTail: PDF pp.4–5, (16),(21): iid pinched lower tail. The complement of the STRICT positive projector includes the zero eigenspace; BOTH rho occurrences in the trace/projection are pinched.
  • goodMass: PDF p.4, (17): one-shot mass of the strictly positive pinched likelihood test.
  • matrixOfHS: PDF p.8, (42): reshaping Hilbert–Schmidt coordinates into a matrix. The Euclidean inner product on these coordinates is Tr(A* B).
  • commutantHS: PDF pp.7–8, (40)–(41): commutant of the generated unital -algebra. For an arbitrary C it requires commuting with C AND C, not just C. Reshaping equips this subspace with the Hilbert–Schmidt inner product.
  • algebraPinch: PDF p.8, (41): Hilbert–Schmidt orthogonal projection onto the commutant. This supplies the literal arbitrary-reference domain of Lemma 3. For Hermitian references it is the spectral pinching (43), preserving degenerate eigenspaces.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_MatrixDistances
import Definitions.Def_QAlgorithms_Defs_ExtendedQuantumEntropy
import Definitions.Def_QAlgorithms_Papers_Independent_Claimed50_P45
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P07
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P35
import Definitions.Def_QAlgorithms_Papers_Independent_Renew46_P44

/-! Ogawa–Nagaoka, arXiv:quant-ph/0208139v1. Natural logarithms.
Only accepted frozen modules are imported. Paper-local operational definitions
adapt the accepted finite laws, averages and ordered iid products to (1)–(4),
(16)–(21), and the general projection (41). Distinct local names preserve the
cq word-code model and natural-log information rather than unrelated frozen
objects sharing old short names; see ASSESSMENT.json.
Lemma 4 is deferred because its negative powers are unpinned for singular states.
Compilation is pending the batch mechanical handoff. -/

noncomputable section

namespace QAlgorithms.Papers.Independent.Intakethird100.P05

open scoped Matrix ComplexConjugate ComplexOrder BigOperators
open Filter Topology QAlgorithms
open QAlgorithms.Papers.Independent.Information100.P60 (Mat copies)
open QAlgorithms.Papers.Independent.Information100.P07 (positiveProjection)
open QAlgorithms.Papers.Independent.Dependency50.P28 (tr pinch typeI accept)
open QAlgorithms.Papers.Independent.Claimed50.P45 (pinchedTest)
open QAlgorithms.Papers.Independent.Information100.P58 (Distribution)
open QAlgorithms.Papers.Independent.Information100.P27 (average)
open QAlgorithms.Papers.Independent.Dependency50.P07 (wordProb)
open QAlgorithms.Papers.Independent.Dependency50.P35 (directSum)
open QAlgorithms.Papers.Independent.Renew46.P44 (wordOutput)

attribute [local instance] Classical.propDecidable Classical.decEq

variable {X I : Type} [Fintype X] [DecidableEq X] [Fintype I] [DecidableEq I]

/-- PDF p.1, (1): a classical-input channel with normalized PSD output matrices. -/
structure DensityOutputChannel (X I : Type) [Fintype I] where
  state : X → Mat I
  normalized : ∀ x, IsDensityMatrix (state x)

/-- PDF p.2, (4): the average output operator, constructed from the channel and law. -/
def channelAverage (W : DensityOutputChannel X I) (p : Distribution X) : Mat I :=
  average p.val W.state

/-- PDF p.2, (4): entropy in nats; zero eigenvalues contribute 0 log 0 = 0. -/
def outputEntropyNats (rho : Mat I) : ℝ :=
  -(cfc (fun x : ℝ => x * Real.log x) rho).trace.re

/-- PDF p.2, (4): Holevo mutual information for the given input law, in nats. -/
def channelInformationNats (W : DensityOutputChannel X I) (p : Distribution X) : ℝ :=
  outputEntropyNats (channelAverage W p) - ∑ x, p.val x * outputEntropyNats (W.state x)

/-- PDF pp.1–2: a nonempty codebook of distinct words and a sub-POVM decoder.
The remaining effect 1 - sum decoder is the failure outcome. -/
structure DistinctWordCode (A J : Type) [Fintype J] [DecidableEq J] where
  size : ℕ
  positive_size : 0 < size
  word : Fin size → A
  distinct : Function.Injective word
  decoder : Fin size → Mat J
  positive_decoder : ∀ k, (decoder k).PosSemidef
  failure_positive : (1 - ∑ k, decoder k).PosSemidef

/-- PDF p.1, (2): error averaged over the uniformly distributed messages,
computed on the original output states, without pinching. -/
def uniformMessageError {A J : Type} [Fintype J] [DecidableEq J]
    (rho : A → Mat J) (C : DistinctWordCode A J) : ℝ :=
  (C.size : ℝ)⁻¹ * ∑ k, (1 - tr (rho (C.word k) * C.decoder k))

/-- PDF pp.3–5: pinching onto full distinct-eigenvalue eigenspaces of sigma^n. -/
def pinchedWord (W : DensityOutputChannel X I) (p : Distribution X) (n : ℕ)
    (u : Fin n → X) : Mat (Fin n → I) :=
  pinch (copies n (channelAverage W p)) (wordOutput W.state u)

/-- PDF pp.4–5, (16),(21): iid pinched lower tail. The complement of the
STRICT positive projector includes the zero eigenspace; BOTH rho occurrences
in the trace/projection are pinched. -/
def pinchedLowerTail (W : DensityOutputChannel X I) (p : Distribution X) (n : ℕ) (a : ℝ) : ℝ :=
  ∑ u : Fin n → X, wordProb p.val n u *
    tr (pinchedWord W p n u *
      (1 - positiveProjection (pinchedWord W p n u -
        (Real.exp ((n : ℝ) * a) : ℂ) • copies n (channelAverage W p))))

/-- PDF p.4, (17): one-shot mass of the strictly positive pinched likelihood test. -/
def goodMass (W : DensityOutputChannel X I) (p : Distribution X) (c : ℝ) : ℝ :=
  ∑ x, p.val x *
    tr (pinch (channelAverage W p) (W.state x) *
      positiveProjection (pinch (channelAverage W p) (W.state x) -
        (c : ℂ) • channelAverage W p))

/-- PDF p.8, (42): reshaping Hilbert–Schmidt coordinates into a matrix.
The Euclidean inner product on these coordinates is Tr(A* B). -/
def matrixOfHS : EuclideanSpace ℂ (I × I) →ₗ[ℂ] Mat I where
  toFun v := Matrix.of fun i j => v (i, j)
  map_add' v w := by ext i j; rfl
  map_smul' c v := by ext i j; rfl

/-- PDF pp.7–8, (40)–(41): commutant of the generated unital *-algebra.
For an arbitrary C it requires commuting with C AND C*, not just C.
Reshaping equips this subspace with the Hilbert–Schmidt inner product. -/
def commutantHS (C : Mat I) : Submodule ℂ (EuclideanSpace ℂ (I × I)) :=
  (Subalgebra.centralizer ℂ ({C, Cᴴ} : Set (Mat I))).toSubmodule.comap matrixOfHS

/-- PDF p.8, (41): Hilbert–Schmidt orthogonal projection onto the commutant.
This supplies the literal arbitrary-reference domain of Lemma 3. For Hermitian
references it is the spectral pinching (43), preserving degenerate eigenspaces. -/
def algebraPinch (C A : Mat I) : Mat I :=
  matrixOfHS ((commutantHS C).starProjection
    (WithLp.toLp 2 (fun ij : I × I => A ij.1 ij.2)))

/-- Sanity: every law, including laws with zero weights, has total mass one. -/
example (p : Distribution X) : ∑ x, p.val x = 1 := p.property.2

/-- Sanity: the channel carries normalization rather than an unnormalized state. -/
example (W : DensityOutputChannel X I) (x : X) : (W.state x).trace = 1 :=
  (W.normalized x).2

/-- Sanity: the empty product is 1, but all rates below use positive lengths. -/
example (p : Distribution X) (u : Fin 0 → X) : wordProb p.val 0 u = 1 := by
  simp [wordProb]

/-- Sanity: at a fixed one-use word the output is exactly its single factor. -/
example (W : DensityOutputChannel X I) (u : Fin 1 → X) (i j : Fin 1 → I) :
    wordOutput W.state u i j = W.state (u 0) (i 0) (j 0) := by
  simp [wordOutput]

/-- Sanity: the zero density candidate has zero entropy in the total definition. -/
example : outputEntropyNats (0 : Mat I) = 0 := by
  simp [outputEntropyNats, cfc_zero]

/-- Sanity: the general pinching maps the zero operator to zero for EVERY reference. -/
example (C : Mat I) : algebraPinch C 0 = 0 := by
  change matrixOfHS ((commutantHS C).starProjection
    (0 : EuclideanSpace ℂ (I × I))) = 0
  rw [map_zero, map_zero]

/-- Sanity: a direct sum has zero off-diagonal blocks. -/
example (A B : Mat I) (i j : I) : directSum A B (Sum.inl i) (Sum.inr j) = 0 := by
  rfl

end QAlgorithms.Papers.Independent.Intakethird100.P05
Source
A New Proof of the Channel Coding Theorem via Hypothesis Testing in Quantum Information Theory, arXiv:quant-ph/0208139v1, https://arxiv.org/abs/quant-ph/0208139v1
Read-back

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

QAlgorithms.Papers.Independent.Intakethird100.P05.DensityOutputChannel

For a type XXX and a finite type III, a density-output channel consists of a family x↦ρxx\mapsto \rho_xx↦ρx​ of complex matrices indexed by I×II\times II×I, together with the requirement that every ρx\rho_xρx​ is positive semidefinite and has complex trace 111. There is no finiteness assumption on XXX in this structure. If XXX is empty, the normalization requirement is vacuous; if III is empty and XXX is nonempty, it cannot be satisfied.

QAlgorithms.Papers.Independent.Intakethird100.P05.DistinctWordCode

For an arbitrary type AAA and a finite type JJJ with decidable equality, a distinct-word code consists of a natural number M>0M>0M>0, an injective function w:{0,…,M−1}→Aw:\{0,\ldots,M-1\}\to Aw:{0,…,M−1}→A, and complex J×JJ\times JJ×J matrices D0,…,DM−1D_0,\ldots,D_{M-1}D0​,…,DM−1​ such that every DkD_kDk​ is positive semidefinite and 1−∑kDk1-\sum_kD_k1−∑k​Dk​ is positive semidefinite. Thus the decoder matrices may sum to less than the identity, and individual decoder matrices may be zero. No states or channel are part of this structure. The condition M>0M>0M>0 excludes an empty message set and makes the structure impossible when AAA is empty.

QAlgorithms.Papers.Independent.Intakethird100.P05.algebraPinch

For a finite index type III with decidable equality and arbitrary complex I×II\times II×I matrices C,AC,AC,A, this defines a matrix by viewing the entries of AAA as the Euclidean vector v(i,j)=Aijv_{(i,j)}=A_{ij}v(i,j)​=Aij​, orthogonally projecting vvv onto the complex subspace whose associated matrices commute with both CCC and C†C^\daggerC†, and converting the resulting vector back into a matrix. Orthogonality uses the Euclidean inner product ⟨v,w⟩=∑i,jv(i,j)‾w(i,j)\langle v,w\rangle=\sum_{i,j}\overline{v_{(i,j)}}w_{(i,j)}⟨v,w⟩=∑i,j​v(i,j)​​w(i,j)​. Neither input is required to be Hermitian or positive semidefinite; for empty III, the result is the unique empty matrix.

QAlgorithms.Papers.Independent.Intakethird100.P05.channelAverage

For finite types XXX and III, a family W=(ρx)x∈XW=(\rho_x)_{x\in X}W=(ρx​)x∈X​ of positive semidefinite complex I×II\times II×I matrices with trace 111, and a distribution p:X→Rp:X\to\mathbb Rp:X→R satisfying px≥0p_x\geq0px​≥0 and ∑xpx=1\sum_xp_x=1∑x​px​=1, the channel average is the matrix ρ‾=∑x∈Xpxρx\overline\rho=\sum_{x\in X}p_x\rho_xρ​=∑x∈X​px​ρx​. Zero weights are allowed. An empty XXX admits no such distribution.

QAlgorithms.Papers.Independent.Intakethird100.P05.channelInformationNats

For finite types XXX and III, with decidable equality on III, a family W=(ρx)x∈XW=(\rho_x)_{x\in X}W=(ρx​)x∈X​ of positive semidefinite complex matrices of trace 111, and real weights px≥0p_x\geq0px​≥0 summing to 111, this defines

H ⁣(∑xpxρx)−∑xpxH(ρx),H(A)=−Re⁡Tr⁡((t↦tlog⁡t)(A)),H\!\left(\sum_xp_x\rho_x\right)-\sum_xp_xH(\rho_x), \qquad H(A)=-\operatorname{Re}\operatorname{Tr}\bigl((t\mapsto t\log t)(A)\bigr),H(x∑​px​ρx​)−x∑​px​H(ρx​),H(A)=−ReTr((t↦tlogt)(A)),

where the matrix function uses real continuous functional calculus and the logarithm is natural. Zero weights are permitted; an empty XXX cannot support the required distribution.

QAlgorithms.Papers.Independent.Intakethird100.P05.commutantHS

For a finite index type III with decidable equality and any complex I×II\times II×I matrix CCC, this defines the complex subspace of Euclidean coordinate vectors v∈CI×Iv\in\mathbb C^{I\times I}v∈CI×I whose associated matrix Aij=v(i,j)A_{ij}=v_{(i,j)}Aij​=v(i,j)​ commutes with both CCC and its conjugate transpose:

AC=CA,AC†=C†A.AC=CA,\qquad AC^\dagger=C^\dagger A.AC=CA,AC†=C†A.

No Hermiticity or normality assumption on CCC is required. If III is empty, this is the unique zero-dimensional subspace.

QAlgorithms.Papers.Independent.Intakethird100.P05.goodMass

For finite types X,IX,IX,I, with decidable equality on III, density matrices ρx=W.state(x)\rho_x=W.\mathrm{state}(x)ρx​=W.state(x), a distribution px≥0p_x\geq0px​≥0 summing to 111, and any real ccc, put ρ‾=∑xpxρx\overline\rho=\sum_xp_x\rho_xρ​=∑x​px​ρx​ and Ax=∑λEλρxEλA_x=\sum_\lambda E_\lambda\rho_xE_\lambdaAx​=∑λ​Eλ​ρx​Eλ​, where EλE_\lambdaEλ​ are the spectral projections of ρ‾\overline\rhoρ​, summed over its distinct eigenvalues. This defines the real number

∑xpx Re⁡Tr⁡ ⁣[AxP+(Ax−cρ‾)],\sum_xp_x\,\operatorname{Re}\operatorname{Tr}\!\left[A_xP_+(A_x-c\overline\rho)\right],x∑​px​ReTr[Ax​P+​(Ax​−cρ​)],

where P+(H)P_+(H)P+​(H) is the orthogonal projection onto the range of (t↦max⁡(t,0))(H)(t\mapsto\max(t,0))(H)(t↦max(t,0))(H), evaluated by continuous functional calculus. Thus the projection selects strictly positive eigenvalues and excludes zero eigenvalues. The parameter ccc may be zero or negative, and zero distribution weights are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P05.matrixOfHS

For an index type III, this defines the complex-linear map from the coordinate space CI×I\mathbb C^{I\times I}CI×I, represented as a Euclidean space, to complex I×II\times II×I matrices that sends vvv to the matrix AAA with entries Aij=v(i,j)A_{ij}=v_{(i,j)}Aij​=v(i,j)​. The structure includes proofs that this assignment preserves addition and multiplication by every complex scalar. It imposes no condition on vvv; for empty III, it maps the unique coordinate vector to the unique empty matrix.

QAlgorithms.Papers.Independent.Intakethird100.P05.outputEntropyNats

For a finite index type III with decidable equality and any complex I×II\times II×I matrix ρ\rhoρ, this defines the real number H(ρ)=−Re⁡Tr⁡(f(ρ))H(\rho)=-\operatorname{Re}\operatorname{Tr}(f(\rho))H(ρ)=−ReTr(f(ρ)), where f(t)=tlog⁡tf(t)=t\log tf(t)=tlogt, log⁡\loglog is the real natural logarithm, and f(ρ)f(\rho)f(ρ) is evaluated by the real continuous functional calculus. No positivity, Hermiticity, or trace normalization is assumed. The real logarithm is total, with log⁡0=0\log0=0log0=0; the value is 000 for the zero matrix, including the matrix on an empty index type.

QAlgorithms.Papers.Independent.Intakethird100.P05.pinchedLowerTail

For finite types X,IX,IX,I, with decidable equality on III, density matrices ρx=W.state(x)\rho_x=W.\mathrm{state}(x)ρx​=W.state(x), a distribution px≥0p_x\geq0px​≥0 summing to 111, a natural number nnn, and any real aaa, let ρ‾=∑xpxρx\overline\rho=\sum_xp_x\rho_xρ​=∑x​px​ρx​, let Bvw=∏i<nρ‾viwiB_{vw}=\prod_{i<n}\overline\rho_{v_iw_i}Bvw​=∏i<n​ρ​vi​wi​​, and, for each word u∈Xnu\in X^nu∈Xn, let Au=∑λEλ(⨂i<nρui)EλA_u=\sum_\lambda E_\lambda(\bigotimes_{i<n}\rho_{u_i})E_\lambdaAu​=∑λ​Eλ​(⨂i<n​ρui​​)Eλ​, where EλE_\lambdaEλ​ are the spectral projections of BBB, summed over its distinct eigenvalues. This defines

∑u∈Xn(∏i<npui)Re⁡Tr⁡ ⁣[Au(1−P+(Au−enaB))].\sum_{u\in X^n}\left(\prod_{i<n}p_{u_i}\right) \operatorname{Re}\operatorname{Tr}\!\left[A_u\left(1-P_+(A_u-e^{na}B)\right)\right].u∈Xn∑​(i<n∏​pui​​)ReTr[Au​(1−P+​(Au​−enaB))].

Here P+(H)P_+(H)P+​(H) is the orthogonal projection onto the range of the matrix obtained by applying t↦max⁡(t,0)t\mapsto\max(t,0)t↦max(t,0) to HHH by continuous functional calculus; for these Hermitian matrices it selects the strictly positive eigenspaces, so its complement includes the zero eigenspace. There is no restriction on aaa, and n=0n=0n=0 is allowed and gives value 111.

QAlgorithms.Papers.Independent.Intakethird100.P05.pinchedWord

For finite types X,IX,IX,I, with decidable equality on III, density matrices ρx=W.state(x)\rho_x=W.\mathrm{state}(x)ρx​=W.state(x), a distribution px≥0p_x\geq0px​≥0 with ∑xpx=1\sum_xp_x=1∑x​px​=1, any natural number nnn, and a word u:{0,…,n−1}→Xu:\{0,\ldots,n-1\}\to Xu:{0,…,n−1}→X, put ρ‾=∑xpxρx\overline\rho=\sum_xp_x\rho_xρ​=∑x​px​ρx​ and define matrices indexed by functions a,b:{0,…,n−1}→Ia,b:\{0,\ldots,n-1\}\to Ia,b:{0,…,n−1}→I by Bab=∏i<nρ‾aibiB_{ab}=\prod_{i<n}\overline\rho_{a_i b_i}Bab​=∏i<n​ρ​ai​bi​​ and Aab=∏i<n(ρui)aibiA_{ab}=\prod_{i<n}(\rho_{u_i})_{a_i b_i}Aab​=∏i<n​(ρui​​)ai​bi​​. The pinched word is ∑λEλAEλ\sum_{\lambda}E_\lambda A E_\lambda∑λ​Eλ​AEλ​, where the sum runs once over each distinct eigenvalue of BBB and EλE_\lambdaEλ​ is the continuous-functional-calculus matrix for the function equal to 111 at λ\lambdaλ and 000 elsewhere. Here BBB is Hermitian; the underlying pinching definition returns zero for a non-Hermitian pinching matrix. The case n=0n=0n=0 is included and gives the one-by-one matrix with entry 111, since all coordinate products are empty.

QAlgorithms.Papers.Independent.Intakethird100.P05.uniformMessageError

For an arbitrary type AAA, a finite type JJJ with decidable equality, any matrix-valued function ρ:A→CJ×J\rho:A\to\mathbb C^{J\times J}ρ:A→CJ×J, and a code having M>0M>0M>0 distinct words wk∈Aw_k\in Awk​∈A and positive semidefinite decoder matrices DkD_kDk​ with 1−∑kDk1-\sum_kD_k1−∑k​Dk​ positive semidefinite, this defines

1M∑k=0M−1(1−Re⁡Tr⁡(ρ(wk)Dk)).\frac1M\sum_{k=0}^{M-1}\left(1-\operatorname{Re}\operatorname{Tr}(\rho(w_k)D_k)\right).M1​k=0∑M−1​(1−ReTr(ρ(wk​)Dk​)).

The function ρ\rhoρ is not required to consist of density matrices, so the definition imposes no probability-range guarantee on this real number. The denominator is nonzero because the code requires M>0M>0M>0.

Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Nov 1, 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