QuantumParallelRepetition.entangledValue_exponential_decay
ProvedLet be a finite two-player one-round game with nonempty answer alphabets and entangled value . The exponential parallel-repetition theorem asserts that there are constants and , depending only on , such that every repetition count satisfies
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 , where it simply requires the zero-fold repeated value to be at most .
import Definitions.Def_quantum_parallel_repetition_game import Mathlib.Analysis.SpecialFunctions.Exp
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 QuantumParallelRepetitionRead-back
What the Lean code literally says, in plain math · gpt-5
For arbitrary types , equipped with finite-type structures on all four types and with explicit nonemptiness assumptions only on and , and for every game consisting of a real weight satisfying for every and , together with a Boolean predicate , assume that , where is Lean’s real supremum of the winning probabilities of all structures having arbitrary finite types with decidable equality (with no separately stated assumptions on them), a positive-semidefinite complex matrix on with , and, for every and , respectively POVMs on and on , meaning that every operator is positive semidefinite and and ; the winning probability whose supremum is taken is with each summand replaced by when . Then there exist real numbers and , in that order, such that , , and for every natural number , , where is coerced to a real number and has question types and , answer types and , question weight , and Boolean predicate true exactly when for every ; 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 : all four tuple types then consist of the unique empty function, the question weight is the empty product , the repeated predicate is true by the empty universal condition, and the asserted inequality is merely . There are no nonemptiness assumptions on or ; however, if either is empty, the required normalization equation for would read , so no such game exists in that case.
Confirmed by the mission captain (proposal self-audit).