Threshold parallel repetition for finite-dimensional entangled games

1 Introduction

A repeated game allows two players to coordinate their answers across many independently sampled question pairs. 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 asks whether the probability that the fraction of wins exceeds the single-game value by any fixed positive amount is exponentially small. Such a bound permits error amplification even when an intended strategy sometimes loses individual games.

1.1 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

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

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

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 [17, 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

In particular, a singleton component contributes zero. Corollary 5.2 proves, under the same hypotheses and for every k\ge1, the complementary estimate

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.1 gives the sharper probability zero.

1.2 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 [16]. Holenstein’s information-theoretic proof introduced correlated sampling into this argument and improved its quantitative dependence on the gap from one [9]. Rao then proved exponential concentration above the classical value for general games [15, 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 [5]. Kempe, Regev, and Toner proved exponential repetition for unique games, whose constraints are permutations between the answer sets [11]. 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 [7]. Jain, Pereszlényi, and Yao treated free games, where the players’ questions are independently distributed [10]; Chailloux and Scarpa subsequently improved the rate [4]. 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 [3, 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 [18, Theorem 1]. His proof combines conditioning with classical and quantum correlated sampling; its tested-coordinate selection already samples indices with replacement [18, Proposition 9, full version]. Bavarian, Vidick, and Yuen obtained exponential amplification by anchoring, a transformation that adds questions to the game [2]. Their threshold theorem concerns these anchored games [1, Section 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 [13]. 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 [17]. 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.1.

1.3 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

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 2.4, bounds the average success on the remaining coordinates by

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 6.1 applies the threshold theorem to amplify both completeness and soundness.

2 From conditioning to a threshold bound

Fix a repeated strategy and write v=\omega^*(G) and d=|\mathcal A||\mathcal B|. For a set C\subseteq[k], put

For C\subsetneq[k] with p_C>0, define its conditioning cost by

For a target excess 0<\delta<1-v, the analytic task is to find a budget T>0 such that \tau(C)\le T forces the average win rate outside C, conditioned on E_C, to be at most v+\delta/4. We prove that this implication, uniformly over repetition lengths and strategies, yields exponential rate \delta T/(16(1+\log d)) whenever T\le\delta/4. Thus the quantitative role of a conditioning estimate is entirely determined by the budget it permits.

The proof has two steps. If a large upper tail persists, sampling a short list of indices selects a tested set of sufficiently large probability whose conditional win rate is too high. This gives the bound for all sufficiently large repetition lengths. Independent tensor copies then extend the same rate to every length. The selection itself uses only the joint law of the binary win indicators.

The passage from tested-coordinate conditioning to concentration has precedents in Rao’s classical proof [15, Section 8] and in the anchored entangled-game theorem [1, Section 5.4]. Sampling tested indices with replacement also appears in Yuen’s proof of Proposition 9 in the full version of [18]. The transfer below separates this probabilistic step from the choice of a conditioning bound.

2.1 Marginal success probabilities

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

2.2 Selecting the tested coordinates

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

2.3 An exponential rate for every repetition length

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

2.4 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 [13]; 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.

3 A common purification of effects

Conditioning on answers replaces the shared state by local positive operators applied to that state. We need purifications of these operators that are close whenever an operator entropy gap is small. For positive definite operators, this gap is an average of Petz’s operator Bregman divergence [14]; related resolvent estimates appear in Kim [12]. The following construction provides all purifications in a common space and will let us retain the original answer measurements. The purification formulation and its Jensen estimate are given in [13, Chapter 6, Definition 4.2, Lemma 4.3, and Appendix A.4]; we include the proof, including its finite-dimensional reduction.

For a finite-dimensional complex Hilbert space \mathcal H, an effect is a self-adjoint operator T with 0\preceq T\preceq I. Put f(t)=t\log t for t>0 and f(0)=0, and define

The inverse in this expression exists for every s>0, including when T has a kernel.

The common codomain is essential: compressing different operators separately would not in general preserve their distances. In our application the number of effects is finite, although their number and the resulting dimension need not have a uniform bound.

The transport of answer effects below follows the ideal-state extraction in [13, Chapter 6, Lemma 3.2 and Appendix A.1].

In particular, if \Psi=(\mathcal F_T\otimes\mathcal F_S)\psi and \sum_aG_a=T, \sum_bH_b=S, the transported measurements satisfy

Thus the common purification preserves the exact answer probabilities, not just the norms of the conditioned vectors.

4 Conditioning on a tested set

Fix a finite-dimensional strategy for the k-fold game, with state \psi and POVMs \{M_{\mathbf x}^{\mathbf a}\} and \{N_{\mathbf y}^{\mathbf b}\}. Let C\subseteq[k] be a set of tested coordinates and let

Assume that m=k-|C|\ge1, and put

We construct a vector and local measurements that reproduce the conditional answers at an untested coordinate. Two approximating vectors, one determined by each player’s question and a transcript, will have total squared error at most 2p\tau on average. These comparisons let Section 5 replace the conditional vector by a fixed state on each support component. Throughout this section, conditional expectations of operators use the original, unconditioned question distribution \mu^{\otimes k}. We adapt the weighted reveal argument of [13, Chapter 6, Section 4], using the fixed ordering below.

4.1 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

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

and the testing mask

For C=\varnothing there is one pair of empty answer strings and the empty product is 1. Write

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,

A mode is an index i\in[m]. Delete its question from the flag and set

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

We use these formulas only on positive marginal probabilities. In each conditional ensemble, zero weights are omitted before applying Lemma 3.1. 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,

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.

4.2 The conditional vector and its measurements

Apply the common finite-dimensional compression in Lemma 3.1 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

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

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 3.2 provides POVMs \{\widetilde M_{r,x}^a\} on \mathcal K_A and \{\widetilde N_{r,y}^b\} on \mathcal K_B such that

If p_{xy}^r>0, write \varphi_{xy}^r=\Psi_{xy}^r/\sqrt{p_{xy}^r}. Then

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

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

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.

4.3 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:

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

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

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.

4.4 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.

5 A cubic bound for a fixed question distribution

The exposure estimates also give a direct route to threshold repetition when constants may depend on the question distribution. Within each connected component of its support, we replace the conditional vector by one reference vector. Adjacent question pairs have a common local approximation, so the cost of this replacement is controlled along paths in the support. The resulting conditioning error is of square-root order, which gives a cubic threshold rate. The construction uses the exposure vectors and transported answer measurements of Section 4.

The connection-graph viewpoint of Dinur, Harsha, Venkat, and Yuen [6] helped motivate this fixed-support approach. The quantum common-vector replacement by a component root and the explicit cubic coefficient are proved here, rather than imported from their classical parallel-repetition theorem.

For a finite question distribution \mu, let

Join two vertices of H when they share either question. Let H_j be the connected components, and define

This constant depends on the positive masses of \mu, as well as its support. In particular, \kappa_\mu=0 when every component is a singleton.

For a fixed \mu, (26) is O_\mu(\sqrt\tau+\tau). Song’s estimate in Proposition 2.4 has fourth-root error with a universal constant. Where both apply, one may use the smaller error. The proof above does not use Song’s sampler.

5.1 The resulting threshold rate

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

6 Two-sided error amplification

A threshold between completeness and soundness amplifies both guarantees without changing the number of players or rounds. Tensor copies of a single-game strategy give completeness; Theorem 1.1 controls soundness even for joint strategies across all repetitions.

For polynomial-time verifier families with efficiently computable rational bounds c,s, inverse-polynomial gap c-s, and polynomial answer bit-length, polynomially many repetitions therefore make both errors exponentially small in the input length, while preserving two provers, one round, and classical messages. Indeed, 1+\log d is polynomially bounded and the ceiling threshold is efficiently computable.