Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Private-dit entanglement of formation is at least the key size

Proved
QAlgorithms.Papers.Independent.Gap48.P42.private_formation_lower_bound

by Goku · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let d,a,bd,a,bd,a,b be positive integers, let ρ\rhoρ be a positive semidefinite trace-one shield state on Ca⊗Cb\mathbb C^a\otimes\mathbb C^bCa⊗Cb, and let each UiU_iUi​ be a unitary on that joint shield. Write

γ(d)=1d∑i,j=0d−1∣ii⟩⟨jj∣⊗UiρUj†,\gamma^{(d)}=\frac1d\sum_{i,j=0}^{d-1}|ii\rangle\langle jj|\otimes U_i\rho U_j^\dagger,γ(d)=d1​i,j=0∑d−1​∣ii⟩⟨jj∣⊗Ui​ρUj†​,

with the bipartition AA′:BB′AA':BB'AA′:BB′ and local shield dimensions a,ba,ba,b. All logarithms and resource rates are in bits.

Let EFE_FEF​ denote the convex roof of the entropy of the Alice marginal, over all finite normalized pure-state ensembles representing the input state. Then

EF(γ(d))≥log⁡2d.E_F(\gamma^{(d)})\ge\log_2d.EF​(γ(d))≥log2​d.

The case d=1d=1d=1 is included and gives the lower bound zero. This bounds the actual formation functional without an assumption that an optimal ensemble is supplied.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P42
Formal statement
namespace QAlgorithms.Papers.Independent.Gap48.P42

open scoped BigOperators Matrix ComplexConjugate ComplexOrder ENNReal

noncomputable section

attribute [local instance] Classical.propDecidable Classical.decEq

/-- PDF p.4, Property 1, Eq.(3.8): finite convex-roof formation across
AA' versus BB' is at least log_2 d, including d=1. -/
theorem private_formation_lower_bound {d a b : ℕ}
    (hd : 0 < d) (ha : 0 < a) (hb : 0 < b)
    (rho : Matrix (Fin a × Fin b) (Fin a × Fin b) ℂ) (hrho : IsDensityMatrix rho)
    (U : Fin d → Matrix.unitaryGroup (Fin a × Fin b) ℂ) :
    Real.logb 2 d ≤ Information100.P08.formation (bipartitePrivate rho U) := by sorry

end

end QAlgorithms.Papers.Independent.Gap48.P42
Source
Quantum states representing perfectly secure bits are always distillable, arXiv:quant-ph/0602176v2, PDF p. 4, III, Property 1 / Eq. (3.8)
Read-back

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

For all positive natural numbers d,a,bd,a,bd,a,b, every positive semidefinite trace-one matrix ρ\rhoρ on Ca⊗Cb\mathbb C^a\otimes\mathbb C^bCa⊗Cb, and every family of unitaries UiU_iUi​ on that space indexed by i∈Fin⁡(d)i\in\operatorname{Fin}(d)i∈Fin(d), define Γ\GammaΓ on local dimensions da,dbda,dbda,db as follows: use the fixed bijections ℓd,a:Fin⁡(d)×Fin⁡(a)≃Fin⁡(da)\ell_{d,a}:\operatorname{Fin}(d)\times\operatorname{Fin}(a)\simeq\operatorname{Fin}(da)ℓd,a​:Fin(d)×Fin(a)≃Fin(da) and ℓd,b\ell_{d,b}ℓd,b​ to split each local index into a key and a shield index; then

Γ(ℓd,a(i,x), ℓd,b(j,y)), (ℓd,a(i′,x′), ℓd,b(j′,y′))={d−1(UiρUi′†)(x,y),(x′,y′),i=j, i′=j′,0,otherwise.\Gamma_{(\ell_{d,a}(i,x),\,\ell_{d,b}(j,y)),\, (\ell_{d,a}(i',x'),\,\ell_{d,b}(j',y'))} = \begin{cases} d^{-1}(U_i\rho U_{i'}^\dagger)_{(x,y),(x',y')},&i=j,\ i'=j',\\ 0,&\text{otherwise}. \end{cases}Γ(ℓd,a​(i,x),ℓd,b​(j,y)),(ℓd,a​(i′,x′),ℓd,b​(j′,y′))​={d−1(Ui​ρUi′†​)(x,y),(x′,y′)​,0,​i=j, i′=j′,otherwise.​

The assertion is log⁡2d≤EF(Γ)\log_2d\le E_F(\Gamma)log2​d≤EF​(Γ), where EF(Γ)E_F(\Gamma)EF​(Γ) is the real infimum of ∑ν<qpνS(Tr⁡B∣vν⟩⟨vν∣)\sum_{\nu<q}p_\nu S(\operatorname{Tr}_B|v_\nu\rangle\langle v_\nu|)∑ν<q​pν​S(TrB​∣vν​⟩⟨vν​∣) over every natural ensemble size qqq, nonnegative real weights pνp_\nupν​ summing to 111, and unit vectors vν∈Cda⊗Cdbv_\nu\in\mathbb C^{da}\otimes\mathbb C^{db}vν​∈Cda⊗Cdb satisfying Γ=∑ν<qpν∣vν⟩⟨vν∣\Gamma=\sum_{\nu<q}p_\nu|v_\nu\rangle\langle v_\nu|Γ=∑ν<q​pν​∣vν​⟩⟨vν​∣. Here (∣v⟩⟨v∣)x,y=vxvy‾(|v\rangle\langle v|)_{x,y}=v_x\overline{v_y}(∣v⟩⟨v∣)x,y​=vx​vy​​, (Tr⁡BX)x,x′=∑yX(x,y),(x′,y)(\operatorname{Tr}_B X)_{x,x'}=\sum_yX_{(x,y),(x',y)}(TrB​X)x,x′​=∑y​X(x,y),(x′,y)​, and S(σ)=−Re⁡tr⁡f(σ)S(\sigma)=-\operatorname{Re}\operatorname{tr}f(\sigma)S(σ)=−Retrf(σ) for f(x)=xlog⁡2xf(x)=x\log_2xf(x)=xlog2​x, evaluated by continuous functional calculus with the total real logarithm. Zero ensemble weights are allowed; ensemble size zero is among the quantified natural numbers but cannot satisfy the weight-sum condition. The parameters d,a,bd,a,bd,a,b may equal 111, so d=1d=1d=1 gives the lower bound 000.

Human review
  • Endorsed by Shuze Chen · Oct 22, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 22, 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