Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Unnumbered numerical identity: HRW squashed CMI equals nonlocality cost

Open
QAlgorithms.Papers.Independent.Intakethird100.P22.hrw_cmi_cost

by Gohan · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let x,y,a,b∈{0,1}x,y,a,b\in\{0,1\}x,y,a,b∈{0,1}. For real parameters δ,η\delta,\etaδ,η, define the binary HRW device as follows. At x=y=0x=y=0x=y=0, each equal-output event has probability (1−δ)/2(1-\delta)/2(1−δ)/2 and each unequal-output event has probability δ/2\delta/2δ/2. At every other setting, each CHSH-winning event a⊕b=xya\oplus b=xya⊕b=xy has probability 3/8−η/23/8-\eta/23/8−η/2 and each losing event has probability 1/8+η/21/8+\eta/21/8+η/2. Let ϵ(P)\epsilon(P)ϵ(P) be the CHSH loss averaged over independent uniform inputs. In the printed single-vertex convention, C(P)C(P)C(P) is the infimum of t∈[0,1]t\in[0,1]t∈[0,1] in decompositions P=tV+(1−t)LP=tV+(1-t)LP=tV+(1−t)L with VVV a nonlocal extreme non-signaling device and LLL local.

Assume 0≤δ≤10\le\delta\le10≤δ≤1 and −1/4≤η≤1/12−δ/3-1/4\le\eta\le1/12-\delta/3−1/4≤η≤1/12−δ/3. Compute squashed CMI from the vertex-labelled complete extension, with a general Eve input randomizer after the honest input choice. Define the source cost NC(P)=C(P)log⁡2min⁡{dA,dB}N_C(P)=C(P)\log_2\min\{d_A,d_B\}NC​(P)=C(P)log2​min{dA​,dB​} using maximum marginal support sizes. Then

I^(A:B∣E)E(P)=NC(P)=14−δ−3η.\widehat I(A:B\mid E)_{\mathcal E(P)}=N_C(P)=\frac14-\delta-3\eta.I(A:B∣E)E(P)​=NC​(P)=41​−δ−3η.

The binary HRW marginals have support two. Optimality against every general CE measurement is asserted as conclusion, never as a hypothesis.

Eve retains the dice result zzz and extension output eee. Squashed CMI conditions on (z,e)(z,e)(z,e); intrinsic-information channels may depend on both. This is the operational convention of XI.B.3 used by the proof, rather than discarding the dice result in display (7).

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P22
Formal statement
noncomputable section

open scoped BigOperators

namespace QAlgorithms.Papers.Independent.Intakethird100.P22

attribute [local instance] Classical.propDecidable Classical.decEq

open QAlgorithms.Papers.Independent.Advance50.P47
  (Box IsCorrelation IsNoSignaling HasLocalModel correlationMixture prBox)

open QAlgorithms.Papers.Independent.Information100.P56 (IsLaw)

open QAlgorithms.Papers.Independent.Information100.P27 (shannon)

open QAlgorithms.Papers.Independent.Gap48.P25 (classicalMI)

/-- PDF pp.56,58: the source's HRW squashed-CMI/cost identity on its binary
CHSH sector. The equality against ALL general CE measurements is the conclusion;
the displayed witness ensemble is never assumed optimal. Source convention: Eve keeps the dice
result (p.22, XI.B.3); CE members may depend on (z,e) -/
theorem hrw_cmi_cost (delta eta : ℝ) (hd : 0 ≤ delta) (hdOne : delta ≤ 1)
    (he : -(1/4 : ℝ) ≤ eta) (heUpper : eta ≤ 1/12 - delta/3)
    (c : CompleteExtension (hrwBox delta eta)) :
    squashedCMI c = nonlocalityCost (hrwBox delta eta) false false ∧
    nonlocalityCost (hrwBox delta eta) false false = 1/4 - delta - 3*eta := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P22

end
Source
Limitations on device independent key secure against non signaling adversary via the squashed non-locality, arXiv:1903.12154v7, PDF p. 58, HRW squashed-CMI identity / equations (323), (324)
Read-back

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

For every δ,η∈R\delta,\eta\in\mathbb Rδ,η∈R satisfying 0≤δ≤10\le\delta\le10≤δ≤1 and −14≤η≤112−δ3-\tfrac14\le\eta\le\tfrac1{12}-\tfrac{\delta}{3}−41​≤η≤121​−3δ​, let ppp be the Boolean array given at x=y=0x=y=0x=y=0 by p(x,y,a,b)=(1−δ)/2p(x,y,a,b)=(1-\delta)/2p(x,y,a,b)=(1−δ)/2 when a=ba=ba=b and δ/2\delta/2δ/2 otherwise, and at every other input pair by 3/8−η/23/8-\eta/23/8−η/2 when a⊕b=xya\oplus b=xya⊕b=xy and 1/8+η/21/8+\eta/21/8+η/2 otherwise. A valid array means a nonnegative array normalized over a,ba,ba,b at each x,yx,yx,y, whose bbb-marginal is independent of xxx and whose aaa-marginal is independent of yyy. A finite decomposition of ppp consists of a natural number nnn, weights wi≥0w_i\ge0wi​≥0 summing to 111, and valid arrays viv_ivi​, with ∑iwivi=p\sum_iw_iv_i=p∑i​wi​vi​=p pointwise; its support is the set of arrays viv_ivi​ with wi>0w_i>0wi​>0. Such a decomposition is minimal when every positively weighted member is a vertex and no finite decomposition of ppp has support strictly contained in its support; a vertex is a valid array vvv for which v=tq+(1−t)rv=tq+(1-t)rv=tq+(1−t)r, with valid q,rq,rq,r and 0<t<10<t<10<t<1, implies q=r=vq=r=vq=r=v. For every supplied complete extension ccc of ppp, the hypotheses therefore include validity of ppp, positive natural numbers Z,EZ,EZ,E, and, for each z<Zz<Zz<Z, a minimal decomposition (wz,e,vz,e)e<E(w_{z,e},v_{z,e})_{e<E}(wz,e​,vz,e​)e<E​ of ppp; all these decompositions use fixed member labels vz,e=vev_{z,e}=v_evz,e​=ve​, and every minimal finite decomposition ddd of ppp has exactly one index z<Zz<Zz<Z such that, for every array vvv, ∑e: ve=vwz,e\sum_{e:\,v_e=v}w_{z,e}∑e:ve​=v​wz,e​ equals the total weight assigned to vvv by ddd. Zero weights and repeated member labels are allowed. For every probability vector q=(qz)z<Zq=(q_z)_{z<Z}q=(qz​)z<Z​, meaning qz≥0q_z\ge0qz​≥0 and ∑zqz=1\sum_zq_z=1∑z​qz​=1, define Px,y,q(a,b,e)=∑zqzwz,eve(x,y,a,b)P^{x,y,q}(a,b,e)=\sum_zq_zw_{z,e}v_e(x,y,a,b)Px,y,q(a,b,e)=∑z​qz​wz,e​ve​(x,y,a,b). For a finite real-valued array rrr, put H(r)=−∑irilog⁡2riH(r)=-\sum_i r_i\log_2 r_iH(r)=−∑i​ri​log2​ri​, using the total real logarithm, and define

I(P)=H ⁣((∑bP(a,b,e))a,e)+H ⁣((∑aP(a,b,e))b,e)−H ⁣((∑a,bP(a,b,e))e)−H(P).I(P)=H\!\left((\textstyle\sum_bP(a,b,e))_{a,e}\right) +H\!\left((\textstyle\sum_aP(a,b,e))_{b,e}\right) -H\!\left((\textstyle\sum_{a,b}P(a,b,e))_e\right)-H(P).I(P)=H((∑b​P(a,b,e))a,e​)+H((∑a​P(a,b,e))b,e​)−H((∑a,b​P(a,b,e))e​)−H(P).

The quantity called squashedCMI⁡(c)\operatorname{squashedCMI}(c)squashedCMI(c) is max⁡x,y∈{0,1}inf⁡qI(Px,y,q)\max_{x,y\in\{0,1\}}\inf_q I(P^{x,y,q})maxx,y∈{0,1}​infq​I(Px,y,q). To define the other quantity, an array is local when it is nonnegative and normalized and admits a representation ∑l′μ(l)Rαl(a∣x)βl(b∣y)\sum'_l\mu(l)_{\mathbb R}\alpha_l(a\mid x)\beta_l(b\mid y)∑l′​μ(l)R​αl​(a∣x)βl​(b∣y) for some arbitrary latent type LLL, probability mass function μ\muμ, and nonnegative, normalized local response functions αl,βl\alpha_l,\beta_lαl​,βl​. Let F(p)F(p)F(p) be the real infimum of t∈[0,1]t\in[0,1]t∈[0,1] admitting p=tv+(1−t)lp=tv+(1-t)lp=tv+(1−t)l, where vvv is a vertex without a local model and lll is local, with the total real-infimum convention giving 000 if this set is empty. Set

A0=max⁡x#{a:∑bp(x,0,a,b)>0},B0=max⁡y#{b:∑ap(0,y,a,b)>0}.A_0=\max_x\#\{a:\sum_b p(x,0,a,b)>0\}, \qquad B_0=\max_y\#\{b:\sum_a p(0,y,a,b)>0\}.A0​=xmax​#{a:b∑​p(x,0,a,b)>0},B0​=ymax​#{b:a∑​p(0,y,a,b)>0}.

The nonlocality cost at inputs false, false is, by definition, F(p)log⁡2(min⁡(A0,B0))F(p)\log_2(\min(A_0,B_0))F(p)log2​(min(A0​,B0​)). The theorem asserts both equalities

squashedCMI⁡(c)=F(p)log⁡2(min⁡(A0,B0)),F(p)log⁡2(min⁡(A0,B0))=14−δ−3η.\operatorname{squashedCMI}(c) =F(p)\log_2(\min(A_0,B_0)), \qquad F(p)\log_2(\min(A_0,B_0)) =\frac14-\delta-3\eta.squashedCMI(c)=F(p)log2​(min(A0​,B0​)),F(p)log2​(min(A0​,B0​))=41​−δ−3η.

The parameter bounds are inclusive, and the assertion applies to every complete extension ccc satisfying the stated structure.

Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Nov 1, 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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me