Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition III.2: randomness compression for an exactly disentangling block

Open
QAlgorithms.Papers.Independent.Intakenext100.P47.disentangling_compression

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

prove2quantum

Let ρAB\rho_{AB}ρAB​ be a density matrix on finite nonzero spaces and let k≥1k\ge1k≥1. Fix a coordinated local product-unitary map TTT on kkk copies such that the constructed output σ=T(ρ⊗k)\sigma=T(\rho^{\otimes k})σ=T(ρ⊗k) is separable. For every ϵ>0\epsilon>0ϵ>0 there exists n0≥1n_0\ge1n0​≥1 such that for every n≥n0n\ge n_0n≥n0​ a uniform coordinated product-unitary ensemble RRR on knknkn copies, with NNN terms, satisfies

∥R(ρ⊗kn)−σ⊗n∥1≤ϵ,log⁡2N≤n(S(σ)−kS(ρ)+ϵ).\|R(\rho^{\otimes kn})-\sigma^{\otimes n}\|_1\le\epsilon,\qquad\log_2N\le n\bigl(S(\sigma)-kS(\rho)+\epsilon\bigr).∥R(ρ⊗kn)−σ⊗n∥1​≤ϵ,log2​N≤n(S(σ)−kS(ρ)+ϵ).

Tensor copies of σ\sigmaσ are explicitly regrouped in the same party order as the knknkn-copy input. In particular, RRR ϵ\epsilonϵ-disentangles this input. This compresses the randomness needed to reproduce an exactly disentangling block asymptotically.

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.6--7, Proposition III.2: the input contains k*n copies, not n copies. -/
theorem disentangling_compression {A B : Type} [Fintype A] [Fintype B]
    [Nonempty A] [Nonempty B] (rho : Matrix (A × B) (A × B) ℂ)
    (hrho : IsDensityMatrix rho) (k : ℕ) (hk : 0 < k)
    (T : COLUR (Copies A k) (Copies B k))
    (hT : Entanglement.IsSeparableDensity (T.operation (sourcePower rho k)))
    (eps : ℝ) (heps : 0 < eps) :
    ∃ n0 : ℕ, 0 < n0 ∧ ∀ n ≥ n0,
      ∃ R : COLUR (Copies A (k*n)) (Copies B (k*n)),
        (∀ i, R.weight i = (R.count : ℝ)⁻¹) ∧
        traceNorm (R.operation (sourcePower rho (k*n)) -
          (Matrix.of fun (x y : Copies A (k*n) × Copies B (k*n)) => ∏ t : Fin n,
            T.operation (sourcePower rho k)
              ((fun s => x.1 (blockIndex t s)),
                (fun s => x.2 (blockIndex t s)))
              ((fun s => y.1 (blockIndex t s)),
                (fun s => y.2 (blockIndex t s))))) ≤ eps ∧
        Disentangles (R.operation (sourcePower rho (k*n))) eps ∧
        Real.logb 2 R.count ≤ (n : ℝ) *
          (vnEntropy (T.operation (sourcePower rho k)) - k * vnEntropy rho + 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. 6, Proposition III.2: randomness compression for an exactly disentangling block
Read-back

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

For any finite nonempty types A,BA,BA,B, density matrix ρ\rhoρ on A×BA\times BA×B, positive integer kkk, and operation T\mathcal TT on Ak×BkA^k\times B^kAk×Bk that is a finite mixture of paired local unitary conjugations with nonnegative weights summing to 111, assume that ω=T(ρk)\omega=\mathcal T(\rho_k)ω=T(ρk​) is a separable density matrix, meaning a finite convex combination of products of local density matrices. Here (ρj)(a,b),(a′,b′)=∏t=0j−1ρ(at,bt),(at′,bt′)(\rho_j)_{(a,b),(a',b')}=\prod_{t=0}^{j-1}\rho_{(a_t,b_t),(a'_t,b'_t)}(ρj​)(a,b),(a′,b′)​=∏t=0j−1​ρ(at​,bt​),(at′​,bt′​)​. For every real ε>0\varepsilon>0ε>0, there exists a positive integer n0n_0n0​ such that, for every natural number n≥n0n\ge n_0n≥n0​, there exists an operation R\mathcal RR on Akn×BknA^{kn}\times B^{kn}Akn×Bkn with a positive finite number rrr of paired local unitary conjugations, all of whose weights equal 1/r1/r1/r, such that

∥R(ρkn)−Ωn∥1≤ε,(Ωn)(a,b),(a′,b′)=∏t=0n−1ω((akt+s)s<k,(bkt+s)s<k), ((akt+s′)s<k,(bkt+s′)s<k).\|\mathcal R(\rho_{kn})-\Omega_n\|_1\le\varepsilon, \qquad (\Omega_n)_{(a,b),(a',b')} =\prod_{t=0}^{n-1} \omega_{((a_{kt+s})_{s<k},(b_{kt+s})_{s<k}),\, ((a'_{kt+s})_{s<k},(b'_{kt+s})_{s<k})}.∥R(ρkn​)−Ωn​∥1​≤ε,(Ωn​)(a,b),(a′,b′)​=t=0∏n−1​ω((akt+s​)s<k​,(bkt+s​)s<k​),((akt+s′​)s<k​,(bkt+s′​)s<k​)​.

Its output is also within trace norm ε\varepsilonε of some separable density matrix, and

log⁡2r≤n(H(ω)−kH(ρ)+ε).\log_2r\le n\bigl(H(\omega)-kH(\rho)+\varepsilon\bigr).log2​r≤n(H(ω)−kH(ρ)+ε).

Here ∥M∥1=Re⁡Tr⁡M†M\|M\|_1=\operatorname{Re}\operatorname{Tr}\sqrt{M^\dagger M}∥M∥1​=ReTrM†M​ and H(X)=−Re⁡Tr⁡[x↦xlog⁡2x](X)H(X)=-\operatorname{Re}\operatorname{Tr}[x\mapsto x\log_2x](X)H(X)=−ReTr[x↦xlog2​x](X). Both kkk and the asserted block counts nnn are positive.

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