Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Threshold parallel repetition for finite-dimensional entangled games

OpenAI

Published Oct 6, 2026• 0 citations
Publisher

Abstract

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. The result allows arbitrary correlated question distributions and holds for every 0\lt \delta\lt 1-v and k\ge1. Its universal rate is proportional to \delta^5/(1+\log(|\mathcal A||\mathcal B|)), where \mathcal A,\mathcal B are the answer alphabets. For each fixed question distribution, we also obtain an explicit cubic rate in \delta.

DOI
10.83295/rdw7-54cx

Related papers

Parallel Repetition for Entangled Games via Conditional Relative Entropy

Rahul Jain

We give a proof of the cubic parallel-repetition bound for finite two-player entangled games using quantum conditional relative entropy. For a game with entangled value $1-\varepsilon<1$ and answer alphabets $\mathcal A,\mathcal B$, its $n$-fold repeated value is at most \[ \exp[-Ω(\varepsilon^3n/L)],\qquad L:=\max\{1,\log(|\mathcal A||\mathcal B|)\}, \] for every $n\ge1$. This recovers Song's cubic rate. We also prove a threshold bound: the probability of winning a fraction at least $1-\varepsilon+δ$ is at most $\exp[-Ω(δ^5n/(\varepsilon^2L))]$ for $0<δ\le\varepsilon$. Our information charge is the decrease in relative entropy when a question reference is discarded. Our comparison states preserve the original conditional question law. A chain rule bounds the coordinate charges using the cost of conditioning on checked wins and retaining checked answers. Our main lemma converts small charges into nearby pure-state descriptions and local corrections, each depending only on one player's question. Together with Song's sampler, these enable approximate local preparation of the conditioned workspace.

quant-pharXiv:2610.21410•Oct 16, 2026•0 citations

A Parallel Repetition Theorem for Entangled Projection Games

Irit Dinur, David Steurer, Thomas Vidick

We study the behavior of the entangled value of two-player one-round projection games under parallel repetition. We show that for any projection game G of entangled value 1 - εc)k), for some universal constant c ≥ 1. Previously parallel repetition with an exponential decay in k was only known for the case of XOR and unique games. To prove the theorem we extend an analytical framework recently introduced by Dinur and Steurer for the study of the classical value of projection games under parallel repetition. Our proof, as theirs, relies on the introduction of a simple relaxation of the entangled value that is perfectly multiplicative. The main technical component of the proof consists in showing that the relaxed value remains tightly connected to the entangled value, thereby establishing the parallel repetition theorem. More generally, we obtain results on the behavior of the entangled value under products of arbitrary (not necessarily identical) projection games. Relating our relaxed value to the entangled value is done by giving an algorithm for converting a relaxed variant of quantum strategies that we call “vector quantum strategy” to a quantum strategy. The algorithm is considerably simpler in case the bipartite distribution of questions in the game has good expansion properties. When this is not the case, rounding relies on a quantum analogue of Holenstein's correlated sampling lemma which may be of independent interest. Our “quantum correlated sampling lemma” generalizes results of van Dam and Hayden on universal embezzlement to the following approximate scenario: two isolated parties, given classical descriptions of arbitrary bipartite states |ψ〉, |φ〉 respectively such that |ψ〉 ≈ |φ〉, are able to locally generate a joint entangled state|Ψ〉 ≈ |ψ〉 ≈ |φ〉 using an initial entangled state that is independent of their inputs.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2014•29 citations

A parallel repetition theorem for entangled projection games

Irit Dinur, David Steurer, Thomas Vidick

We study the behavior of the entangled value of two-player one-round projection games under parallel repetition. We show that for any projection game $G$ of entangled value 1-eps < 1, the value of the $k$-fold repetition of G goes to zero as O((1-eps^c)^k), for some universal constant c\geq 1. Previously parallel repetition with an exponential decay in $k$ was only known for the case of XOR and unique games. To prove the theorem we extend an analytical framework recently introduced by Dinur and Steurer for the study of the classical value of projection games under parallel repetition. Our proof, as theirs, relies on the introduction of a simple relaxation of the entangled value that is perfectly multiplicative. The main technical component of the proof consists in showing that the relaxed value remains tightly connected to the entangled value, thereby establishing the parallel repetition theorem. More generally, we obtain results on the behavior of the entangled value under products of arbitrary (not necessarily identical) projection games. Relating our relaxed value to the entangled value is done by giving an algorithm for converting a relaxed variant of quantum strategies that we call "vector quantum strategy" to a quantum strategy. The algorithm is considerably simpler in case the bipartite distribution of questions in the game has good expansion properties. When this is not the case, rounding relies on a quantum analogue of Holenstein's correlated sampling lemma which may be of independent interest. Our "quantum correlated sampling lemma" generalizes results of van Dam and Hayden on universal embezzlement.

arXiv:1310.4113•Oct 15, 2013•5 citations

Parallel Repetition in Projection Games and a Concentration Bound

Anup Rao

A two-player game is played by cooperating players who are not allowed to communicate. A referee asks the players questions sampled from some known distribution and decides whether they win or not based on a known predicate of the questions and the players' answers. The parallel repetition of the game is the game in which the referee samples n independent pairs of questions and sends the corresponding questions to the players simultaneously. If the players cannot win the original game with probability better than $(1-\epsilon)$, what's the best they can do in the repeated game? We improve earlier results of [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803] and [T. Holenstein, Theory Comput., 5 (2009), pp. 141–172], who showed that the players cannot win all copies in the repeated game with probability better than $(1-\epsilon/2)^{\Omega(n\epsilon^2/c)}$ (here c is the length of the answers in the game), in the following ways: (i) We show that the probability of winning all copies is $(1-\epsilon/2)^{\Omega(\epsilon n)}$ as long as the game is a “projection game,” the type of game most commonly used in hardness of approximation results. (ii) We prove a concentration bound for parallel repetition (of general games) showing that for any constant $0<\delta <\epsilon$, the probability that the players win a $(1-\epsilon+\delta)$ fraction of the games in the parallel repetition is at most $\exp\left(-\Omega_{\epsilon}(\delta^3 n/c)\right)$ (here the constant may depend on $\epsilon$); our result has applications to testing Bell inequalities, since it implies that the parallel repetition of the CHSH game can be used to get an experiment that has a very large classical versus quantum gap. Our first bound is independent of the answer length and has a better dependence on $\epsilon$. By the recent work of Raz [Proceedings of the $49$th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 369–373], this bound is tight. Our bound gives a generic way to improve the soundness of a probabilistically checkable proof (PCP), in a way that is independent of the answer length of the PCP. Using it, for every k, one can convert any q query PCP with answer length c, size $sc$, and soundness $(1-\epsilon)$ into a two-query PCP with answer length $ck$, size $O(ck (2s)^k)$, and soundness $(1-\epsilon/2q)^{\Omega(\epsilon k/q)}$. Another consequence of our bound is that the unique games conjecture of Khot [Proceedings of the $34$th Annual ACM Symposium on Theory of Computing, 2002, pp. 767–775] can now be shown to be equivalent to the following a priori weaker conjecture: There is an unbounded increasing function $f:\mathbb{R}^+\rightarrow \mathbb{R}^+$ such that for every $\epsilon> 0$, there exists an alphabet size $M(\epsilon)$ for which it is NP-hard to distinguish a unique game with alphabet size M in which a $(1-\epsilon^2)$ fraction of the constraints can be satisfied from one in which a $(1-\epsilon f(1/\epsilon))$ fraction of the constraints can be satisfied.

SIAM Journal on Computing•May 17, 2008•150 citations

Parallel Repetition of Free Entangled Games: Simplification and Improvements

André Chailloux, Scarpa, Giannicola

In a two-player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs/outputs. The entangled value $ω^*(G)$ of a game $G$ is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs. The $n$-fold parallel repetition $G^n$ of $G$ consists of $n$ instances of $G$ where Alice and Bob receive all the inputs at the same time and must produce all the outputs at the same time. They win $G^n$ if they win each instance of $G$. Recently, there has been a series of works showing parallel repetition with exponential decay for projection games [DSV13], games on the uniform distribution [CS14] and for free games, i.e. games on a product distribution [JPY13]. This article is meant to be a follow up of [CS14], where we improve and simplify several parts of our previous paper. Our main result is that for any free game $G$ with value $ω^*(G)=1-\varepsilon$, we have $ω^*(G^n) \le (1 - \varepsilon^2)^{Ω(\frac{n}{\log(l)})}$ where $l$ is the size of the output set of the game. This result improves on both the results in [JPY13] and [CS14]. The framework we use can also be extended to free projection games. We show that for a free projection game $G$ with value $ω^*(G)=1-\varepsilon$, we have $ω^*(G^n) \le (1 - \varepsilon)^{Ω(n)}$.

arXiv:1410.4397•Oct 16, 2014•7 citations

Non-signalling parallel repetition using de Finetti reductions

Rotem Arnon-Friedman, Renato Renner, Thomas Vidick

In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game $G$ with optimal winning probability $1-α$ and its repeated version $G^n$ (in which $n$ games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this work the case of multiplayer non-signalling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero probability to be asked) with any number of players we prove a threshold theorem stating that the probability that non-signalling players win more than a fraction $1-α+β$ of the $n$ games is exponentially small in $nβ^2$, for every $0\leq β\leq α$. For games with incomplete support we derive a similar statement, for a slightly modified form of repetition. The result is proved using a new technique, based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.

arXiv:1411.1582•Nov 6, 2014•6 citations
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. The result allows arbitrary correlated question distributions and holds for every 0\lt \delta\lt 1-v and k\ge1. Its universal rate is proportional to \delta^5/(1+\log(|\mathcal A||\mathcal B|)), where \mathcal A,\mathcal B are the answer alphabets. For each fixed question distribution, we also obtain an explicit cubic rate in \delta.
We give a proof of the cubic parallel-repetition bound for finite two-player entangled games using quantum conditional relative entropy. For a game with entangled value 1−ε<11-\varepsilon<11−ε<1 and answer alphabets A,B\mathcal A,\mathcal BA,B, its nnn-fold repeated value is at most exp⁡[−Ω(ε3n/L)],L:=max⁡{1,log⁡(∣A∣∣B∣)}, \exp[-Ω(\varepsilon^3n/L)],\qquad L:=\max\{1,\log(|\mathcal A||\mathcal B|)\}, exp[−Ω(ε3n/L)],L:=max{1,log(∣A∣∣B∣)}, for every n≥1n\ge1n≥1. This recovers Song's cubic rate. We also prove a threshold bound: the probability of winning a fraction at least 1−ε+δ1-\varepsilon+δ1−ε+δ is at most exp⁡[−Ω(δ5n/(ε2L))]\exp[-Ω(δ^5n/(\varepsilon^2L))]exp[−Ω(δ5n/(ε2L))] for 0<δ≤ε0<δ\le\varepsilon0<δ≤ε. Our information charge is the decrease in relative entropy when a question reference is discarded. Our comparison states preserve the original conditional question law. A chain rule bounds the coordinate charges using the cost of conditioning on checked wins and retaining checked answers. Our main lemma converts small charges into nearby pure-state descriptions and local corrections, each depending only on one player's question. Together with Song's sampler, these enable approximate local preparation of the conditioned workspace.
We study the behavior of the entangled value of two-player one-round projection games under parallel repetition. We show that for any projection game G of entangled value 1 - εc)k), for some universal constant c ≥ 1. Previously parallel repetition with an exponential decay in k was only known for the case of XOR and unique games. To prove the theorem we extend an analytical framework recently introduced by Dinur and Steurer for the study of the classical value of projection games under parallel repetition. Our proof, as theirs, relies on the introduction of a simple relaxation of the entangled value that is perfectly multiplicative. The main technical component of the proof consists in showing that the relaxed value remains tightly connected to the entangled value, thereby establishing the parallel repetition theorem. More generally, we obtain results on the behavior of the entangled value under products of arbitrary (not necessarily identical) projection games. Relating our relaxed value to the entangled value is done by giving an algorithm for converting a relaxed variant of quantum strategies that we call “vector quantum strategy” to a quantum strategy. The algorithm is considerably simpler in case the bipartite distribution of questions in the game has good expansion properties. When this is not the case, rounding relies on a quantum analogue of Holenstein's correlated sampling lemma which may be of independent interest. Our “quantum correlated sampling lemma” generalizes results of van Dam and Hayden on universal embezzlement to the following approximate scenario: two isolated parties, given classical descriptions of arbitrary bipartite states |ψ〉, |φ〉 respectively such that |ψ〉 ≈ |φ〉, are able to locally generate a joint entangled state|Ψ〉 ≈ |ψ〉 ≈ |φ〉 using an initial entangled state that is independent of their inputs.
We study the behavior of the entangled value of two-player one-round projection games under parallel repetition. We show that for any projection game GGG of entangled value 1-eps < 1, the value of the kkk-fold repetition of G goes to zero as O((1-eps^c)^k), for some universal constant c\geq 1. Previously parallel repetition with an exponential decay in kkk was only known for the case of XOR and unique games. To prove the theorem we extend an analytical framework recently introduced by Dinur and Steurer for the study of the classical value of projection games under parallel repetition. Our proof, as theirs, relies on the introduction of a simple relaxation of the entangled value that is perfectly multiplicative. The main technical component of the proof consists in showing that the relaxed value remains tightly connected to the entangled value, thereby establishing the parallel repetition theorem. More generally, we obtain results on the behavior of the entangled value under products of arbitrary (not necessarily identical) projection games. Relating our relaxed value to the entangled value is done by giving an algorithm for converting a relaxed variant of quantum strategies that we call "vector quantum strategy" to a quantum strategy. The algorithm is considerably simpler in case the bipartite distribution of questions in the game has good expansion properties. When this is not the case, rounding relies on a quantum analogue of Holenstein's correlated sampling lemma which may be of independent interest. Our "quantum correlated sampling lemma" generalizes results of van Dam and Hayden on universal embezzlement.
A two-player game is played by cooperating players who are not allowed to communicate. A referee asks the players questions sampled from some known distribution and decides whether they win or not based on a known predicate of the questions and the players' answers. The parallel repetition of the game is the game in which the referee samples n independent pairs of questions and sends the corresponding questions to the players simultaneously. If the players cannot win the original game with probability better than (1−ϵ)(1-\epsilon)(1−ϵ), what's the best they can do in the repeated game? We improve earlier results of [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803] and [T. Holenstein, Theory Comput., 5 (2009), pp. 141–172], who showed that the players cannot win all copies in the repeated game with probability better than (1−ϵ/2)Ω(nϵ2/c)(1-\epsilon/2)^{\Omega(n\epsilon^2/c)}(1−ϵ/2)Ω(nϵ2/c) (here c is the length of the answers in the game), in the following ways: (i) We show that the probability of winning all copies is (1−ϵ/2)Ω(ϵn)(1-\epsilon/2)^{\Omega(\epsilon n)}(1−ϵ/2)Ω(ϵn) as long as the game is a “projection game,” the type of game most commonly used in hardness of approximation results. (ii) We prove a concentration bound for parallel repetition (of general games) showing that for any constant 0<δ<ϵ0<\delta <\epsilon0<δ<ϵ, the probability that the players win a (1−ϵ+δ)(1-\epsilon+\delta)(1−ϵ+δ) fraction of the games in the parallel repetition is at most exp⁡(−Ωϵ(δ3n/c))\exp\left(-\Omega_{\epsilon}(\delta^3 n/c)\right)exp(−Ωϵ​(δ3n/c)) (here the constant may depend on ϵ\epsilonϵ); our result has applications to testing Bell inequalities, since it implies that the parallel repetition of the CHSH game can be used to get an experiment that has a very large classical versus quantum gap. Our first bound is independent of the answer length and has a better dependence on ϵ\epsilonϵ. By the recent work of Raz [Proceedings of the 494949th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 369–373], this bound is tight. Our bound gives a generic way to improve the soundness of a probabilistically checkable proof (PCP), in a way that is independent of the answer length of the PCP. Using it, for every k, one can convert any q query PCP with answer length c, size scscsc, and soundness (1−ϵ)(1-\epsilon)(1−ϵ) into a two-query PCP with answer length ckckck, size O(ck(2s)k)O(ck (2s)^k)O(ck(2s)k), and soundness (1−ϵ/2q)Ω(ϵk/q)(1-\epsilon/2q)^{\Omega(\epsilon k/q)}(1−ϵ/2q)Ω(ϵk/q). Another consequence of our bound is that the unique games conjecture of Khot [Proceedings of the 343434th Annual ACM Symposium on Theory of Computing, 2002, pp. 767–775] can now be shown to be equivalent to the following a priori weaker conjecture: There is an unbounded increasing function f:R+→R+f:\mathbb{R}^+\rightarrow \mathbb{R}^+f:R+→R+ such that for every ϵ>0\epsilon> 0ϵ>0, there exists an alphabet size M(ϵ)M(\epsilon)M(ϵ) for which it is NP-hard to distinguish a unique game with alphabet size M in which a (1−ϵ2)(1-\epsilon^2)(1−ϵ2) fraction of the constraints can be satisfied from one in which a (1−ϵf(1/ϵ))(1-\epsilon f(1/\epsilon))(1−ϵf(1/ϵ)) fraction of the constraints can be satisfied.
In a two-player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs/outputs. The entangled value ω∗(G)ω^*(G)ω∗(G) of a game GGG is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs. The nnn-fold parallel repetition GnG^nGn of GGG consists of nnn instances of GGG where Alice and Bob receive all the inputs at the same time and must produce all the outputs at the same time. They win GnG^nGn if they win each instance of GGG. Recently, there has been a series of works showing parallel repetition with exponential decay for projection games [DSV13], games on the uniform distribution [CS14] and for free games, i.e. games on a product distribution [JPY13]. This article is meant to be a follow up of [CS14], where we improve and simplify several parts of our previous paper. Our main result is that for any free game GGG with value ω∗(G)=1−εω^*(G)=1-\varepsilonω∗(G)=1−ε, we have ω∗(Gn)≤(1−ε2)Ω(nlog⁡(l))ω^*(G^n) \le (1 - \varepsilon^2)^{Ω(\frac{n}{\log(l)})}ω∗(Gn)≤(1−ε2)Ω(log(l)n​) where lll is the size of the output set of the game. This result improves on both the results in [JPY13] and [CS14]. The framework we use can also be extended to free projection games. We show that for a free projection game GGG with value ω∗(G)=1−εω^*(G)=1-\varepsilonω∗(G)=1−ε, we have ω∗(Gn)≤(1−ε)Ω(n)ω^*(G^n) \le (1 - \varepsilon)^{Ω(n)}ω∗(Gn)≤(1−ε)Ω(n).
In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game GGG with optimal winning probability 1−α1-α1−α and its repeated version GnG^nGn (in which nnn games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this work the case of multiplayer non-signalling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero probability to be asked) with any number of players we prove a threshold theorem stating that the probability that non-signalling players win more than a fraction 1−α+β1-α+β1−α+β of the nnn games is exponentially small in nβ2nβ^2nβ2, for every 0≤β≤α0\leq β\leq α0≤β≤α. For games with incomplete support we derive a similar statement, for a slightly modified form of repetition. The result is proved using a new technique, based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.