The GHZ game is a 3-player game in which a verifier samples a triplet (x, y, z) uniformly from S = { (x, y, z) | x, y, z ∈ {0, 1}, x ⊕ y ⊕ z = 0 (mod 2)}, then sends x to Alice, y to Bob and z to Charlie. The verifier receives from each one of them a bit, a from Alice, b from Bob and c from Charlie, and accepts if and only if a ⊕ b ⊕ c = x ∨ y ∨ z. It is easy to prove that the value of the GHZ game, val(GHZ), defined as the maximum acceptance probability of the verifier over all strategies of the players, is 3/4. The n-fold repeated GHZ game is the game in which the verifier samples (x i , y i , z i ) independently from S for i = 1, . . . , n, sends x = (x 1 , . . . , x n ), y = (y 1 , . . . , y n ) and z = (z 1 , . . . , z n ) to Alice, Bob and Charlie respectively, receives vector answers f ( x) = (f 1 ( x), . . . , f n ( x)), g( y) = (g 1 ( y), . . . , g n ( y)) and h( z) = (h 1 ( z), . . . , h n ( z)) and accepts if and only if f i ( x) ⊕ g i ( y) ⊕ h i ( z) = x i ∨ y i ∨ z i for all i = 1, . . . , n. What can one say about the value of the n-fold repeated game, val(GHZ ⊗n )? As for lower bounds, it is clearly that case that val(GHZ ⊗n ) (3/4) n and one expects that value of the game to be exponentially decaying with n. Proving such upper bounds though is significantly more challenging.
The GHZ game is a prime example of a 3-player game for which parallel repetition is not well understood. For 2player games, parallel repetition theorems with an exponential decay have been known for a long time [14], [9], [13], [2], [4], and in fact the state of the art parallel repetition theorems for 2-player games are essentially optimal. As for multi-player games, Verbitsky showed [18] that the value of the n-fold repeated game approaches 0, however his argument uses the density Hales-Jewett theorem and hence gives a weak rate of decay (inverse Ackermann type bounds in n). More recently, researchers have been trying to investigate multi-player games more systematically and managed to prove an exponential decay for a certain class of games known as expanding games [3]. This work also identified the GHZ game as a bottleneck for current technique, saying that, in a sense, the GHZ game exhibits the worst possible correlations between questions for which existing information-theoretic techniques are incapable of handling.
A sequence of recent works [10] (subsequently simplified by [5]) managed to prove stronger parallel repetition theorems for the GHZ game, and indeed as suggested by [3] this development led to a parallel repetition theorem for a certain class of 3-player games [6], [7], namely for the class of games with binary questions. Quantitatively, they showed that val(GHZ ⊗n ) 1/n Ω (1) , and subsequently that for any 3player game G with val(G) < 1 whose questions are binary, one has that val(G ⊗n ) 1/n Ω (1) . The techniques utilized by these works is a combination of information theoretic techniques (as used in the case of 2-player games) and Fourier analytic techniques.
The main result of this paper is an improved upper bound for the value of the n-fold repeated GHZ game, which is exponential in n. More precisely: Theorem I.1. There is ε > 0 such that for all n, val(GHZ ⊗n ) 2 -ε•n . Such bounds cannot be achieved by the methods of [10], [5], [6], [7], and we hope that the observations made herein would be useful towards getting better parallel repetition theorems for more general classes of 3-player games.
Our proof of Theorem I.1 follows by reducing it to approximate sub-group type questions from additive combinatorics, and our argument uses results of Gowers [8]. Similar ideas have been also explored in the TCS community (for example, by Samorodnitsky [16]). Suppose f : {0, 1} n → {0, 1} n , g : {0, 1} n → {0, 1} n and h : {0, 1} n → {0, 1} n represent the strategies of Alice, Bob and Charlie respectively, and denote their success probability by η. Thus, we have that where the operations are coordinate-wise. Using Cauchy-Schwarz it follows that if we sample x, y, z and u, v, w conditioned on
What functions f, g, h can satisfy this? We draw an intuition from [1], that suggested that such advantage can only be gained from linear embeddings. In this respect, we are looking at the predicate
A linear embedding is an Abelian group (A, +) and a collection of maps φ : Σ → A, γ : Σ → A and δ : Σ → A not all constant such that φ(x, u) + γ(y, v) + δ(z, w) = 0. There are 2 trivial linear embeddings into (Z 2 , +): the projection onto the first coordinate as well as the projection onto the second coordinate. Thus, one is tempted to guess that in the above scenario, the functions f, g and h must use these linear embeddings and thus be correlated with linear functions over Z 2 . Alas, it turns out that there is yet, another embedding which is less obvious:
This motivates us to look at the original problem and see if we can already see (Z 4 , +) structure there.
a) Approximate Homomorphisms.: For (x, y, z) ∈ S, if x∨y ∨z = 1, then exactly two of the variables are 1; if x∨y ∨ z = 0, then all of x, y, z are 0. Thus, one can see that the check we are making is equivalent to checking that 2f (x) + 2g(y) + 2h(z) = x + y + z (mod 4). Indeed, on a given coordinate i, if
0 and the constraint says that we want f (x) i + g(y) i + h(z) i = 0 (mod 2) which implies that 2f (x) i +2g(y) i +2h(z) i = 0 (mod 4). Thus, the GHZ test can be thought of as a system of equations modulo 4, as suggested by the above intuition. More precisely, defining
Proof. Without loss of generality we focus on the first coordinate. If (x 1 , y 1 , z 1 ) = (0, 0, 0), then by (1) we get that f (x) 1 ⊕ g(y) 1 ⊕ h(z) 1 = 0, hence either all of them are 0 or exactly two of them are 1, and in any case 2f (x) 1 + 2g(y) 1 + 2h(z) 1 = 0 (mod 4). Otherwise, without loss of generality (x 1 , y 1 , z 1 ) = (1, 1, 0), and then by (1) we get f (x) 1 ⊕ g(y) 1 ⊕ h(z) 1 = 1, and there are two cases. If
In words, Lemma I.2 says that F, G, H form an approximate "cross homomorphism" from Z n 2 to Z n 4 . Once we have made this observation, the proof is concluded by a routine application of powerful tools from additive combinatorics.
More specifically, we appeal to results of Gowers and show for any F that satisfies Lemma I.2 (for some G and H) must exhibit some weak linear behaviour. Specifically, we show that for such F there is a shift s ∈ Z n 4 such that F (x) ∈ s+{0, 2} n for at least η = Ω(η 1028 ) fraction of inputs. On the other hand, on such points x we get that 2f (x)-x = F (x) = s+L(x) for some L(x) ∈ {0, 2} n , and noting that this must hold modulo 2 we get that there can only be one such point, x = -s (mod 2). Thus, η 2 -n , giving an exponential bound on η.
II. PROOF OF THEOREM I.1
We need the following definition:
Definition II.1. Let (A, +), (B, +) be Abelian groups, and let
In our application, we will always have A = {0, 1}. For convenience we denote N = 2 n . Thus, it is clear that the number of additive quadruples is always at most N 3 (as this is the number of solutions to x + y = u + v). The following lemma asserts that if F, G, H : {0, 1} n → B n are functions such that F (x) + G(y) + H(z) = 0 for at least η of the triples x, y, z satisfying x ⊕ y = z (such as the one given in Lemma I.2), then each one of the functions F, G and H has a substaintial amount of additive quadruples.
Lemma II.2. Suppose that F, G, H : {0, 1} n → B n satisfy that
Then F has at least η 4 N 3 additive quadruples.
Proof. By the premise and Cauchy-Schwarz
Making change of variables, we get that η 2 Ex,u,u 1 F (x)-F (x⊕u⊕u )=H(u )-H(u) .
Squaring and using Cauchy-Schwarz again we get that
which by another change of variables is equal to Ex,y,u,v:x+y=u+v 1 F (x)+F (y)=F (u)+F (v) , and the claim is proved.
We intend to use Lemma II.2 to conclude a structural result for F , and towards this end we show that a function that has many additive quadruples must exhibit some linear structure. The content of this section is a straight-forward combination of well-known results in additive combinatorics, and we include it here for the sake of completeness. We need the notions of Freiman homomorphism, sum-sets and a result of Gowers [8]. We begin with two definitions:
Definition II.4. Let (A, +) be an Abelian group, let n ∈ N and let A, B ⊆ A n . We define
If A = B, we denote the sum-set A + B more succinctly as 2A, and more generally kA denotes the k-fold sum set of A.
We need a result of Gowers [8] asserting that a function F with many additive quadruples can be restricted to a relatively large set and yield a Freiman homomorphism. Gowers states and proves the statement for Z N , and we adapt his proof for our setting. For the proof we need two notable results in additive combinatorics. The first of which is the Balog-Szemerédi-Gowers theorem, and we use the version from [17]:
Let G be an Abelian group, and suppose that Γ ⊆ G contains at least ξ |Γ| 3 additive quadruples, that is,
The second result we need is Plünnecke's inequality [12], [15] (see also [11]):
6 (Plünnecke's inequality). Let G be an Abelian group, and suppose that Γ ⊆ G has |Γ -Γ| C |Γ|. Then |mΓ -rΓ| C m+r |Γ|. Lemma II.7 (Corollary 7.6 in [8]). Let n ∈ N, and suppose that a function φ : Z n 2 → Z n 4 has at least ξ |Z n 2 | 3 additive quadruples. Then there exists A ⊆ Z n 2 such that φ| A is a Freiman homomorphism of order 8 and |A| Ω(ξ 257 |Z n 2 |).
be the graph of φ, and think of it as a set in the Abelian group
C and towards contradiction we assume the contrary. First, note that we may choose |Γ | distinct values of x such that (x, w x ) ∈ 8Γ -8Γ for some w x . Indeed, we can fix any 15 elements (x i , w i ) ∈ Γ for i = 1, . . . , 15, and range over all |Γ | pairs (x, w x ) ∈ Γ to get |Γ | elements (x + x -x , w x + w -w ) ∈ 8Γ -8Γ where x = x 1 +. . .+x 7 , x = x 8 +. . .+x 15 and w = w 1 +. . .+w 7 and w = w 8 + . . .+ w 15 , which have distinct first coordinate. Thus, looking at the |Γ | elements (x, w x ) ∈ 8Γ -8Γ with distinct first coordinate, we get that (x,
The set Y will be useful for us as for any x ∈ Z n 2 , we may define
Take t = log(C)+1, choose I 1 , . . . , I t ⊆ [n] independently and uniformly and consider
We note that the 0 vector is always in
W, but any other y ∈ Z n 4 is in W with probability at most 2 -t . Indeed, if y's entries are all {0, 2}-valued then y can be in W only if y/2 satisfies t randomly chosen equations modulo 2, which happens with probability 2 -t . If there are entries of y that are either 1 or 3, then we get that y (mod 2) is a non-zero vector that must satisfy t randomly chosen equations modulo 2, which happens with probability 2 -t . Thus, E [|Y ∩ W \ {0}|] 2 -t |Y| < 1, so we may choose W such that Y ∩ W = {0}. For an a ∈ Z n 4 we define Γ a = { (x, y) ∈ Γ | y ∈ a + W}. We claim that there is a choice for a such that (1) |Γ a | 4 -t |Γ | Ω(ξ 257 |Z n 2 |), and (2) taking A = { x | ∃y such that (x, y) ∈ Γ a }, the function φ| A is a Freiman homomorphism of order 8. Together, this gives the statement of the lemma. Suppose towards contradiction that φ| A is not a Freiman homomorphism of order 8. Thus we can find x 1 , . . . , x 8 ∈ A and x 1 , . . . , x 8 ∈ A that have the same sum yet φ(x 1 ) + . . .
In particular, y -y ∈ Y x -Y x ⊆ Y. On the other hand, by choice of A we get that φ(x i ), φ(x i ) ∈ a + W for all i and so y, y ∈ 4W -4W = W and so y -y ∈ W. It follows that y -y ∈ Y ∩ W, but by the choice of W this last intersection only contains the 0 vector, and contradiction. Thus, combining Lemmas II.2 and II.7 we are able to conclude that F is a Freiman homomorphism of order 8 when restricted to a set A ⊆ Z n 2 whose size is at least Ω(η 1028 N ). A Freiman homomorphism of order 8 is also a Freiman homomorphism of order 4, and the following lemma shows this tells that there is a shift of {0, 2} n in which F (x) lies for many x's:
Lemma II.8. Let A ⊆ Z n 2 and suppose that φ : A → Z n 4 is a Freiman homomorphism of order 4. Then there is s ∈ Z n 4 such that for all x ∈ A, φ(x) ∈ s + {0, 2} n . Proof. Choose any a ∈ A and let s = φ(a). Then for any x ∈ A, applying the Freiman homomorphism condition on the tuples (x, x, a, a) and (a, a, a, a) that have the same sum over Z n 2 , we get that 2φ(x)+2φ(a) = 4φ(a) = 0, so 2(φ(x)-s) = 0. This implies that φ(x) -s ∈ {0, 2} n , and the proof is concluded.
Combining the last two lemmas we get the following corollary.
Corollary II.9. Suppose that F :
4 is a function for which there are G, H : Z n 2 → Z n 4 such that Pr (x,y,z)∈S n [F (x) + G(y) + H(z) = 0] η. Then there is s ∈ Z n 4 such that Pr x∈Z n 2 [F (x) ∈ {0, 2} n + s] Ω(η 1028 ). Proof. By Lemma II.2 we get that F has at least η 4 N 3 additive quadruples, so by Lemma II.7 there is A ⊆ Z n 2 of size at least Ω(η 1028 N ) such that F | A is a Freiman homomorphism. Applying Lemma II.8 we conclude that there is s ∈ Z n 4 such that F (x) ∈ s + {0, 2} n for all x ∈ A and the proof is concluded.
Let f, g, h : {0, 1} n → {0, 1} n be strategies that achieve value at least η in GHZ ⊗n , and define F : Z n 2 → Z n 4 by F (x) = 2f (x) -x and similarly G(y) = 2g(y) -y and H(z) = 2h(z) -z. By Lemma I.2 we get that Pr (x,y,z)∈S n [F (x) + G(y) + H(z) = 0] η, hence by Corollary II.9 there is s ∈ Z n 4 such that Pr x∈Z n 2 [F (x) ∈ s + {0, 2} n ] η for η = Ω(η 1028 ). For any such x, we get that 2f (x) -x = F (x) = s + L(x) where L(x) ∈ {0, 2} n , and so x = -s + 2f (x) -L(x). Note that this is equality modulo 4 hence it implies it also holds modulo 2. We also have that 2f (x) -L(x) ∈ {0, 2} n so this vanishes modulo 2, hence we get that x = -s (mod 2). In other words, there can be at most single x such that F (x) ∈ s + {0, 2} n and so Pr x∈Z n 2 [F (x) ∈ s + {0, 2} n ] 2 -n . Combining, we get that η 2 -n and so η 2 -n/1028+O (1) .
Authorized licensed use limited to: New York University. Downloaded on September 07,2024 at 14:18:44 UTC from IEEE Xplore. Restrictions apply.