Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A later block has positive coherent information

Open
QAlgorithms.Papers.Independent.Intakenext100.P70.positiveLaterBlock

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

prove2quantum

Let 0<p<10<p<10<p<1 and 0<κ<1/20<\kappa<1/20<κ<1/2. There exist positive integers N,m,rN,m,rN,m,r, an integer d≥2d\geq2d≥2, and a weight qqq that can be chosen with

q=13,r=2m+⌈log⁡2m⌉,d=2Nr.q=\frac13,\qquad r=2m+\lceil\log_2m\rceil,\qquad d=2Nr.q=31​,r=2m+⌈log2​m⌉,d=2Nr.

Construct Γ\GammaΓ from the normalized Choi state (S18), and M\mathcal MM from the measured, retained switch (S15), with whole-register erasure flags as defined on pp.5–6. These choices satisfy the PPT condition

0<q≤13,(dd−1)rN≤1−qq,0<q\leq\frac13,\qquad \left(\frac d{d-1}\right)^{rN}\leq\frac{1-q}{q},0<q≤31​,(d−1d​)rN≤q1−q​,

so Γ\GammaΓ is PPT-binding; M\mathcal MM is completely positive and trace preserving. They also give

Q(N+1)(M)>0,Q^{(N+1)}(\mathcal M)>0,Q(N+1)(M)>0,

where the rate divides the maximum coherent information over all joint density inputs by N+1N+1N+1 and is measured in bits.

This existential construction makes the finite-block obstruction compatible with positive capacity.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P70
Formal statement
namespace QAlgorithms.Papers.Independent.Intakenext100.P70

noncomputable section

open scoped Matrix ComplexConjugate ComplexOrder

attribute [local instance] Classical.propDecidable Classical.decEq

open QAlgorithms.Papers.Independent.Information100.P22
  (Op coherentInformation singleUseInformation quantumCapacity mixed)

/-- Supplementary Lemma 4, PDF pp.9--10: choose actual S18 parameters satisfying S19
and giving positive optimized coherent information at N+1 uses. The witness choices
q=1/3, d=2*N*r and integer r are the choices used by the proof. -/
theorem positiveLaterBlock (p kappa : ℝ) (hp0 : 0 < p) (hp1 : p < 1)
    (hk0 : 0 < kappa) (hk1 : kappa < 1 / 2) :
    ∃ P : CubittParameters, CubittValid P ∧ P.q = 1 / 3 ∧ P.r = cubittRepetitions P.m ∧
      P.d = 2 * P.N * P.r ∧ CubittPPTCondition P ∧ CubittPPTBinding (cubittGammaChannel P) ∧
      IsChannel (cubittPaperChannel P kappa p) ∧
      0 < cubittBlockInformation (cubittPaperChannel P kappa p) (P.N + 1) := by sorry

end

end QAlgorithms.Papers.Independent.Intakenext100.P70
Source
Unbounded number of channel uses are required to see quantum capacity, arXiv:1408.5115v1, PDF p. 9, Supplementary Lemma 4; parameter choice p.10
Read-back

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

For every pair of real numbers p,κp,\kappap,κ with 0<p<10<p<10<p<1 and 0<κ<1/20<\kappa<1/20<κ<1/2, there exist natural numbers N,r,m,dN,r,m,dN,r,m,d and a real number qqq such that

N>0,r>0,m>0,d≥2,0<q≤12,q=13,r=2m+⌈log⁡2m⌉,d=2Nr,N>0,\quad r>0,\quad m>0,\quad d\ge2,\quad 0<q\le\tfrac12,\quad q=\tfrac13,\quad r=2m+\lceil\log_2m\rceil,\quad d=2Nr,N>0,r>0,m>0,d≥2,0<q≤21​,q=31​,r=2m+⌈log2​m⌉,d=2Nr,

and

0<q≤13,(dd−1)rN≤1−qq=2.0<q\le\tfrac13, \qquad \left(\frac d{d-1}\right)^{rN}\le\frac{1-q}{q}=2.0<q≤31​,(d−1d​)rN≤q1−q​=2.

The maps asserted to have the properties below are defined as follows. Set A={0,…,d−1}{0,…,r−1}×{0,…,m−1}A=\{0,\ldots,d-1\}^{\{0,\ldots,r-1\}\times\{0,\ldots,m-1\}}A={0,…,d−1}{0,…,r−1}×{0,…,m−1}, H=A{0,…,N−1}H=A^{\{0,\ldots,N-1\}}H=A{0,…,N−1}, L=Bool×HL=\mathrm{Bool}\times HL=Bool×H, and D=∣L∣D=|L|D=∣L∣. On pairs of ddd-valued indices put

Sd(x,y)=1x=y+1x1=y2, x2=y1d(d+1),Td(x,y)=1x=y−1x1=y2, x2=y1d(d−1).S_d(x,y)=\frac{\mathbf1_{x=y}+\mathbf1_{x_1=y_2,\ x_2=y_1}}{d(d+1)}, \qquad T_d(x,y)=\frac{\mathbf1_{x=y}-\mathbf1_{x_1=y_2,\ x_2=y_1}}{d(d-1)}.Sd​(x,y)=d(d+1)1x=y​+1x1​=y2​, x2​=y1​​​,Td​(x,y)=d(d−1)1x=y​−1x1​=y2​, x2​=y1​​​.

For s,t,u,v∈Hs,t,u,v\in Hs,t,u,v∈H, define

Ωk(s,t;u,v)=∏i=0N−1∏j=0r−1Sd((sijk,tijk),(uijk,vijk))+Td((sijk,tijk),(uijk,vijk))2,Σk(s,t;u,v)=∏i=0N−1∏j=0r−1Sd((sijk,tijk),(uijk,vijk)).\Omega_k(s,t;u,v)=\prod_{i=0}^{N-1}\prod_{j=0}^{r-1} \frac{S_d((s_{ijk},t_{ijk}),(u_{ijk},v_{ijk})) +T_d((s_{ijk},t_{ijk}),(u_{ijk},v_{ijk}))}{2}, \quad \Sigma_k(s,t;u,v)=\prod_{i=0}^{N-1}\prod_{j=0}^{r-1} S_d((s_{ijk},t_{ijk}),(u_{ijk},v_{ijk})).Ωk​(s,t;u,v)=i=0∏N−1​j=0∏r−1​2Sd​((sijk​,tijk​),(uijk​,vijk​))+Td​((sijk​,tijk​),(uijk​,vijk​))​,Σk​(s,t;u,v)=i=0∏N−1​j=0∏r−1​Sd​((sijk​,tijk​),(uijk​,vijk​)).

Define ZZZ on L×LL\times LL×L, with row ((α,s),(β,t))((\alpha,s),(\beta,t))((α,s),(β,t)) and column ((γ,u),(δ,v))((\gamma,u),(\delta,v))((γ,u),(δ,v)), by

Z=12(qm+(1/2−q)m){∏k=0m−1q2(Ωk+Σk),α=β, γ=δ, α=γ,∏k=0m−1q2(Ωk−Σk),α=β, γ=δ, α≠γ,∏k=0m−1(1/2−q)Σk,α≠β, α=γ, β=δ,0,otherwise,Z=\frac{1}{2(q^m+(1/2-q)^m)} \begin{cases} \displaystyle\prod_{k=0}^{m-1}\frac q2(\Omega_k+\Sigma_k), &\alpha=\beta,\ \gamma=\delta,\ \alpha=\gamma,\\ \displaystyle\prod_{k=0}^{m-1}\frac q2(\Omega_k-\Sigma_k), &\alpha=\beta,\ \gamma=\delta,\ \alpha\ne\gamma,\\ \displaystyle\prod_{k=0}^{m-1}(1/2-q)\Sigma_k, &\alpha\ne\beta,\ \alpha=\gamma,\ \beta=\delta,\\ 0,&\text{otherwise}, \end{cases}Z=2(qm+(1/2−q)m)1​⎩⎨⎧​k=0∏m−1​2q​(Ωk​+Σk​),k=0∏m−1​2q​(Ωk​−Σk​),k=0∏m−1​(1/2−q)Σk​,0,​α=β, γ=δ, α=γ,α=β, γ=δ, α=γ,α=β, α=γ, β=δ,otherwise,​

where every factor uses (s,t;u,v)(s,t;u,v)(s,t;u,v), and put

Γ(X)b,c=D∑a,a′∈LXa,a′Z(a,b),(a′,c).\Gamma(X)_{b,c}=D\sum_{a,a'\in L}X_{a,a'}Z_{(a,b),(a',c)}.Γ(X)b,c​=Da,a′∈L∑​Xa,a′​Z(a,b),(a′,c)​.

For any real ttt, define Et(X)E_t(X)Et​(X) on Bool×L\mathrm{Bool}\times LBool×L to have false diagonal block (1−t)X(1-t)X(1−t)X, true diagonal block t tr⁡(X) 1/Dt\,\operatorname{tr}(X)\,1/Dttr(X)1/D, and zero off-diagonal blocks. Define Φ\PhiΦ on input Bool×L\mathrm{Bool}\times LBool×L by setting its off-diagonal switch blocks to zero, applying EpE_pEp​ to the true input block and Eκ∘ΓE_\kappa\circ\GammaEκ​∘Γ to the false input block, and retaining the switch label in the output Bool×(Bool×L)\mathrm{Bool}\times(\mathrm{Bool}\times L)Bool×(Bool×L). Then Γ\GammaΓ is a channel and its normalized Choi matrix has positive semidefinite output partial transpose: explicitly, Γ(X)=∑jKjXKj†\Gamma(X)=\sum_jK_jXK_j^\daggerΓ(X)=∑j​Kj​XKj†​ for a finite family satisfying ∑jKj†Kj=1\sum_jK_j^\dagger K_j=1∑j​Kj†​Kj​=1, and the matrix with entries

Γ(∣a⟩⟨c∣)e,bDat row (a,b), column (c,e)\frac{\Gamma(|a\rangle\langle c|)_{e,b}}{D} \quad\text{at row }(a,b),\text{ column }(c,e)DΓ(∣a⟩⟨c∣)e,b​​at row (a,b), column (c,e)

is positive semidefinite. The map Φ\PhiΦ is also a channel, meaning that it has a finite Kraus representation satisfying the same trace-preserving identity. Finally, for any map Ψ\PsiΨ, define

S(M)=−Re⁡tr⁡(cfc⁡(x↦xlog⁡2x)(M)),vρ(a,b)=(ρ)b,a,J(Ψ)=sup⁡ρ≥0, tr⁡ρ=1[S(Ψ(ρ))−S((id⁡⊗Ψ)(vρvρ†))].S(M)=-\operatorname{Re}\operatorname{tr} \bigl(\operatorname{cfc}(x\mapsto x\log_2x)(M)\bigr),\quad v_\rho(a,b)=(\sqrt{\rho})_{b,a},\quad J(\Psi)=\sup_{\rho\ge0,\ \operatorname{tr}\rho=1} \left[S(\Psi(\rho))- S\bigl((\operatorname{id}\otimes\Psi)(v_\rho v_\rho^\dagger)\bigr)\right].S(M)=−Retr(cfc(x↦xlog2​x)(M)),vρ​(a,b)=(ρ​)b,a​,J(Ψ)=ρ≥0, trρ=1sup​[S(Ψ(ρ))−S((id⊗Ψ)(vρ​vρ†​))].

The functional calculus defines the square root and entropy; the identity tensor map applies Ψ\PsiΨ blockwise on the second register, and Ψ⊗ℓ\Psi^{\otimes \ell}Ψ⊗ℓ applies Ψ\PsiΨ independently to all ℓ\ellℓ coordinates, as determined by expansion in matrix units. The asserted strict positivity is

0<J(Φ⊗(N+1))N+1.0<\frac{J(\Phi^{\otimes(N+1)})}{N+1}.0<N+1J(Φ⊗(N+1))​.
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