Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Depolarizing channel: 42 uses are necessary to exceed the displayed coherent-information value

Open
QAlgorithms.Papers.Independent.Support50.P04.depolarizing_necessary_42

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

prove2quantum

Let α=33/400=0.0825\alpha=33/400=0.0825α=33/400=0.0825 and ε=11/200=0.055\varepsilon=11/200=0.055ε=11/200=0.055. Let Dα(ρ)=(1−α)ρ+(α/3)(XρX+YρY+ZρZ)D_\alpha(\rho)=(1-\alpha)\rho+(\alpha/3)(X\rho X+Y\rho Y+Z\rho Z)Dα​(ρ)=(1−α)ρ+(α/3)(XρX+YρY+ZρZ), where X,Y,ZX,Y,ZX,Y,Z are the Pauli matrices. For every positive integer n<42n<42n<42, the maximum entanglement-transmission rate with classical post-processing satisfies

R^Dαcpp(n;ε)≤1−h(α)−αlog⁡23.\widehat R^{\mathrm{cpp}}_{D_\alpha}(n;\varepsilon)\le 1-h(\alpha)-\alpha\log_2 3.RDα​cpp​(n;ε)≤1−h(α)−αlog2​3.

Here hhh is binary entropy and fidelity is squared fidelity to the normalized maximally entangled target. The right side is the explicit comparison expression in Eq.(11); no general identity between this expression and maximized coherent information is assumed. This is a necessary block-length condition, with no achievability claim at 42.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P04
Formal statement
noncomputable section

open scoped Matrix ComplexConjugate ComplexOrder

open QAlgorithms

namespace QAlgorithms.Papers.Independent.Support50.P04

variable {A B E : Type} [Fintype A] [DecidableEq A]

variable [Fintype B] [DecidableEq B] [Fintype E] [DecidableEq E]

/-- arXiv:1504.04617v2, PDF pp.6–7, Fig.4(b) and its discussion.
At alpha=0.0825 and epsilon=5.5%, at least 42 channel uses are necessary to
exceed the comparison value displayed in Eq.(11). The statement is only this
necessary condition: it does not assert that a code attains the bound at n=42.
The separate 738 value is explicitly based on a second-order approximation.
No numerical certification premise is added to this source claim. -/
theorem depolarizing_necessary_42 (n : ℕ) (hn : 0 < n) (hsmall : n < 42) :
    cppBoundary (QuditFidelity.depolarizingMap 2 (by norm_num) (4*(33/400)/3)) n (11/200) ≤
      ((1 - QAlgorithms.Papers.Independent.Frontier18.P07.binaryEntropyBits (33/400) -
        (33/400) * QAlgorithms.Papers.Independent.Information100.P80.log2 3 : ℝ) : EReal) := by sorry

end QAlgorithms.Papers.Independent.Support50.P04

end
Source
Quantum Coding with Finite Resources, arXiv:1504.04617v2, PDF p. 7, §II.C, Fig.4(b) discussion
Read-back

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

For every natural number nnn with 0<n<420<n<420<n<42, hence n∈{1,…,41}n\in\{1,\ldots,41\}n∈{1,…,41}, let N\mathcal NN be the map on complex 2×22\times22×2 matrices defined by N(X)=89100X+11200tr⁡(X)I2\mathcal N(X)=\frac{89}{100}X+\frac{11}{200}\operatorname{tr}(X)I_2N(X)=10089​X+20011​tr(X)I2​. Consider all positive integers M,qM,qM,q, encoding channels E\mathcal EE from an MMM-dimensional register to nnn qubits together with a qqq-dimensional memory, and decoding channels D\mathcal DD from that memory together with the nnn output qubits to an MMM-dimensional register, subject to the following restriction on the decoder. There must exist positive integers a,ba,ba,b, isometries W:Cq→CaW:\mathbb C^q\to\mathbb C^aW:Cq→Ca and V:C2n→CbV:\mathbb C^{2^n}\to\mathbb C^bV:C2n→Cb, a map L\mathcal LL on the joint aaa- and bbb-dimensional registers, and a channel F\mathcal FF from the latter register to the MMM-dimensional output, such that, for every matrix XXX,

D(X)=F ⁣(tr⁡a(L((W⊗V)X(W⊗V)†))).\mathcal D(X)=\mathcal F\!\left(\operatorname{tr}_{a} \bigl(\mathcal L((W\otimes V)X(W\otimes V)^\dagger)\bigr)\right).D(X)=F(tra​(L((W⊗V)X(W⊗V)†))).

Here the singleton-outcome family consisting of L\mathcal LL must admit the following construction: there is a sequence of instruments with natural-number outcomes, each obtained by a positive finite number of successive rounds, with every instrument in the sequence extended by one further round to obtain the next. In each round, one of the two parties applies an instrument and the other applies an outcome-dependent channel, and the joint branch map is their tensor product; later rounds may depend on the accumulated outcome history. An instrument here has completely positive complex-linear branch maps, its branch outputs are summable for every input matrix, and their sum preserves trace; complete positivity means that every finite identity extension preserves positive semidefinite matrices. For each instrument in the sequence, its outcomes can be grouped to produce a singleton-outcome instrument whose map approaches L\mathcal LL in the distance

d(J,K)=sup⁡ρ≥0, tr⁡ρ=1∑o∥(id⁡⊗(Jo−Ko))(ρ)∥1,d(J,K)=\sup_{\rho\ge0,\ \operatorname{tr}\rho=1} \sum_o\left\|(\operatorname{id}\otimes(J_o-K_o))(\rho)\right\|_1,d(J,K)=ρ≥0, trρ=1sup​o∑​∥(id⊗(Jo​−Ko​))(ρ)∥1​,

where the reference register has the same dimension as the joint input and ∥Y∥1=Re⁡tr⁡Y†Y\|Y\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Y^\dagger Y}∥Y∥1​=RetrY†Y​. Every channel mentioned above is required to have a finite Kraus representation X↦∑jKjXKj†X\mapsto\sum_jK_jXK_j^\daggerX↦∑j​Kj​XKj†​ with ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I. For such an encoder and decoder, define the effective map T\mathcal TT by applying E\mathcal EE, applying N⊗n\mathcal N^{\otimes n}N⊗n to its qubit register while retaining its memory, and then applying D\mathcal DD. With ΦM\Phi_MΦM​ the matrix having entry 1/M1/M1/M at ((i,i),(j,j))((i,i),(j,j))((i,i),(j,j)) and zero elsewhere, require

Re⁡tr⁡ ⁣[ΦM(id⁡M⊗T)(ΦM)]≥189200.\operatorname{Re}\operatorname{tr}\!\left[ \Phi_M(\operatorname{id}_M\otimes\mathcal T)(\Phi_M)\right] \ge \frac{189}{200}.Retr[ΦM​(idM​⊗T)(ΦM​)]≥200189​.

The assertion is that the supremum, in the extended real numbers, of all real RRR for which such a code exists and R≤log⁡2(M)/nR\le \log_2(M)/nR≤log2​(M)/n satisfies

sup⁡R ≤ 1−h2 ⁣(33400)−33400log⁡23,h2(t)=−tlog⁡t−(1−t)log⁡(1−t)log⁡2.\sup R\ \le\ 1-h_2\!\left(\frac{33}{400}\right) -\frac{33}{400}\log_2 3, \qquad h_2(t)=\frac{-t\log t-(1-t)\log(1-t)}{\log 2}.supR ≤ 1−h2​(40033​)−40033​log2​3,h2​(t)=log2−tlogt−(1−t)log(1−t)​.

The memory dimension and message dimension are unrestricted apart from positivity, RRR has no nonnegativity requirement, and the supremum uses the extended-real convention that the supremum of the empty set is −∞-\infty−∞.

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

    Confirmed by the moderator at approval.

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