Games and the main theorem

A finite two-player one-round game consists of nonempty finite question sets \(\mathcal X,\mathcal Y\), nonempty finite answer sets \(\mathcal A,\mathcal B\), a probability distribution \(\mu\) on \(\mathcal X\times\mathcal Y\), and a predicate \[V:\mathcal X\times\mathcal Y\times\mathcal A\times\mathcal B \longrightarrow\{0,1\}.\] The referee samples \((x,y)\) from \(\mu\), sends \(x\) to Alice and \(y\) to Bob, and accepts answers \((a,b)\) when \(V(x,y,a,b)=1\). The players do not communicate. A finite-dimensional entangled strategy consists of a unit vector \(\psi\in\mathcal H_A\otimes\mathcal H_B\) and, for each local question, a positive operator-valued measurement (POVM): positive operators \(M_x^a,N_y^b\) satisfying \(\sum_aM_x^a=I\) and \(\sum_bN_y^b=I\). Its success probability is \[\sum_{x,y,a,b}\mu(x,y)V(x,y,a,b) \langle\psi,M_x^a\otimes N_y^b\psi\rangle.\] Using pure states causes no loss, since a finite-dimensional mixed state can be purified by adding a finite local register. The entangled value \(\omega^*(G)\) is the supremum of this expression over all finite dimensions and all such strategies; the supremum need not be attained.

In \(k\) repetitions the referee samples \((X_1,Y_1),\ldots,(X_k,Y_k)\) independently from \(\mu\) and sends each player the entire local question string. A strategy may use arbitrary joint POVMs \(M_{\mathbf x}^{\mathbf a}\) and \(N_{\mathbf y}^{\mathbf b}\), with answer strings in \(\mathcal A^k\) and \(\mathcal B^k\). Write \[I_i=V(X_i,Y_i,A_i,B_i),\qquad W_k=\sum_{i=1}^k I_i, \qquad d=|\mathcal A||\mathcal B|.\] All logarithms below are natural.

The distribution \(\mu\) may be correlated and may have zero entries or disconnected support. Neither the question alphabet sizes nor the strategy dimension enter the displayed rate. We obtain this theorem by combining a transfer from conditioning bounds to threshold bounds with Song’s conditioning estimate (Song 2026, Lemma 4.4). The transfer is proved in Section 2; its tested-set selection uses only the joint law of the binary win indicators.

A second bound records the geometry of a fixed question distribution. Form the graph whose vertices are the positive-probability pairs \(H=\{(x,y):\mu(x,y)>0\}\), joining two pairs when they share either question. For its connected components \(H_j\), let \(\mu_j=\mu(\,\cdot\mid H_j)\) and \(\mu_{j,\min}=\min_{z\in H_j}\mu_j(z)\), and set \[\kappa_\mu=8\max_j\frac{|H_j|-1}{\mu_{j,\min}}.\] In particular, a singleton component contributes zero. Corollary 11 proves, under the same hypotheses and for every \(k\ge1\), the complementary estimate \[\Pr\!\left[W_k\ge\lceil(v+\delta)k\rceil\right] \le\exp\!\left(-\frac{\delta^3} {16384(1+\kappa_\mu)(1+\log d)}\,k\right).\] Both estimates apply to the same strategy, so one may use the larger exponential rate. The cubic bound is proved in Section 5 by constructing one reference state per support component. Its constant depends on the fixed distribution through \(\kappa_\mu\), whereas the fifth-power constant is universal. Both bounds hold at every repetition length, including when rounding the threshold to an integer matters. When \(v=0\), Lemma 2 gives the sharper probability zero.

Related work

The classical value of a game is its largest success probability using only shared randomness and local response functions. Raz proved that, when this value is less than one, the probability of winning every coordinate decays exponentially under repetition (Raz 1998). Holenstein’s information-theoretic proof introduced correlated sampling into this argument and improved its quantitative dependence on the gap from one (Holenstein 2009). Rao then proved exponential concentration above the classical value for general games (Rao 2011, Theorem 7). This threshold conclusion is stronger than an all-wins bound: the event that every coordinate is won is only a subset of the event that a specified fraction is won.

For entangled strategies, early repetition results used structure in the acceptance predicate or in the question distribution. Cleve, Slofstra, Unger, and Upadhyay proved perfect repetition for XOR games, whose answers are bits and whose acceptance depends on their parity: the all-wins value of a product is the product of the individual values (Cleve et al. 2008). Kempe, Regev, and Toner proved exponential repetition for unique games, whose constraints are permutations between the answer sets (Kempe et al. 2010). Dinur, Steurer, and Vidick extended exponential repetition to projection games, in which one player’s answer determines the other player’s required answer, and developed quantum correlated sampling (Dinur et al. 2015). Jain, Pereszlényi, and Yao treated free games, where the players’ questions are independently distributed (Jain et al. 2014); Chailloux and Scarpa subsequently improved the rate (Chailloux and Scarpa 2015). These results require restrictions on either the predicate or the question distribution. For complete-support question distributions, which may be correlated, Chailloux and Scarpa also proved exponential all-wins decay with a rate depending on the distribution (Chailloux and Scarpa 2014, Corollary 1, corrected version). That result does not cover arbitrary zero entries in the question law.

Yuen proved polynomial all-wins decay for arbitrary finite two-player entangled games (Yuen 2016, Theorem 1). His proof combines conditioning with classical and quantum correlated sampling; its tested-coordinate selection already samples indices with replacement (Yuen 2016, Proposition 9, full version). Bavarian, Vidick, and Yuen obtained exponential amplification by anchoring, a transformation that adds questions to the game (Bavarian et al. 2022). Their threshold theorem concerns these anchored games (Bavarian et al. 2017, sec. 5.4, Theorem 5.6). Rao’s and their concentration arguments are precedents for extracting a threshold bound from control after conditioning on tested coordinates. Unlike the anchoring transformation, the present bounds retain the given question distribution throughout.

Chapter 6 of Ten Advances in Mathematics and Theoretical Computer Science obtains exponential all-wins repetition for arbitrary finite entangled games (OpenAI 2026). Its operator entropy estimate and conditioning construction are the analytic antecedents of the argument below. We reproduce that chapter’s resolvent purification and its estimate from Definition 4.2 and Lemma 4.3, and adapt its Section 4 weighted reveal argument to a fixed ordering of the untested coordinates. Song replaces the quantum sampler in that framework by a smooth construction and improves the all-wins gap dependence to a cubic power (Song 2026). His generic conditioning lemma supplies our fifth-power threshold theorem. The cubic all-wins result uses an additional estimate for near-perfect conditional success; it does not by itself imply a cubic threshold rate above an arbitrary value.

Our contribution is a quantitative transfer from tested-set conditioning to threshold decay, together with its universal fifth-power application and the explicit cubic bound for each fixed question distribution. The universal application uses Song’s sampler independently of the Dinur–Steurer–Vidick sampling theorem, while retaining the conditioning machinery of Chapter 6. Since \(0<\delta<1\), the weaker rate \(\kappa_0\delta^{13}/(1+\log d)\) already follows from Theorem 1.

The proof in outline

Fix a repeated strategy. For a tested set \(C\subsetneq[k]\), let \(E_C\) be the event that all coordinates in \(C\) are won, and suppose \(p=\Pr(E_C)>0\). Put \(m=k-|C|\) and \[\tau=\frac{\log(1/p)+|C|\log d}{m}.\] The numerator records the rarity of the conditioning event and the logarithm of the number of possible tested answer strings. Song’s estimate, stated in Proposition 5, bounds the average success on the remaining coordinates by \[ \frac1m\sum_{i\notin C}\Pr(I_i=1\mid E_C) \le v+B_4\tau^{1/4}\qquad(0\le\tau\le1), \tag{2}\] where \(B_4\) is universal. Thus a small conditioning budget cannot raise the average win probability far above \(v\).

Section 2 first proves the generic transfer. If the upper tail has too much probability, sampling a short list of coordinate indices with replacement identifies a fixed tested set \(C\) whose success probability is large and whose conditional win rate outside \(C\) exceeds \(v\) by a fixed fraction of \(\delta\). Its budget is small enough to contradict (2). This binary sampling argument gives the exponential bound for sufficiently large repetition lengths. Taking independent tensor copies of any shorter strategy then gives the same rate for every length. The generic transfer turns a conditioning error of order \(\tau^{1/4}\) into the fifth-power rate in the main theorem.

The fixed-distribution cubic bound uses a different construction of a single-game strategy. Sections 3 and 4 represent the conditional answers by measurements on vectors in common finite-dimensional spaces. Resolvent purifications preserve the answer probabilities. To compare the vectors, order the untested coordinates and expose Alice’s questions before a chosen coordinate and Bob’s questions after it. Moving this dividing point gives two entropy telescopes, with total cost at most \(p(\log(1/p)+|C|\log d)\) on each side. The resulting vector has two nearby approximations, each determined by one player’s question and a transcript of exposed questions and tested answers.

Section 5 compares these vectors along paths in each connected component of the question support. The resulting strategies for the component games can be combined in one fixed tensor-product state, since each player identifies the component from the local question. The loss is \(O_\mu(\sqrt\tau+\tau)\), and the same transfer therefore gives cubic dependence on \(\delta\). Corollary 12 applies the threshold theorem to amplify both completeness and soundness.

Marginal success probabilities

We first record a bound that also settles the zero-value case.

Selecting the tested coordinates

The next lemma identifies one fixed tested set. Its hypotheses impose no independence on the win indicators.

An exponential rate for every repetition length

The next statement isolates the quantitative use of a conditioning estimate. All logarithms are natural.

Proof of the universal threshold bound

We use the following conditioning estimate as an external theorem. It supplies a budget uniform in the question distribution and the strategy dimension.

Song proves this estimate using a smooth sampler and the analytic conditioning machinery of Chapter 6 of (OpenAI 2026); the proof does not use the Dinur–Steurer–Vidick sampling theorem.

The next sections develop the common purification and exposure construction needed for the fixed-distribution cubic bound. That argument does not use Song’s sampler.

Exposing one question at each coordinate

Fix any ordering of the untested coordinates, and abbreviate their questions as \(X_1,\ldots,X_m\) and \(Y_1,\ldots,Y_m\), with answers \(A_1,\ldots,A_m\) and \(B_1,\ldots,B_m\). The tested questions retain the notation \(X_C,Y_C\). Position-indexed win indicators refer to these same untested coordinates; sums over \(i\notin C\) in the result statements use the original coordinate labels. For \(0\le j\le m\) define the flag \[\Omega_j=(X_C,Y_C,X_{\le j},Y_{>j}).\] Conditioned on a flag of positive probability, the full question vectors \(\mathbf X\) and \(\mathbf Y\) are independent. Indeed, at a tested coordinate both questions are fixed. At each untested coordinate one question is fixed and the other has its conditional law under \(\mu\); these remaining choices are independent across coordinates. This argument uses no independence between the two questions within a coordinate.

For tested answer strings \(\alpha\in\mathcal A^C\) and \(\gamma\in\mathcal B^C\), define the coarse-grained effects \[M_{\mathbf x}^{\alpha} =\sum_{\mathbf a:\,a_C=\alpha}M_{\mathbf x}^{\mathbf a}, \qquad N_{\mathbf y}^{\gamma} =\sum_{\mathbf b:\,b_C=\gamma}N_{\mathbf y}^{\mathbf b},\] and the testing mask \[\theta(x_C,y_C,\alpha,\gamma) =\prod_{j\in C}V(x_j,y_j,\alpha_j,\gamma_j).\] For \(C=\varnothing\) there is one pair of empty answer strings and the empty product is \(1\). Write \[F_j^\alpha=\mathbb E[M_{\mathbf X}^\alpha\mid\Omega_j],\qquad H_j^\gamma=\mathbb E[N_{\mathbf Y}^\gamma\mid\Omega_j],\qquad \chi(A,B)=\langle\psi|A\otimes B|\psi\rangle.\] The answer strings here are fixed indices of the effects, not additional conditions on the question distribution. These are positive contractions. Conditional independence and linearity give, for every \(j\), \[ \mathbb E_{\Omega_j}\sum_{\alpha,\gamma} \theta\,\chi(F_j^\alpha,H_j^\gamma)=p. \tag{15}\]

A mode is an index \(i\in[m]\). Delete its question from the flag and set \[r_0=(X_C,Y_C,X_{<i},Y_{>i}),\qquad \nu_i=\operatorname{law}(r_0).\] Figure 1 records which questions are retained.

The variable \(r_0\) is independent of \((X_i,Y_i)\sim\mu\). For each value of \(r_0\) of positive probability, put \[\begin{align*} F_x^\alpha&=\mathbb E[M_{\mathbf X}^\alpha\mid r_0,X_i=x],& H_y^\gamma&=\mathbb E[N_{\mathbf Y}^\gamma\mid r_0,Y_i=y],\\ F_y^\alpha&=\sum_x\mu(x\mid y)F_x^\alpha,& H_x^\gamma&=\sum_y\mu(y\mid x)H_y^\gamma. \end{align*}\] We use these formulas only on positive marginal probabilities. In each conditional ensemble, zero weights are omitted before applying Lemma 6. Questions of zero marginal probability may be assigned arbitrary complete local POVMs with answers in the original alphabets. All four effects also depend on \(i,r_0\), which are suppressed in the notation. The subscripts in \(F_y^\alpha,H_x^\gamma\) indicate the question on which the conditional average depends. In particular, \[(F_{i-1}^\alpha,H_{i-1}^\gamma)=(F_y^\alpha,H_y^\gamma), \qquad (F_i^\alpha,H_i^\gamma)=(F_x^\alpha,H_x^\gamma).\] Here the first identity is evaluated at \(Y_i=y\), and the second at \(X_i=x\). The mask depends only on \(r_0,\alpha,\gamma\), not on \(x,y\).

The conditional vector and its measurements

Apply the common finite-dimensional compression in Lemma 6 to all four families \(F_x^\alpha,F_y^\alpha,H_x^\gamma,H_y^\gamma\), over every mode, flag and positive-marginal question. This gives fixed finite-dimensional target spaces \(\mathcal K_A,\mathcal K_B\) for the maps \(\mathcal F_T\), including the maps used later for the approximations.

Let \(R_i\) be the finite set of transcripts \(r=(r_0,\alpha,\gamma)\), where \(r_0\) ranges over its positive-probability values and \((\alpha,\gamma)\in\mathcal A^C\times\mathcal B^C\). Put \[\begin{gather*} w_i(r)=\nu_i(r_0)\theta(r),\qquad \Psi_{xy}^r=(\mathcal F_{F_x^\alpha}\otimes \mathcal F_{H_y^\gamma})\psi,\\ p_{xy}^r=\|\Psi_{xy}^r\|^2=\chi(F_x^\alpha,H_y^\gamma). \end{gather*}\] The last identity follows from \(\mathcal F_T^*\mathcal F_T=T\). The weights \(w_i(r)\) use counting measure on the answer strings; they are independent of \((x,y)\) and need not sum to one. Their sum is at most \(d_C\). The vector’s squared norm supplies the remaining probability of the tested answers.

We next exhibit measurements on \(\Psi_{xy}^r\) reproducing the conditional answers. Define the finer effects \[G_x^{\alpha,a} =\mathbb E[M_{\mathbf X}^{\alpha,a_i=a}\mid r_0,X_i=x],\qquad K_y^{\gamma,b} =\mathbb E[N_{\mathbf Y}^{\gamma,b_i=b}\mid r_0,Y_i=y],\] where an unmentioned answer is summed out. They are positive and satisfy \(\sum_aG_x^{\alpha,a}=F_x^\alpha\) and \(\sum_bK_y^{\gamma,b}=H_y^\gamma\). Lemma 7 provides POVMs \(\{\widetilde M_{r,x}^a\}\) on \(\mathcal K_A\) and \(\{\widetilde N_{r,y}^b\}\) on \(\mathcal K_B\) such that \[\mathcal F_{F_x^\alpha}^*\widetilde M_{r,x}^a \mathcal F_{F_x^\alpha}=G_x^{\alpha,a},\qquad \mathcal F_{H_y^\gamma}^*\widetilde N_{r,y}^b \mathcal F_{H_y^\gamma}=K_y^{\gamma,b}.\] If \(p_{xy}^r>0\), write \(\varphi_{xy}^r=\Psi_{xy}^r/\sqrt{p_{xy}^r}\). Then \[ \langle\varphi_{xy}^r| \widetilde M_{r,x}^a\otimes\widetilde N_{r,y}^b |\varphi_{xy}^r\rangle =\frac{\chi(G_x^{\alpha,a},K_y^{\gamma,b})}{p_{xy}^r}. \tag{16}\] To identify this probability, condition the original experiment on \(r_0,X_i=x,Y_i=y\). The unfixed Alice questions \(X_{>i}\) and Bob questions \(Y_{<i}\) are independent, with conditional laws determined by \(Y_{>i}\) and \(X_{<i}\) respectively. More explicitly, for positive-mass conditioning data their joint law is \[\Pr(X_{>i}=\mathbf u,Y_{<i}=\mathbf z\mid r_0,X_i=x,Y_i=y) =\prod_{j>i}\mu(u_j\mid y_j) \prod_{j<i}\mu(z_j\mid x_j).\] This is a statement about the original question law, before conditioning on tested answers. Neither product depends on the fresh pair \((x,y)\). Since Alice’s effect depends only on \(\mathbf X\), dropping the condition \(Y_i=y\) leaves its average unchanged; the analogous assertion holds for Bob after dropping \(X_i=x\). Hence averaging the joint effect \(M_{\mathbf X}^{\alpha,a_i=a}\otimes N_{\mathbf Y}^{\gamma,b_i=b}\) gives exactly \(G_x^{\alpha,a}\otimes K_y^{\gamma,b}\). Its coarse-grained probability is \(p_{xy}^r\). When \(\theta(r)=1\), conditioning further on the tested answers \((\alpha,\gamma)\) already implies \(E_C\). Thus (16) is the conditional distribution of the untested answers \((A_i,B_i)\) given \(E_C,r,X_i=x,Y_i=y\). Values with \(\theta(r)p_{xy}^r=0\) have no mass in that conditional experiment.

In particular, the joint law of the transcript and fresh questions conditioned on \(E_C\) is \[ \lambda_i(r,x,y)=\frac{w_i(r)\mu(x,y)\|\Psi_{xy}^r\|^2}{p}. \tag{17}\] Thus \(\lambda_i\) is a probability law even though the weights \(w_i\) alone are not. The measurements in (16) are local: Alice’s depends only on \((i,r,x)\) and Bob’s only on \((i,r,y)\). The transcript is an analysis variable, not information given to the players. A legal one-game strategy must start with a shared resource independent of the fresh questions and obtain any transcript information using only that resource and the player’s own question.

Local descriptions and their approximation error

The conditional vector \(\Psi_{xy}^r\) depends on both fresh questions. Replace the effect on the opposite player’s space by its conditional average to obtain two vectors with one-question descriptions: \[\Psi_x^r=(\mathcal F_{F_x^\alpha}\otimes \mathcal F_{H_x^\gamma})\psi,\qquad \Psi_y^r=(\mathcal F_{F_y^\alpha}\otimes \mathcal F_{H_y^\gamma})\psi.\] The first is determined by \((i,r,x)\) and the second by \((i,r,y)\). Both lie in the same fixed space \(\mathcal K_A\otimes\mathcal K_B\) as \(\Psi_{xy}^r\). Put \(p_x^r=\|\Psi_x^r\|^2\) and \(p_y^r=\|\Psi_y^r\|^2\). The identity \(\mathcal F_T^*\mathcal F_T=T\) and linearity of \(\chi\) give \[ \begin{gathered} p_{xy}^r=\chi(F_x^\alpha,H_y^\gamma),\qquad p_x^r=\sum_y\mu(y\mid x)p_{xy}^r,\qquad p_y^r=\sum_x\mu(x\mid y)p_{xy}^r,\\ \mathbb E_{\nu_i\mu}\sum_{\alpha,\gamma}\theta p_{xy}^r =\mathbb E_{\nu_i\mu}\sum_{\alpha,\gamma}\theta p_x^r =\mathbb E_{\nu_i\mu}\sum_{\alpha,\gamma}\theta p_y^r=p. \end{gathered} \tag{18}\] Here the total mass is \(p\) by (17); the two averaging identities give the same mass for the local descriptions.

Define the errors at mode \(i\) by \[ e_A(i)=\mathbb E_{\nu_i\mu}\sum_{\alpha,\gamma}\theta \|\Psi_{xy}^r-\Psi_y^r\|^2,\qquad e_B(i)=\mathbb E_{\nu_i\mu}\sum_{\alpha,\gamma}\theta \|\Psi_{xy}^r-\Psi_x^r\|^2. \tag{19}\] The subscript names the tensor factor that changes: \(e_A\) replaces Alice’s effect and compares with \(\Psi_y\), which Bob can describe from \((i,r,y)\); \(e_B\) replaces Bob’s effect and compares with \(\Psi_x\), which Alice can describe from \((i,r,x)\). We will bound their averages by an entropy telescope.

The change in the sampled question distribution

The vectors describe the experiment after conditioning on \(E_C\). A one-game strategy, however, receives questions with the original law \(\mu\). The following estimate bounds the resulting discrepancy. We use \(\|\cdot\|_1\) for the full \(\ell_1\) distance of probability distributions.

The resulting threshold rate

The larger of the exponents in (9) and (34) is valid. Lemma 2 gives the sharper probability zero when \(v=0\).