Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Lemma 2 (PBT stretching), Eqs.(15)–(18)

Open
QAlgorithms.Papers.Independent.Intakethird100.P49.pbt_stretching

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

prove2quantum

Fix d≥2d\ge2d≥2, e,o≥1e,o\ge1e,o≥1, an integer M≥2M\ge2M≥2, and a fixed nnn-use adaptive protocol PPP with arbitrary finite memory, normalized initialization, CPTP interleavings and an explicit CPTP terminal map to an ooo-dimensional output. Its operations are independent of the unknown channel. There is one CPTP map ΛP,M\Lambda_{P,M}ΛP,M​, chosen before E\mathcal EE, such that for every CPTP E:d→e\mathcal E:d\to eE:d→e,

ρP(EM)=ΛP,M(ρE⊗nM),∥ρP(E)−ρP(EM)∥1≤n∥E−EM∥⋄≤nδd,M.\rho_P(\mathcal E^M)=\Lambda_{P,M}(\rho_{\mathcal E}^{\otimes nM}),\qquad\|\rho_P(\mathcal E)-\rho_P(\mathcal E^M)\|_1\le n\|\mathcal E-\mathcal E^M\|_\diamond\le n\delta_{d,M}.ρP​(EM)=ΛP,M​(ρE⊗nM​),∥ρP​(E)−ρP​(EM)∥1​≤n∥E−EM∥⋄​≤nδd,M​.

At n=0n=0n=0, the output is the channel-independent prepared and terminally processed state. For any actual two-party protocol initialized separably and consisting of dimension-changing trace-preserving LOCC interleaved with exactly nnn channel transmissions, the approximate stretched output can be produced by a trace-preserving LOCC on the grouped nMnMnM Choi resources, with full trace-norm error at most nδd,Mn\delta_{d,M}nδd,M​. This includes communication as well as general estimation and discrimination tasks.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P49
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakethird100.P49

open QAlgorithms Filter

open scoped Matrix ComplexConjugate ComplexOrder BigOperators

attribute [local instance] Classical.propDecidable Classical.decEq

open QAlgorithms.Papers.Independent.Information100.P63 (Mat tensorPower)

open QAlgorithms.Papers.Independent.Dependency50.P18 (bipartiteTensor)

open QAlgorithms.Papers.Independent.Information100.P71 (diamond AdaptiveTest adaptiveInput adaptiveAccept)

open QAlgorithms.Papers.Independent.Bridge50.P25
  (LOCCOn normalizedChannelChoi TwoWayGenerationCode TwoWayChannelProtocol
   generationCodeError twoWayGenerationCapacity sendChannelRegister StateFunctional
   IsDimensionChangingLOCCMonotone privateStateInPartyOrder)

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

/-- Lemma 2, PDF p.4, (15)--(18), Methods pp.8--9: common stretching map
for arbitrary tasks and every unknown channel. The additional two-party clause
uses separable preparation and actual finite dimension-changing LOCC execution. -/
theorem pbt_stretching (d e o n M : ℕ) [NeZero d] [NeZero e] [NeZero o]
    (hd : 2 ≤ d) (hM : 2 ≤ M) (P : AdaptiveProtocol d e o n) :
    (∃ L : Superop (Fin (n*M) → Fin d × Fin e) (Fin o), IsChannel L ∧
      ∀ E : Superop (Fin d) (Fin e), IsChannel E →
        adaptiveProtocolOutput P (simulated E M) = L (tensorPower (n*M) (normalizedChannelChoi E)) ∧
        traceNorm (adaptiveProtocolOutput P E - adaptiveProtocolOutput P (simulated E M)) ≤
          n * diamond (fun X => E X - simulated E M X) ∧
        n * diamond (fun X => E X - simulated E M X) ≤ n * pbtError d M) ∧
    (∀ (E : Superop (Fin d) (Fin e)), IsChannel E →
      ∀ (a b c f : ℕ), ∀ initial : Mat ((Fin (a+1) × Fin d) × Fin (b+1)),
        IsDensityMatrix initial → Entanglement.IsSeparableDensity initial →
        ∀ evolution : Superop ((Fin (a+1) × Fin d) × Fin (b+1))
          (Fin (c+1) × Fin (f+1)),
        TwoWayChannelProtocol E (Fin (c+1)) (Fin (f+1)) n a b evolution →
        ∃ L : Superop (Ports d (n*M) × Ports e (n*M)) (Fin (c+1) × Fin (f+1)),
          LOCCOn L ∧ IsChannel L ∧
          traceNorm (evolution initial - L (choiPorts E (n*M))) ≤ n * pbtError d M) := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P49

end
Source
Fundamental limits to quantum channel discrimination, arXiv:1803.02834v4, PDF p. 4, Lemma 2 (PBT stretching), Eqs.(15)–(18)
Read-back

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

For all natural numbers d,e,o,n,Md,e,o,n,Md,e,o,n,M, equipped with d,e,o≠0d,e,o\ne0d,e,o=0, with d≥2d\ge2d≥2 and M≥2M\ge2M≥2, fix an adaptive protocol PPP consisting of a positive memory dimension, an initial positive semidefinite trace-one matrix on memory and the ddd-dimensional input, a channel from memory and the eee-dimensional output back to memory and input for every natural-number step index, and two terminal channels to dimension ooo, one for zero uses and one for positive uses. Every channel here means a map with finitely many Kraus operators KjK_jKj​, acting by ∑jKjXKj†\sum_jK_jXK_j^\dagger∑j​Kj​XKj†​, with ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I. Write OP(E)\mathcal O_P(\mathcal E)OP​(E) for its output: for n=0n=0n=0 apply the zero-use terminal channel to the initial matrix; for n>0n>0n>0, apply E\mathcal EE to the input register nnn times, use the prescribed intervening channels after its first n−1n-1n−1 applications, and then apply the positive-use terminal channel. Define Φd=d−1∑x,y∣x,x⟩⟨y,y∣\Phi_d=d^{-1}\sum_{x,y}|x,x\rangle\langle y,y|Φd​=d−1∑x,y​∣x,x⟩⟨y,y∣, JE=(id⁡d⊗E)(Φd)J_{\mathcal E}=(\operatorname{id}_d\otimes\mathcal E)(\Phi_d)JE​=(idd​⊗E)(Φd​), and the port map Pd,M\mathcal P_{d,M}Pd,M​ as follows: its signal matrices are Si[(x,a),(y,b)]=d−11{x=ai, y=bi, aj=bj ∀j≠i}S_i[(x,a),(y,b)]=d^{-1}\mathbf1_{\{x=a_i,\ y=b_i,\ a_j=b_j\ \forall j\ne i\}}Si​[(x,a),(y,b)]=d−11{x=ai​, y=bi​, aj​=bj​ ∀j=i}​; with S=∑iSiS=\sum_iS_iS=∑i​Si​, R=f(S)R=f(S)R=f(S), f(t)=(t)−1f(t)=(\sqrt t)^{-1}f(t)=(t​)−1, f(0)=0f(0)=0f(0)=0, its effects are Qi=RSiR+M−1(I−RSR)Q_i=RS_iR+M^{-1}(I-RSR)Qi​=RSi​R+M−1(I−RSR); on X⊗Φd⊗MX\otimes\Phi_d^{\otimes M}X⊗Φd⊗M​, contract the input and first halves with QiQ_iQi​, trace out all second halves except iii, and sum over iii. Put E~M=E∘Pd,M\widetilde{\mathcal E}_M=\mathcal E\circ\mathcal P_{d,M}EM​=E∘Pd,M​, ϵd,M=Δd(id⁡−Pd,M)\epsilon_{d,M}=\Delta_d(\operatorname{id}-\mathcal P_{d,M})ϵd,M​=Δd​(id−Pd,M​), and Δd(F)=sup⁡∥X∥1≤1∥(id⁡d⊗F)(X)∥1\Delta_d(\mathcal F)=\sup_{\|X\|_1\le1}\|(\operatorname{id}_d\otimes\mathcal F)(X)\|_1Δd​(F)=sup∥X∥1​≤1​∥(idd​⊗F)(X)∥1​, where the supremum ranges over all matrices on two input registers and ∥X∥1=Re⁡tr⁡X†X\|X\|_1=\operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X}∥X∥1​=RetrX†X​. There exists a single channel L\mathcal LL, from nMnMnM registers of dimension dedede to dimension ooo, such that for every channel E:d→e\mathcal E:d\to eE:d→e,

OP(E~M)=L(JE⊗nM),∥OP(E)−OP(E~M)∥1≤nΔd(E−E~M)≤nϵd,M.\mathcal O_P(\widetilde{\mathcal E}_M) =\mathcal L(J_{\mathcal E}^{\otimes nM}), \qquad \|\mathcal O_P(\mathcal E)-\mathcal O_P(\widetilde{\mathcal E}_M)\|_1 \le n\Delta_d(\mathcal E-\widetilde{\mathcal E}_M) \le n\epsilon_{d,M}.OP​(EM​)=L(JE⊗nM​),∥OP​(E)−OP​(EM​)∥1​≤nΔd​(E−EM​)≤nϵd,M​.

In addition, for every such E\mathcal EE, all natural numbers a,b,c,fa,b,c,fa,b,c,f, every separable density matrix ρ\rhoρ on (Ca+1⊗Cd)⊗Cb+1(\mathbb C^{a+1}\otimes\mathbb C^d)\otimes\mathbb C^{b+1}(Ca+1⊗Cd)⊗Cb+1, and every evolution V\mathcal VV to dimensions c+1,f+1c+1,f+1c+1,f+1 having the specified nnn-use two-way form, there is a channel L′\mathcal L'L′ that is finite LOCC and satisfies

∥V(ρ)−L′(JE[nM])∥1≤nϵd,M.\|\mathcal V(\rho)-\mathcal L'(J_{\mathcal E}^{[nM]})\|_1 \le n\epsilon_{d,M}.∥V(ρ)−L′(JE[nM]​)∥1​≤nϵd,M​.

Here separability means a finite convex combination of tensor products of positive semidefinite trace-one local matrices; JE[nM]J_{\mathcal E}^{[nM]}JE[nM]​ is the same product of Choi entries with all ddd-registers grouped on one side and all eee-registers on the other. The specified two-way form has a finite LOCC terminal map at zero uses and, at each positive use, sends the designated input register through E\mathcal EE to the other party, applies a finite LOCC map to registers of the next prescribed dimensions, and continues recursively; finite LOCC itself is generated by identities and local complete finite Kraus measurements with outcome-dependent continuations. The natural number nnn may be zero, in which case the tensor product has zero factors, is the scalar matrix 111, and both displayed error bounds are zero.

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