Repeating an entangled game: why unusually many wins become exponentially rare

← All digests

Family 277 · Mathematical physics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-25

1. The question

Suppose two separated players can win a game with probability at most $v<1$. Repeat the game many times using independently sampled questions. If the players independently repeat their original strategy, elementary probability says their fraction of wins will rarely exceed $v$ by much.

But the players need not behave independently. They can receive all questions at once, share an entangled quantum state and make joint measurements across every repetition. The individual wins can then be correlated. Ordinary concentration bounds for independent trials no longer apply to an arbitrary strategy.

Family 277 claims that an exponential threshold bound nevertheless holds for every finite two-player game. It permits correlated questions within each game, arbitrary finite-dimensional shared entanglement and joint strategies over all repetitions. A second estimate improves the dependence on the excess winning fraction when the question distribution is fixed.

2. Background and essential definitions

A nonlocal game

A finite one-round game has question sets $X,Y$, answer sets $A,B$, a distribution $\mu$ on question pairs and an acceptance rule

$$V:X\times Y\times A\times B\longrightarrow\{0,1\}.$$

A referee draws $(x,y)$, sends $x$ to Alice and $y$ to Bob, then checks their answers. The players cannot communicate after receiving questions. They may have agreed on a strategy and shared entanglement beforehand.

A finite-dimensional quantum strategy consists of a unit vector $\psi\in\mathcal H_A\otimes\mathcal H_B$ and local measurements. For each question, a measurement is a collection of positive matrices summing to the identity, called a POVM. If its effects are $M_x^a,N_y^b$, the answer probability is

$$\Pr[a,b\mid x,y]=\langle\psi,M_x^a\otimes N_y^b\psi\rangle.$$

The entangled value $\omega^*(G)$ is the supremum of the winning probability over all finite dimensions and strategies. There need not be a strategy attaining this supremum. No fixed dimension bound is built into the definition.

Repetition and thresholds

For $k$ repetitions, the referee independently samples $k$ pairs from $\mu$, then gives each player its entire question string. Each player’s measurement may depend on that whole string and return a whole answer string.

Let $I_i\in\{0,1\}$ indicate a win in coordinate $i$, and let $W_k=\sum_{i=1}^k I_i$. The threshold event is

$$W_k\geq\lceil(v+\delta)k\rceil, \qquad v=\omega^*(G),\quad0<\delta<1-v.$$

The ceiling makes the noninteger threshold precise. Independence applies to question pairs across coordinates, not to the resulting wins under a joint strategy. Within a coordinate, Alice’s and Bob’s questions may be correlated and some pairs may have probability zero.

3. Development history and previous partial results

Raz’s parallel repetition theorem established exponential decay for winning every coordinate in classical two-player games. Holenstein simplified the argument using information theory and correlated sampling. Rao then obtained exponential concentration above the classical game value.

The threshold formulation is stronger than an all-wins statement. If winning 90 percent of the repetitions is already exceptional, then winning all of them is exceptional too. The converse implication does not follow: an all-wins bound alone can leave substantial probability of winning a large but imperfect fraction.

Early entangled-game results used additional structure. Cleve, Slofstra, Unger and Upadhyay proved perfect repetition for XOR games. Kempe, Regev and Toner treated unique games, and Dinur, Steurer and Vidick treated projection games while developing quantum correlated sampling. Jain, Pereszlényi and Yao handled independent question distributions, with improvements by Chailloux and Scarpa. Complete-support correlated distributions also admitted exponential all-wins bounds with distribution-dependent constants.

Yuen obtained polynomial all-wins decay for arbitrary finite entangled games. Bavarian, Vidick and Yuen established exponential amplification through anchoring, which modifies the game by adding questions. Their threshold result concerns that modified setting.

More directly, Chapter 6 of OpenAI’s Ten advances in mathematics and theoretical computer science, in its August 2026 version, reports exponential all-wins repetition for arbitrary finite entangled games. Song improved the all-wins gap dependence using a smoother quantum sampling construction.

The present manuscript credits these inputs. Its universal threshold theorem uses Song’s conditioning estimate, rather than claiming a new independent origin for the entire repetition machinery. The additional contribution is a quantitative passage from tested-coordinate conditioning to threshold concentration, together with a separate fixed-distribution cubic estimate. A cubic all-wins rate does not automatically give cubic concentration above an arbitrary value.

4. What the new manuscript claims

Write $d=|A||B|$, the product of answer-alphabet sizes. The manuscript claims a universal constant $\kappa_0>0$ such that every finite game with $v<1$, every allowed $\delta$, every $k\geq1$, and every finite-dimensional joint strategy satisfy

$$\Pr[W_k\geq\lceil(v+\delta)k\rceil] \leq\exp\!\left(-\frac{\kappa_0\delta^5}{1+\log d}\,k\right).$$

Logarithms are natural. Neither question-alphabet size nor entanglement dimension enters the displayed rate. The same bound holds after taking the supremum over strategies. The distribution may have zero entries or disconnected support.

A complementary bound records that support geometry. Make a graph whose vertices are positive-probability question pairs, joining pairs when they share either question. For each connected component $H_j$, let $\mu_j$ be the distribution conditioned on that component and $\mu_{j,\min}$ its smallest positive probability. Set

$$\kappa_\mu=8\max_j\frac{|H_j|-1}{\mu_{j,\min}}.$$

A singleton contributes zero. The second claimed bound is

$$\Pr[W_k\geq\lceil(v+\delta)k\rceil] \leq\exp\!\left(-\frac{\delta^3}{16384(1+\kappa_\mu)(1+\log d)}\,k\right).$$

Both bounds apply to the same strategy, so the larger exponential rate may be used. The cubic dependence is not universal in the question distribution: its constant can deteriorate when support probabilities become small. When $v=0$, the manuscript obtains the sharper conclusion that the threshold probability is zero.

For error amplification, suppose a verification game has completeness at least $c$ and soundness at most $s<c$. Accept a repeated game when the win fraction reaches $(c+s)/2$. With $\Delta=c-s$, the manuscript gives completeness at least $1-e^{-\Delta^2k/8}$ and soundness at most

$$\exp\!\left(-\frac{\kappa_0(\Delta/2)^5}{1+\log d}\,k\right).$$

The number of players and communication rounds remains unchanged, though question and answer strings grow with $k$.

5. Why the advance matters

Importance: 4/5, provisional. Threshold repetition is a substantial general amplification theorem for entangled games. It applies directly to the original game, including imperfect honest strategies and correlated question distributions with missing pairs.

The operational gain is clear. Requiring every coordinate to be won can reject an honest strategy that occasionally fails. A threshold tolerates those failures while still suppressing strategies whose single-game value lies below the acceptance level. The theorem claims this suppression even against arbitrary joint quantum measurements.

The two rates also distinguish uniformity from precision. One bound depends only on answer size and the excess fraction; the other uses additional information about the question law to improve the power of that fraction. This rating concerns the significance of these claims if correct, not independent verification of the conditioning arguments.

6. The main idea

Charge a budget for conditioning

Choose a set $C$ of tested coordinates and condition on winning every one of them. If that event has probability $p>0$, the manuscript assigns a cost per remaining coordinate

$$\tau(C)=\frac{\log(1/p)+|C|\log d}{k-|C|}.$$

The first term measures how rare the conditioning event is; the second accounts for the information in tested answers. Song’s estimate bounds the average conditional success on untested coordinates by $v+B\tau^{1/4}$ when the budget is small, for a universal constant $B$.

Intuitively, a little conditioning information cannot turn an intrinsically limited game into a substantially easier one. The difficulty is making that principle valid for entangled strategies without giving players illicit information about each other’s questions.

Extract a useful test set from too many wins

If the upper-tail event were too likely, sampling a short list of coordinate indices with replacement would identify a fixed tested set with two properties: its all-wins event is not too rare, and conditioning on it raises success elsewhere too much.

The selection uses only the joint distribution of the binary win indicators. A generic transfer then turns a conditioning error of order $\tau^{1/4}$ into the fifth-power exponential rate. Independent tensor copies of a short strategy extend the conclusion from sufficiently large lengths to every $k$, preserving the rounded threshold.

Use support geometry for the cubic rate

The second argument represents conditional measurements by vectors in common finite-dimensional spaces. It reveals Alice’s earlier questions and Bob’s later questions in a fixed coordinate order. Moving the dividing point gives two telescoping entropy estimates, controlling the information spent.

Within each connected component of question support, paths compare these vectors to one reference state. Each player can identify the component from its own question, so the component strategies can be combined without communication. The resulting loss is controlled at square-root scale in the conditioning budget, with constants depending on $\mu$. The same transfer then gives cubic dependence on $\delta$.

7. Scope, limitations, and open questions

The model has two players, one round, finite question and answer sets, Boolean acceptance and finite-dimensional tensor-product strategies. The dimension may grow arbitrarily with repetition length. The theorem does not automatically cover infinite-dimensional or commuting-operator strategy models, more players, or other payoff conventions.

The reference value is entangled value, not classical value. A quantum strategy may exceed the latter without violating the conclusion. The theorem also does not compute $v$, guarantee an optimizing strategy or make the repeated wins independent.

Optimal dependence on the gap and alphabet sizes remains a separate quantitative question. The distribution-dependent cubic rate should not be advertised as a universal cubic threshold theorem. The manuscript’s universal claim has fifth-power dependence.

8. Sources and further reading

The historical links above trace classical repetition, general entangled-game progress and the direct conditioning input. The source below supplies the threshold transfer, support-dependent rate and amplification corollary, reported with its finite-dimensional strategy convention.

Source manuscripts

• M1. OpenAI, Threshold parallel repetition for finite-dimensional entangled games (September 25, 2026).

Sources consulted on 25 October 2026 at repository revision 1581d4c. Download the manuscript citations.