Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

§5 unnumbered extension: approximately recoverable channels

Open
QAlgorithms.Papers.Independent.Intakethird100.P50.approximatelyRecoverable_capacities

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

prove2quantum

All systems are nonzero finite-dimensional complex Hilbert spaces. A channel is complex-linear, completely positive and trace preserving. Its receiver and full complementary channel are obtained from the same isometric dilation. Write Q(N)Q(N)Q(N) and P(N)P(N)P(N) for the unassisted operational quantum and private capacities, allowing arbitrary collective codes over independent uses with vanishing reliability error and environmental leakage. Write Ic(N)=max⁡ρ[S(N(ρ))−S(Nc(ρ))]I_c(N)=\max_\rho[S(N(\rho))-S(N^c(\rho))]Ic​(N)=maxρ​[S(N(ρ))−S(Nc(ρ))], where the maximum includes every density operator. Entropies and logarithms are in bits, with 0log⁡0=00\log 0=00log0=0. The diamond norm has no factor 1/21/21/2.

Fix input and receiver spaces A,BA,BA,B. Let N:A→BN:A\to BN:A→B and M:B→AM:B\to AM:B→A be channels. Choose compatible dilations V:A→B⊗E1V:A\to B\otimes E_1V:A→B⊗E1​ and W:B→A⊗E2W:B\to A\otimes E_2W:B→A⊗E2​ and the sequential dilation of M∘NM\circ NM∘N, with environment ordered E1⊗E2E_1\otimes E_2E1​⊗E2​. On every input operator XXX,

Tr⁡E2(M∘N)c(X)=Nc(X).\operatorname{Tr}_{E_2}(M\circ N)^c(X)=N^c(X).TrE2​​(M∘N)c(X)=Nc(X).

Define the CPTP degrader D=Tr⁡E2∘(M∘N)c∘MD=\operatorname{Tr}_{E_2}\circ(M\circ N)^c\circ MD=TrE2​​∘(M∘N)c∘M. For any 0≤ε≤20\le\varepsilon\le20≤ε≤2 satisfying ∥M∘N−idA∥⋄≤ε\|M\circ N-\mathrm{id}_A\|_\diamond\le\varepsilon∥M∘N−idA​∥⋄​≤ε,

∥Nc−D∘N∥⋄≤2ε3/2.\|N^c-D\circ N\|_\diamond\le2\varepsilon^{3/2}.∥Nc−D∘N∥⋄​≤2ε3/2.

Moreover, there are CQ,CP≥0C_Q,C_P\ge0CQ​,CP​≥0 and 0<δ≤20<\delta\le20<δ≤2, uniform over these channels and their dilations at fixed A,BA,BA,B, such that for 0≤ε≤δ0\le\varepsilon\le\delta0≤ε≤δ the original channel NNN satisfies exactly the two capacity bounds below, with its own actual Choi rank eee. If e=1e=1e=1 or ε=0\varepsilon=0ε=0, Q(N)=P(N)=Ic(N)Q(N)=P(N)=I_c(N)Q(N)=P(N)=Ic​(N); otherwise:

∣Q(N)−Ic(N)∣≤−3ε3/2log⁡2ε+2ε3/2[1ln⁡2+log⁡2e+12log⁡2(e−1)]+CQε9/2,|Q(N)-I_c(N)|\le-3\varepsilon^{3/2}\log_2\varepsilon+2\varepsilon^{3/2}\left[\frac1{\ln2}+\log_2e+\tfrac12\log_2(e-1)\right]+C_Q\varepsilon^{9/2},∣Q(N)−Ic​(N)∣≤−3ε3/2log2​ε+2ε3/2[ln21​+log2​e+21​log2​(e−1)]+CQ​ε9/2, ∣P(N)−Ic(N)∣≤−9ε3/2log⁡2ε+2ε3/2[3ln⁡2+4log⁡2e+log⁡2(e−1)]+CPε3.|P(N)-I_c(N)|\le-9\varepsilon^{3/2}\log_2\varepsilon+2\varepsilon^{3/2}\left[\frac3{\ln2}+4\log_2e+\log_2(e-1)\right]+C_P\varepsilon^3.∣P(N)−Ic​(N)∣≤−9ε3/2log2​ε+2ε3/2[ln23​+4log2​e+log2​(e−1)]+CP​ε3.

This extends the low-noise conclusion to approximately recoverable channels even when their input and receiver dimensions differ.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P50
Formal statement
noncomputable section

open scoped BigOperators Matrix ComplexConjugate ComplexOrder

open Filter

namespace QAlgorithms.Papers.Independent.Intakethird100.P50

variable {A B E F : Type}

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

variable [Fintype E] [DecidableEq E] [Fintype F] [DecidableEq F]

open QAlgorithms.Papers.Independent.Information100.P67
  (IsIsometry receiverChannel complementaryChannel maximumCoherentInformation
    dilationPower idealJoint)

open QAlgorithms.Papers.Independent.Information100.P80 (log2)

open QAlgorithms.Papers.Independent.Information100.P69 (diamond choi)

open QAlgorithms.Papers.Independent.Support50.P07 (fullTracePrivateCapacity)

open QAlgorithms.Papers.Independent.Frontier18.P17 (clock)

/-- §5 unnumbered extension, PDF pp.18–19: compatible dilations give the partial
trace identity on ALL matrices and the specified degrader for the ORIGINAL N.
The full norm inequality and all Theorem 12 remainders are retained. -/
theorem approximatelyRecoverable_capacities [Nonempty A] [Nonempty B] :
    ∃ Cq Cp : ℝ, 0 ≤ Cq ∧ 0 ≤ Cp ∧ ∃ delta : ℝ, 0 < delta ∧ delta ≤ 2 ∧
      ∀ (E F : Type) [Fintype E] [DecidableEq E] [Nonempty E]
        [Fintype F] [DecidableEq F] [Nonempty F],
      ∀ (V : Matrix (B × E) A ℂ) (W : Matrix (A × F) B ℂ),
        IsIsometry V → IsIsometry W →
        (∀ rho : Matrix A A ℂ,
          traceRight (complementaryChannel (composedDilation V W) rho) = complementaryChannel V rho) ∧
        (∀ eps ∈ Set.Icc 0 2,
          diamond (channelDifference (receiverChannel W ∘ receiverChannel V) id) ≤ eps →
          diamond (channelDifference (complementaryChannel V) (recoveryDegrader V W ∘ receiverChannel V)) ≤
            2 * eps ^ (3 / 2 : ℝ)) ∧
        (∀ eps ∈ Set.Icc 0 delta,
          diamond (channelDifference (receiverChannel W ∘ receiverChannel V) id) ≤ eps →
          LowNoiseCapacityBounds V eps Cq Cp) := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P50

end
Source
Quantum and private capacities of low-noise channels, arXiv:1705.04335v3, PDF p. 18, §5 unnumbered extension: approximately recoverable channels
Read-back

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

Fix finite nonempty index sets A,BA,BA,B, with decidable equality. There exist real Cq,Cp≥0C_q,C_p\ge0Cq​,Cp​≥0 and 0<δ≤20<\delta\le20<δ≤2, chosen independently of the environments below, such that the following holds for every pair of finite nonempty index sets E,FE,FE,F, also with decidable equality, and every pair of complex matrices V:A→B×EV:A\to B\times EV:A→B×E, W:B→A×FW:B\to A\times FW:B→A×F satisfying V†V=IAV^\dagger V=I_AV†V=IA​ and W†W=IBW^\dagger W=I_BW†W=IB​. Write

NV(X)=Tr⁡E(VXV†),NVc(X)=Tr⁡B(VXV†),Ua′,(e,f);a=∑bWa′,f;bVb,e;a,D=Tr⁡F∘NUc∘NW,N_V(X)=\operatorname{Tr}_{E}(VXV^\dagger),\quad N_V^c(X)=\operatorname{Tr}_{B}(VXV^\dagger),\quad U_{a',(e,f);a}=\sum_bW_{a',f;b}V_{b,e;a},\quad D=\operatorname{Tr}_{F}\circ N_U^c\circ N_W,NV​(X)=TrE​(VXV†),NVc​(X)=TrB​(VXV†),Ua′,(e,f);a​=b∑​Wa′,f;b​Vb,e;a​,D=TrF​∘NUc​∘NW​,

where receiver and complementary maps always trace out respectively the environment and receiver registers. First, for every complex matrix ρ\rhoρ on AAA, with no density assumption, Tr⁡F(NUc(ρ))=NVc(ρ)\operatorname{Tr}_{F}(N_U^c(\rho))=N_V^c(\rho)TrF​(NUc​(ρ))=NVc​(ρ). Second, for every ε∈[0,2]\varepsilon\in[0,2]ε∈[0,2],

∥NW∘NV−id⁡A∥⋄≤ε⟹∥NVc−D∘NV∥⋄≤2ε3/2.\|N_W\circ N_V-\operatorname{id}_A\|_\diamond\le\varepsilon \quad\Longrightarrow\quad \|N_V^c-D\circ N_V\|_\diamond\le2\varepsilon^{3/2}.∥NW​∘NV​−idA​∥⋄​≤ε⟹∥NVc​−D∘NV​∥⋄​≤2ε3/2.

Here ∥T∥⋄=sup⁡∥X∥1≤1∥(id⁡H⊗T)(X)∥1\|T\|_\diamond=\sup_{\|X\|_1\le1}\|(\operatorname{id}_{H}\otimes T)(X)\|_1∥T∥⋄​=sup∥X∥1​≤1​∥(idH​⊗T)(X)∥1​ for input index set HHH, with arbitrary complex XXX on H×HH\times HH×H, and ∥X∥1=Re⁡Tr⁡X†X\|X\|_1=\operatorname{Re}\operatorname{Tr}\sqrt{X^\dagger X}∥X∥1​=ReTrX†X​. Third, whenever 0≤ε≤δ0\le\varepsilon\le\delta0≤ε≤δ and the same recovery error is at most ε\varepsilonε, put e=rank⁡J(NV)e=\operatorname{rank}J(N_V)e=rankJ(NV​), where J(NV)(a,b),(a′,b′)=NV(∣a⟩⟨a′∣)bb′J(N_V)_{(a,b),(a',b')}=N_V(|a\rangle\langle a'|)_{bb'}J(NV​)(a,b),(a′,b′)​=NV​(∣a⟩⟨a′∣)bb′​, and define

Ic(V)=sup⁡ρ≥0, Tr⁡ρ=1[S(NV(ρ))−S(NVc(ρ))],S(ρ)=−Re⁡Tr⁡f(ρ),f(x)=xlog⁡2x.I_c(V)=\sup_{\rho\ge0,\ \operatorname{Tr}\rho=1}[S(N_V(\rho))-S(N_V^c(\rho))], \quad S(\rho)=-\operatorname{Re}\operatorname{Tr}f(\rho),\quad f(x)=x\log_2x.Ic​(V)=ρ≥0, Trρ=1sup​[S(NV​(ρ))−S(NVc​(ρ))],S(ρ)=−ReTrf(ρ),f(x)=xlog2​x.

The matrix function uses spectral functional calculus, log⁡2x=log⁡x/log⁡2\log_2x=\log x/\log2log2​x=logx/log2, and 0log⁡20=00\log_2 0=00log2​0=0. Let Q(V)Q(V)Q(V) be the supremum of nonnegative rates rrr admitting, for every n≥0n\ge0n≥0, positive message dimensions MnM_nMn​ and encoding and decoding channels through NV⊗nN_V^{\otimes n}NV⊗n​, whose entanglement transmission fidelities tend to 111 and whose rates satisfy, for every s>0s>0s>0, eventually r−s≤log⁡2Mn/nr-s\le\log_2M_n/nr−s≤log2​Mn​/n. This fidelity is the overlap with ∣ΦMn⟩⟨ΦMn∣|\Phi_{M_n}\rangle\langle\Phi_{M_n}|∣ΦMn​​⟩⟨ΦMn​​∣ after the encoded channel and decoder act on the second half of ∣ΦMn⟩=Mn−1/2∑m∣m,m⟩|\Phi_{M_n}\rangle=M_n^{-1/2}\sum_m|m,m\rangle∣ΦMn​​⟩=Mn−1/2​∑m​∣m,m⟩. Let P(V)P(V)P(V) be the supremum of nonnegative rates rrr such that, for every ϵ′,s>0\epsilon',s>0ϵ′,s>0, all sufficiently large positive nnn admit M>0M>0M>0, input density matrices ρm\rho_mρm​, and positive semidefinite decoding matrices FjF_jFj​ summing to III, with r−s≤log⁡2M/nr-s\le\log_2M/nr−s≤log2​M/n and

∥Ω−1M∑m∣m,m⟩⟨m,m∣⊗ΩE∥1<ϵ′,Ω=1M∑m,j∣m,j⟩⟨m,j∣⊗Tr⁡Bn ⁣[(Fj⊗I)V⊗nρm(V⊗n)†],ΩE=Tr⁡m,jΩ.\left\|\Omega-\frac1M\sum_m|m,m\rangle\langle m,m|\otimes\Omega_E\right\|_1<\epsilon', \quad \Omega=\frac1M\sum_{m,j}|m,j\rangle\langle m,j| \otimes\operatorname{Tr}_{B^n}\!\left[(F_j\otimes I)V^{\otimes n}\rho_m(V^{\otimes n})^\dagger\right], \quad \Omega_E=\operatorname{Tr}_{m,j}\Omega .​Ω−M1​m∑​∣m,m⟩⟨m,m∣⊗ΩE​​1​<ϵ′,Ω=M1​m,j∑​∣m,j⟩⟨m,j∣⊗TrBn​[(Fj​⊗I)V⊗nρm​(V⊗n)†],ΩE​=Trm,j​Ω.

All channels in these definitions are finite Kraus sums with ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I, and density matrices are positive semidefinite with trace 111. If e=1e=1e=1 or ε=0\varepsilon=0ε=0, the conclusion is exactly Q(V)=Ic(V)Q(V)=I_c(V)Q(V)=Ic​(V) and P(V)=Ic(V)P(V)=I_c(V)P(V)=Ic​(V). Otherwise the conclusion is

∣Q(V)−Ic(V)∣≤−3ε3/2log⁡2ε+2ε3/2[1log⁡2+log⁡2e+12log⁡2(e−1)]+Cqε9/2,∣P(V)−Ic(V)∣≤−9ε3/2log⁡2ε+2ε3/2[3log⁡2+4log⁡2e+log⁡2(e−1)]+Cpε3.\begin{aligned} |Q(V)-I_c(V)| &\le-3\varepsilon^{3/2}\log_2\varepsilon +2\varepsilon^{3/2}\left[\frac1{\log2}+\log_2e+\frac12\log_2(e-1)\right] +C_q\varepsilon^{9/2},\\ |P(V)-I_c(V)| &\le-9\varepsilon^{3/2}\log_2\varepsilon +2\varepsilon^{3/2}\left[\frac3{\log2}+4\log_2e+\log_2(e-1)\right] +C_p\varepsilon^3 . \end{aligned}∣Q(V)−Ic​(V)∣∣P(V)−Ic​(V)∣​≤−3ε3/2log2​ε+2ε3/2[log21​+log2​e+21​log2​(e−1)]+Cq​ε9/2,≤−9ε3/2log2​ε+2ε3/2[log23​+4log2​e+log2​(e−1)]+Cp​ε3.​

Both error ranges include ε=0\varepsilon=0ε=0; only the capacity assertions use the smaller range [0,δ][0,\delta][0,δ]. The quantum code sequence includes n=0n=0n=0, with real division by zero interpreted as 000.

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me