Entangled games: conditioning and threshold repetition

Source and verification

This article explains family 277 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Games, measurements, and dependent wins

A two-player game tests separated players with correlated questions. Repeating the test gives each player a whole string of questions, so they can coordinate their answers across coordinates. Independence of the referee’s samples does not make their wins independent. Family 277 develops concentration above the best single-game success probability, even for joint quantum strategies. Its central mechanism converts a bound on the cost of conditioning into an exponential tail. (OpenAI, 2026)

The prerequisites are finite-dimensional positive operators, tensor products, conditional probability, and entropy. A positive operator-valued measurement, or POVM, is a finite family of positive operators summing to the identity. If Alice and Bob share a unit vector $\psi \in H_A\otimes H_B$, their local POVMs give answer probability $⟨\psi ,(M_x^a\otimes N_y^b)\psi ⟩$.

A game $G$ specifies finite nonempty question sets $X,Y$, answer sets $A,B$, a probability law $\mu$ on $X\times Y$, and a Boolean predicate $V(x,y,a,b)$. The referee samples $(x,y)$, sends one question to each player, and accepts precisely when $V=1$. Players cannot communicate. The entangled value $v={\omega }^{\ast }(G)$ is the supremum of success probabilities over all finite-dimensional shared states and local POVMs. Mixed states can be purified using a finite local register. The supremum need not be attained.

In $k$ repetitions, question pairs are independent with law $\mu$, but each player receives the entire local string and can use a joint POVM. Write $I_i$ for the win indicator at coordinate $i$, $W={\sum }_i{I}_i$, and $d=|A||B|$. All logarithms below are natural.

Every marginal satisfies $\mathbb{E}{I}_i\le v$: fix all other question pairs, insert a fresh game at position $i$, run the repeated strategy, and retain its $i$th answers. This is a legitimate single-game strategy; averaging the fixed questions proves the claim. Consequently $\mathbb{E}W\le kv$. This alone gives no exponential concentration. For arbitrary random indicators, setting every $I_i$ equal to one Bernoulli variable has the same marginal bound and a constant upper tail. The structure of local quantum strategies supplies the additional constraint.

🏷️ Two concentration rates

Manuscript's universal threshold bound

There is a universal ${\kappa }_0>0$ such that, for $v<1$, $0<\delta <1-v$, every $k\ge 1$, and every finite-dimensional joint strategy,

$$\begin{array}{c}\mathrm{Pr}\left(W\ge \lceil (v+\delta )k\rceil \right)\\ \le \exp \left(-\frac{{\kappa }_0{\delta }^{5}k}{1+\log d}\right).\end{array}$$

The same bound holds for the supremum over these strategies. Question correlations, zero probabilities, and disconnected support are allowed. (OpenAI, 2026)

Neither question alphabet size nor strategy dimension enters this rate. The manuscript also proves a cubic rate whose constant depends on $\mu$. Form a graph with vertices $H=\{(x,y):\mu (x,y)>0\}$, connecting pairs that share either question. Let $H_j$ be its components, ${\mu }_j$ the conditional law on $H_j$, and ${\mu }_{j,\min }$ its smallest mass. Define

$$\begin{array}{c}{K}_{\mu }=8\underset{j}{\max }\frac{|H_j|-1}{{\mu }_{j,\min }},\\ c_{\mu }(\delta )=\frac{{\delta }^3}{16384(1+K_{\mu })(1+\log d)}.\end{array}$$

Then the same threshold probability is at most $e^{-c_{\mu }(\delta )k}$. A singleton component contributes zero to $K_{\mu }$. Very small positive masses can make this rate poor; the universal estimate remains available. Since both apply, one may take the larger exponential rate. When $v=0$, the marginal argument gives probability zero for every positive threshold.

The accompanying formal scope page selects a ${\delta }^{13}$ universal rate, not the manuscript’s stronger ${\delta }^5$ statement, and excludes the distribution-dependent cubic bound. Since $0<\delta <1$, the fifth-power theorem implies a thirteenth-power estimate, but that implication does not identify what was formally checked.

🏷️ Conditioning cost and upper-tail selection

For a tested set $C$, let $E_C$ mean that all its coordinates are won, and put $p_C=\mathrm{Pr}(E_C)$. For $C⊊[k]$ and $p_C>0$, define

$$\begin{array}{c}m=k-|C|,\\ \tau (C)=\frac{\log (1/p_C)+|C|\log d}{m},\\ {\bar{s}}_C=\frac{1}{m}\sum _{i\notin C}\mathrm{Pr}(I_i=1\mid E_C).\end{array}$$

The numerator charges both the rarity of the conditioning event and the information in tested answer strings. The denominator distributes that cost over untested coordinates.

The transfer theorem says: if a budget $0<T\le \delta /4$ guarantees ${\bar{s}}_C\le v+\delta /4$ whenever $\tau (C)\le T$, uniformly over all repetition lengths and strategies, then the threshold tail has rate

$$c=\frac{\delta T}{16(1+\log d)}.$$

The probabilistic selection behind this result works for arbitrary dependent binary indicators. Set $p_H=\mathrm{Pr}(W\ge \lceil qk\rceil )>0$, choose $0<q_0<q<1$ and $0<\epsilon <1$, and draw

$$\ell =\lceil \frac{\log (4/(\epsilon p_H))}{\log (q/q_0)}\rceil$$

indices independently with replacement. Let $C$ be their distinct set. Conditional on the indicators, all sampled positions win with probability $(W/k{)}^{\ell }$. Thus, averaging over draws,

$$\begin{array}{rl}{\mathbb{E}}_C{p}_C& =\mathbb{E}(W/k{)}^{\ell }\\ & \ge p_H{q}^{\ell }=:a,\\ {\mathbb{E}}_C\mathrm{Pr}(E_C,W<q_{0}k)& \le q_0^{\ell }\le \epsilon a/4.\end{array}$$

Draws with $p_C<a/2$ contribute at most $a/2$ to the first average. Draws whose conditional low-win probability exceeds $\epsilon$ contribute at most $a/4$. Some remaining draw therefore has $|C|\le \ell$, $p_C\ge a/2$, and $\mathrm{Pr}(W<q_{0}k\mid E_C)\le \epsilon$. This argument would not have the displayed power identity for sampling distinct indices uniformly.

To use it, take $q=v+\delta$, $q_0=v+\delta /2$, and $\epsilon =\eta =\delta /16$. Suppose $p_H\ge e^{-ck}$. With $r=\log (q/q_0)$ and $R=\log (d/q)$, the selected size is at most $ck/r+O(1)$. The inequalities $r\ge \delta /(2q)$ and $q\log (1/q)\le 1/e$ imply

$$\begin{array}{c}\frac{c}{r}\le \frac{T}{8}\le \frac{\eta }{2},\\ c\left(1+\frac{R}{r}\right)\le \frac{3T}{16}.\end{array}$$

For sufficiently large $k$, these estimates give $|C|\le \eta k$ and $\tau (C)<T$. Yet, conditional on $E_C$, the event $W\ge q_{0}k$ has probability at least $1-\eta$. Removing the tested wins gives ${\bar{s}}_C\ge q_0-\eta =v+7\delta /16$, contradicting the budget’s upper bound.

There is no loss at small repetition lengths. Take $N$ independent tensor copies of any fixed $k$-coordinate strategy. All $N$ blocks exceeding their thresholds has probability $p_H^N$ and implies the $Nk$ threshold, because $N\lceil qk\rceil \ge \lceil qNk\rceil$. Choose $N$ large enough for the preceding argument and take an $N$th root. All tensor products remain finite dimensional; no maximizing strategy is required.

🏷️ The universal analytic input

The manuscript imports Song’s conditioning estimate: for a universal $B_4\ge 1$ and $\tau (C)\le 1$,

$${\bar{s}}_C\le v+B_4\tau (C{)}^{1/4}.$$

This is an external theorem in the manuscript’s proof, using a smooth sampler. Its proof was not independently audited for this post. Taking $T=(\delta /(4B_4){)}^4$ makes the error at most $\delta /4$, and the transfer yields the fifth-power rate with ${\kappa }_0=1/(16(4B_4{)}^4)$. An all-wins repetition theorem alone would not supply this threshold statement: an upper bound on the smaller all-wins event does not bound the larger threshold event.

The cubic result uses a different conditioning estimate, constructed through the support graph. The next two sections explain the quantum and probabilistic ingredients of that construction. (OpenAI, 2026)

🏷️ Common purifications and local descriptions

An effect is an operator $0⪯T⪯I$. The manuscript embeds every effect into one common Hilbert space through

$$\begin{array}{c}({\mathcal{F}}_{T}h)(s)=T(T+sI{)}^{-1}h,\\ s>0.\end{array}$$

The target initially is $L^2((0,\infty ),ds;H)$. The scalar identity ${\int }_0^{\infty }{t}^2/(t+s{)}^{2}ds=t$ gives ${\mathcal{F}}_T^{\ast }{\mathcal{F}}_T=T$. For an ensemble of effects $T_j$ with weights $q_j$ and mean $\bar{T}$, a resolvent identity gives

$$\begin{array}{rl}& \sum _j{q}_j({\mathcal{F}}_{T_j}-{\mathcal{F}}_{\bar{T}}{)}^{\ast }({\mathcal{F}}_{T_j}-{\mathcal{F}}_{\bar{T}})\\ & ⪯\sum _j{q}_{j}f(T_j)-f(\bar{T}),\\ & f(t)=t\log t.\end{array}$$

Here $f(0)=0$. To see the source of the inequality, expand the entropy gap using resolvents and cancel the term linear in $T_j-\bar{T}$. The squared-distance integrand is bounded by that gap integrand using $s(T_j+sI{)}^{-2}⪯(T_j+sI{)}^{-1}$. The common kernel contributes zero. Only finitely many effects occur in a fixed repeated strategy, so their image spaces span a finite-dimensional common target. Compressing to that span preserves every cross inner product.

The construction also preserves answers. If $F^{\ast }F=T$ and positive operators $G_a$ sum to $T$, let $U=F{T}^{-1/2}$, with inverse on the support of $T$. Transport $G_a$ to $U{T}^{-1/2}{G}_a{T}^{-1/2}{U}^{\ast }$ and assign the unused orthogonal complement to one answer. The resulting POVM satisfies $F^{\ast }{\tilde{G}}_{a}F=G_a$. Thus purified vectors reproduce the original fine answer probabilities, including cases where an effect is singular.

For the untested coordinates in a fixed order, expose Alice’s questions before position $i$, Bob’s questions after it, and both players’ tested questions. This transcript excludes the fresh pair $(x,y)$ and is independent of it under the original question law. Fixing the transcript and fresh pair makes the remaining question strings independent across players: each unexposed question has the conditional law determined by its already exposed partner.

Average the tested-answer effects under these conditional laws, and purify them with the common maps. This produces a vector ${\Psi }_{xy}$ and two local descriptions ${\Psi }_x,{\Psi }_y$, with the transcript and tested answers suppressed from notation. The transported measurements reproduce the conditional answers exactly. The manuscript’s weighted exposure lemma gives total squared error at most $2p_C\tau (C)$, averaged over the fresh coordinate, transcript, and questions.

The weights here need not sum to one: vector norms provide the missing tested-answer probabilities. The proof uses two entropy potentials, one increasing and one decreasing as the exposed question at a position changes from Bob’s to Alice’s. Each lies between $-p_{C}L$ and zero, where $L=\log (d^{|C|}/p_C)$. The resolvent inequality bounds each squared error by a potential increment; telescoping yields the stated budget. This is why the denominator is the number of untested coordinates.

🏷️ Support components and legal shared states

A vector ${\Psi }_{xy}$ depending on both fresh questions is not an available shared state. The support graph removes that dependence. Adjacent vertices sharing $y$ have the same anchor ${\Psi }_y$; those sharing $x$ have anchor ${\Psi }_x$. With

$$\begin{array}{rl}{e}_z=& \Vert {\Psi }_{xy}-{\Psi }_x{\Vert }^2\\ & +\Vert {\Psi }_{xy}-{\Psi }_y{\Vert }^2,\\ & z=(x,y),\end{array}$$

an adjacent pair has squared distance at most $2(e_z+e_{z^{\prime }})$. A simple path to a fixed component root has length at most $|H_j|-1$. Cauchy–Schwarz along the path, followed by conversion from counting measure to ${\mu }_j$, bounds the root-replacement error. Averaging all transcripts and coordinates gives total error $E\le K_{\mu }{p}_C\tau (C)$.

Now use the root vector for each transcript and coordinate, attach matching shared flags, and normalize their weighted direct sum. This defines a finite-dimensional shared state independent of the new questions. The players control their transported POVMs by those flags and their own questions. Each component’s resulting success is at most its value $v_j$.

Both the accepting mass and the normalization mass change under root replacement. For an effect $0⪯Q⪯I$,

$$\begin{array}{c}|⟨a,Qa⟩-⟨b,Qb⟩|\\ \le (\Vert a\Vert +\Vert b\Vert )\Vert a-b\Vert .\end{array}$$

Weighted Cauchy–Schwarz bounds the total comparison error by $4\sqrt{E/p_C}+2E/p_C$. Keeping the normalization error is essential because the conditional vectors were not unit vectors.

Conditioning also changes the frequencies of components. Their unconditioned law is a product, and the conditional density is at most $1/p_C$. Thus its relative entropy is at most $\log (1/p_C)$. Relative entropy to a product bounds the sum of marginal relative entropies; Pinsker’s inequality bounds the average change in component weights by $\sqrt{\log (1/p_C)/(2m)}$ in total variation, defined as half the ${\ell }_1$ distance.

Each local question identifies its component. Tensoring near-optimal strategies for the finitely many components shows ${\sum }_j\mu (H_j)v_j\le v$, even without attainment. Combining the root and frequency comparisons gives

$$\begin{array}{rl}{\bar{s}}_C\le v& +\sqrt{\frac{\log (1/p_C)}{2m}}\\ & +4\sqrt{K_{\mu }\tau (C)}+2K_{\mu }\tau (C).\end{array}$$

Take $T={\delta }^2/(1024(1+K_{\mu }))$. The excess is at most $81\delta /512<\delta /4$, and $T\le \delta /4$. The same transfer theorem now gives the claimed cubic rate. This proof exposes where small support probabilities enter; it does not replace $K_{\mu }$ by a universal constant.

🏷️ Error amplification and related notes

Suppose a verifier has completeness at least $c$ and soundness at most $s<c$. Accept after $k$ repetitions when at least a fraction $(c+s)/2$ wins. On the completeness side, tensor copies of a near-optimal single-game strategy give independent wins, so Hoeffding’s inequality bounds rejection by $\exp (-(c-s{)}^{2}k/8)$. On the soundness side, the threshold theorem bounds acceptance even for arbitrary joint strategies, with fifth-power gap dependence. These two arguments require different amounts of independence.

The selected review includes the manuscript’s conditioning-to-tail proof, resolvent and measurement transport, exposure telescope, support-root construction, and amplification argument. The imported smooth-sampler theorem and external historical results remain source-attributed.

Quantum circuit localization studies how correlations obstruct conclusions drawn from individual outputs; its circuit hypotheses and conclusions differ from game repetition. Amplitude-damping capacity uses entropy inequalities to control arbitrary joint quantum inputs, providing a complementary example of reducing a many-system optimization to one-system information.

🏷️ Key steps and proof outlines

Resolvent purification has an exact quadratic remainder

The operator estimate above is the analytic device that makes conditional information cost control distances between quantum states. Its proof can be written without assuming that the effects commute.

Let $B={\sum }_j{q}_j{A}_j$, $D_j=A_j-B$, and abbreviate $R_B(s)=(B+sI{)}^{-1}$, $R_j(s)=(A_j+sI{)}^{-1}$. The exact second-order resolvent identity is

$$R_j=R_B-R_B{D}_j{R}_B+R_B{D}_j{R}_j{D}_j{R}_B.$$

Since ${\sum }_j{q}_j{D}_j=0$, averaging removes its linear term. The integral formula for $f(t)=t\log t$ then gives

$$\sum _j{q}_{j}f(A_j)-f(B)={\int }_0^{\infty }s\sum _j{q}_j{R}_B{D}_j{R}_j{D}_j{R}_{B}ds.$$

The integrand is positive: each summand is a congruence of the positive resolvent $R_j$.

Meanwhile, the difference between the two purification kernels is

$$A_j(A_j+sI{)}^{-1}-B(B+sI{)}^{-1}=s{R}_j{D}_j{R}_B.$$

Its squared norm therefore has operator integrand

$$s^2{R}_B{D}_j{R}_j^2{D}_j{R}_B.$$

The scalar spectral inequality $s{R}_j^2⪯R_j$, inserted between the same factors, bounds this by the entropy-gap integrand. Integration proves the purification-distance inequality.

Singular effects cause no missing term. If $v\in \ker B$, positivity and strictly positive weights imply $A_{j}v=0$ for every $j$, so both sides vanish there. On the support of $B$, the entropy-gap integrand is bounded near zero and $O(s^{-2})$ at infinity, establishing norm convergence. Thus the inequality holds for all the singular tested-answer effects generated by a repeated strategy (OpenAI, 2026).

Common spaces and transported measurements preserve legality

For a fixed strategy, finitely many effects appear. Each map ${\mathcal{F}}_T$ has an image of dimension at most the original Hilbert-space dimension, even though its displayed codomain is an $L^2$ space. Taking the span of all these images produces one finite-dimensional space preserving every product ${\mathcal{F}}_S^{\ast }{\mathcal{F}}_T$. Compressing each image separately would preserve individual norms but could alter the cross inner products used by the exposure estimates.

Suppose the fine answer effects satisfy ${\sum }_a{G}_a=T$, and put $V_T=F{T}^{-1/2}$ for $F^{\ast }F=T$, with inverse only on the support. The transported measurement is explicitly

$$\begin{array}{rl}{\tilde{G}}_a=& V_T{T}^{-1/2}{G}_a{T}^{-1/2}{V}_T^{\ast }\\ & +1_{\{a=a_{\ast }\}}(I-V_T{V}_T^{\ast }),\end{array}$$

where $a_{\ast }$ is one chosen answer. The first terms sum to the projection $V_T{V}_T^{\ast }$; the second completes them to the identity. Their pullbacks are exactly $G_a$, because the added complement is orthogonal to the range of $F$.

These two constructions serve different requirements. The common embedding gives quantitative closeness during exposure. The measurement transport retains the original answer probabilities and produces actual POVMs on the extracted shared space. Together with the later support-root replacement, they turn an approximate conditional description into a legal finite-dimensional single-game strategy, which is what permits comparison with the supremum $v$ (OpenAI, 2026).

🏷️ Manuscripts and verification scope

• Threshold parallel repetition for finite-dimensional entangled games — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The selected scope states a universal thirteenth-power threshold rate for arbitrary finite-dimensional joint strategies and their supremum, without attainment. The manuscript proves the stronger fifth-power rate. The separate distribution-dependent cubic estimate is explicitly outside the selected scope. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Threshold parallel repetition for finite-dimensional entangled games.