A nonlocal game is played between a classical referee and two or more cooperating players who are not allowed to communicate during the game. In the two-player, one-round setting, the referee samples a pair of questions from a distribution , sends to Alice and to Bob, and receives answers and . The players win when a predicate accepts. Before the game begins they may agree on a strategy and share a resource, but after receiving their questions they are isolated from one another.
Nonlocal games occupy a useful interface between complexity theory and quantum information. From the perspective of complexity theory, they are the basic objects underlying multiprover interactive proofs: a verifier delegates a computation to separated provers and uses the consistency of their answers to distinguish valid from invalid claims. Classical two-prover games play a central role in the PCP theorem, hardness of approximation, and soundness amplification. Allowing the provers to share entanglement leads to the class and to a substantially richer theory. The theorem shows how dramatically entanglement changes this landscape: even estimating the entangled value of a nonlocal game can encode undecidable computation Ji--Natarajan--Vidick--Wright--Yuen 2020.
From the perspective of quantum information, nonlocal games are operational formulations of Bell experiments. A separation between classical and entangled values witnesses correlations that cannot be explained by a local hidden-variable model. The same framework supports self-testing, in which near-optimal behavior certifies the underlying state and measurements up to local equivalence, and device-independent cryptography, in which security or randomness is certified from observed input-output statistics rather than a trusted description of the devices. Representative references include Cleve--Høyer--Toner--Watrous 2004, Reichardt--Unger--Vazirani 2013, and Pironio et al. 2010. The survey of Palazuelos--Vidick 2016 describes further connections among nonlocal games, Bell inequalities, operator spaces, and quantum information.
Thus the value of a nonlocal game is simultaneously a complexity-theoretic soundness parameter and a quantitative measure of the power of nonclassical correlations. Understanding how this value changes under natural operations on games is important in both subjects.
We take the finite answer alphabets to be nonempty. In a classical strategy, Alice's answer depends only on , Bob's answer depends only on , and the players may coordinate using shared randomness. In a finite-dimensional entangled strategy, the players share a bipartite state and use POVM measurement operators
for their respective questions. The probability of producing answers on questions is
The supremum of the winning probability over all such finite-dimensional strategies is the entangled value . This optimization ranges over arbitrary local dimensions, shared states, and local measurements, which is one reason even apparently elementary questions about nonlocal games can be difficult.
For a positive integer , the repeated game consists of independently sampled copies of played simultaneously. Alice receives , Bob receives , and they answer with tuples and . They win only if
for every coordinate .
Parallel repetition is a basic method of soundness amplification. Starting from a game that dishonest players cannot win with certainty, the verifier repeats the test in the hope of driving the optimal success probability rapidly toward zero. The difficulty is that independence in the verifier's sampling does not force independence in the players' strategy. Alice may choose her entire answer tuple as a function of all her questions, Bob may do the same, and an entangled strategy may use a single state and joint measurements spanning all coordinates. In particular, one cannot obtain an upper bound on merely by analyzing the strategy that plays each coordinate independently.
For classical games, Raz's parallel repetition theorem gives exponential decay whenever the one-shot value is below one Raz 1998. Establishing the corresponding behavior for entangled games has been a long-running problem. A general polynomial bound was proved in Yuen 2016, implying for the first time that tends to zero for every finite two-player entangled game with .
The full exponential-decay theorem was recently settled by OpenAI. In Chapter 6 of Ten Advances in Mathematics and Theoretical Computer Science, OpenAI proves that for every finite two-player entangled game with , there is a constant such that
for every positive . OpenAI also released a Lean certificate for the result. This resolves the general quantum parallel-repetition conjecture, but it does not end the study of the problem. The proof introduces quantitative losses and a substantial technical apparatus, and there remains considerable value in finding alternative arguments, isolating the essential mechanism, improving the dependence on the one-shot gap and answer size, and producing shorter or more conceptual formal proofs.
This mission develops a reusable Lean framework for parallel repetition rather than formalizing only one paper. Its targets are organized by the strength of the asserted decay.
The main mission theorem is the fundamental asymptotic statement:
Equivalently, for every , all sufficiently large satisfy . This statement deliberately specifies no rate. It is a stable top-level theorem that can be recovered from any sufficiently strong quantitative bound.
A stronger target asks for game-dependent constants and such that
The abstract formulation avoids fixing a particular exponent or logarithmic correction. More refined formalizations can record explicit dependence on the gap , the answer alphabet, or other game parameters. Yuen's 2016 theorem is one important result at this level.
The exponential target asks for game-dependent constants such that
Following OpenAI's recent resolution, this target is now a theorem rather than an open conjecture. Within this mission it remains a central milestone: contributors may formalize the released argument in the mission's common interface, construct an independent proof, seek a more elegant or modular proof, or establish sharper quantitative variants.
These levels do not exhaust the project. The same framework can accommodate explicit finite- inequalities, stretched-exponential estimates, bounds for structured classes of games, improved parameter dependence, and reductions showing that one decay statement implies another.
The foundational Lean development represents a game by finite question sets , finite answer sets , a nonnegative normalized question distribution , and a Boolean verification predicate . The parallel-repetition theorems explicitly assume that and are nonempty. The development defines finite-dimensional entangled strategies using density matrices and POVM measurement operators, defines the repeated game on tuples, and takes the entangled value as a supremum over all finite-dimensional strategies. Repeated strategies are indexed by complete question tuples and are not required to factor coordinatewise.
A complete development will draw on formal libraries for finite probability, tensor products, positive semidefinite matrices, density matrices, POVMs, trace norms, fidelity, entropy, mutual information, and correlated sampling. These components should be formulated for reuse and should expose the dependence of each bound on the relevant game parameters.
The goal is both to verify parallel-repetition theorems and to build a dependable language for nonlocal games in Lean. Formalization forces distinctions that are easy to suppress on paper: whether constants depend on the game, whether a bound holds for all or only asymptotically, which strategy model is optimized over, and which hypotheses are needed for a particular rate. The mission welcomes reconstructions of known proofs as well as new, shorter, or conceptually different proofs.
namespace QuantumParallelRepetition
/-- The entangled value of every nontrivial finite two-player game tends to zero under
parallel repetition. -/
theorem entangledValue_tendsto_zero
{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) :
Tendsto (repeatedEntangledValue G) atTop (𝓝 0) := by
sorry
end QuantumParallelRepetitionLet be a finite two-player one-round game with nonempty answer alphabets, and let be the supremal winning probability of its finite-dimensional entangled strategies. Let denote the -fold parallel repetition, in which the referee samples all coordinates independently and the players win only if every coordinate accepts.
If the original game cannot be won with certainty,
then its repeated entangled value converges to zero:
Equivalently, for every , all sufficiently large repetition counts satisfy . The theorem deliberately asserts no rate of convergence.
Formalization Note Lean expresses the conclusion as Tendsto (repeatedEntangledValue G) atTop (𝓝 0). The sequence includes the zero-fold repetition, but changing finitely many terms does not affect its limit.
No open leaves. Every sub-goal is proved or awaiting decomposition.