Prove2Me
Navigate
MissionsFormalpediaUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

QuantumParallelRepetition.entangledValue_exponential_decay

Proved

by Henry Yuen · Aug 9, 2026 · Mathlib c5ea003 (Lean v4.30.0)

nonlocal-gamesparallel-repetitionquantum-information

Let GGG be a finite two-player one-round game with nonempty answer alphabets and entangled value ω∗(G)<1\omega^*(G)<1ω∗(G)<1. The exponential parallel-repetition theorem asserts that there are constants C>0C>0C>0 and c>0c>0c>0, depending only on GGG, such that every repetition count nnn satisfies

ω∗(Gn)≤Ce−cn.\omega^*(G^n)\le C e^{-cn}.ω∗(Gn)≤Ce−cn.

This is stronger than polynomial decay. The general theorem was recently established by OpenAI; this abstract milestone supports formalization of that argument as well as alternative, more modular, or quantitatively sharper proofs.

Formalization Note The bound includes n=0n=0n=0, where it simply requires the zero-fold repeated value to be at most CCC.

Preamble
import Definitions.Def_quantum_parallel_repetition_game
import Mathlib.Analysis.SpecialFunctions.Exp
Formal statement
namespace QuantumParallelRepetition

/-- Exponential parallel repetition for finite two-player entangled games.
The constants may depend on the game. -/
theorem entangledValue_exponential_decay
    {X Y A B : Type*}
    [Fintype X] [Fintype Y] [Fintype A] [Fintype B]
    [Nonempty A] [Nonempty B]
    (G : Game X Y A B)
    (hG : entangledValue G < 1) :
    ∃ C c : ℝ, 0 < C ∧ 0 < c ∧ ∀ n : ℕ,
      repeatedEntangledValue G n ≤ C * Real.exp (-c * n) := by
  sorry

end QuantumParallelRepetition
Source
OpenAI, Ten Advances in Mathematics and Theoretical Computer Science, Chapter 6, Theorem 1.1, pp. 154–155, 2026, https://cdn.openai.com/pdf/ten-proofs-oai.pdf; Lean certificate: https://github.com/openai/ten-proofs/blob/main/QuantumParallelRepetition.lean; earlier general polynomial bound: Henry Yuen, arXiv:1604.04340v1, Theorem 1.
Read-back

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

For arbitrary types X,Y,A,BX,Y,A,BX,Y,A,B, equipped with finite-type structures on all four types and with explicit nonemptiness assumptions only on AAA and BBB, and for every game GGG consisting of a real weight q:X→Y→Rq:X\to Y\to\mathbb Rq:X→Y→R satisfying q(x,y)≥0q(x,y)\ge 0q(x,y)≥0 for every x,yx,yx,y and ∑x:X∑y:Yq(x,y)=1\sum_{x:X}\sum_{y:Y}q(x,y)=1∑x:X​∑y:Y​q(x,y)=1, together with a Boolean predicate V:X→Y→A→B→BoolV:X\to Y\to A\to B\to\mathrm{Bool}V:X→Y→A→B→Bool, assume that ω∗(G)<1\omega^*(G)<1ω∗(G)<1, where ω∗(G)\omega^*(G)ω∗(G) is Lean’s real supremum of the winning probabilities of all structures SSS having arbitrary finite types DA,DBD_A,D_BDA​,DB​ with decidable equality (with no separately stated Nonempty\mathrm{Nonempty}Nonempty assumptions on them), a positive-semidefinite complex matrix ρ\rhoρ on DA×DBD_A\times D_BDA​×DB​ with tr⁡(ρ)=1\operatorname{tr}(\rho)=1tr(ρ)=1, and, for every x:Xx:Xx:X and y:Yy:Yy:Y, respectively POVMs {Mxa}a:A\{M_x^a\}_{a:A}{Mxa​}a:A​ on DAD_ADA​ and {Nyb}b:B\{N_y^b\}_{b:B}{Nyb​}b:B​ on DBD_BDB​, meaning that every operator is positive semidefinite and ∑aMxa=I\sum_aM_x^a=I∑a​Mxa​=I and ∑bNyb=I\sum_bN_y^b=I∑b​Nyb​=I; the winning probability whose supremum is taken is ∑x:X∑y:Yq(x,y)∑a:A∑b:B(Re⁡tr⁡(ρ(Mxa⊗Nyb)))\sum_{x:X}\sum_{y:Y}q(x,y)\sum_{a:A}\sum_{b:B}\bigl(\operatorname{Re}\operatorname{tr}(\rho(M_x^a\otimes N_y^b))\bigr)∑x:X​∑y:Y​q(x,y)∑a:A​∑b:B​(Retr(ρ(Mxa​⊗Nyb​))) with each summand replaced by 000 when V(x,y,a,b)≠trueV(x,y,a,b)\ne\mathrm{true}V(x,y,a,b)=true. Then there exist real numbers CCC and ccc, in that order, such that 0<C0<C0<C, 0<c0<c0<c, and for every natural number nnn, ω∗(G×n)≤C exp⁡(−c n)\omega^*(G^{\times n})\le C\,\exp(-c\,n)ω∗(G×n)≤Cexp(−cn), where nnn is coerced to a real number and G×nG^{\times n}G×n has question types Fin(n)→X\mathrm{Fin}(n)\to XFin(n)→X and Fin(n)→Y\mathrm{Fin}(n)\to YFin(n)→Y, answer types Fin(n)→A\mathrm{Fin}(n)\to AFin(n)→A and Fin(n)→B\mathrm{Fin}(n)\to BFin(n)→B, question weight ∏i:Fin(n)q(xi,yi)\prod_{i:\mathrm{Fin}(n)}q(x_i,y_i)∏i:Fin(n)​q(xi​,yi​), and Boolean predicate true exactly when V(xi,yi,ai,bi)=trueV(x_i,y_i,a_i,b_i)=\mathrm{true}V(xi​,yi​,ai​,bi​)=true for every i:Fin(n)i:\mathrm{Fin}(n)i:Fin(n); ω∗(G×n)\omega^*(G^{\times n})ω∗(G×n) is again the supremum over all finite-dimensional strategies of precisely the same form, now with measurements indexed by those question tuples and with outcomes indexed by those answer tuples. The universal quantifier includes n=0n=0n=0: all four tuple types then consist of the unique empty function, the question weight is the empty product 111, the repeated predicate is true by the empty universal condition, and the asserted inequality is merely ω∗(G×0)≤C\omega^*(G^{\times0})\le Cω∗(G×0)≤C. There are no nonemptiness assumptions on XXX or YYY; however, if either is empty, the required normalization equation for GGG would read 0=10=10=1, so no such game GGG exists in that case.

Human review
  • Endorsed by Shuze Chen · Aug 9, 2026

  • Endorsed by Henry Yuen · Aug 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeLaunch a missionPropose a formalization projectFAQ

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.

How Prove2Me works
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me