Threshold repetition for entangled games

Proves that winning well above the entangled value in many repeated two-player games is exponentially unlikely.

1 paper September 25, 2026 Explained by AI

In a two-player game, a referee asks Alice and Bob separate questions, and they answer without talking. Even with shared quantum entanglement, they win at most a fraction v of the time. This paper shows that, over many independent rounds, winning a fraction noticeably above v is exponentially unlikely. Lean checks a version with a weaker rate; the paper's sharper rates are claims.

First step

1998

Raz, parallel repetition theorem for classical two-player games

Significance

Solid

It gives threshold amplification for all finite entangled two-player games, without restrictions on the questions or answers.

Trust

Formal proof listed

Field

Mathematical physics

1 paper

The explanation

In the CHSH game, a referee sends Alice one random bit and Bob another. Each answers with one bit. They win when their answers differ exactly when both questions are 1. With shared entanglement, the best winning chance per round is cos²(π/8), about 0.854. Entanglement is a quantum link between their particles that lets their answers be more correlated than any shared classical plan allows.

Now play 100 independent rounds. Suppose Alice and Bob need at least 96 wins. If each round were won independently with chance 0.854, the chance of 96 or more wins is about 0.0006. But players may coordinate across rounds. Their answers can depend on all questions they receive, and their wins need not be independentSource 1. Threshold parallel repetition asks whether beating the single-game value by a fixed margin is still exponentially rareSource 1.

For classical players, Raz proved that winning every round decays exponentiallySource 2. Rao later proved exponential concentration above the classical valueSource 3. For entangled players, results came first for special games, such as XOR games, unique games, projection games and free games. Those results restrict either the winning rule or the question distributionSource 4. Yuen proved polynomial decay for winning all rounds of any finite entangled gameSource 5. The obstacle is that entangled strategies across many rounds can correlate wins in complicated ways.

The paper proves a bound for every finite two-player game with entangled value v below oneSource 6. Fix any margin δ between 0 and 1 − v. The chance of winning at least a fraction v + δ of k rounds decays exponentially in kSource 6. The question pairs may be correlated, and the rate involves only δ and the answer sizes. The claimed rate is proportional to δ⁵ divided by 1 + log(|A||B|)Source 7. Here |A| and |B| are the numbers of possible answers. For CHSH, |A||B| = 4, and 1 + log 4 is about 2.39.

The universal constant in that rate is not stated as a number. A second, cubic bound has an explicit constant for each question distributionSource 8. For CHSH it gives a rate of δ³ divided by about 3.8 million. With δ = 0.1, that is about 2.6 × 10⁻¹⁰ per round. So it bites only after billions of rounds. The paper builds on an all-wins result in a 2026 book chapter and on a conditioning lemma of SongSource 9.

How sure is this? Lean, a computer proof checker, has a formal proof of a weaker version, with rate proportional to δ¹³. The paper notes that this weaker rate follows from its main theoremSource 10. The Lean statement covers every finite-dimensional strategy and their supremum. The δ⁵ rate as stated and the cubic bound are outside the Lean statement. They rest on the paper and on cited work, with no published specialist review.

What it doesn't show. This does not cover infinite-dimensional strategies, games with more than two players, or Lean-checked versions of the δ⁵ and cubic rates.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Solid. Lean covers the threshold bound with a weaker δ^13 rate. The δ^5 and cubic rates rest on the paper and cited work, with no published specialist review.

Words used

Two-player game: A referee sends each player a question; they answer without talking, and a fixed rule decides whether they win.
Entangled value: The best winning chance per round when players share quantum entanglement of any finite dimension.
Parallel repetition: Playing many independent copies of a game at once, with each player seeing all of their questions together.
Threshold: A required fraction of rounds won, here v + δ, a fixed margin above the single-game value.
CHSH game: A standard one-bit game where entangled players win about 85.4% of the time, against 75% for classical players.
Exponential decay: A probability that shrinks like e^(−ck) as the number of rounds k grows, for some fixed c > 0.

The original paper

Threshold parallel repetition for finite-dimensional entangled games (PDF, opens in a new tab)
September 25, 2026 Formal proof listed

Lean notes

All quoted lines (10)

Even when their success in a single game is bounded away from one, the wins in a joint strategy need not be independent.
Threshold parallel repetition for finite-dimensional entangled games Back to text
Raz proved that, when this value is less than one, the probability of winning every coordinate decays exponentially under repetition.
Threshold parallel repetition for finite-dimensional entangled games Back to text
Rao then proved exponential concentration above the classical value for general games.
Threshold parallel repetition for finite-dimensional entangled games Back to text
These results require restrictions on either the predicate or the question distribution.
Threshold parallel repetition for finite-dimensional entangled games Back to text
Yuen proved polynomial all-wins decay for arbitrary finite two-player entangled games.
Threshold parallel repetition for finite-dimensional entangled games Back to text
For every finite two-player game with entangled value $v<1$ , we prove exponential decay for the probability of winning at least a $v+\delta$ fraction of $k$ independent repetitions, uniformly over all finite-dimensional joint strategies.
Threshold parallel repetition for finite-dimensional entangled games Back to text
Its universal rate is proportional to $\delta^5/(1+\log(|\mathcal A||\mathcal B|))$ , where $\mathcal A,\mathcal B$ are the answer alphabets.
Threshold parallel repetition for finite-dimensional entangled games Back to text
For each fixed question distribution, we also obtain an explicit cubic rate in $\delta$ .
Threshold parallel repetition for finite-dimensional entangled games Back to text
We obtain this theorem by combining a transfer from conditioning bounds to threshold bounds with Song's conditioning estimate.
Threshold parallel repetition for finite-dimensional entangled games Back to text
Since $0<\delta<1$ , the weaker rate $\kappa_0\delta^{13}/(1+\log d)$ already follows from Theorem ….
Threshold parallel repetition for finite-dimensional entangled games Back to text

Other sources

openai/math, Lean scope note for family 277 The separate distribution-dependent cubic bound is outside this scope.
openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

279Exact quantum factoring over a fixed finite gate setMathematical physics
274Parity is not in QAC 0Mathematical physics
270Threshold and positive-energy bound states of the BFSS matrix modelMathematical physics
266Exactly three mutually unbiased bases in dimension sixMathematical physics
276Classical capacity of generalized amplitude dampingMathematical physics

Browse Mathematical physics Open since the 1990s Lean-checked results Solid results