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

arXiv:2211.13741 · Annual Symposium on Foundations of Computer Science

Parallel Repetition for the GHZ Game: Exponential Decay

Mark Braverman, Subhash Khot, Dor Minzer

Published Nov 6, 2023• 7 citations
arXivHTMLPDF

Abstract

We show that the value of the n-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

DOI
10.1109/focs57990.2023.00080

Related papers

Parallel Repetition for the GHZ Game: Exponential Decay

Mark Braverman, Subhash Khot, Dor Minzer

Abstract. We show that the value of the [Formula: see text]-fold repeated GHZ game is at most [Formula: see text], improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup-type questions from additive combinatorics.

SIAM Journal on Computing•Feb 4, 2025•1 citation

Parallel Repetition for the GHZ Game: A Simpler Proof

Uma Girish, Justin Holmgren, Mittal, Kunal +2 more

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the $n$-fold GHZ game is at most $n^{-Ω(1)}$. This was first established by Holmgren and Raz [HR20]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [GHZ89] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [DHVY17] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.

arXiv:2107.06156•Leibniz international proceedings in informatics•Jan 1, 2021•5 citations

Multiplayer Parallel Repetition for Expanding Games

Irit Dinur, Prahladh Harsha, Rakesh Venkat +1 more

We investigate the value of parallel repetition of one-round games with any number of players k>=2. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are *connected* in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.

arXiv:1610.08349•Leibniz international proceedings in informatics•Oct 26, 2016•18 citations

A Parallel Repetition Theorem for the GHZ Game

Justin Holmgren, Ran Raz

We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel $t$ times is at most $t^{-Ω(1)}$. Previously, only a bound of $\approx \frac{1}{α(t)}$, where $α$ is the inverse Ackermann function, was known. The GHZ game was recently identified by Dinur, Harsha, Venkat and Yuen as a multi-player game where all existing techniques for proving strong bounds on the value of the parallel repetition of the game fail. Indeed, to prove our result we use a completely new proof technique. Dinur, Harsha, Venkat and Yuen speculated that progress on bounding the value of the parallel repetition of the GHZ game may lead to further progress on the general question of parallel repetition of multi-player games. They suggested that the strong correlations present in the GHZ question distribution represent the "hardest instance" of the multi-player parallel repetition problem. Another motivation for studying the parallel repetition of the GHZ game comes from the field of quantum information. The GHZ game, first introduced by Greenberger, Horne and Zeilinger, is a central game in the study of quantum entanglement and has been studied in numerous works. For example, it is used for testing quantum entanglement and for device-independent quantum cryptography. In such applications a game is typically repeated to reduce the probability of error, and hence bounds on the value of the parallel repetition of the game may be useful.

arXiv:2008.05059•Aug 12, 2020•13 citations

Improved Parallel Repetition for GHZ-Supported Games via Spreadness

Yang P. Liu, Shachar Lovett, Mittal, Kunal

We prove that for any 3-player game $\mathcal G$, whose query distribution has the same support as the GHZ game (i.e., all $x,y,z\in \{0,1\}$ satisfying $x+y+z=0\pmod{2}$), the value of the $n$-fold parallel repetition of $\mathcal G$ decays exponentially fast: \[ \text{val}(\mathcal G^{\otimes n}) \leq \exp(-n^c)\] for all sufficiently large $n$, where $c>0$ is an absolute constant. We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant $ε>0$, the probability that the players win at least a $\left(\frac{3}{4}+ε\right)$ fraction of the $n$ coordinates is at most $\exp(-n^c)$, where $c=c(ε)>0$ is a constant. In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order $n^{-Ω(1)}$. Our key technical tool is the notion of \emph{algebraic spreadness} adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions.

arXiv:2602.09290•Leibniz international proceedings in informatics•Jan 1, 2026•0 citations

A Counterexample to Strong Parallel Repetition

Ran Raz

The parallel repetition theorem states that, for any two-prover game with value $1-\epsilon$ (for, say, $\epsilon\leq1/2$), the value of the game repeated in parallel n times is at most $(1-\epsilon^c)^{\Omega(n/s)}$, where s is the answer's length (of the original game) and c is a universal constant [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803]. Several researchers asked whether this bound could be improved to $(1-\epsilon)^{\Omega(n/s)}$; this question is usually referred to as the strong parallel repetition problem. We show that the answer to this question is negative. More precisely, we consider the odd cycle game of size m, a two-prover game with value $1-1/2m$. We show that the value of the odd cycle game repeated in parallel n times is at least $1-(1/m)\cdot O(\sqrt{n})$. This implies that, for large enough n (say, $n\geq\Omega(m^2)$), the value of the odd cycle game repeated in parallel n times is at least $(1-1/4m^2)^{O(n)}$. Thus the following hold. 1. For parallel repetition of general games, the bounds of $(1-\epsilon^c)^{\Omega(n/s)}$ given in [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803; T. Holenstein, in Proceedings of STOC 2002, ACM, New York, 2002, pp. 767–775] are of the right form, up to determining the exact value of the constant $c\geq2$. 2. For parallel repetition of XOR games, unique games, and projection games, the bounds of $(1-\epsilon^2)^{\Omega(n)}$ given in [U. Feige, G. Kindler, and R. O'Donnell, in Proceedings of CCC 2007, IEEE Computer Society, Washington, DC, 2007, pp. 179–192] (for XOR games) and in [A. Rao, in Proceedings of STOC 2008, ACM, New York, 2008, pp. 1–10] (for unique and projection games) are tight. 3. For parallel repetition of the odd cycle game, the bound of $1-(1/m)\cdot\tilde{\Omega}(\sqrt{n})$ given in [U. Feige, G. Kindler, and R. O'Donnell, in Proceedings of CCC 2007, IEEE Computer Society, Washington, DC, 2007, pp. 179–192] is almost tight. A major motivation for the recent interest in the strong parallel repetition problem is that a strong parallel repetition theorem would have implied that the unique game conjecture is equivalent to the NP hardness of distinguishing between instances of Max-Cut that are at least $1-\epsilon^2$ satisfiable from instances that are at most $1-(2/\pi)\cdot\epsilon$ satisfiable. Our results suggest that this cannot be proved just by improving the known bounds on parallel repetition.

SIAM Journal on Computing•Oct 1, 2008•84 citations
We show that the value of the n-fold repeated GHZ game is at most 2−Ω(n)2^{-\Omega(n)}2−Ω(n), improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.
We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the nnn-fold GHZ game is at most n−Ω(1)n^{-Ω(1)}n−Ω(1). This was first established by Holmgren and Raz [HR20]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [GHZ89] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [DHVY17] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.
We investigate the value of parallel repetition of one-round games with any number of players k>=2. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are *connected* in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.
We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel ttt times is at most t−Ω(1)t^{-Ω(1)}t−Ω(1). Previously, only a bound of ≈1α(t)\approx \frac{1}{α(t)}≈α(t)1​, where ααα is the inverse Ackermann function, was known. The GHZ game was recently identified by Dinur, Harsha, Venkat and Yuen as a multi-player game where all existing techniques for proving strong bounds on the value of the parallel repetition of the game fail. Indeed, to prove our result we use a completely new proof technique. Dinur, Harsha, Venkat and Yuen speculated that progress on bounding the value of the parallel repetition of the GHZ game may lead to further progress on the general question of parallel repetition of multi-player games. They suggested that the strong correlations present in the GHZ question distribution represent the "hardest instance" of the multi-player parallel repetition problem. Another motivation for studying the parallel repetition of the GHZ game comes from the field of quantum information. The GHZ game, first introduced by Greenberger, Horne and Zeilinger, is a central game in the study of quantum entanglement and has been studied in numerous works. For example, it is used for testing quantum entanglement and for device-independent quantum cryptography. In such applications a game is typically repeated to reduce the probability of error, and hence bounds on the value of the parallel repetition of the game may be useful.
We prove that for any 3-player game G\mathcal GG, whose query distribution has the same support as the GHZ game (i.e., all x,y,z∈{0,1}x,y,z\in \{0,1\}x,y,z∈{0,1} satisfying x+y+z=0(mod2)x+y+z=0\pmod{2}x+y+z=0(mod2)), the value of the nnn-fold parallel repetition of G\mathcal GG decays exponentially fast: val(G⊗n)≤exp⁡(−nc) \text{val}(\mathcal G^{\otimes n}) \leq \exp(-n^c)val(G⊗n)≤exp(−nc) for all sufficiently large nnn, where c>0c>0c>0 is an absolute constant. We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant ε>0ε>0ε>0, the probability that the players win at least a (34+ε)\left(\frac{3}{4}+ε\right)(43​+ε) fraction of the nnn coordinates is at most exp⁡(−nc)\exp(-n^c)exp(−nc), where c=c(ε)>0c=c(ε)>0c=c(ε)>0 is a constant. In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order n−Ω(1)n^{-Ω(1)}n−Ω(1). Our key technical tool is the notion of \emph{algebraic spreadness} adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions.
The parallel repetition theorem states that, for any two-prover game with value 1−ϵ1-\epsilon1−ϵ (for, say, ϵ≤1/2\epsilon\leq1/2ϵ≤1/2), the value of the game repeated in parallel n times is at most (1−ϵc)Ω(n/s)(1-\epsilon^c)^{\Omega(n/s)}(1−ϵc)Ω(n/s), where s is the answer's length (of the original game) and c is a universal constant [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803]. Several researchers asked whether this bound could be improved to (1−ϵ)Ω(n/s)(1-\epsilon)^{\Omega(n/s)}(1−ϵ)Ω(n/s); this question is usually referred to as the strong parallel repetition problem. We show that the answer to this question is negative. More precisely, we consider the odd cycle game of size m, a two-prover game with value 1−1/2m1-1/2m1−1/2m. We show that the value of the odd cycle game repeated in parallel n times is at least 1−(1/m)⋅O(n)1-(1/m)\cdot O(\sqrt{n})1−(1/m)⋅O(n​). This implies that, for large enough n (say, n≥Ω(m2)n\geq\Omega(m^2)n≥Ω(m2)), the value of the odd cycle game repeated in parallel n times is at least (1−1/4m2)O(n)(1-1/4m^2)^{O(n)}(1−1/4m2)O(n). Thus the following hold. 1. For parallel repetition of general games, the bounds of (1−ϵc)Ω(n/s)(1-\epsilon^c)^{\Omega(n/s)}(1−ϵc)Ω(n/s) given in [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803; T. Holenstein, in Proceedings of STOC 2002, ACM, New York, 2002, pp. 767–775] are of the right form, up to determining the exact value of the constant c≥2c\geq2c≥2. 2. For parallel repetition of XOR games, unique games, and projection games, the bounds of (1−ϵ2)Ω(n)(1-\epsilon^2)^{\Omega(n)}(1−ϵ2)Ω(n) given in [U. Feige, G. Kindler, and R. O'Donnell, in Proceedings of CCC 2007, IEEE Computer Society, Washington, DC, 2007, pp. 179–192] (for XOR games) and in [A. Rao, in Proceedings of STOC 2008, ACM, New York, 2008, pp. 1–10] (for unique and projection games) are tight. 3. For parallel repetition of the odd cycle game, the bound of 1−(1/m)⋅Ω~(n)1-(1/m)\cdot\tilde{\Omega}(\sqrt{n})1−(1/m)⋅Ω~(n​) given in [U. Feige, G. Kindler, and R. O'Donnell, in Proceedings of CCC 2007, IEEE Computer Society, Washington, DC, 2007, pp. 179–192] is almost tight. A major motivation for the recent interest in the strong parallel repetition problem is that a strong parallel repetition theorem would have implied that the unique game conjecture is equivalent to the NP hardness of distinguishing between instances of Max-Cut that are at least 1−ϵ21-\epsilon^21−ϵ2 satisfiable from instances that are at most 1−(2/π)⋅ϵ1-(2/\pi)\cdot\epsilon1−(2/π)⋅ϵ satisfiable. Our results suggest that this cannot be proved just by improving the known bounds on parallel repetition.