Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corrected fixed-pair and optimized multipartite GHZ bounds

Open
QAlgorithms.Papers.Independent.Gap48.P42.multipartite_private_rate

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

prove2quantum

Let there be N≥2N\ge2N≥2 parties, a key dimension d≥2d\ge2d≥2, and positive finite local shield dimensions s1,…,sNs_1,\ldots,s_Ns1​,…,sN​. Let ρ\rhoρ be any positive semidefinite trace-one operator on the joint shield, and let U0,…,Ud−1U_0,\ldots,U_{d-1}U0​,…,Ud−1​ be arbitrary unitaries on that whole shield. Party kkk owns its key and shield registers. The exact private state is

Γ=1d∑i,j=0d−1∣i,…,i⟩⟨j,…,j∣⊗UiρUj†.\Gamma=\frac1d\sum_{i,j=0}^{d-1}|i,\ldots,i\rangle\langle j,\ldots,j|\otimes U_i\rho U_j^\dagger.Γ=d1​i,j=0∑d−1​∣i,…,i⟩⟨j,…,j∣⊗Ui​ρUj†​.

For every ordered pair i<ji<ji<j, let ηij\eta_{ij}ηij​ be the maximum of ∣⟨f∣UiρUj†∣g⟩∣|\langle f|U_i\rho U_j^\dagger|g\rangle|∣⟨f∣Ui​ρUj†​∣g⟩∣ over product vectors whose every local factor has norm one. All these maxima are attained. For any choice of maximizing vectors (fij,gij)(f^{ij},g^{ij})(fij,gij) for every pair, compute

aij=⟨fij∣UiρUi†∣fij⟩,bij=⟨gij∣UjρUj†∣gij⟩.a_{ij}=\langle f^{ij}|U_i\rho U_i^\dagger|f^{ij}\rangle,\qquad b_{ij}=\langle g^{ij}|U_j\rho U_j^\dagger|g^{ij}\rangle.aij​=⟨fij∣Ui​ρUi†​∣fij⟩,bij​=⟨gij∣Uj​ρUj†​∣gij⟩.

They satisfy aij,bij,ηij>0a_{ij},b_{ij},\eta_{ij}>0aij​,bij​,ηij​>0 and ηij≤aijbij\eta_{ij}\le\sqrt{a_{ij}b_{ij}}ηij​≤aij​bij​​. The balanced local success operators are contractions and yield exactly the unnormalized mixture qij[pijΦ+ij+(1−pij)Φ−ij]q_{ij}[p_{ij}\Phi^{ij}_++(1-p_{ij})\Phi^{ij}_-]qij​[pij​Φ+ij​+(1−pij​)Φ−ij​], of trace qijq_{ij}qij​, where Φ±ij\Phi^{ij}_\pmΦ±ij​ project onto (∣i,…,i⟩±∣j,…,j⟩)/2(|i,\ldots,i\rangle\pm|j,\ldots,j\rangle)/\sqrt2(∣i,…,i⟩±∣j,…,j⟩)/2​. Set

qij=2min⁡(aij,bij)d,pij=12+ηij2aijbij,Rij=qij[1−H2(pij)].q_{ij}=\frac{2\min(a_{ij},b_{ij})}{d},\qquad p_{ij}=\frac12+\frac{\eta_{ij}}{2\sqrt{a_{ij}b_{ij}}},\qquad R_{ij}=q_{ij}[1-H_2(p_{ij})].qij​=d2min(aij​,bij​)​,pij​=21​+2aij​bij​​ηij​​,Rij​=qij​[1−H2​(pij​)].

Then 0<qij≤10<q_{ij}\le10<qij​≤1, 1/2<pij≤11/2<p_{ij}\le11/2<pij​≤1, and both the fixed-pair and optimized bounds hold:

0<Rij≤ED(Γ)(i<j),0<max⁡i<jRij≤ED(Γ).0<R_{ij}\le E_D(\Gamma)\quad(i<j),\qquad 0<\max_{i<j}R_{ij}\le E_D(\Gamma).0<Rij​≤ED​(Γ)(i<j),0<i<jmax​Rij​≤ED​(Γ).

Here H2H_2H2​ is binary entropy in bits, and EDE_DED​ is the unconditional asymptotic vanishing-error GHZ rate per input copy under adaptive trace-preserving LOCC. The finite maximum retains the optimization over key pairs.

Source corrections. The printed rate uses amax⁡ija_{\max}^{ij}amaxij​ and omits a factor two in the entropy argument. The two equal unnormalized diagonal entries are min⁡(aij,bij)/d\min(a_{ij},b_{ij})/dmin(aij​,bij​)/d, fixing both corrections. The mixture formula (2.6) itself already contains the correct outer 1/21/21/2.

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.3, Eq.(2.6) and fixed-pair/optimized bounds, note [11] p.5.
Source correction: printed a_max is replaced by 2 min(a_1,a_2)/d, and
printed 1/2+eta/sqrt(a_1*a_2) by 1/2+eta/(2 sqrt(a_1*a_2)). The computed
success output has both diagonal entries min(a_1,a_2)/d, forcing these changes.
The complete fixed-pair conclusions and finite maximum are retained. -/
theorem multipartite_private_rate {N d : ℕ} (hN : 2 ≤ N) (hd : 2 ≤ d)
    (S : Fin N → ℕ) (hS : ∀ k, 0 < S k)
    (rho : Matrix (PartyBasis S) (PartyBasis S) ℂ) (hrho : IsDensityMatrix rho)
    (U : Fin d → Matrix.unitaryGroup (PartyBasis S) ℂ) :
    (∀ p : KeyPair d, ∃ f g : ProductVectors S,
      Maximizes (shieldBlock rho U p.val.1 p.val.2) f g) ∧
    ∀ v : KeyPair d → ProductVectors S × ProductVectors S,
      (∀ p, Maximizes (shieldBlock rho U p.val.1 p.val.2) (v p).1 (v p).2) →
      (∀ p, PairConclusion rho U p.val.1 p.val.2 (v p).1 (v p).2) ∧
      0 < bestPairYield rho U v ∧
      ENNReal.ofReal (bestPairYield rho U v) ≤
        distillableGHZ (fun k => d * S k) (indexedPrivateDit 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. 3, II.B, Eqs. (2.5)–(2.6) and following bounds
Read-back

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

For every pair of natural numbers N,dN,dN,d with N≥2N\ge2N≥2 and d≥2d\ge2d≥2, every family of positive integers SkS_kSk​ indexed by k∈Fin⁡(N)k\in\operatorname{Fin}(N)k∈Fin(N), every positive semidefinite trace-one matrix ρ\rhoρ on H=⨂kCSk\mathcal H=\bigotimes_k\mathbb C^{S_k}H=⨂k​CSk​, and every family of unitaries UiU_iUi​ on H\mathcal HH, indexed by i∈Fin⁡(d)i\in\operatorname{Fin}(d)i∈Fin(d), put Xij=UiρUj†X_{ij}=U_i\rho U_j^\daggerXij​=Ui​ρUj†​ and ηij=sup⁡∣⟨⨂kfk,Xij⨂kgk⟩∣\eta_{ij}=\sup|\langle\bigotimes_k f_k,X_{ij}\bigotimes_k g_k\rangle|ηij​=sup∣⟨⨂k​fk​,Xij​⨂k​gk​⟩∣, where the supremum ranges over all families with ∥fk∥=∥gk∥=1\|f_k\|=\|g_k\|=1∥fk​∥=∥gk​∥=1. For each ordered index pair i<ji<ji<j, unit factor families attaining ηij\eta_{ij}ηij​ exist. Moreover, for every simultaneous choice (fij,gij)(f^{ij},g^{ij})(fij,gij) of such maximizing families for every i<ji<ji<j, the following conclusions hold for every pair. Set cij=⟨⨂kfkij,Xij⨂kgkij⟩c_{ij}=\langle\bigotimes_k f_k^{ij},X_{ij}\bigotimes_k g_k^{ij}\ranglecij​=⟨⨂k​fkij​,Xij​⨂k​gkij​⟩, aij=Re⁡⟨⨂kfkij,Xii⨂kfkij⟩a_{ij}=\operatorname{Re}\langle\bigotimes_k f_k^{ij},X_{ii}\bigotimes_k f_k^{ij}\rangleaij​=Re⟨⨂k​fkij​,Xii​⨂k​fkij​⟩, bij=Re⁡⟨⨂kgkij,Xjj⨂kgkij⟩b_{ij}=\operatorname{Re}\langle\bigotimes_k g_k^{ij},X_{jj}\bigotimes_k g_k^{ij}\ranglebij​=Re⟨⨂k​gkij​,Xjj​⨂k​gkij​⟩, qij=2min⁡(aij,bij)/dq_{ij}=2\min(a_{ij},b_{ij})/dqij​=2min(aij​,bij​)/d, pij=12+ηij/(2aijbij)p_{ij}=\frac12+\eta_{ij}/(2\sqrt{a_{ij}b_{ij}})pij​=21​+ηij​/(2aij​bij​​), and Yij=qij[1−h2(pij)]Y_{ij}=q_{ij}[1-h_2(p_{ij})]Yij​=qij​[1−h2​(pij​)], where h2(x)=binEntropy⁡(x)/log⁡2h_2(x)=\operatorname{binEntropy}(x)/\log2h2​(x)=binEntropy(x)/log2. Then ηij,aij,bij,qij,Yij>0\eta_{ij},a_{ij},b_{ij},q_{ij},Y_{ij}>0ηij​,aij​,bij​,qij​,Yij​>0, ηij≤aijbij\eta_{ij}\le\sqrt{a_{ij}b_{ij}}ηij​≤aij​bij​​, qij≤1q_{ij}\le1qij​≤1, and 12<pij≤1\frac12<p_{ij}\le121​<pij​≤1. Using the fixed bijections ℓd,Sk:Fin⁡(d)×Fin⁡(Sk)≃Fin⁡(dSk)\ell_{d,S_k}:\operatorname{Fin}(d)\times\operatorname{Fin}(S_k)\simeq\operatorname{Fin}(dS_k)ℓd,Sk​​:Fin(d)×Fin(Sk​)≃Fin(dSk​), define the matrix Γ\GammaΓ whose block between the constant key strings iNi^NiN and jNj^NjN is Xij/dX_{ij}/dXij​/d, with all blocks involving nonconstant key strings zero. For the chosen pair, define Kk=∣i⟩⟨i,fkij∣+∣j⟩⟨j,gkij∣K_k=|i\rangle\langle i,f_k^{ij}|+|j\rangle\langle j,g_k^{ij}|Kk​=∣i⟩⟨i,fkij​∣+∣j⟩⟨j,gkij​∣ for k≠0k\ne0k=0, and K0=min⁡(aij,bij)/aij ∣i⟩⟨i,f0ij∣+min⁡(aij,bij)/bij (cij/∣cij∣) ∣j⟩⟨j,g0ij∣K_0=\sqrt{\min(a_{ij},b_{ij})/a_{ij}}\,|i\rangle\langle i,f_0^{ij}|+\sqrt{\min(a_{ij},b_{ij})/b_{ij}}\,(c_{ij}/|c_{ij}|)\,|j\rangle\langle j,g_0^{ij}|K0​=min(aij​,bij​)/aij​​∣i⟩⟨i,f0ij​∣+min(aij​,bij​)/bij​​(cij​/∣cij​∣)∣j⟩⟨j,g0ij​∣. Every I−Kk†KkI-K_k^\dagger K_kI−Kk†​Kk​ is positive semidefinite, and K=⨂kKkK=\bigotimes_kK_kK=⨂k​Kk​ satisfies KΓK†=qij[pij∣ψ+⟩⟨ψ+∣+(1−pij)∣ψ−⟩⟨ψ−∣]K\Gamma K^\dagger=q_{ij}[p_{ij}|\psi_+\rangle\langle\psi_+|+(1-p_{ij})|\psi_-\rangle\langle\psi_-|]KΓK†=qij​[pij​∣ψ+​⟩⟨ψ+​∣+(1−pij​)∣ψ−​⟩⟨ψ−​∣], with trace qijq_{ij}qij​, where ∣ψ±⟩=(∣i⟩⊗N±∣j⟩⊗N)/2|\psi_\pm\rangle=(|i\rangle^{\otimes N}\pm|j\rangle^{\otimes N})/\sqrt2∣ψ±​⟩=(∣i⟩⊗N±∣j⟩⊗N)/2​. Each ofReal⁡(Yij)\operatorname{ofReal}(Y_{ij})ofReal(Yij​) is at most D(Γ)\mathcal D(\Gamma)D(Γ); additionally Y∗=sup⁡i<jYijY_*=\sup_{i<j}Y_{ij}Y∗​=supi<j​Yij​ is strictly positive and ofReal⁡(Y∗)≤D(Γ)\operatorname{ofReal}(Y_*)\le\mathcal D(\Gamma)ofReal(Y∗​)≤D(Γ). Here D(Γ)∈[0,∞]\mathcal D(\Gamma)\in[0,\infty]D(Γ)∈[0,∞] is the supremum of ofReal⁡(r)\operatorname{ofReal}(r)ofReal(r), with ofReal⁡(r)=max⁡(r,0)\operatorname{ofReal}(r)=\max(r,0)ofReal(r)=max(r,0), over nonnegative rates rrr for which every ε,δ>0\varepsilon,\delta>0ε,δ>0 admits a threshold after which every positive integer nnn has an integer m≥0m\ge0m≥0 and a deterministically obtainable density matrix σ\sigmaσ satisfying ∥σ−(∣GHZN,+⟩⟨GHZN,+∣)⊗m∥1≤ε\|\sigma-(|\mathrm{GHZ}_{N,+}\rangle\langle\mathrm{GHZ}_{N,+}|)^{\otimes m}\|_1\le\varepsilon∥σ−(∣GHZN,+​⟩⟨GHZN,+​∣)⊗m∥1​≤ε and r−δ≤m/nr-\delta\le m/nr−δ≤m/n, where ∣GHZN,+⟩=(∣0⟩⊗N+∣1⟩⊗N)/2|\mathrm{GHZ}_{N,+}\rangle=(|0\rangle^{\otimes N}+|1\rangle^{\otimes N})/\sqrt2∣GHZN,+​⟩=(∣0⟩⊗N+∣1⟩⊗N)/2​ and copies are grouped by party using fixed cardinality bijections. The trace norm is ∥Z∥1=Re⁡tr⁡Z†Z\|Z\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Z^\dagger Z}∥Z∥1​=RetrZ†Z​. Deterministic obtainability means that a finite adaptive tree ends in the list [(1,σ)][(1,\sigma)][(1,σ)]: a node applies one party’s finite Kraus instrument, with nonnegative probabilities summing to 111, normalized output states obeying pjρj=∑zA~jzρA~jz†p_j\rho_j=\sum_z\widetilde A_{jz}\rho\widetilde A_{jz}^\daggerpj​ρj​=∑z​Ajz​ρAjz†​, and global completeness ∑j,zA~jz†A~jz=I\sum_{j,z}\widetilde A_{jz}^\dagger\widetilde A_{jz}=I∑j,z​Ajz†​Ajz​=I, followed by branch-dependent trees; output ensembles of identical local dimensions may also be replaced by their weighted sum. Every state in such a tree has positive local dimensions. The index-pair set is nonempty because d≥2d\ge2d≥2; shield dimensions equal to 111 and zero extracted copies m=0m=0m=0 are included.

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