Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

One parity protocol family distills quantum and post-quantum boxes

Open
QAlgorithms.Papers.Independent.Intakethird100.P48.main_result

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

prove2quantum

A binary behavior is a conditional probability table P(ab∣xy)P(ab\mid xy)P(ab∣xy) with x,y,a,b∈{0,1}x,y,a,b\in\{0,1\}x,y,a,b∈{0,1}. Valid resource and output behaviors are nonnegative, normalized separately at every input pair, and non-signaling in both directions. Write NL⁡(P)\operatorname{NL}(P)NL(P) for the maximum absolute three-plus/one-minus CHSH expression over the four input pairs. For nnn independent identical copies, NDP⁡n\operatorname{NDP}_nNDPn​ supplies the same local input to every copy and outputs the local XOR of the resulting bits.

There is one fixed family W=(NDP⁡n)n≥0W=(\operatorname{NDP}_n)_{n\ge0}W=(NDPn​)n≥0​ of classical local protocols without communication, chosen before the resources, such that

∃nQ>1, Q quantum:NL⁡(WnQ(Q))>NL⁡(Q)>2, ∃nR>1, R non-quantum:NL⁡(WnR(R))>NL⁡(R)>2.\begin{aligned} &\exists n_Q>1,\ Q\text{ quantum}:\quad \operatorname{NL}(W_{n_Q}(Q))>\operatorname{NL}(Q)>2,\ &\exists n_R>1,\ R\text{ non-quantum}:\quad \operatorname{NL}(W_{n_R}(R))>\operatorname{NL}(R)>2. \end{aligned}​∃nQ​>1, Q quantum:NL(WnQ​​(Q))>NL(Q)>2, ​∃nR​>1, R non-quantum:NL(WnR​​(R))>NL(R)>2.​

Quantum means exact realization of the entire table by local binary measurements on a normalized bipartite quantum state. The two resource claims hold together for the same protocol family. This is the paper's existence result; the following targets give its explicit families.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P48
Formal statement
namespace QAlgorithms.Papers.Independent.Intakethird100.P48

open scoped BigOperators TensorProduct

noncomputable section

/-- PDF p.2, Main Result (abstract p.1): one fixed local parity protocol family
distills some quantum and some post-quantum binary non-local resources. -/
theorem main_result :
    ∃ W : (n : ℕ) → ParallelProtocol n,
      (∀ n, W n = parityProtocol n) ∧
      (∃ (n : ℕ) (Q : Behavior), 1 < n ∧ IsQuantum Q ∧ StrictlyDistills (W n) Q) ∧
      (∃ (n : ℕ) (R : Behavior), 1 < n ∧ ¬ IsQuantum R ∧ StrictlyDistills (W n) R) := by sorry

end

end QAlgorithms.Papers.Independent.Intakethird100.P48
Source
Distilling Non-Locality, arXiv:0809.3173v4, PDF p. 2, Main Result (abstract p.1; explicit statement p.2)
Read-back

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

There exists a family W=(Wn)n∈NW=(W_n)_{n\in\mathbb N}W=(Wn​)n∈N​ of protocols, where an nnn-copy protocol consists of Boolean input functions α,β:{0,1}×{0,…,n−1}→{0,1}\alpha,\beta:\{0,1\}\times\{0,\ldots,n-1\}\to\{0,1\}α,β:{0,1}×{0,…,n−1}→{0,1} and Boolean output functions f,g:{0,1}×{0,1}n→{0,1}f,g:\{0,1\}\times\{0,1\}^n\to\{0,1\}f,g:{0,1}×{0,1}n→{0,1}, such that for every natural number nnn, including 000 and 111, WnW_nWn​ is exactly the protocol α(x,i)=x\alpha(x,i)=xα(x,i)=x, β(y,i)=y\beta(y,i)=yβ(y,i)=y, f(x,u)=⨁iuif(x,u)=\bigoplus_i u_if(x,u)=⨁i​ui​, and g(y,v)=⨁ivig(y,v)=\bigoplus_i v_ig(y,v)=⨁i​vi​, where ⨁\bigoplus⨁ is addition modulo two and the empty parity is 000. There exist a natural number n>1n>1n>1 and a real Boolean-indexed array QQQ for which QQQ is quantum and WnW_nWn​ strictly distills QQQ; there also exist a natural number m>1m>1m>1 and a real Boolean-indexed array RRR for which RRR is not quantum and WmW_mWm​ strictly distills RRR. These two copy counts are separate existential choices. Here, for any such array SSS, its output under WkW_kWk​ is

(TkS)(x,y,a,b)=∑u,v∈{0,1}k⨁iui=a, ⨁ivi=b∏i=0k−1S(x,y,ui,vi).(T_kS)(x,y,a,b)= \sum_{\substack{u,v\in\{0,1\}^k\\ \bigoplus_i u_i=a,\ \bigoplus_i v_i=b}} \prod_{i=0}^{k-1}S(x,y,u_i,v_i).(Tk​S)(x,y,a,b)=u,v∈{0,1}k⨁i​ui​=a, ⨁i​vi​=b​∑​i=0∏k−1​S(x,y,ui​,vi​).

Writing CS(x,y)=S(x,y,0,0)+S(x,y,1,1)−S(x,y,0,1)−S(x,y,1,0)C_S(x,y)=S(x,y,0,0)+S(x,y,1,1)-S(x,y,0,1)-S(x,y,1,0)CS​(x,y)=S(x,y,0,0)+S(x,y,1,1)−S(x,y,0,1)−S(x,y,1,0) and L(S)=max⁡x,y∣CS(x,y)+CS(x,1−y)+CS(1−x,y)−CS(1−x,1−y)∣L(S)=\max_{x,y}|C_S(x,y)+C_S(x,1-y)+C_S(1-x,y)-C_S(1-x,1-y)|L(S)=maxx,y​∣CS​(x,y)+CS​(x,1−y)+CS​(1−x,y)−CS​(1−x,1−y)∣, strict distillation means that both SSS and TkST_kSTk​S have nonnegative entries, total mass one at each input pair, first-output marginals independent of the second input and second-output marginals independent of the first input, and satisfy 2<L(S)<L(TkS)2<L(S)<L(T_kS)2<L(S)<L(Tk​S). An array SSS is quantum precisely when there exist complete complex inner-product spaces A,BA,BA,B, a unit vector ψ∈A⊗CB^\psi\in\widehat{A\otimes_{\mathbb C}B}ψ∈A⊗C​B​, and positive continuous complex-linear operators Mx,aM_{x,a}Mx,a​ and Ny,bN_{y,b}Ny,b​, summing to the identity over aaa and bbb, respectively, for each input, such that S(x,y,a,b)=Re⁡⟨ψ,Mx,a⊗Ny,b^ψ⟩S(x,y,a,b)=\operatorname{Re}\langle\psi,\widehat{M_{x,a}\otimes N_{y,b}}\psi\rangleS(x,y,a,b)=Re⟨ψ,Mx,a​⊗Ny,b​​ψ⟩ for every Boolean quadruple, with the hat denoting the induced map on the completion. The claim about RRR denies the existence of any such representation.

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