Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Equation (5): flagged coherent information and achievable concatenated-cat rate

Open
QAlgorithms.Papers.Independent.Intakenext100.P93.cat_flagged_rate

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

prove2quantum

Let px,py,pz≥0p_x,p_y,p_z\ge0px​,py​,pz​≥0 with sum at most one, and fix the positive cat length m=k+1m=k+1m=k+1. Encode half of the normalized Bell state Φ+=∣ϕ+⟩⟨ϕ+∣\Phi^+=|\phi^+\rangle\langle\phi^+|Φ+=∣ϕ+⟩⟨ϕ+∣, apply the independent physical Pauli channel, decode, and measure and retain the complete syndrome. Denote this actual instrument output by ωABS\omega_{ABS}ωABS​, the syndrome mass by P(s)=∑u,vJ(u,v,s)P(s)=\sum_{u,v}J(u,v,s)P(s)=∑u,v​J(u,v,s), and its conditional logical channel by Ns\mathcal N^sNs. Each conditional channel is the Pauli mixture with weights J(u,v,s)/P(s)J(u,v,s)/P(s)J(u,v,s)/P(s) when P(s)>0P(s)>0P(s)>0; at zero mass choose the identity. The output is a density matrix and

ωABS=∑sP(s)(id⁡⊗Ns)(Φ+)⊗∣s⟩⟨s∣,\omega_{ABS}=\sum_s P(s)(\operatorname{id}\otimes\mathcal N^s)(\Phi^+)\otimes|s\rangle\langle s|,ωABS​=s∑​P(s)(id⊗Ns)(Φ+)⊗∣s⟩⟨s∣, Rm=Ic(ωABS)m=1m∑sP(s)Ic((id⁡⊗Ns)(Φ+))=1+H(S)−H(U,V,S)m.R_m=\frac{I^c(\omega_{ABS})}{m} =\frac1m\sum_sP(s)I^c((\operatorname{id}\otimes\mathcal N^s)(\Phi^+)) =\frac{1+H(S)-H(U,V,S)}m.Rm​=mIc(ωABS​)​=m1​s∑​P(s)Ic((id⊗Ns)(Φ+))=m1+H(S)−H(U,V,S)​.

Here Ic(ρAB)=S(ρB)−S(ρAB)I^c(\rho_{AB})=S(\rho_B)-S(\rho_{AB})Ic(ρAB​)=S(ρB​)−S(ρAB​), the receiver includes the syndrome, and every entropy uses base two. If Rm≥0R_m\ge0Rm​≥0, this rate is achievable by this fixed cat inner encoder concatenated with outer additive stabilizer encoders: for every fidelity error ϵ>0\epsilon>0ϵ>0 and rate slack δ>0\delta>0δ>0, every sufficiently large positive outer length nnn admits an encoder for l≥(Rm−δ)mnl\ge(R_m-\delta)mnl≥(Rm​−δ)mn logical qubits and a CPTP decoder with entanglement fidelity and every normalized pure-input transmission fidelity at least 1−ϵ1-\epsilon1−ϵ.

The operational assertion supplies high-fidelity unassisted quantum communication, rather than only an entropic number. Negative values remain signed expressions. At m=1m=1m=1 the expression is the Bell-input hashing yield, without input optimization.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P93
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P93

open QAlgorithms

open scoped BigOperators ComplexConjugate Matrix

attribute [local instance] Classical.propDecidable Classical.decEq

/-- Smith--Smolin, PDF p.2, Eq.(5): actual flagged output, Pauli conditional
channels, coherent-information identity and operational random-stabilizer
concatenation rate. A negative signed expression is not an operational rate. -/
theorem cat_flagged_rate (k : ℕ) (px py pz : ℝ)
    (hx : 0 ≤ px) (hy : 0 ≤ py) (hz : 0 ≤ pz) (hsum : px + py + pz ≤ 1) :
    IsDensityMatrix (catInstrumentOutput k px py pz) ∧
    (∀ s : Qubits k, IsChannel (conditionalChannel k px py pz s) ∧
      ∀ rho : Matrix Bool Bool ℂ,
        conditionalChannel k px py pz s rho =
          ∑ u : Bool, ∑ v : Bool,
            ((if iidCatSyndromeMass k px py pz s = 0 then
              (if u = false ∧ v = false then 1 else 0)
            else catLogicalSyndromeMass k px py pz u v s / iidCatSyndromeMass k px py pz s : ℝ) : ℂ) •
              conjSuperop ((Stabilizer.pauliOfBits u v).mat) rho) ∧
    (∀ x y : Bool × (Bool × Qubits k), catInstrumentOutput k px py pz x y =
      if x.2.2 = y.2.2 then
        (iidCatSyndromeMass k px py pz x.2.2 : ℂ) *
          idTensorSuperop (R := Bool) (conditionalChannel k px py pz x.2.2)
            (pureDensity catBellInput) (x.1, x.2.1) (y.1, y.2.1)
      else 0) ∧
    catRate k px py pz =
      (∑ s : Qubits k, iidCatSyndromeMass k px py pz s *
        (let rho := idTensorSuperop (R := Bool) (conditionalChannel k px py pz s)
          (pureDensity catBellInput)
         vnEntropy (traceLeft rho) - vnEntropy rho)) / (k + 1 : ℕ) ∧
    catRate k px py pz =
      (1 + QAlgorithms.Papers.Independent.Support50.P40.finiteEntropyBits (iidCatSyndromeMass k px py pz) -
        QAlgorithms.Papers.Independent.Support50.P40.finiteEntropyBits (fun z : Bool × Bool × Qubits k =>
          catLogicalSyndromeMass k px py pz z.1 z.2.1 z.2.2)) / (k + 1 : ℕ) ∧
    (0 ≤ catRate k px py pz → CatAchievable k px py pz (catRate k px py pz)) := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P93

end
Source
Degenerate Quantum Codes for Pauli Channels, arXiv:quant-ph/0604107v2, PDF p. 2, Equation (5): flagged coherent information and achievable concatenated-cat rate
Read-back

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

For every natural number kkk, including 000, and nonnegative real numbers px,py,pzp_x,p_y,p_zpx​,py​,pz​ with px+py+pz≤1p_x+p_y+p_z\le1px​+py​+pz​≤1, write Br={0,1}r\mathcal B_r=\{0,1\}^rBr​={0,1}r. For x,z∈Bk+1x,z\in\mathcal B_{k+1}x,z∈Bk+1​, let w(x,z)=∏iw1(xi,zi)w(x,z)=\prod_iw_1(x_i,z_i)w(x,z)=∏i​w1​(xi​,zi​), where w1(0,0)=1−px−py−pzw_1(0,0)=1-p_x-p_y-p_zw1​(0,0)=1−px​−py​−pz​, w1(1,0)=pxw_1(1,0)=p_xw1​(1,0)=px​, w1(1,1)=pyw_1(1,1)=p_yw1​(1,1)=py​, and w1(0,1)=pzw_1(0,1)=p_zw1​(0,1)=pz​. Set σ(x)j=x0⊕xj+1\sigma(x)_j=x_0\oplus x_{j+1}σ(x)j​=x0​⊕xj+1​, let J(u,v,s)J(u,v,s)J(u,v,s) be the sum of w(x,z)w(x,z)w(x,z) over x0=ux_0=ux0​=u, ⨁izi=v\bigoplus_i z_i=v⨁i​zi​=v, σ(x)=s\sigma(x)=sσ(x)=s, and put Ps=∑u,vJ(u,v,s)P_s=\sum_{u,v}J(u,v,s)Ps​=∑u,v​J(u,v,s). Define Px,z∣y⟩=(−1)∑iziyi∣y⊕x⟩P_{x,z}|y\rangle=(-1)^{\sum_i z_i y_i}|y\oplus x\ranglePx,z​∣y⟩=(−1)∑i​zi​yi​∣y⊕x⟩, N(ρ)=∑x,zw(x,z)Px,zρPx,z†\mathcal N(\rho)=\sum_{x,z}w(x,z)P_{x,z}\rho P_{x,z}^\daggerN(ρ)=∑x,z​w(x,z)Px,z​ρPx,z†​, the repetition encoder C(y,b)=1{yi=b for all i}C(y,b)=\mathbf1_{\{y_i=b\text{ for all }i\}}C(y,b)=1{yi​=b for all i}​, and the decoder branch Bs(b,y)=1{y0=b, σ(y)=s}B_s(b,y)=\mathbf1_{\{y_0=b,\ \sigma(y)=s\}}Bs​(b,y)=1{y0​=b, σ(y)=s}​. Let Bs(ρ)=BsN(CρC†)Bs†\mathcal B_s(\rho)=B_s\mathcal N(C\rho C^\dagger)B_s^\daggerBs​(ρ)=Bs​N(CρC†)Bs†​, and define Cs=id⁡\mathcal C_s=\operatorname{id}Cs​=id if Ps=0P_s=0Ps​=0, and Cs=Ps−1Bs\mathcal C_s=P_s^{-1}\mathcal B_sCs​=Ps−1​Bs​ otherwise. With ∣Φ⟩=(∣00⟩+∣11⟩)/2|\Phi\rangle=(|00\rangle+|11\rangle)/\sqrt2∣Φ⟩=(∣00⟩+∣11⟩)/2​, let Ω\OmegaΩ, indexed by (r,b,s)∈{0,1}×({0,1}×Bk)(r,b,s)\in\{0,1\}\times(\{0,1\}\times\mathcal B_k)(r,b,s)∈{0,1}×({0,1}×Bk​), have zero entries between distinct syndrome blocks and block sss equal to (id⁡⊗Bs)(∣Φ⟩⟨Φ∣)(\operatorname{id}\otimes\mathcal B_s)(|\Phi\rangle\langle\Phi|)(id⊗Bs​)(∣Φ⟩⟨Φ∣). Write S(X)=−Re⁡Tr⁡[f(X)]S(X)=-\operatorname{Re}\operatorname{Tr}[f(X)]S(X)=−ReTr[f(X)], where f(x)=xlog⁡2xf(x)=x\log_2xf(x)=xlog2​x is applied by continuous functional calculus with the total real logarithm, and H(q)=−∑jqjlog⁡2qjH(q)=-\sum_jq_j\log_2q_jH(q)=−∑j​qj​log2​qj​, so zero terms contribute 000. Define R=[S(Tr⁡rΩ)−S(Ω)]/(k+1)R=[S(\operatorname{Tr}_r\Omega)-S(\Omega)]/(k+1)R=[S(Trr​Ω)−S(Ω)]/(k+1). The theorem asserts that Ω\OmegaΩ is positive semidefinite with trace 111; that every Cs\mathcal C_sCs​ is a channel, meaning it has a finite Kraus representation with Kraus matrices KjK_jKj​ satisfying ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I; and that, for every sss and every complex 2×22\times22×2 matrix ρ\rhoρ,

Cs(ρ)=∑u,v∈{0,1}qs(u,v)AuvρAuv†,qs(u,v)={1{u=0, v=0},Ps=0,J(u,v,s)/Ps,Ps≠0,\mathcal C_s(\rho)=\sum_{u,v\in\{0,1\}}q_s(u,v)A_{uv}\rho A_{uv}^\dagger, \quad q_s(u,v)= \begin{cases} \mathbf1_{\{u=0,\ v=0\}},&P_s=0,\\ J(u,v,s)/P_s,&P_s\ne0, \end{cases}Cs​(ρ)=u,v∈{0,1}∑​qs​(u,v)Auv​ρAuv†​,qs​(u,v)={1{u=0, v=0}​,J(u,v,s)/Ps​,​Ps​=0,Ps​=0,​

where A00=I,A10=X,A11=Y,A01=ZA_{00}=I,A_{10}=X,A_{11}=Y,A_{01}=ZA00​=I,A10​=X,A11​=Y,A01​=Z, with X=(0110)X=\left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right)X=(01​10​), Y=(0−ii0)Y=\left(\begin{smallmatrix}0&-\mathrm i\\\mathrm i&0\end{smallmatrix}\right)Y=(0i​−i0​), and Z=(100−1)Z=\left(\begin{smallmatrix}1&0\\0&-1\end{smallmatrix}\right)Z=(10​0−1​). It further asserts, for all Boolean r,b,r′,b′r,b,r',b'r,b,r′,b′ and all s,s′s,s's,s′,

Ω(r,b,s),(r′,b′,s′)={Ps ωs((r,b),(r′,b′)),s=s′,0,s≠s′,ωs=(id⁡⊗Cs)(∣Φ⟩⟨Φ∣),\Omega_{(r,b,s),(r',b',s')}= \begin{cases} P_s\,\omega_s((r,b),(r',b')),&s=s',\\ 0,&s\ne s', \end{cases} \quad \omega_s=(\operatorname{id}\otimes\mathcal C_s)(|\Phi\rangle\langle\Phi|),Ω(r,b,s),(r′,b′,s′)​={Ps​ωs​((r,b),(r′,b′)),0,​s=s′,s=s′,​ωs​=(id⊗Cs​)(∣Φ⟩⟨Φ∣),

and the two rate identities

R=∑sPs [S(Tr⁡rωs)−S(ωs)]k+1=1+H((Ps)s)−H((J(u,v,s))u,v,s)k+1.R=\frac{\sum_sP_s\,[S(\operatorname{Tr}_r\omega_s)-S(\omega_s)]}{k+1} =\frac{1+H((P_s)_s)-H((J(u,v,s))_{u,v,s})}{k+1}.R=k+1∑s​Ps​[S(Trr​ωs​)−S(ωs​)]​=k+11+H((Ps​)s​)−H((J(u,v,s))u,v,s​)​.

Finally, if R≥0R\ge0R≥0, then for every ϵ>0\epsilon>0ϵ>0 and δ>0\delta>0δ>0 there exists an integer n0≥1n_0\ge1n0​≥1 such that for every n≥n0n\ge n_0n≥n0​ there are a natural number ℓ\ellℓ, an encoder matrix E:CBℓ→CBnE:\mathbb C^{\mathcal B_\ell}\to\mathbb C^{\mathcal B_n}E:CBℓ​→CBn​, and a channel DDD from nnn blocks of k+1k+1k+1 qubits to ℓ\ellℓ qubits, satisfying (R−δ)(k+1)n≤ℓ(R-\delta)(k+1)n\le\ell(R−δ)(k+1)n≤ℓ. The encoder satisfies ℓ≤n\ell\le nℓ≤n, E†E=IE^\dagger E=IE†E=I, and its range is the common fixed space of a commuting subgroup of the unitary group generated by matrices ic⨂jAj\mathrm i^c\bigotimes_jA_jic⨂j​Aj​, where c∈{0,1,2,3}c\in\{0,1,2,3\}c∈{0,1,2,3} and Aj∈{I,X,Y,Z}A_j\in\{I,X,Y,Z\}Aj​∈{I,X,Y,Z}, with that subgroup containing no −I-I−I. If C(n)(y,x)=∏j<nC(yj,xj)C^{(n)}(y,x)=\prod_{j<n}C(y_j,x_j)C(n)(y,x)=∏j<n​C(yj​,xj​) and

T=D∘N⊗n∘(ρ↦C(n)ρC(n)†)∘(ρ↦EρE†),\mathcal T=D\circ\mathcal N^{\otimes n}\circ (\rho\mapsto C^{(n)}\rho C^{(n)\dagger})\circ(\rho\mapsto E\rho E^\dagger),T=D∘N⊗n∘(ρ↦C(n)ρC(n)†)∘(ρ↦EρE†),

then both ⟨Φℓ∣(id⁡⊗T)(∣Φℓ⟩⟨Φℓ∣)∣Φℓ⟩≥1−ϵ\langle\Phi_\ell|(\operatorname{id}\otimes\mathcal T)(|\Phi_\ell\rangle\langle\Phi_\ell|)|\Phi_\ell\rangle\ge1-\epsilon⟨Φℓ​∣(id⊗T)(∣Φℓ​⟩⟨Φℓ​∣)∣Φℓ​⟩≥1−ϵ, where ∣Φℓ⟩=2−ℓ/2∑x∈Bℓ∣x,x⟩|\Phi_\ell\rangle=2^{-\ell/2}\sum_{x\in\mathcal B_\ell}|x,x\rangle∣Φℓ​⟩=2−ℓ/2∑x∈Bℓ​​∣x,x⟩, and Re⁡Tr⁡[∣ψ⟩⟨ψ∣T(∣ψ⟩⟨ψ∣)]≥1−ϵ\operatorname{Re}\operatorname{Tr}[|\psi\rangle\langle\psi|\mathcal T(|\psi\rangle\langle\psi|)]\ge1-\epsilonReTr[∣ψ⟩⟨ψ∣T(∣ψ⟩⟨ψ∣)]≥1−ϵ for every unit vector ψ∈CBℓ\psi\in\mathbb C^{\mathcal B_\ell}ψ∈CBℓ​. Zero-mass syndrome branches are included through the identity-map convention, and the achievability implication includes R=0R=0R=0 and ℓ=0\ell=0ℓ=0.

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