Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Private-dit entanglement cost is at least the key size

Open
QAlgorithms.Papers.Independent.Gap48.P42.private_cost_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 ECE_CEC​ be operational entanglement cost in singlets per input copy, allowing trace-preserving adaptive LOCC, arbitrary local ancillary systems and vanishing preparation error. Then

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

The statement includes d=1d=1d=1. It uses the accepted operational cost, without assuming the formation lower bound for tensor powers or attainment of an optimal cost.

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 1a: operational singlet cost is at least log_2 d.
Uses the accepted Hayden--Horodecki--Terhal cost, not a prescribed scalar or
an assumed formation bound for tensor powers. The case d=1 is included. -/
theorem private_cost_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 ≤ Dependency50.P42.entanglementCost Dependency50.P42.paperBures
      (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 1a
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​ indexed by i∈Fin⁡(d)i\in\operatorname{Fin}(d)i∈Fin(d), form Γ\GammaΓ on local dimensions da,dbda,dbda,db by splitting local indices with the fixed bijections ℓd,a\ell_{d,a}ℓd,a​ and ℓd,b\ell_{d,b}ℓd,b​: its block between equal row keys iii on both parties and equal column keys jjj on both parties is d−1UiρUj†d^{-1}U_i\rho U_j^\daggerd−1Ui​ρUj†​, and all other key blocks vanish. Then log⁡2d≤CB(Γ)\log_2d\le C_B(\Gamma)log2​d≤CB​(Γ). Here CB(Γ)C_B(\Gamma)CB​(Γ) is the real infimum of all real numbers EEE such that, for every ε,δ>0\varepsilon,\delta>0ε,δ>0, there exist natural numbers m,nm,nm,n with n>0n>0n>0 and a finite local-operations map LLL from local dimensions 2m,2m2^m,2^m2m,2m to (da)n,(db)n(da)^n,(db)^n(da)n,(db)n satisfying ∣E−m/n∣≤δ|E-m/n|\le\delta∣E−m/n∣≤δ and B(L(Ψ−⊗m),Γ⊗n)≤εB(L(\Psi_-^{\otimes m}),\Gamma^{\otimes n})\le\varepsilonB(L(Ψ−⊗m​),Γ⊗n)≤ε. The state Ψ−=∣ψ−⟩⟨ψ−∣\Psi_-=|\psi_-\rangle\langle\psi_-|Ψ−​=∣ψ−​⟩⟨ψ−​∣ has ∣ψ−⟩=(∣01⟩−∣10⟩)/2|\psi_-\rangle=(|01\rangle-|10\rangle)/\sqrt2∣ψ−​⟩=(∣01⟩−∣10⟩)/2​, all tensor copies are grouped by party through the fixed cardinality bijections, and B(α,β)=21−Froot(α,β)B(\alpha,\beta)=2\sqrt{1-F_{\rm root}(\alpha,\beta)}B(α,β)=21−Froot​(α,β)​, where Froot(α,β)=Re⁡tr⁡α β αF_{\rm root}(\alpha,\beta)=\operatorname{Re}\operatorname{tr}\sqrt{\sqrt\alpha\,\beta\,\sqrt\alpha}Froot​(α,β)=Retrα​βα​​, with matrix square roots evaluated by continuous functional calculus and the real square root taken as a total function. The allowed maps are exactly those built by finitely many applications of identity maps and the recursion X↦∑jLj[(Aj⊗I)X(Aj⊗I)†]X\mapsto\sum_jL_j[(A_j\otimes I)X(A_j\otimes I)^\dagger]X↦∑j​Lj​[(Aj​⊗I)X(Aj​⊗I)†], where ∑jAj†Aj=I\sum_jA_j^\dagger A_j=I∑j​Aj†​Aj​=I and every LjL_jLj​ is itself allowed, or the corresponding recursion with I⊗AjI\otimes A_jI⊗Aj​ for the other party. Rectangular Kraus operators and branch-dependent continuations are allowed. The block sizes may depend on ε,δ\varepsilon,\deltaε,δ; the definition requires existence of a block and does not require a construction at every sufficiently large block size. Zero input singlets m=0m=0m=0 are allowed, giving a scalar input state, and d=1d=1d=1 gives the asserted 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