Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Section V, Eq. (16): multipartite total erasure and successive local decorrelation

Open
QAlgorithms.Papers.Independent.Intakenext100.P47.multipartite_totalErasure

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

prove2quantum

Let p≥1p\ge1p≥1 and let ρA1⋯Ap\rho_{A_1\cdots A_p}ρA1​⋯Ap​​ be a density matrix with finite positive local dimensions did_idi​. Define multipartite erasure rates by minimizing finite ensembles of product unitaries whose output on nnn independent copies is within full trace norm ϵ\epsilonϵ of a normalized fully product state, dividing by n≥1n\ge1n≥1, taking lim inf⁡\liminfliminf or lim sup⁡\limsuplimsup, and then taking the supremum over ϵ>0\epsilon>0ϵ>0. Feasible finite costs are nonempty, bounded below, and attain their minima; normalized sequences and outer error suprema are bounded. For coordinated or independent local randomness and each of the costs log⁡2N,H(p),Se\log_2N,H(p),S_elog2​N,H(p),Se​,

Cer(ρ)=∑i=1pS(ρAi)−S(ρ)=∑j=1p−1I(Aj:Aj+1⋯Ap)ρ.C_{\rm er}(\rho)=\sum_{i=1}^p S(\rho_{A_i})-S(\rho)=\sum_{j=1}^{p-1}I(A_j:A_{j+1}\cdots A_p)_\rho.Cer​(ρ)=i=1∑p​S(ρAi​​)−S(ρ)=j=1∑p−1​I(Aj​:Aj+1​⋯Ap​)ρ​.

Moreover, for every ϵ>0\epsilon>0ϵ>0, eventually every nnn admits exactly p−1p-1p−1 successive uniform local randomizations RjR_jRj​, with stage jjj acting only on party jjj, such that

log⁡2Nj≤n(I(Aj:Aj+1⋯Ap)ρ+ϵ/p),∑jlog⁡2Nj≤n(Cer(ρ)+ϵ),\log_2N_j\le n\bigl(I(A_j:A_{j+1}\cdots A_p)_\rho+\epsilon/p\bigr),\quad\sum_j\log_2N_j\le n(C_{\rm er}(\rho)+\epsilon),log2​Nj​≤n(I(Aj​:Aj+1​⋯Ap​)ρ​+ϵ/p),j∑​log2​Nj​≤n(Cer​(ρ)+ϵ),

and the composed output is within trace norm ϵ\epsilonϵ of a fully product state. The tail information quantities are computed from actual compatible marginals of the original state. For p=1p=1p=1 the protocol is empty and the rate is zero. This states both Eq. (16) and its successive local protocol.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P47
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P47

open QAlgorithms Filter

open QAlgorithms.Papers.Independent.Gap48.P20 (Copies localProduct)

open QAlgorithms.Papers.Independent.Dependency50.P19 (mutualInformation first)

open QAlgorithms.Papers.Independent.Dependency50.P45 (entropyExchange)

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

open QAlgorithms.Papers.Independent.Information100.P71 (channelPower)

open QAlgorithms.Papers.Independent.Advance50.P05 (RectangularInstrument)

open scoped Matrix ComplexConjugate

attribute [local instance] Classical.propDecidable Classical.decEq

/-- PDF pp.9--10, (16) and the protocol paragraph: total erasure and successive local decorrelation.
All three costs, both block limits, and independent/coordinated randomness have the same rate.
Only p-1 stages are used. The p=1 boundary is the empty protocol, of zero cost. -/
theorem multipartite_totalErasure {p : ℕ} (hp : 0 < p) (d : Fin p → ℕ)
    (hd : ∀ i, 0 < d i)
    (rho : Matrix (Config d) (Config d) ℂ)
    (hrho : IsDensityMatrix rho) :
    (∀ eps > (0 : ℝ), ∀ independent cost,
      (∀ n, 0 < n → (multiCosts rho n eps independent cost).Nonempty ∧
        BddBelow (multiCosts rho n eps independent cost) ∧
        sInf (multiCosts rho n eps independent cost) ∈ multiCosts rho n eps independent cost) ∧
      BddBelow (Set.range (multiBlockRate rho eps independent cost)) ∧
      BddAbove (Set.range (multiBlockRate rho eps independent cost))) ∧
    (∀ independent cost pessimistic,
      BddAbove {v | ∃ eps > (0 : ℝ),
        v = rateLimit pessimistic (multiBlockRate rho eps independent cost)} ∧
      multiErasure rho independent cost pessimistic = multiInformation rho) ∧
    (∑ j, tailInformation rho j) = multiInformation rho ∧
    (∀ eps > (0 : ℝ), ∃ n0 : ℕ, 0 < n0 ∧ ∀ n ≥ n0,
      ∃ R : Fin (p-1) → MultiNoise (MultiCopies d n),
        (∀ j t i, i.val ≠ j.val → (R j).unitary t i = 1) ∧
        (∀ j t, (R j).weight t = ((R j).count : ℝ)⁻¹) ∧
        (∀ j, Real.logb 2 (R j).count ≤
          (n : ℝ) * (tailInformation rho j + eps / p)) ∧
        (∑ j, Real.logb 2 (R j).count) ≤ (n : ℝ) * (multiInformation rho + eps) ∧
        MultiDecorrelates (successiveBlockOutput R (multiSourcePower rho n)) eps) := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P47

end
Source
On the quantum, classical and total amount of correlations in a quantum state, arXiv:quant-ph/0410091v2, PDF p. 10, Section V, Eq. (16): multipartite total erasure and successive local decorrelation
Read-back

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

Let p>0p>0p>0 be a natural number, let di>0d_i>0di​>0 be natural dimensions for i=0,…,p−1i=0,\ldots,p-1i=0,…,p−1, and let ρ\rhoρ be a positive semidefinite matrix of complex trace 111 on X=∏i{0,…,di−1}\mathcal X=\prod_i\{0,\ldots,d_i-1\}X=∏i​{0,…,di​−1}. Write S(X)=−Re⁡tr⁡(cfc⁡[x↦xlog⁡2x](X))S(X)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[x\mapsto x\log_2x](X))S(X)=−Retr(cfc[x↦xlog2​x](X)) and ∥X∥1=Re⁡tr⁡(cfc⁡[⋅](X†X))\|X\|_1=\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[\sqrt{\cdot}](X^\dagger X))∥X∥1​=Retr(cfc[⋅​](X†X)). For a subset JJJ of parties, define (ρJ)uv=∑ρxy(\rho_J)_{uv}=\sum\rho_{xy}(ρJ​)uv​=∑ρxy​, summing over full configurations restricting to u,vu,vu,v on JJJ and agreeing outside JJJ, and put

I(ρ)=∑i=0p−1S(ρ{i})−S(ρ),Tj(ρ)=S(ρ{j})+S(ρ{i:i>j})−S(ρ{i:i≥j})(0≤j<p−1).I(\rho)=\sum_{i=0}^{p-1}S(\rho_{\{i\}})-S(\rho), \qquad T_j(\rho)=S(\rho_{\{j\}})+S(\rho_{\{i:i>j\}})-S(\rho_{\{i:i\ge j\}}) \quad(0\le j<p-1).I(ρ)=i=0∑p−1​S(ρ{i}​)−S(ρ),Tj​(ρ)=S(ρ{j}​)+S(ρ{i:i>j}​)−S(ρ{i:i≥j}​)(0≤j<p−1).

For block length nnn, give party iii the space Hi={0,…,di−1}{0,…,n−1}\mathcal H_i=\{0,\ldots,d_i-1\}^{\{0,\ldots,n-1\}}Hi​={0,…,di​−1}{0,…,n−1} and set (ρ[n])xy=∏t<nρ(xi(t))i,(yi(t))i(\rho^{[n]})_{xy}=\prod_{t<n}\rho_{(x_i(t))_i,(y_i(t))_i}(ρ[n])xy​=∏t<n​ρ(xi​(t))i​,(yi​(t))i​​. A noise choice RRR has a positive count NRN_RNR​, weights wa≥0w_a\ge0wa​≥0 summing to 111, and local unitaries Ua,iU_{a,i}Ua,i​, giving ΦR(X)=∑awaVaXVa†\Phi_R(X)=\sum_aw_aV_aXV_a^\daggerΦR​(X)=∑a​wa​Va​XVa†​ with Va=⨂iUa,iV_a=\bigotimes_iU_{a,i}Va​=⨂i​Ua,i​. For a Boolean bbb and cost kind ccc, let Cn(ε,b,c)\mathcal C_n(\varepsilon,b,c)Cn​(ε,b,c) be the real costs of such choices satisfying ∥ΦR(ρ[n])−⨂iσi∥1≤ε\|\Phi_R(\rho^{[n]})-\bigotimes_i\sigma_i\|_1\le\varepsilon∥ΦR​(ρ[n])−⨂i​σi​∥1​≤ε for some positive semidefinite trace-one σi\sigma_iσi​; if b=trueb=\mathrm{true}b=true, additionally require a bijection from the global choice set to a product of positive-sized local choice sets, product probability weights, and each party’s unitary depending only on its local choice, while b=falseb=\mathrm{false}b=false adds no restriction. The three costs are log⁡2NR\log_2N_Rlog2​NR​, −∑awalog⁡2wa-\sum_aw_a\log_2w_a−∑a​wa​log2​wa​, and S((id⁡⊗ΦR)(∣ψρ[n]⟩⟨ψρ[n]∣))S((\operatorname{id}\otimes\Phi_R)(|\psi_{\rho^{[n]}}\rangle\langle\psi_{\rho^{[n]}}|))S((id⊗ΦR​)(∣ψρ[n]​⟩⟨ψρ[n]​∣)), respectively for size, entropy, and exchange, where ψX\psi_XψX​ has the transposed entries of the formal square root of XXX in the finite enumeration used by the definition. Set ak(ε,b,c)=inf⁡Ck+1(ε,b,c)/(k+1)a_k(\varepsilon,b,c)=\inf\mathcal C_{k+1}(\varepsilon,b,c)/(k+1)ak​(ε,b,c)=infCk+1​(ε,b,c)/(k+1), and let Lh(a)L_h(a)Lh​(a) mean its real lim sup⁡\limsuplimsup when h=trueh=\mathrm{true}h=true and real lim inf⁡\liminfliminf when h=falseh=\mathrm{false}h=false. The theorem asserts all of the following conjunctions: for every ε>0\varepsilon>0ε>0, every Boolean bbb, and every cost kind ccc, each Cn(ε,b,c)\mathcal C_n(\varepsilon,b,c)Cn​(ε,b,c) with n>0n>0n>0 is nonempty and bounded below and contains its real infimum, and the range of k↦ak(ε,b,c)k\mapsto a_k(\varepsilon,b,c)k↦ak​(ε,b,c) is bounded both below and above; for every b,c,hb,c,hb,c,h, the set {Lh(a(ε,b,c)):ε>0}\{L_h(a(\varepsilon,b,c)):\varepsilon>0\}{Lh​(a(ε,b,c)):ε>0} is bounded above and its real supremum equals I(ρ)I(\rho)I(ρ); and

∑j=0p−2Tj(ρ)=I(ρ).\sum_{j=0}^{p-2}T_j(\rho)=I(\rho).j=0∑p−2​Tj​(ρ)=I(ρ).

Moreover, for every ε>0\varepsilon>0ε>0, there exists a positive natural n0n_0n0​ such that for every n≥n0n\ge n_0n≥n0​ there are noise choices RjR_jRj​, 0≤j<p−10\le j<p-10≤j<p−1, whose local unitary is the identity at every party i≠ji\ne ji=j, whose every weight equals 1/NRj1/N_{R_j}1/NRj​​, and which satisfy

log⁡2NRj≤n ⁣(Tj(ρ)+εp)for every j,∑j=0p−2log⁡2NRj≤n(I(ρ)+ε).\log_2N_{R_j}\le n\!\left(T_j(\rho)+\frac{\varepsilon}{p}\right) \quad\text{for every }j, \qquad \sum_{j=0}^{p-2}\log_2N_{R_j}\le n\bigl(I(\rho)+\varepsilon\bigr).log2​NRj​​≤n(Tj​(ρ)+pε​)for every j,j=0∑p−2​log2​NRj​​≤n(I(ρ)+ε).

Applying ΦR0,ΦR1,…,ΦRp−2\Phi_{R_0},\Phi_{R_1},\ldots,\Phi_{R_{p-2}}ΦR0​​,ΦR1​​,…,ΦRp−2​​ successively in that order to ρ[n]\rho^{[n]}ρ[n] produces an output within trace norm ε\varepsilonε of a product of local positive semidefinite trace-one matrices. The case p=1p=1p=1 is included: the tail-index family, both sums over jjj, and the list of successive operations are empty.

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