Prove2Me
Navigate
MissionsFormalpediaUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

QuantumParallelRepetition.entangledValue_polynomial_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. Then there are constants C>0C>0C>0 and α>0\alpha>0α>0, depending only on GGG, such that every positive repetition count mmm satisfies

ω∗(Gm)≤Cm−α.\omega^*(G^m)\le C m^{-\alpha}.ω∗(Gm)≤Cm−α.

Thus the repeated value not only tends to zero but admits an inverse-polynomial upper bound. This is the quantitative decay supplied by Yuen's parallel-repetition theorem, stated abstractly without fixing the exponent or the dependence of the constants on the game.

Formalization Note The Lean theorem writes m=n+1m=n+1m=n+1 so that the real power has a strictly positive base and the estimate begins at the one-fold repetition.

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

/-- The entangled value of a nontrivial finite game decays at least polynomially
under parallel repetition.  The constants may depend on the game. -/
theorem entangledValue_polynomial_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 α : ℝ, 0 < C ∧ 0 < α ∧ ∀ n : ℕ,
      repeatedEntangledValue G (n + 1) ≤ C * Real.rpow (n + 1) (-α) := by
  sorry

end QuantumParallelRepetition
Source
Henry Yuen, A parallel repetition theorem for all entangled games, arXiv:1604.04340v1, p. 2, Theorem 1 (Main Theorem), https://arxiv.org/abs/1604.04340
Read-back

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

For every four types X,Y,A,BX,Y,A,BX,Y,A,B, each equipped with a Fintype structure, with AAA and BBB additionally equipped with Nonempty structures, and for every GGG consisting of a function 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 function V:X→Y→A→B→BoolV:X\to Y\to A\to B\to\mathrm{Bool}V:X→Y→A→B→Bool, assume that sSup⁡{WG(S):S is a strategy for G}<1\operatorname{sSup}\{W_G(S):S\text{ is a strategy for }G\}<1sSup{WG​(S):S is a strategy for G}<1, where a strategy SSS chooses types HA,HBH_A,H_BHA​,HB​, Fintype and DecidableEq structures on each, a matrix ρ∈Matrix⁡(HA×HB,HA×HB;C)\rho\in\operatorname{Matrix}(H_A\times H_B,H_A\times H_B;\mathbb C)ρ∈Matrix(HA​×HB​,HA​×HB​;C) that is positive semidefinite and has trace 111, for every x:Xx:Xx:X matrices Mx(a)∈Matrix⁡(HA,HA;C)M_x(a)\in\operatorname{Matrix}(H_A,H_A;\mathbb C)Mx​(a)∈Matrix(HA​,HA​;C), indexed by a:Aa:Aa:A, that are individually positive semidefinite and satisfy ∑a:AMx(a)=I\sum_{a:A}M_x(a)=I∑a:A​Mx​(a)=I, and for every y:Yy:Yy:Y matrices Ny(b)∈Matrix⁡(HB,HB;C)N_y(b)\in\operatorname{Matrix}(H_B,H_B;\mathbb C)Ny​(b)∈Matrix(HB​,HB​;C), indexed by b:Bb:Bb:B, that are individually positive semidefinite and satisfy ∑b:BNy(b)=I\sum_{b:B}N_y(b)=I∑b:B​Ny​(b)=I, and where WG(S)=∑x:X∑y:Yq(x,y)∑a:A∑b:B(if V(x,y,a,b)=true then Re⁡tr⁡(ρ(Mx(a)⊗kNy(b))) else 0)W_G(S)=\sum_{x:X}\sum_{y:Y}q(x,y)\sum_{a:A}\sum_{b:B}\bigl(\text{if }V(x,y,a,b)=\mathrm{true}\text{ then }\operatorname{Re}\operatorname{tr}(\rho(M_x(a)\otimes_kN_y(b)))\text{ else }0\bigr)WG​(S)=∑x:X​∑y:Y​q(x,y)∑a:A​∑b:B​(if V(x,y,a,b)=true then Retr(ρ(Mx​(a)⊗k​Ny​(b))) else 0); then there exist real numbers CCC and α\alphaα, in that order, such that 0<C0<C0<C, 0<α0<\alpha0<α, and for every natural number nnn, the real sSup of the winning probabilities of all strategies of the (n+1)(n+1)(n+1)-fold repeated game is at most C rpow⁡(n+1,−α)C\,\operatorname{rpow}(n+1,-\alpha)Crpow(n+1,−α), where that repeated game has questions x∙:Fin⁡(n+1)→Xx_\bullet:\operatorname{Fin}(n+1)\to Xx∙​:Fin(n+1)→X and y∙:Fin⁡(n+1)→Yy_\bullet:\operatorname{Fin}(n+1)\to Yy∙​:Fin(n+1)→Y, answers a∙:Fin⁡(n+1)→Aa_\bullet:\operatorname{Fin}(n+1)\to Aa∙​:Fin(n+1)→A and b∙:Fin⁡(n+1)→Bb_\bullet:\operatorname{Fin}(n+1)\to Bb∙​:Fin(n+1)→B, question weight ∏i:Fin⁡(n+1)q(xi,yi)\prod_{i:\operatorname{Fin}(n+1)}q(x_i,y_i)∏i:Fin(n+1)​q(xi​,yi​), and Boolean winning predicate equal to 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+1)i:\operatorname{Fin}(n+1)i:Fin(n+1), with the supremum ranging afresh over strategies having arbitrary chosen finite, decidable-equality types HA,HBH_A,H_BHA​,HB​, a positive-semidefinite trace-one state, and complete positive-semidefinite POVMs for those function-valued questions and answers as above; the statement assumes no Nonempty structure on XXX or YYY (although if either were empty, the required normalization ∑x,yq(x,y)=1\sum_{x,y}q(x,y)=1∑x,y​q(x,y)=1 could not hold), uses the total real sSup operation without separately hypothesizing that either strategy range is nonempty or bounded above, and includes n=0n=0n=0, for which it asserts the one-fold repeated-game value is at most C rpow⁡(1,−α)=CC\,\operatorname{rpow}(1,-\alpha)=CCrpow(1,−α)=C, while making no assertion about a zero-fold repetition.

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