Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Proposition 5.1: redistribution converse outer bound

Open
QAlgorithms.Papers.Independent.Intakethird100.P42.redistributionOuterBound

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

prove2quantum

Let ∣ψ⟩RA^B^B|\psi\rangle^{R\widehat A\widehat B B}∣ψ⟩RABB be a normalized pure state on finite nonzero registers. Alice initially owns A^B^\widehat A\widehat BAB, Bob owns BBB, and RRR is inaccessible. A redistribution protocol transfers B^\widehat BB to Bob, leaves A^\widehat AA with Alice, and reconstructs the joint source/reference state and final Bell pairs with vanishing full trace-norm error. Only one-way qubit communication, Bell resources, and arbitrary local CPTP maps are allowed.

Every asymptotically achievable pair of qubit rate QQQ and signed net Bell consumption rate EEE satisfies

Q≥12I(B^;R∣A^)ψ,Q+E≥H(B^∣B)ψ.Q\ge\tfrac12 I(\widehat B;R\mid\widehat A)_\psi,\qquad Q+E\ge H(\widehat B\mid B)_\psi.Q≥21​I(B;R∣A)ψ​,Q+E≥H(B∣B)ψ​.

Rates use every positive error and rate slack and all sufficiently large positive IID blocklengths. All information quantities are in bits and are computed from this same pure source.

This is a converse outer bound. The conditional mutual information is stated with the printed conditioning register A^\widehat AA; pure-state entropy duality identifies it with conditioning on BBB.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P42
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakethird100.P42

open scoped BigOperators ComplexConjugate ENNReal

open Filter

open QAlgorithms.Papers.Independent.Dependency50.P07

open QAlgorithms.Papers.Independent.Gap48.P20

open QAlgorithms.Papers.Independent.Information100.P27 (IsProbability shannon)

attribute [local instance] Classical.decEq Classical.propDecidable

/-- PDF p.18, Proposition 5.1: converse only, with the source's conditioning
on Ahat and signed net Bell consumption. Alice retains Ahat and Bob retains B. -/
theorem redistributionOuterBound {A C B R : Type}
    [Fintype A] [Fintype C] [Fintype B] [Fintype R]
    [Nonempty A] [Nonempty C] [Nonempty B] [Nonempty R]
    (psi : EuclideanSpace ℂ (RedistributionSource A C B R)) (hpsi : IsState psi)
    (Q E : ℝ) (h : RedistributionAchievable psi Q E) :
    printedQuantumCost psi ≤ Q ∧ conditionalCost psi ≤ Q + E := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P42

end
Source
Channel simulation with quantum side information, arXiv:quant-ph/0611008v1, PDF p. 18, Proposition 5.1: redistribution converse outer bound
Read-back

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

Let A,C,B,RA,C,B,RA,C,B,R be nonempty finite types, let ψ∈CR×(A×(C×B))\psi\in\mathbb C^{R\times(A\times(C\times B))}ψ∈CR×(A×(C×B)) have norm 111, and let Q,E∈RQ,E\in\mathbb RQ,E∈R. Assume Q≥0Q\ge0Q≥0 and that, for every ε,δ>0\varepsilon,\delta>0ε,δ>0, there is a natural NNN such that for every n≥Nn\ge Nn≥N with n≥1n\ge1n≥1 there are natural numbers q,k,lq,k,lq,k,l and encoder and decoder channels with the following properties. The encoder takes AnCnA^nC^nAnCn and kkk qubits to AnA^nAn, lll qubits, and a qqq-qubit message; the decoder takes that message, BnB^nBn, and kkk qubits to CnBnC^nB^nCnBn and lll qubits. A channel here is a map X↦∑jKjXKj†X\mapsto\sum_jK_jXK_j^\daggerX↦∑j​Kj​XKj†​ for a finite Kraus family satisfying ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I. Starting with ψ⊗n\psi^{\otimes n}ψ⊗n and Φk=2−k/2∑z∈{0,1}k∣z,z⟩\Phi_k=2^{-k/2}\sum_{z\in\{0,1\}^k}|z,z\rangleΦk​=2−k/2∑z∈{0,1}k​∣z,z⟩, these channels, applied in that order with RnR^nRn unchanged, produce a matrix within trace norm ε\varepsilonε of the projector onto ψ⊗n⊗Φl\psi^{\otimes n}\otimes\Phi_lψ⊗n⊗Φl​, with AnA^nAn retained by the encoder and CnBnC^nB^nCnBn at the decoder, and satisfy q≤n(Q+δ)q\le n(Q+\delta)q≤n(Q+δ) and k−l≤n(E+δ)k-l\le n(E+\delta)k−l≤n(E+δ). The trace norm is ∥M∥1=Re⁡tr⁡M†M\|M\|_1=\operatorname{Re}\operatorname{tr}\sqrt{M^\dagger M}∥M∥1​=RetrM†M​, and q,k,lq,k,lq,k,l may be zero. Form ρuv=ψuψv‾\rho_{uv}=\psi_u\overline{\psi_v}ρuv​=ψu​ψv​​; for a register collection UUU, reduce by summing over equal complementary labels and define S(U)=−Re⁡tr⁡(f(ρU))S(U)=-\operatorname{Re}\operatorname{tr}(f(\rho_U))S(U)=−Retr(f(ρU​)), where f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t is applied by continuous functional calculus, with 0log⁡20=00\log_20=00log2​0=0. The conclusion is precisely

S(AC)+S(RA)−S(A)−S(RAC)2≤QandS(CB)−S(B)≤Q+E.\frac{S(AC)+S(RA)-S(A)-S(RAC)}2\le Q \quad\text{and}\quad S(CB)-S(B)\le Q+E.2S(AC)+S(RA)−S(A)−S(RAC)​≤QandS(CB)−S(B)≤Q+E.
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