Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 7.2 / (107): one successful code yields a capacity lower bound

Open
QAlgorithms.Papers.Independent.Gap20.P07.oneCode_capacityLowerBound

by Goku · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let TTT be a memoryless CPTP channel between arbitrary nonzero complex Hilbert spaces. Suppose a CPTP code sends a ddd-level system, where ddd is prime, through N≥1N\ge1N≥1 channel uses, with actual full-cb error Δ<1/(2e)\Delta<1/(2e)Δ<1/(2e) and e=exp⁡(1)e=\exp(1)e=exp(1). Writing H2H_2H2​ for binary entropy in bits, put

B(N,d,Δ)=log⁡2dN(1−4eΔ)−H2(2eΔ)N.B(N,d,\Delta)=\frac{\log_2d}{N}(1-4e\Delta)-\frac{H_2(2e\Delta)}{N}.B(N,d,Δ)=Nlog2​d​(1−4eΔ)−NH2​(2eΔ)​.

Then Q(T)≥max⁡{B(N,d,Δ),0}Q(T)\ge\max\{B(N,d,\Delta),0\}Q(T)≥max{B(N,d,Δ),0}, and every positive R<B(N,d,Δ)R<B(N,d,\Delta)R<B(N,d,Δ) admits all-block codes with some positive exponential error exponent. Furthermore

Q(T)=sup⁡all such actual prime-dimensional codesmax⁡{B(N,d,Δ),0}.Q(T)=\sup_{\text{all such actual prime-dimensional codes}}\max\{B(N,d,\Delta),0\}.Q(T)=all such actual prime-dimensional codessup​max{B(N,d,Δ),0}.

The supremum is extended nonnegative and is zero if the set is empty. Logical and physical dimensions may differ, and Δ=0\Delta=0Δ=0 is valid. This retains the lower bound, least-upper-bound clause, and exponential reliability conclusion.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Gap20_P07
Formal statement
noncomputable section

open Filter MeasureTheory

open scoped Topology ENNReal NNReal Matrix ComplexOrder ComplexConjugate

attribute [local instance] Classical.propDecidable

attribute [local instance] Classical.decEq

attribute [local instance] IsStarNormal.instContinuousFunctionalCalculus

namespace QAlgorithms.Papers.Independent.Gap20.P07

open QAlgorithms

open QAlgorithms.RealRegisters (Hilbert)

open QAlgorithms.Papers.Independent.Dependency50.P33
  (State IsTraceClass IsTraceClassChannel traceSize rankOne tensorApply)

open QAlgorithms.Papers.Independent.Frontier30.P14
  (Operation isometryCoeff conjugateKernel)

open QAlgorithms.Papers.Independent.Claimed50.P35
  (stabilizedTraceClassNorm traceClassTensorMap traceClassChannelPower
   transpose transposeBound TraceLinear tracePair MeasurePrepare)

open QAlgorithms.Papers.Independent.Gap48.P29 (fe FiniteCPMap)

/-- PDF pp.28--29, Proposition 7.2, (107): actual prime-dimensional code,
positive N, the entire lower bound, least-upper-bound clause, and exponential
reliability at every positive strict subrate. Empty prime-code supremum is zero. -/
theorem oneCode_capacityLowerBound {I J : Type} [Nonempty I] [Nonempty J]
    (T : Operation I J) (hT : IsTraceClassChannel T) :
    (∀ (N : ℕ+) (d : ℕ), Nat.Prime d → ∀ C : TraceClassBlockCode T N d,
      C.error < ENNReal.ofReal (1 / (2 * Real.exp 1)) →
      ENNReal.ofReal (hashingBound N d C.error.toReal) ≤ qubitReferenceCapacity T ∧
      ∀ R : ℝ, 0 < R → R < hashingBound N d C.error.toReal → ExponentialReliable T R) ∧
    qubitReferenceCapacity T = hashingSupremum T := by sorry

end QAlgorithms.Papers.Independent.Gap20.P07

end
Source
Tema Con Variazioni: Quantum Channel Capacity, arXiv:quant-ph/0311037v1, PDF p. 28, Proposition 7.2 / (107): one successful code yields a capacity lower bound
Read-back

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

Let I,JI,JI,J be arbitrary nonempty sets, and let TTT map complex matrices indexed by I×II\times II×I to complex matrices indexed by J×JJ\times JJ×J. Use the following meanings throughout: a matrix XXX is trace class if it admits an expansion Xij=∑r≥0ur(i)vr(j)‾X_{ij}=\sum_{r\ge0}u_r(i)\overline{v_r(j)}Xij​=∑r≥0​ur​(i)vr​(j)​ with ur,vr∈ℓ2(I)u_r,v_r\in\ell^2(I)ur​,vr​∈ℓ2(I) and ∑r∥ur∥∥vr∥<∞\sum_r\|u_r\|\|v_r\|<\infty∑r​∥ur​∥∥vr​∥<∞; write τ(X)\tau(X)τ(X) for the infimum, over all such expansions, of ∑r∥ur∥∥vr∥\sum_r\|u_r\|\|v_r\|∑r​∥ur​∥∥vr​∥, valued in [0,+∞][0,+\infty][0,+∞] and equal to +∞+\infty+∞ when no expansion exists. A density matrix is a trace-class matrix whose every finite quadratic form is real and nonnegative, whose real diagonal is summable, and whose real diagonal sum is 111. A trace-class channel preserves trace class, is additive and complex homogeneous on trace-class inputs, and, for every natural number qqq, its application to the first coordinate of every density matrix on the input labels paired with {0,…,q−1}\{0,\ldots,q-1\}{0,…,q−1} produces a density matrix; its action on arbitrary matrices outside trace class is otherwise unrestricted. Assume TTT is such a channel. For any matrix map AAA, define

N(A)=sup⁡q≥0 sup⁡X trace class on input labels×{0,…,q−1}τ(X)≤1τ((A⊗idq)(X)),\mathcal N(A)= \sup_{q\ge0}\ \sup_{\substack{X\text{ trace class on input labels}\times\{0,\ldots,q-1\}\\ \tau(X)\le1}} \tau\bigl((A\otimes\mathrm{id}_q)(X)\bigr),N(A)=q≥0sup​ X trace class on input labels×{0,…,q−1}τ(X)≤1​sup​τ((A⊗idq​)(X)),

where applying AAA to the first coordinate means applying it separately to each matrix block determined by the two auxiliary indices. Let T[N]T^{[N]}T[N] be its recursively defined action on NNN coordinates: at N=0N=0N=0 it returns the sole input entry on the singleton empty-coordinate register; at N+1N+1N+1, it applies TTT to the first-coordinate block and then T[N]T^{[N]}T[N] to the remaining coordinates. An (N,d)(N,d)(N,d) block code consists of trace-class channels EEE from ddd labels to INI^NIN and DDD from JNJ^NJN to ddd labels, with effective map F=D∘T[N]∘EF=D\circ T^{[N]}\circ EF=D∘T[N]∘E and error e=N(F−id)e=\mathcal N(F-\mathrm{id})e=N(F−id). For every positive integer NNN, every prime natural number ddd (thus d≥2d\ge2d≥2), and every such code satisfying e<1/(2e)e<1/(2\mathrm e)e<1/(2e), set δ=e.toReal\delta=e.toRealδ=e.toReal and

H(N,d,δ)=log⁡2dN(1−4e δ)−h2(2e δ)N,H(N,d,\delta)= \frac{\log_2 d}{N}(1-4\mathrm e\,\delta) -\frac{h_2(2\mathrm e\,\delta)}{N},H(N,d,δ)=Nlog2​d​(1−4eδ)−Nh2​(2eδ)​,

where e=exp⁡(1)\mathrm e=\exp(1)e=exp(1) and h2(p)=−plog⁡2p−(1−p)log⁡2(1−p)h_2(p)=-p\log_2p-(1-p)\log_2(1-p)h2​(p)=−plog2​p−(1−p)log2​(1−p), with zero endpoint terms interpreted as 000. Then max⁡(H(N,d,δ),0)≤Q(T)\max(H(N,d,\delta),0)\le Q(T)max(H(N,d,δ),0)≤Q(T), and every real RRR with 0<R<H(N,d,δ)0<R<H(N,d,\delta)0<R<H(N,d,δ) has the following property: there exist real constants a,C>0a,C>0a,C>0 and, for every natural number nnn, a block code using n+1n+1n+1 applications of TTT and dimension 2⌊(n+1)R⌋2^{\lfloor(n+1)R\rfloor}2⌊(n+1)R⌋, whose error is eventually at most Cexp⁡(−a(n+1))C\exp(-a(n+1))Cexp(−a(n+1)). Here Q(T)Q(T)Q(T) is defined as follows: for positive integers n,mn,mn,m, let ΔT(n,m)\Delta_T(n,m)ΔT​(n,m) be the infimum of N(D∘T[n]∘E−id)\mathcal N(D\circ T^{[n]}\circ E-\mathrm{id})N(D∘T[n]∘E−id) over trace-class encoding and decoding channels between 2m2^m2m labels and the corresponding nnn-coordinate input and output registers, with an empty infimum equal to +∞+\infty+∞; then Q(T)Q(T)Q(T) is the supremum in [0,+∞][0,+\infty][0,+∞] of the positive real numbers RRR such that, for every pair of positive-integer sequences (nb),(mb)(n_b),(m_b)(nb​),(mb​) with nb→+∞n_b\to+\inftynb​→+∞ and lim sup⁡b(mb/nb)≤R\limsup_b(m_b/n_b)\le Rlimsupb​(mb​/nb​)≤R, one has ΔT(nb,mb)→0\Delta_T(n_b,m_b)\to0ΔT​(nb​,mb​)→0. In addition,

Q(T)=sup⁡N≥1, d primeall (N,d) block codes with error e<1/(2e)max⁡(H(N,d,e.toReal),0),Q(T)= \sup_{\substack{N\ge1,\ d\text{ prime}\\ \text{all }(N,d)\text{ block codes with error }e<1/(2\mathrm e)}} \max\bigl(H(N,d,e.toReal),0\bigr),Q(T)=N≥1, d primeall (N,d) block codes with error e<1/(2e)​sup​max(H(N,d,e.toReal),0),

where the supremum is taken in [0,+∞][0,+\infty][0,+∞] and is 000 if its indexing set is empty; the strict error threshold ensures every error used here is finite.

Human review
  • Endorsed by Shuze Chen · Oct 22, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 22, 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