Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§8, equation (20): a polynomial criterion for the formation–distillation gap

Open
QAlgorithms.Papers.Independent.Intakenext100.P60.pauli_gap_criterion

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

prove2quantum

Let p0,px,py,pz≥0p_0,p_x,p_y,p_z\ge0p0​,px​,py​,pz​≥0 sum to one, with

p0+pz−px−py≥∣p0+py−px−pz∣,p0+pz−px−py≥∣p0+px−py−pz∣.p_0+p_z-p_x-p_y\ge |p_0+p_y-p_x-p_z|,\qquad p_0+p_z-p_x-p_y\ge |p_0+p_x-p_y-p_z|.p0​+pz​−px​−py​≥∣p0​+py​−px​−pz​∣,p0​+pz​−px​−py​≥∣p0​+px​−py​−pz​∣.

In output:environment order on C2⊗C4\mathbb C^2\otimes\mathbb C^4C2⊗C4, put

u=p0∣00⟩+px∣1x⟩+ipy∣1y⟩+pz∣0z⟩,u=\sqrt{p_0}|00\rangle+\sqrt{p_x}|1x\rangle+i\sqrt{p_y}|1y\rangle+\sqrt{p_z}|0z\rangle,u=p0​​∣00⟩+px​​∣1x⟩+ipy​​∣1y⟩+pz​​∣0z⟩, v=p0∣10⟩+px∣0x⟩−ipy∣0y⟩−pz∣1z⟩.v=\sqrt{p_0}|10\rangle+\sqrt{p_x}|0x\rangle-i\sqrt{p_y}|0y\rangle-\sqrt{p_z}|1z\rangle.v=p0​​∣10⟩+px​​∣0x⟩−ipy​​∣0y⟩−pz​​∣1z⟩.

Write ρs=s∣u⟩⟨u∣+(1−s)∣v⟩⟨v∣\rho_s=s|u\rangle\langle u|+(1-s)|v\rangle\langle v|ρs​=s∣u⟩⟨u∣+(1−s)∣v⟩⟨v∣ for 0≤s≤10\le s\le10≤s≤1, ρT=ρ1/2\rho_T=\rho_{1/2}ρT​=ρ1/2​, and h=H2(p0+pz)h=H_2(p_0+p_z)h=H2​(p0​+pz​), where H2(t)=−tlog⁡2t−(1−t)log⁡2(1−t)H_2(t)=-t\log_2t-(1-t)\log_2(1-t)H2​(t)=−tlog2​t−(1−t)log2​(1−t) and 0log⁡20=00\log_2 0=00log2​0=0. Entanglement is measured across the two displayed parties.

Define

fp(z)=z4−z3+4(p0pxpy+p0pxpz+p0pypz+pxpypz)z−16p0pxpypz.f_p(z)=z^4-z^3+4(p_0p_xp_y+p_0p_xp_z+p_0p_yp_z+p_xp_yp_z)z-16p_0p_xp_yp_z.fp​(z)=z4−z3+4(p0​px​py​+p0​px​pz​+p0​py​pz​+px​py​pz​)z−16p0​px​py​pz​.

Writing Γ\GammaΓ for partial transpose on the output qubit and ∥⋅∥1\|\cdot\|_1∥⋅∥1​ for trace norm, the source's criterion is the equivalence

log⁡2∥ρTΓ∥1<Ec(ρT)⟺fp(−(2h−1)/2)>0.\log_2\|\rho_T^\Gamma\|_1<E_c(\rho_T)\quad\Longleftrightarrow\quad f_p(-(2^h-1)/2)>0.log2​∥ρTΓ​∥1​<Ec​(ρT​)⟺fp​(−(2h−1)/2)>0.

For every admissible distribution, ED(ρT)≤log⁡2∥ρTΓ∥1E_D(\rho_T)\le\log_2\|\rho_T^\Gamma\|_1ED​(ρT​)≤log2​∥ρTΓ​∥1​. Consequently, whenever the polynomial condition holds,

ED(ρT)≤log⁡2∥ρTΓ∥1<Ec(ρT).E_D(\rho_T)\le\log_2\|\rho_T^\Gamma\|_1<E_c(\rho_T).ED​(ρT​)≤log2​∥ρTΓ​∥1​<Ec​(ρT​).

The log-negativity bound is the cited input [34]. This criterion includes closed-simplex boundaries and does not assume the source's overbroad auxiliary negative-root claim.

Here EfE_fEf​ is the infimum of average pure-state marginal entropy over normalized finite decompositions of the stated density matrix. EcE_cEc​ is the asymptotic EPR preparation rate under deterministic two-way LOCC, and EDE_DED​ is the corresponding asymptotic distillation rate, in bits per copy. All entropies and logarithms are in bits.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P60
Formal statement
namespace QAlgorithms.Papers.Independent.Intakenext100.P60

open scoped Matrix ComplexConjugate ComplexOrder TensorProduct

noncomputable section

attribute [local instance] Classical.propDecidable Classical.decEq

-- Exact accepted matrix, normalized ensemble, convex roof, grouped copies and LOCC.

open QAlgorithms.Papers.Independent.Information100.P21 (Op FiniteLOCC)

open QAlgorithms.Papers.Independent.Information100.P08 (PureEnsemble pureAverage formation)

open QAlgorithms.Papers.Independent.Information100.P80 (groupedPower)

open QAlgorithms.Papers.Independent.Gap48.P32 (twoWayDistillable)

/-- PDF pp.14--15, (20): the polynomial condition is equivalent to the strict
log-negativity--cost inequality on the closed simplex. The upper bound on ordinary
distillation is credited to [34], and gives the strict gap when the condition holds.
No universal negative-root assertion is assumed, including at zero weights. -/
theorem pauli_gap_criterion (p : Fin 4 → ℝ) (hp : PauliAdmissible p) :
    (Real.logb 2 (traceNorm (Entanglement.partialTransposeFirst (pauliMixture p (1 / 2)))) <
      formationCostBits (pauliMixture p (1 / 2)) ↔ GapCriterion p) ∧
    twoWayDistillable (pauliMixture p (1 / 2)) ≤
      Real.logb 2 (traceNorm (Entanglement.partialTransposeFirst (pauliMixture p (1 / 2)))) ∧
    (GapCriterion p → twoWayDistillable (pauliMixture p (1 / 2)) <
      formationCostBits (pauliMixture p (1 / 2))) := by sorry

end

end QAlgorithms.Papers.Independent.Intakenext100.P60
Source
Remarks on additivity of the Holevo channel capacity and of the entanglement of formation, arXiv:quant-ph/0206148v4, PDF p. 14, §8, equation (20): a polynomial criterion for the formation–distillation gap
Read-back

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

Let p0,p1,p2,p3p_0,p_1,p_2,p_3p0​,p1​,p2​,p3​ be real numbers satisfying

pi≥0,∑i=03pi=1,∣p0+p2−p1−p3∣≤p0+p3−p1−p2,∣p0+p1−p2−p3∣≤p0+p3−p1−p2.p_i\ge0,\qquad \sum_{i=0}^3p_i=1,\qquad |p_0+p_2-p_1-p_3|\le p_0+p_3-p_1-p_2,\qquad |p_0+p_1-p_2-p_3|\le p_0+p_3-p_1-p_2.pi​≥0,i=0∑3​pi​=1,∣p0​+p2​−p1​−p3​∣≤p0​+p3​−p1​−p2​,∣p0​+p1​−p2​−p3​∣≤p0​+p3​−p1​−p2​.

On C2⊗C4\mathbb C^2\otimes\mathbb C^4C2⊗C4, with computational basis ∣i,j⟩|i,j\rangle∣i,j⟩, put

v0=p0∣0,0⟩+p1∣1,1⟩+ip2∣1,2⟩+p3∣0,3⟩,v1=p0∣1,0⟩+p1∣0,1⟩−ip2∣0,2⟩−p3∣1,3⟩,ρ=12∣v0⟩⟨v0∣+12∣v1⟩⟨v1∣.v_0=\sqrt{p_0}|0,0\rangle+\sqrt{p_1}|1,1\rangle +i\sqrt{p_2}|1,2\rangle+\sqrt{p_3}|0,3\rangle,\qquad v_1=\sqrt{p_0}|1,0\rangle+\sqrt{p_1}|0,1\rangle -i\sqrt{p_2}|0,2\rangle-\sqrt{p_3}|1,3\rangle, \qquad \rho=\tfrac12|v_0\rangle\langle v_0|+\tfrac12|v_1\rangle\langle v_1|.v0​=p0​​∣0,0⟩+p1​​∣1,1⟩+ip2​​∣1,2⟩+p3​​∣0,3⟩,v1​=p0​​∣1,0⟩+p1​​∣0,1⟩−ip2​​∣0,2⟩−p3​​∣1,3⟩,ρ=21​∣v0​⟩⟨v0​∣+21​∣v1​⟩⟨v1​∣.

For a bipartite matrix XXX, write X(i,j),(k,l)TA=X(k,j),(i,l)X^{T_A}_{(i,j),(k,l)}=X_{(k,j),(i,l)}X(i,j),(k,l)TA​​=X(k,j),(i,l)​, and write ∥X∥1=Re⁡Tr⁡X†X\|X\|_1=\operatorname{Re}\operatorname{Tr}\sqrt{X^\dagger X}∥X∥1​=ReTrX†X​. Let C(X)C(X)C(X) be the following formation cost: first relabel each local computational basis by the fixed equivalence with the initial segment of natural numbers of the same cardinality, and then take the real infimum of all real EEE such that, for every ε,δ>0\varepsilon,\delta>0ε,δ>0, there exist integers m≥0,n>0m\ge0,n>0m≥0,n>0 and a finite local protocol LLL satisfying

∣E−m/n∣≤δ,12∥L(Sm)−X[n]∥1≤ε.|E-m/n|\le\delta,\qquad \tfrac12\bigl\|L(S_m)-X^{[n]}\bigr\|_1\le\varepsilon.∣E−m/n∣≤δ,21​​L(Sm​)−X[n]​1​≤ε.

Here SmS_mSm​ is the mmm-fold tensor power of the projector onto (∣0,1⟩−∣1,0⟩)/2(|0,1\rangle-|1,0\rangle)/\sqrt2(∣0,1⟩−∣1,0⟩)/2​, X[n]X^{[n]}X[n] is the nnn-fold tensor power with the two parties grouped and relabelled by the fixed equivalences to dimensions an,bna^n,b^nan,bn, and a finite local protocol is recursively built from identity maps and local Kraus operations {Kj}\{K_j\}{Kj​} satisfying ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I, with an outcome-dependent finite continuation and the branch outputs summed. The case m=0m=0m=0 supplies the scalar state 111; the infimum defining CCC does not explicitly restrict EEE to be nonnegative. Let D(X)D(X)D(X) be the real supremum of all R≥0R\ge0R≥0 such that, for every ε,δ>0\varepsilon,\delta>0ε,δ>0, there is NNN such that every integer n≥Nn\ge Nn≥N with n>0n>0n>0 admits an integer l>0l>0l>0 and such a finite local protocol LLL with

n(R−δ)≤log⁡2l,∥L(X[n])−1l∑j,k=0l−1∣j,j⟩⟨k,k∣∥1≤ε.n(R-\delta)\le\log_2l,\qquad \left\|L(X^{[n]})-\frac1l\sum_{j,k=0}^{l-1}|j,j\rangle\langle k,k|\right\|_1\le\varepsilon.n(R−δ)≤log2​l,​L(X[n])−l1​j,k=0∑l−1​∣j,j⟩⟨k,k∣​1​≤ε.

Define H2(x)=binEntropy⁡(x)/log⁡2H_2(x)=\operatorname{binEntropy}(x)/\log2H2​(x)=binEntropy(x)/log2 and

gp(z)=z4−z3+4(p0p1p2+p0p1p3+p0p2p3+p1p2p3)z−16p0p1p2p3,zp=−2H2(p0+p3)−12.g_p(z)=z^4-z^3+ 4(p_0p_1p_2+p_0p_1p_3+p_0p_2p_3+p_1p_2p_3)z -16p_0p_1p_2p_3,\qquad z_p=-\frac{2^{H_2(p_0+p_3)}-1}{2}.gp​(z)=z4−z3+4(p0​p1​p2​+p0​p1​p3​+p0​p2​p3​+p1​p2​p3​)z−16p0​p1​p2​p3​,zp​=−22H2​(p0​+p3​)−1​.

The declaration asserts all three statements

(log⁡2∥ρTA∥1<C(ρ))  ⟺  gp(zp)>0,D(ρ)≤log⁡2∥ρTA∥1,gp(zp)>0 ⟹ D(ρ)<C(ρ).\bigl(\log_2\|\rho^{T_A}\|_1<C(\rho)\bigr) \iff g_p(z_p)>0,\qquad D(\rho)\le\log_2\|\rho^{T_A}\|_1,\qquad g_p(z_p)>0\ \Longrightarrow\ D(\rho)<C(\rho).(log2​∥ρTA​∥1​<C(ρ))⟺gp​(zp​)>0,D(ρ)≤log2​∥ρTA​∥1​,gp​(zp​)>0 ⟹ D(ρ)<C(ρ).

Zero entries of ppp are allowed.

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