Authors Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald {de} Wolf,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645
www.theoryofcomputing.org
Near-Optimal and Explicit
Bell Inequality Violations∗
Harry Buhrman† Oded Regev‡ Giannicola Scarpa§ Ronald de Wolf¶
Received: September 15, 2011; revised: August 31, 2012; published: December 27, 2012.
Abstract: Entangled quantum systems can exhibit correlations that cannot be simulated
classically. For historical reasons such correlations are called “Bell inequality violations.”
We give two new two-player games with Bell inequality violations that are stronger, fully
explicit, and arguably simpler than earlier work.
The first game is based on the Hidden Matching problem of quantum communication
complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with
probability 1 by a strategy using a maximally entangled state with local dimension n (e. g.,
log n EPR-pairs), while we show that the winning probability of any classical strategy differs
√
from 1/2 by at most O((log n)/ n).
∗ An earlier version of this paper appeared in the Proceedings of the 26th IEEE Conference on Computational Complexity,
pages 157–166, 2011.
† Supported by a Vici grant from the Netherlands Organisation for Scientific Research (NWO), and by the European
Commission under the project QCS (Grant No. 255961).
‡ Supported by the Israel Science Foundation, by the Wolfson Family Charitable Trust, and by a European Research Council
(ERC) Starting Grant. Part of the work done while a DIGITEO visitor in LRI, Orsay.
§ Supported by a Vidi grant from the Netherlands Organisation for Scientific Research (NWO), and by the European
Commission under the project QCS (Grant No. 255961).
¶ Supported by a Vidi grant from the Netherlands Organisation for Scientific Research (NWO), and by the European
Commission under the project QCS (Grant No. 255961).
ACM Classification: J.2
AMS Classification: 81P68
Key words and phrases: quantum communication, nonlocal games, Bell inequalities, Fourier analysis
2012 Harry Buhrman, Oded Regev, Giannicola Scarpa, and Ronald de Wolf
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2012.v008a027
H ARRY B UHRMAN , O DED R EGEV, G IANNICOLA S CARPA , AND RONALD DE W OLF
The second game is based on the integrality gap for Unique Games by Khot and Vishnoi
and the quantum rounding procedure of Kempe, Regev, and Toner. Here n-dimensional
entanglement allows the game to be won with probability 1/(log n)2 , while the best winning
probability without entanglement is 1/n. This near-linear ratio is almost optimal, both in
terms of the local dimension of the entangled state, and in terms of the number of possible
outputs of the two players.
1 Introduction
One of the most striking features of quantum mechanics is the fact that entangled particles can exhibit
correlations that cannot be reproduced or explained by classical physics, or more precisely, by “local
hidden-variable theories.” This was first noted by Bell [2] in response to Einstein, Podolsky, and Rosen’s
challenge to the completeness of quantum mechanics [9]. Experimental realization of such correlations is
the strongest proof we have that nature does not behave according to classical physics: nature cannot
simultaneously be “local” (meaning that information does not travel faster than the speed of light) and
“realistic” (meaning that measurable properties of particles such as its spin always have a definite—if
possibly unknown—value). Many such experiments have been done. All behave in accordance with the
predictions of quantum mechanics, though so far none has closed all “loopholes” that would allow some
(usually very contrived) classical explanation of the observations based on imperfect behavior of, for
instance, the photon detectors used.
Here we study quantitatively how much such correlations obtained from entangled quantum systems
can deviate from what is achievable classically. It will be convenient to describe our results in terms
of two-player games, which are described as follows. Two non-communicating parties, called Alice
and Bob, receive inputs x and y according to some fixed and known probability distribution π, and are
required to produce outputs a and b, respectively. There is a predicate specifying which outputs a, b are
correct on inputs x, y. The definition of a game G consists of this predicate and the distribution π. The
goal is to design games where entangled strategies have much higher winning probability than the best
classical strategy. While this setting is used to study non-locality in physics, the same set-up is also used
extensively to study the power of entanglement in computer science contexts like multi-prover interactive
proofs [16, 17], parallel repetition [6, 18], and cryptography.
Entangled strategies start out with an arbitrary fixed entangled state. No communication takes place
between Alice and Bob. For each input x, Alice has a measurement, and for each input y, Bob has a
measurement. They apply the measurements corresponding to x and y to their halves of the entangled
state, producing classical outputs a and b, respectively. Their goal is to maximize the winning probability.
The entangled value ω ∗ (G) of the game is the supremum of the winning probability, taken over all
entangled strategies. When restricting to strategies that use entanglement of local dimension n, the value
is denoted ωn∗ (G). This should be contrasted with the classical value ω(G) = ω1∗ (G) of the game, which
is the maximum among all classical, non-entangled strategies. Shared randomness between the two
parties is allowed, but is easily seen not to be beneficial.
The remarkable fact, alluded to above, that some entanglement-based correlations cannot be simulated
classically, corresponds to the fact that there are games G for which the entangled value ω ∗ (G) is strictly
larger than the classical value ω(G). The CHSH game is one particularly famous example [5]. Here,
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 624
N EAR -O PTIMAL AND E XPLICIT B ELL I NEQUALITY V IOLATIONS
the inputs x ∈ {0, 1} and y ∈ {0, 1} are uniformly distributed, and Alice and Bob win the game if their
respective outputs a ∈ {0, 1} and b ∈ {0, 1} satisfy a ⊕ b = x ∧ y; in other words, a should equal b
unless x = y = 1. The classical value of this√game is easily seen to be ω(G) = 3/4, while the entangled
value is known to be ω ∗ (G) = 1/2 + 1/(2 2) ≈ 0.85. The entangled value is achieved already with
2-dimensional entanglement (i. e., one EPR-pair), so ω ∗ (G) = ω2∗ (G) for this game [27].
One common figure of merit of a game is that of the Bell inequality violation exhibited by a game,
which is defined as the ratio of entangled and classical values. More generally, we allow to replace the
values (which are the maximum winning probabilities) by biases around some arbitrary “center” p ∈ [0, 1],
where by bias we mean the maximum distance of the winning probability from p. For instance, by using √
p = 1/2 as the center, one can see that the CHSH game above exhibits a Bell inequality violation of 2.1
In Section 2.2 we explain the origin of the term “Bell inequality violation,” define it more formally, and
explain the close relationship between games and Bell inequalities.
In two recent papers, Junge et al. [14, 13] studied how large a Bell inequality violation one can
obtain. In terms of upper bounds, [14] proved that the maximum Bell inequality violation ωn∗ (G)/ω(G)
obtainable with entangled strategies of local dimension n, is at most O(n), and [13, Theorem 6.8] proved
that if Alice and Bob have at most k possible outputs each, then the violation ω ∗ (G)/ω(G) is at most
O(k), irrespective of the amount of entanglement they can use. (This improved an earlier O(k2 ) upper
bound due to Degorre et al. [7], and was also obtained for the special case of games by Dukaric [8,
Theorem 4].)
√
In terms of lower bounds, [14] showed the existence of a Bell inequality violation of Ω( n/(log n)2 ),
where n is both the entanglement dimension and the number of outputs of Alice and Bob. This was
√
improved to n/ log n in [13]. Both constructions are probabilistic, and the proofs show that with high
probability the constructed games exhibit a large violation, yielding the existence of such games, without
giving an explicit formulation. Their proofs are heavily based on connections to the mathematically
beautiful areas of Banach spaces and operator spaces, but as a result are arguably somewhat inaccessible
to those unfamiliar with these areas, and it is difficult to get a good intuition for them. (It is actually
possible to analyze their game and reprove many of their results—often with improved parameters—using
elementary probabilistic techniques [26].)
Our main result in this paper is to exhibit two fully explicit games with strong Bell inequality
√
violations. The first achieves the same violation as [13], namely n/ log n, where n is both the number of
possible outputs and the dimension of entanglement. The second achieves the much stronger violation of
n/(log n)2 , which is optimal up to a polylogarithmic factor by the results of [14, 13]. Even though the
second game gives a much stronger violation, the first one still has some merit; for instance, entanglement
allows the players to win it with certainty. Interestingly, although addressing a question in mathematical
physics, both games are inspired by earlier work in theoretical computer science (communication
complexity and unique games, respectively), and so is their analysis. In the remainder of this introduction
we provide an overview of the two games, followed by some discussion and comparison.
1 Notice that this requires that the winning probability of non-entangled players is always between 1/4 and 3/4, which is
clearly the case.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 625
H ARRY B UHRMAN , O DED R EGEV, G IANNICOLA S CARPA , AND RONALD DE W OLF
1.1 The Hidden Matching game
The “Hidden Matching” problem was introduced in quantum communication complexity by Bar-Yossef et
al. [1], and many variants of it were subsequently studied [12, 11, 10]. The original version is as follows,
where it should be noted that now we allow communication, in contrast to the setting of non-local games.
Let n be a power of 2. Alice is given input x ∈ {0, 1}n and Bob is given a perfect matching M, i. e., a
partition of the set [n] = {1, . . . , n} into n/2 disjoint pairs {i, j}. Both inputs are uniformly distributed.2
We allow one-way communication from Alice to Bob, and Bob is required to output a pair {i, j} ∈ M and
a bit v ∈ {0, 1}. They win if v = xi ⊕ x j .
In Section 3.1 we show that if Alice sends Bob a c-bit message, then their optimal winning probability
√ √
is 1/2 + Θ(c/ n). Bar-Yossef et al. [1] earlier proved this for c = Θ( n), using information theory.
However, their tools seem unable to give good bounds on the success probability for much smaller c.
Instead, the main mathematical tool we use in our analysis is the so-called “KKL inequality” [15] from
Fourier analysis of Boolean functions. Roughly speaking, this inequality implies that if the message
that Alice sends about x is short, then Bob will not be able to predict the parity xi ⊕ x j well for many
{i, j} pairs. His matching M is uniformly distributed, independent of x, and contains only n/2 of all n2
possible {i, j} pairs. Hence it is unlikely that he can predict any one of those n/2 parities well. The KKL
inequality was used before to analyze another variant of Hidden Matching in [11], though their analysis
is different and more complicated because their variant of Hidden Matching is a promise problem with a
non-product input distribution.
The following non-local version of the Hidden Matching problem (and the entangled strategy for it)
is originally due to Buhrman, and related problems were studied in [12, 10].
Definition 1.1 (Non-Local Hidden Matching Game (HMnNL )). Let n be a power of 2 and Mn be the set of
all perfect matchings on the set [n]. Alice is given x ∈ {0, 1}n and Bob is given M ∈ Mn , both distributed
according to the uniform distribution. Alice and Bob do not communicate. Alice’s output is a string
a ∈ {0, 1}log n and Bob’s output is an {i, j} ∈ M and d ∈ {0, 1}. They win the game if and only if
(a · (i ⊕ j)) ⊕ d = xi ⊕ x j , (1.1)
where the dot indicates inner product (modulo 2) of two log n-bit strings.
Observe that Alice has n possible outputs a and Bob has 2 · n/2 = n possible outputs ({i, j}, d) given
his matching.
A classical strategy that wins this game induces a protocol for the original Hidden Matching problem
with communication c = log n bits and the same winning probability p, as follows. Alice sends Bob the
log n-bit output a from the non-local strategy, Bob computes v = (a·(i⊕ j))⊕d and outputs ({i, j}, v). We
have that v = xi ⊕x j with probability p. Hence, our bound for the original communication problem implies
√
that no classical strategy can win with probability that differs from 1/2 by more than O((log n)/ n).
2 All our results also hold with minor modifications for the case that Bob’s matching is chosen uniformly from the set {M |
k
k ∈ {0, . . . , n/2 − 1}}, where the matching Mk consists of the pairs {i, j} where i ≤ n/2 and j = n/2 + 1 + (i + k − 1 mod n/2).
This has the advantage of lowering the number of possible inputs to Bob to n/2. The main thing is to notice that equation (3.1)
still holds with respect to this new distribution on Bob’s matching if we replace the right-hand side by 2/n, and the rest of the
proof goes through.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 626
N EAR -O PTIMAL AND E XPLICIT B ELL I NEQUALITY V IOLATIONS
In contrast, there is a strategy that wins with probability 1 using log n EPR-pairs, which shows
√
ωn∗ (G) = 1.3 This game therefore exhibits a Bell violation of Ω( n/ log n) (by measuring the maximal
deviation of the winning probability from 1/2). This order is the same as that obtained by Junge et
al. [14, 13], but our game is fully explicit and arguably simpler (which would help any future experimental
realization). One might feel that our reduction to a communication complexity lower bound is responsible
for losingpthe log n factor; however in Theorem 3.9 we exhibit a classical strategy with winning probability
1/2 + Ω( (log n)/n). This shows that at least the square root of the log-factor is really necessary.
1.2 The Khot-Vishnoi game
Our second non-local game derives from the work of Khot and Vishnoi [20] on the famous Unique Games
Conjecture (UGC), which was introduced by Khot [19]. Although not necessary for the rest of this paper,
we now provide some background and motivation. Roughly speaking, the UGC says that approximating
the classical value of so-called unique games is a hard problem, even if we are only interested in a very
rough approximation that can tell the difference between value less than ε and value more than 1 − ε.
This conjecture implies many other hardness-of-approximation results that do not seem obtainable using
the more standard techniques based on the PCP theorem. Khot and Vishnoi considered the standard
semidefinite programming (SDP) relaxation of the classical value and showed that there are games for
which it provides a very poor approximation, in the sense that the classical value is close to 0, yet the
SDP relaxation is close to 1. This so-called integrality gap demonstrates that the standard SDP relaxation,
which can be computed efficiently, does not lead to an algorithm contradicting the UGC.
Kempe, Regev, and Toner [18] already observed that they could combine their “quantum rounding”
technique with the game of [20] to get a game with n possible outputs exhibiting a Bell inequality
violation of nε for some small constant ε > 0, using entanglement dimension n. Our main contribution in
the second part of this paper is a refined (and at the same time simpler) analysis of both the Khot-Vishnoi
game and of the quantum rounding technique. We show that, somewhat surprisingly, nearly optimal
violations can be obtained using this method.
We first give a precise definition of the Khot-Vishnoi (KV) game.
Definition 1.2 (Khot-Vishnoi Game (KVn )). The game is parametrized by an integer n, which we assume
to be a power of 2, and a “noise parameter” η ∈ [0, 1/2]. Consider the group ({0, 1}n , ⊕) of n-bit strings
together with bitwise addition mod 2, and let H be the subgroup containing the n Hadamard codewords.4
This subgroup partitions {0, 1}n into 2n /n cosets of n elements each. Alice receives a uniformly random
coset x as input, which we can think of as u ⊕ H for uniformly random u ∈ {0, 1}n . Bob receives a coset
y obtained from Alice’s by adding a string of low Hamming weight, namely y = x ⊕ z = u ⊕ z ⊕ H, where
each bit of z ∈ {0, 1}n is set to 1 with probability η, independently of the other bits. Addition of z gives a
natural bijection between the two cosets, mapping each element of the first coset to a relatively nearby
element of the second coset; namely, the distance between the two elements is the Hamming weight of z,
3 The reader might be a bit confused by the seeming overloading of the meaning of ‘n’. Formally, ‘n’ is a parameter in the
specification of the game. As it happens, for both of our games it is also the number of possible outputs for each player, and the
local dimension of the entangled state that our strategy uses (though we do not claim that this entanglement-dimension n is
necessary to achieve the best-possible entangled value).
4 For a ∈ {0, 1}log n , the corresponding n-bit Hadamard codeword is defined as h(a) := (a · j)
j∈{0,1}log n .
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 627
H ARRY B UHRMAN , O DED R EGEV, G IANNICOLA S CARPA , AND RONALD DE W OLF
which is typically around ηn. Each player is supposed to output one element from its coset, and their
goal is for their elements to match under the bijection. In other words, Alice outputs an element a ∈ x,
Bob outputs b ∈ y, and they win the game if and only if a ⊕ b = z.5
Notice that the number of possible inputs to each player is 2n /n and the number of possible outputs
for each player is n.
Based on the integrality gap analysis of Khot and Vishnoi, in Section 4 we show that no classical
strategy can win this game with probability greater than 1/nη/(1−η) . We also sketch a classical strategy
that achieves this winning probability up to lower order terms. In contrast, using a simplified version of
the “quantum rounding” technique of [18], we exhibit an entangled strategy that uses the n-dimensional
maximally entangled state and wins with probability at least (1 − 2η)2 . This strategy follows from the
observation that each coset of H defines an orthonormal basis of Rn in which we can do a measurement.
Summarizing, we have entangled value ωn∗ (G) ≥ (1 − 2η)2 and classical value ω(G) ≤ 1/nη/(1−η) for
this game. Setting the noise-rate to η = 1/2 − 1/ log n, the entangled value is Ω(1/(log n)2 ) while the
classical value is O(1/n), leading to a Bell inequality violation ωn∗ (G)/ω(G) = Ω(n/(log n)2 ). Up to the
polylogarithmic factor, this is optimal both in terms of the local dimension, and in terms of the number of
possible outputs.
Palazuelos [24] recently used our result to prove an interesting super-activation result. He identified
a constant-dimensional quantum state (a mixture of the maximally entangled state of local dimension 8
with the completely mixed state) that cannot be used to violate any Bell inequality, but a sufficiently large
number of copies of which can be used to violate a Bell inequality—namely the one associated with our
KV game.
1.3 Discussion and open problems
Although Bell violations provide an elegant way to quantify the non-locality exhibited in a game, in
experimental realizations of such games it is often important to take into account the actual classical
and entangled values, and not just their ratio, especially when one tries to take into account possible
imperfections in the experimental set-up. The large Bell violation and the tiny success probability
achievable by classical players seem to make the KV game attractive to an experimental realization. One
should keep in mind, though, that the success probability achievable by entangled players is 1/(log n)2 ,
which is somewhat low in absolute terms, and might not be visible if the experiment has too many false
positives. It also means that an experiment must be repeated about (log n)2 times before we expect to
see the first win. In the HM game, on the other hand, entangled players can win with certainty, which
seems beneficial in case there are few false negatives. Another advantage of the HM game over KV is its
somewhat simpler description.
One natural open question is to improve the Bell violation of n/(log n)2 achieved by the KV game
either by tweaking the game or defining another game, possibly even matching the O(n) upper bound up
5 Note that the winning condition for this game is a “randomized predicate,” as there are n possible ways to obtain the same y
from x, hence there are n possible winning predicates (one for each z ∈ x ⊕ y) corresponding to each pair of inputs x, y. Strictly
speaking, this requires a slightly more general definition of a game than the one given in the introduction; see the definition in
Section 2.2. Although not relevant for any of our applications, we mention that one can modify the game in a straightforward
manner, making it a game with a deterministic predicate. The thing to observe is that with very high probability exactly one of
the n predicates dominates, namely the one corresponding to a z of Hamming weight around ηn.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 628
N EAR -O PTIMAL AND E XPLICIT B ELL I NEQUALITY V IOLATIONS
to a constant factor.6 Throughout this paper we considered the Bell violation as a function of the number
of outputs of the players and/or of the dimension of entanglement. One can also analyze the violation in
terms of the number of possible inputs. We recall that in the KV game both players have inputs taken
from an exponentially large set, and that in the HM game (when modified as in footnote 2) Bob has only
n/2 possible inputs, but Alice still has an exponentially large set of inputs. The Bell inequality violation
√
of n/ log n presented by Junge and Palazuelos [13] has the advantage that the number of inputs is only
O(n). Accordingly, another open question presents itself: can we find a game with a (near-)linear Bell
inequality violation, and linear number of inputs and outputs for both Alice and Bob?
Finally, while this paper focuses on the two-party setting, obtaining stronger Bell inequality violations
for settings with three or more parties is also a worthwhile goal. Pérez-García et al. [25] (see also [4])
gave a randomized construction of a three-party XOR game (in such a game each party outputs a bit, and
winning√ or losing depends only on the XOR of those three bits) that gives a Bell inequality violation
of Ω( d) using an entangled state in dimensions d × D × D with D d.7 In contrast, it is a known
consequence of Grothendieck’s inequality that such non-constant separations do not exist for two-party
XOR games. We do not know how large Bell inequality violations can be for arbitrary three-party games.
Note that it is easy to make a three-party version of the Hidden Matching game: Alice gets input
x ∈ {0, 1}n , Bob gets input y ∈ {0, 1}n , and Charlie gets a matching M as input, all uniformly distributed.
The goal is that Alice outputs a ∈ {0, 1}log n , Bob outputs b ∈ {0, 1}log n , Charlie outputs d ∈ {0, 1} and
{i, j} ∈ M, such that ((a ⊕ b) · (i ⊕ j)) ⊕ d = xi ⊕ x j ⊕ yi ⊕ y j . By modifying the two-party proofs in this
paper, it is not hard to show that the winning probability using an n-dimensional GHZ state is 1, while
the best classical winning probability deviates from 1/2 by at most O((log n)2 /n). So going from two to
three parties squares the Bell inequality violation for Hidden Matching. This improvement unfortunately
does not scale up with more than three parties, because one can show the classical winning probability is
always at least 1/2 + Ω(1/n).
2 Preliminaries
2.1 Fourier analysis
The crucial technical tool used in the analysis of both of our games is Fourier analysis on the Boolean
cube. We will just introduce what we need here, referring to [22, 28] for more details and references.
Unless mentioned otherwise, expectations and probabilities are taken over a uniformly random x ∈ {0, 1}n .
Define the inner product between functions f , g : {0, 1}n → R as
1
h f , gi = ∑ n f (x)g(x) = E[ f (x) · g(x)] .
2n x∈{0,1}
For S ⊆ [n], the function χS (x) = (−1)∑i∈S xi is the parity (represented as a sign) of the variables indexed
in S. These 2n functions (one for each S) form an orthonormal basis for the space of all real-valued
6 Interestingly, very recently Palazuelos [23] showed that this cannot be done using the maximally entangled state (which is
the state used in all our entangled strategies): he proved that the ratio between the optimal√
value of entangled strategies using the
maximally entangled state of local dimension n, and the classical value, is at most O(n/ log n).
7 They also showed that using GHZ states, there is no superconstant Bell inequality violation for XOR games (see also [3].)
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 629
H ARRY B UHRMAN , O DED R EGEV, G IANNICOLA S CARPA , AND RONALD DE W OLF
functions on the Boolean cube. The Fourier coefficients of f are fb(S) = h f , χS i, and we can write f in its
Fourier decomposition
f = ∑ fb(S)χS .
S⊆[n]
Since the χS form an orthonormal basis, it is easy to show
h f , gi = ∑ fb(S)b
g(S) . (2.1)
S
For p ≥ 1, the p-norm of f is defined as
k f k p = E[| f (x)| p ]1/p .
This is monotone non-decreasing in p. For p = 2, equation (2.1) with g = f gives Parseval’s identity:
k f k22 = ∑ fb(S)2 .
S
For ρ ∈ [−1, 1], the noise-operator Tρ adds “η-noise” to each of the input bits, where η = (1 − ρ)/2.
More precisely, the function T1−2η f is defined as
(T1−2η f )(x) = E[ f (x ⊕ z)] ,
z
where z ∈ {0, 1}n is an “η-biased noise string,” i. e., each bit zi is set to 1 with probability η, independently
of the other bits. The linear operator Tρ is diagonal in the Fourier basis: it just multiplies each χS by the
factor ρ |S| . Equivalently,
|S| b
ρ f (S) = ρ f (S) .
Td (2.2)
Since Tρ f is a convex combination of shifted copies fz (x) = f (x ⊕ z) of f , by the triangle inequality
we see that Tρ is a contraction: Tρ f p ≤ k f k p for all p ≥ 1, ρ ∈ [−1, 1], and f . The Bonami-Beckner
hypercontractive inequality implies Tρ f q ≤ k f k p even for q somewhat bigger than p.
Theorem 2.1 (Bonami-Beckner). For f : {0, 1}n → R, 1 ≤ p ≤ q and ρ 2 ≤ (p − 1)/(q − 1), we have
Tρ f q
≤ k f kp .
An important consequence of the hypercontractive inequality is the so-called KKL inequality [15].
Theorem 2.2 (KKL). For f : {0, 1}n → {−1, 0, +1} and δ ∈ [0, 1], we have
∑ δ |S| fb(S)2 ≤ Pr[ f (x) 6= 0]2/(1+δ ) .
S
√
Proof. Applying Theorem 2.1 with q = 2, p = 1 + δ , and ρ = δ gives Tρ f 2 ≤ k f k p . Note that
because of the range of f , the right-hand side equals Pr[ f (x) 6= 0]1/(1+δ ) . Squaring both sides and
rewriting the left-hand side using Parseval’s identity completes the proof.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 630
N EAR -O PTIMAL AND E XPLICIT B ELL I NEQUALITY V IOLATIONS
2.2 A more formal look at Bell violations
Before we analyze the two games mentioned above, let us first say something more about the mathematical
treatment of general Bell inequalities. Readers who are content with the above (more concrete) approach
in terms of winning probabilities of games, may safely skip this section.
Consider a game with n possible inputs to each player and k possible outputs. The behavior of the
players (irrespective of whether they use a classical or an entangled strategy) can be summarized in
terms of n2 probability distributions, each on the set [k] × [k]. We denote by P(ab | xy) the probability of
producing outputs a and b when given inputs x and y, with respect to a fixed strategy. As described in
the introduction, a game is defined by a probability distribution π on the input set [n] × [n], as well as
a (possibly randomized) predicate on [k] × [k] for each input pair (x, y). The winning probability of the
players can be written as
ab
hM, Pi = ∑ Mxy P(ab | xy) .
abxy
where Mxy ab is defined as the probability of the input pair (x, y) multiplied by the probability that the output
pair (a, b) is accepted on this input pair. We call M = (Mxy ab ) the Bell functional corresponding to the
game. More generally, a Bell functional is an arbitrary tensor M = (Mxy ab ) containing n2 k2 real numbers.
We define the classical value of a Bell functional M as
ω(M) = sup |hM, Pi| ,
P
where the supremum is over all distributions P representing classical strategies. Similarly, the entangled
value of M is defined as
ω ∗ (M) = sup |hM, Pi| ,
P
where the supremum now is over all entangled strategies (using an entangled state of arbitrary dimension).
If the entangled state is restricted to local dimension n, the value is denoted ωn∗ (M). We note that if M is
the Bell functional corresponding to a game, then these definitions coincide with our definitions from the
introduction, and in this case the absolute value is unnecessary since M is non-negative.
A Bell inequality is an upper bound on ω(M) for some Bell functional M; it shows a limitation of
classical strategies.8 The Bell inequality violation demonstrated by a Bell functional M is defined as the
ratio between the entangled and the classical value
ω ∗ (M)
.
ω(M)
This provides a convenient quantitative way to measure the extra power provided by entanglement.
This definition of Bell violation enjoys a rich mathematical structure, as witnessed by the numerous
connections found to Banach space and operator space theory [14, 13, 8], and also has a beautiful
geometrical interpretation as the “distance” between the set of all classical strategies and the set of all
entangled strategies. (See Section 6.1 in [13].)
8 An upper bound on ω ∗ (M) is known as a Tsirelson inequality, and shows a limitation of entangled strategies.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 631
H ARRY B UHRMAN , O DED R EGEV, G IANNICOLA S CARPA , AND RONALD DE W OLF
Clearly, any game G for which ω ∗ (G) ≥ Kω(G) gives a Bell violation of K by just taking the
functional corresponding to G. But recall that in the introduction we said that one is also allowed to look
at the ratio of biases around some center probability p. We now explain why this still agrees with the
above definition of Bell violation. We claim that if G is a game for which the winning probability of any
classical strategy cannot deviate from p by more than δ1 and, moreover, there is an entangled strategy
obtaining winning probability at least p + δ2 (or at most p − δ2 ), then we obtain a Bell violation of δ2 /δ1 .
To see why, let M be the functional corresponding to the game, and let M 0 be the functional obtained by
subtracting from each Mxy ab the probability of input pair (x, y) times p. Then it is easy to see that for any
strategy P, hM 0 , Pi = hM, Pi − p. Hence, ω(M 0 ) and ω ∗ (M 0 ) are exactly the bias around p of classical
and entangled strategies, respectively, and the claim follows. The converse to this statement is also true:
any Bell functional M can be converted to a game in such a way that the ratio between the entangled bias
and the classical bias of the game (both around 1/2, say) is exactly the Bell violation demonstrated by
the functional. To prove this, consider the game in which an input pair (x, y) is chosen uniformly, and
outputs a, b are accepted with probability 1/2 + δ Mxy ab for some sufficiently small δ > 0 so that all these
probabilities are in [0, 1].
3 Hidden Matching game
In this section we define and analyze the Hidden Matching game. Here and below, unless stated otherwise,
all probabilities and expectations are taken over the distributions on x and M specified by the game.
3.1 The Hidden Matching problem in communication complexity
While our focus is non-locality, it will actually be useful to first study the original version of the Hidden
Matching problem in the context of protocols where communication from Alice to Bob is allowed. Both
the problem and the efficient quantum protocol below come from [1].
Definition 3.1 (Hidden Matching (HMn )). Let n be a power of 2 and Mn be the set of all perfect
matchings on the set [n]. Alice is given x ∈ {0, 1}n and Bob is given M ∈ Mn , both distributed according
to the uniform distribution. We allow one-way communication from Alice to Bob, and Bob outputs an
{i, j} ∈ M and v ∈ {0, 1}. They win if v = xi ⊕ x j .
Theorem 3.2. For every n that is a power of 2, there is a protocol for HMn with log n qubits of one-way
communication that wins with probability 1 (i. e., v = xi ⊕ x j always holds).
Proof. The protocol is the following:
1 n
1. Alice sends Bob the state |ψi = √ ∑ (−1)xi |ii.
n i=1
2. Bob measures |ψi in the n-element basis
|ii ± | ji
B= √ {i, j} ∈ M .
2
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 632
N EAR -O PTIMAL AND E XPLICIT B ELL I NEQUALITY V IOLATIONS
1
• If the outcome of the measurement is a state √ (|ii + | ji), Bob outputs {i, j} and v = 0.
2
1
• If the outcome of the measurement is a state √ (|ii − | ji), Bob outputs {i, j} and v = 1.
2
√
For each {i, j} ∈ M, the probability
√ to get (1/ 2)(|ii + | ji) equals 2/n if xi ⊕ x j = 0, and equals 0
otherwise, and similarly for (1/ 2)(|ii − | ji) with the parity flipped. Hence Bob’s output is always
correct.
3.1.1 Limits of classical protocols for HMn
Here we show that classical protocols with little communication cannot have good success probability. To
start, note that a protocol that uses shared randomness is just a probability distribution over deterministic
protocols, hence the maximal winning probability is achieved by a deterministic protocol.
Theorem 3.3. Every classical deterministic protocol for HMn with c bits of one-way communication,
where Bob outputs ({i, j}, v), has
1 c+1
Pr[v = xi ⊕ x j ] ≤ +√ .
2 n−1
The intuition behind the proof is the following. If the communication c is small, the set Xm of inputs x
for which Alice sends message m will typically be large (of size about 2n−c ), meaning Bob has little
n
knowledge of most of the bits of x. The KKL inequality implies that for most of the 2 pairs {i, j}, Bob
cannot guess the parity xi ⊕ x j well. Of course, Bob has some freedom in which {i, j} he outputs, but that
freedom is limited to the n/2 pairs {i, j} in his matching M, and it turns out that on average he will not
be able to guess any of those parities well.
Proof. Fix a classical deterministic protocol. For each m ∈ {0, 1}c , let Xm ⊆ {0, 1}n be the set of Alice’s
inputs for which she sends message m. These sets Xm together partition Alice’s input space {0, 1}n .
Define pm = |Xm |/2n . Note that ∑m pm = 1, so {pm } is a probability distribution over the 2c messages m.
For each m, define the following probability distribution over all possible pairs {i, j}:
qm ({i, j}) = Pr[Bob outputs {i, j} | Bob received m] .
We have
1
qm ({i, j}) ≤ , (3.1)
n−1
because we assume Bob always outputs an element from M and for fixed i 6= j we have Pr[{i, j} ∈ M] =
1/(n − 1), since each j is equally likely to be paired up with i under the uniform distribution on M. This
implies
1
∑ qm ({i, j})2 ≤ max
{i, j}
qm ({i, j}) · ∑ qm ({i, j}) = max qm ({i, j}) ≤
{i, j} n−1
. (3.2)
{i, j} {i, j}
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 633
H ARRY B UHRMAN , O DED R EGEV, G IANNICOLA S CARPA , AND RONALD DE W OLF
Define ε such that
1
Pr[v = xi ⊕ x j ] = +ε ,
2
and εm such that
1
Pr[v = xi ⊕ x j | Bob received m] = + εm .
2
Then ε = ∑m pm εm . The best Bob can do when guessing xi ⊕ x j given message m, is to output the value
of xi ⊕ x j that occurs most often among the x ∈ Xm . Define
βmi j = E [(−1)xi ⊕x j ] .
x∈Xm
Intuitively, if Xm (and hence pm ) is large, then most of these βmi j should be small. We now use the KKL
inequality (Theorem 2.2) to make this intuition precise.
(
2 4 log2 (1/pm )2 if pm ≤ 1/2 ,
Claim 3.4. ∑ βmi j≤
{i, j} 2 if pm > 1/2 .
Proof. Let f : {0, 1}n → {0, 1} be the characteristic function of the set Xm , so that Pr[ f (x) 6= 0] =
|Xm |/2n = pm . Observe that βmi j is proportional to the Fourier coefficient fb({i, j}):
2n 1 b
βmi j = E [(−1)xi ⊕x j ] = x ⊕x
E n [ f (x)(−1) i j ] = f ({i, j}) .
x∈Xm |Xm | x∈{0,1} pm
Using the KKL inequality with a δ ∈ [0, 1] to be specified later, we get
2/(1+δ )
δ 2 ∑ fb({i, j})2 ≤ ∑ δ |S| fb(S)2 ≤ Pr[ f (x) 6= 0]2/(1+δ ) = pm ,
{i, j} S⊆[n]
and therefore
1 1
∑ βmi2 j = p2m ∑ fb({i, j})2 ≤ δ 2 (1/pm )2−2/(1+δ ) .
{i, j} {i, j}
For pm > 1/2 simply choose δ = 1. For pm ≤ 1/2, choose δ = 1/ log2 (1/pm ), which is in [0, 1], so that
the above is
log2 (1/pm )2 (1/pm )2δ /(1+δ ) ≤ log2 (1/pm )2 (1/pm )2δ = 4 log2 (1/pm )2 .
The fraction of x ∈ Xm where xi ⊕ x j = 0 is 1/2 + βmi j /2, hence Bob’s optimal success probability
when guessing xi ⊕ x j is 1/2 + |βmi j |/2. This implies, for fixed m,
1 |βmi j | 1
E + ≥ Pr[v = xi ⊕ x j ] = + εm ,
{i, j}∼qm 2 2 2
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 634
N EAR -O PTIMAL AND E XPLICIT B ELL I NEQUALITY V IOLATIONS
where “{i, j} ∼ qm ” means that {i, j} is distributed according to distribution qm . This allows us to upper
bound εm for m where pm ≤ 1/2:
2εm ≤ E [|βmi j |]
{i, j}∼qm
= ∑ qm ({i, j})|βmi j |
{i, j}
s s
≤ ∑ qm ({i, j})2 · ∑ βmi2 j
{i, j} {i, j}
2 log2 (1/pm )
≤ √ ,
n−1
where the second inequality is by Cauchy-Schwarz and the third uses both equation (3.2) and the first
3.4. Since the pm sum to 1, there can be at most one m for which pm > 1/2. For that m we
part of Claim √
have εm ≤ 1/ n − 1 by an analogous argument combined with the second part of Claim 3.4.
Finally we can bound ε, treating the (at most one) m with pm > 1/2 separately:
ε = ∑ pm εm
m∈{0,1}c
log2 (1/pm ) 1
≤ ∑ pm √ +√
m n−1 n−1
1
= √ (H(p) + 1)
n−1
c+1
≤ √ ,
n−1
where H(p) = ∑m pm log2 (1/pm ) denotes the binary entropy function, which is at most c since the
distribution {pm } is on 2c elements.
3.2 Classical protocol for HMn
Here we design a classical protocol that achieves the above upper bound on the success probability. This
protocol has no bearing on the large Bell inequality violations that are our main goal in this paper, but it
is nice to know the previous upper bound on the maximal success probability is essentially tight.
√
Theorem 3.5. For every n that is a power of 2, and every positive integer c ≤ n, there exists a classical
protocol for HMn with c bits of one-way communication, such that for all inputs x, M,
1 c
Pr[v = xi ⊕ x j ] = + Ω √ .
2 n
√
Proof. Assume for simplicity that n is integer, and that c is even and sufficiently large. Alice and Bob
√
use shared randomness to choose two disjoint subsets S1 , S2 of [n] of size n each. Let y denote the bits
of x located in the indices given by the first subset, and z the bits located in the indices given by the second
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 635
H ARRY B UHRMAN , O DED R EGEV, G IANNICOLA S CARPA , AND RONALD DE W OLF
√ c/2
subset. Alice and Bob use shared randomness to produce 2c/2 random n-bit strings y(1) , . . . , y(2 ) . For
√
each `, the distance d(y, y(`) ) is distributed binomially, as the sum of n fair coin flips.
The following well-known fact about the tail of binomial distribution can be seen for instance by
k √
estimating k/2−β k using Stirling’s approximation.
Fact 3.6.√There exists a universal constant γ > 0 such that if X is the sum of k fair coin flips, then for all
0 < β < k/2 we have √ 2
Pr X ≤ k/2 − β k ≥ 2−γ(1+β ) .
Thus we have √ 2
Pr d(y, y(`) ) ≤ n/2 − β n1/4 ≥ 2−γ(1+β ) .
√
Hence by choosing β = Θ( c), with probability close to 1, there will be an ` such that y and y(`) are at
relative distance ≤ 1/2 − Ω(c1/2 /n1/4 ). If so, Alice sends Bob the first such `, and otherwise she tells him
there is no such `. This costs c/2 bits of communication. Similarly, at the expense of another c/2 bits of
communication, Bob obtains an approximation of z with relative distance at most ≤ 1/2 − Ω(c1/2 /n1/4 ).
It is easy to see that with probability at least 1/2, Bob’s matching M contains an {i, j} with i ∈ S1 and
j ∈ S2 . Bob can predict xi with success probability 1/2 + Ω(c1/2 /n1/4 ) from his approximation of y, and
can predict x j with success probability 1/2 + Ω(c1/2 /n1/4 ) from his approximation of z. These success
√
probabilities are independent, hence he can predict xi ⊕ x j with success probability 1/2 + Ω(c/ n). If
there is no such {i, j} ∈ M, or if he did not get good approximations to y or z, then Bob just outputs any
{i, j} ∈ M and a random bit for v, giving success probability 1/2. Putting everything together, we have a
√
protocol that wins with probability 1/2 + Ω(c/ n).
3.3 Entangled value for HMnNL
We now port our results to the non-local setting, referring to Definition 1.1 for the game associated with
the Hidden Matching problem.
Theorem 3.7. For every n that is a power of 2, there exists an entangled strategy for HMnNL using a
maximally entangled state with local dimension n, such that condition (1.1) is always satisfied.
1
Proof. The strategy is as follows. Alice and Bob share |ψi = √ ∑ log n |ii|ii.
n i∈{0,1}
1. Alice performs a phase-flip according to her input x. The state becomes
1
√ ∑ log n (−1)xi |ii|ii .
n i∈{0,1}
2. Bob performs a projective measurement with projectors Pi j = |iihi| + | jih j|, with {i, j} ∈ M. The
state collapses to
1
√ (−1)xi |ii|ii + (−1)x j | ji| ji
2
for some {i, j} ∈ M known to Bob.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 636
N EAR -O PTIMAL AND E XPLICIT B ELL I NEQUALITY V IOLATIONS
3. Both players apply Hadamard transforms H ⊗ log n , and the state becomes
1
xi +a·i+b·i x j +a· j+b· j
√ ∑ (−1) + (−1) |ai|bi .
2n a,b∈{0,1}log n
Notice that in the latter state, any pair a, b with nonzero amplitude must satisfy that
(a · (i ⊕ j)) ⊕ (b · (i ⊕ j)) = xi ⊕ x j .
Hence, if the players measure the state, Alice outputs a, and Bob outputs {i, j} and the bit d = b · (i ⊕ j),
then they win the game with certainty.
3.4 Classical value for HMnNL
In contrast to the entangled value, the optimal classical winning probability is not much better than 1/2:
Theorem 3.8. The winning probability of any classical strategy for HMnNL differs from 1/2 by at most
√
O ((log n)/ n).
Proof. A strategy that wins HMnNL with success probability 1/2 + ε can be turned into a protocol for HMn
with log n bits of communication and the same winning probability: the players play HMnNL , with Alice
producing a and Bob producing {i, j}, d; Alice then sends a to Bob, who outputs {i, j}, (a · (i ⊕ j)) ⊕ d.
The latter bit equals xi ⊕ x j with probability 1/2 + ε. This requires c = log n bits of communication, so
√
Theorem 3.3 implies the upper bound 1/2 + O ((log n)/ n) on the winning probability. The lower bound
√
of 1/2 − O ((log n)/ n) on the winning probability follows similarly.
Next we show that our upper bound on the successp probability of classical strategies for HMnNL is
nearly optimal: we can achieve advantage at least Ω( (log n)/n). In the Appendix we also give a
√
simple alternative strategy with a slightly weaker advantage of Ω(1/ n). The correctness of that more
elementary strategy can be proven from first principles, unlike the one presented here. Theorem 3.9 and
the Appendix have no bearing on our separation, but are included here mostly for completeness.
power of 2, there exists a classical deterministic strategy for HMnNL
Theorem 3.9. For every n that is ap
with winning probability 1/2 + Ω (log n)/n (under the uniform input distribution).
Proof. The strategy is as follows. Bob finds the j ∈ {2, . . . , n} that is matched to 1 in M, and outputs
{1, j} and d = 0. Since the number i = 1 corresponds to the string 0log n , the winning condition (a ·
(i ⊕ j)) ⊕ d = xi ⊕ x j is now equivalent to a · j = x1 ⊕ x j . Alice, given her input x ∈ {0, 1}n , outputs the
value a ∈ {0, 1}log n that maximizes the winning probability subject to j being uniformly distributed over
{2, . . . , n}. That is, she selects an a that maximizes the number
Jax := |{ j ∈ {2, . . . , n} : a · j = x1 ⊕ x j }| .
The winning probability of this strategy, for fixed x and uniformly random M, is maxa Jax /(n − 1). In the
remainder of this proof we show that
p
E[max Jax ] ≥ n/2 + Ω( n log n) , (3.3)
x a
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 637
H ARRY B UHRMAN , O DED R EGEV, G IANNICOLA S CARPA , AND RONALD DE W OLF
which implies the theorem.
We use the following result due to Talagrand [21, Proposition 4.13]. For a finite set T ⊆ Rn , define
" #
n
r(T ) := E sup ∑ ziti .
z∈{±1}n t∈T i=1
This is the expected maximal overlap between z and the elements of T , expectation taken over uniformly
random z ∈ {±1}n . Let N(T, d2 ; ε) denote the minimal number of (open) balls of radius ε > 0 (in
Euclidean distance d2 ) needed to cover T .
Proposition 3.10 (Talagrand). There exists a constant K > 0 such that for any ε > 0 and T ⊆ Rn , if
maxt∈T,i∈[n] |ti | ≤ ε 2 /(Kr(T )), then
p
ε log N(T, d2 ; ε) ≤ Kr(T ) .
We apply this proposition as follows. For a ∈ {0, 1}log n consider the Hadamard codeword h(a) :=
((−1)a· j ) j∈{0,1}log n , with bits represented as ±1 instead of 0/1. Let T = {h(a) : a ∈ {0, 1}log n } be the set
of n Hadamard codewords. √ Any two distinct elements of T differ in exactly n/2 positions, and hence are
√
at Euclidean distance 2n. Therefore a ball of radius ε := n/2 can contain at most one element of T ,
so we need exactly n balls of radius ε to cover T (i. e., N(T, d2 ; ε) = n). Proposition 3.10 now implies
p
r(T ) = Ω( n log n) .
The definition of r(T ) takes the absolute value of ∑ni=1 ziti , but by symmetry, with probability 1/2 this
√
quantity is positive for the maximizing t, and moreover the sum can never be smaller than − n since T
forms an orthogonal basis. Hence we also have
" #
n p
E sup ∑ ziti = Ω( n log n) .
z∈{±1}n t∈T i=1
This means that we expect z to be relatively close in Hamming distance to some Hadamard codeword:
√
the expected number of positions where z agrees with the closest t ∈ T is n/2 + Ω( n log n). In our
application, since x itself is uniformly random, the string y := ((−1)x1 ⊕x j ) j∈{0,1}log n is uniformly random
except for its first bit, which is fixed to 1. Our quantity maxa Jax measures the number of positions where
y agrees with the closest t ∈ T , ignoring the first position. We conclude that
p
E max Jax ≥ n/2 + Ω( n log n) − 1 .
x∈{0,1}n a∈{0,1}log n
This implies equation (3.3).
4 The Khot-Vishnoi game
4.1 The classical value
In this section we analyze the classical value of the Khot-Vishnoi game (Definition 1.2). Our main result
is an upper bound on the classical value of 1/nη/(1−η) , based on the analysis from [20].
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 638
N EAR -O PTIMAL AND E XPLICIT B ELL I NEQUALITY V IOLATIONS
Before we give that upper bound, let us first argue that it is essentially tight, i. e., there exists a strategy
whose winning probability is approximately 1/nη/(1−η) . To get some intuition for this game, first think
of η as some small constant (even though we will eventually choose it close to 1/2), and consider the
following natural classical strategy:
Alice and Bob each output the element of their coset that has highest Hamming weight.
The idea is that if a is the element of highest Hamming weight in Alice’s coset x, we expect a ⊕ z to
also be of high Hamming weight (because it is close to a in Hamming distance), and since a ⊕ z is in
his coset y, Bob is somewhat likely to pick it as his output. We now give a brief back-of-the-envelope
calculation suggesting that the winning probability of this strategy is approximately 1/nη/(1−η) ; since it
is not required for our main result, we will not attempt to make this argument rigorous.
Let t ≥ 0 be such that the probability that a binomial B(n, 1/2) variable is greater than (n + t)/2
is 1/n. Recalling that the cumulative distribution function of the binomial distribution B(n, p) can be
approximated by that of the normal distribution N(np, np(1 − p)), and that the probability that a normal
2
variable is greater than its mean by s standard deviations
√ is approximately e−s /2 , we can essentially
2
choose t to be the solution to e−t /(2n) = 1/n (so t = 2n ln n). Then we expect Alice’s n-element coset
to contain exactly one element of Hamming weight greater than (n + t)/2. Since the element a that
Alice picks is the one of highest Hamming weight, we assume for simplicity that its Hamming weight is
(n + t)/2. The players win the game if and only if a ⊕ z has the highest weight among Bob’s n elements,
which we heuristically approximate by the event that a ⊕ z has Hamming weight at least (n + t)/2.
The Hamming weight of a ⊕ z is distributed as the sum of two independent binomial distributions
B((n + t)/2, 1 − η) and B((n − t)/2, η), which can be approximated as above by the normal distribution
N((n +t)/2 − ηt, nη(1 − η)). Hence, for the Hamming
p weight of a ⊕ z to be at least (n +t)/2, the normal
variable needs to be greater than its mean by ηt/ nη(1 − η) standard deviations, and the probability of
this happening is approximately
2 2 1
e−η t /(2nη(1−η)) = ,
nη/(1−η)
as claimed.
Now we show that no classical strategy can be substantially better. The main technical tool used in
the proof is the hypercontractive inequality (Theorem 2.1), which is applicable to our setting because we
choose u uniformly and u ⊕ z may be viewed as a “noisy version” of u.
Theorem 4.1. For every n that is a power of 2, and every η ∈ [0, 1/2], every classical strategy for the
Khot-Vishnoi game KVn (Definition 1.2) has winning probability at most 1/nη/(1−η) .
Proof. Recall that the inputs are generated as follows: we choose a uniformly random u ∈ {0, 1}n and
an η-biased z ∈ {0, 1}n , and define the respective inputs to be the cosets u ⊕ H and u ⊕ z ⊕ H. We
can assume without loss of generality that Alice and Bob’s behavior is deterministic. Define functions
A, B : {0, 1}n → {0, 1} by A(u) = 1 if and only if Alice’s output on u ⊕ H is u, and similarly for Bob.
Notice that by definition, these functions attain the value 1 on exactly one element of each coset, and
hence Eu [A(u)] = Eu [B(u)] = 1/n.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 639
H ARRY B UHRMAN , O DED R EGEV, G IANNICOLA S CARPA , AND RONALD DE W OLF
Recall that the players win if and only if the sum of Alice’s output and Bob’s output equals z. Hence
for all u, z, ∑h∈H A(u ⊕ h)B(u ⊕ z ⊕ h) equals 1 if the players win on input pair u ⊕ H, u ⊕ z ⊕ H, and
equals 0 otherwise. Therefore, the winning probability is given by
E ∑ A(u ⊕ h)B(u ⊕ z ⊕ h) = ∑ E A(u ⊕ h)B(u ⊕ z ⊕ h)
u,z h∈H h∈H u,z
= n E A(u)B(u ⊕ z) ,
u,z
where the second equality uses the fact that for all h, u ⊕ h is uniformly distributed.
We use the Fourier analysis framework introduced in Section 2.1. We now have
E [A(u)B(u ⊕ z)] = E[A(u)(T1−2η B)(u)]
u,z u
= hA, T1−2η Bi
= hT√1−2η A, T√1−2η Bi
≤ T√1−2η A 2 · T√1−2η B 2
≤ kAk2−2η · kBk2−2η
1/(2−2η) 1/(2−2η)
= E[A(u)] · E[B(u)]
u u
1
= .
n1/(1−η)
Here the third equality follows from equations (2.1) and (2.2), the first inequality is by Cauchy-Schwarz,
√
the second is the hypercontractive inequality (Theorem 2.1 with q = 2, p = 2 − 2η and ρ = 1 − 2η)
applied to each of A and B, and the second to last equality uses the fact that A, B have range {0, 1}. We
complete the proof by noting that n/n1/(1−η) = 1/nη/(1−η) .
4.2 Lower bound on the entangled value
In this section we describe a good entangled strategy for the Khot-Vishnoi game, following the ideas of
Kempe, Regev, and Toner [18] and the SDP-solution of [20].
Theorem 4.2. For every n that is a power of 2, and every η ∈ [0, 1/2], there exists an entangled strategy
that wins KVn with probability at least (1 − 2η)2 , using a maximally entangled state of local dimension n.
√
Proof. For a ∈ {0, 1}n , let va ∈ Rn denote the unit vector ((−1)ai / n)i∈[n] . Notice that for all a, b,
we have hva , vb i = 1 − 2d(a, b)/n, where d(a, b) denotes the Hamming distance between a and b. In
particular, the n vectors va , as a ranges over a coset of H, form an orthonormal basis of Rn .
The entangled strategy is as follows. Alice and Bob start with the n-dimensional maximally entangled
state. Alice, given coset x = u ⊕ H as input, performs a projective measurement in the orthonormal basis
given by {va | a ∈ x} and outputs the value a given by the measurement. Bob proceeds similarly with
the basis {vb | b ∈ y} induced by his coset y = x ⊕ z ⊕ H. A standard calculation now shows that the
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 640
N EAR -O PTIMAL AND E XPLICIT B ELL I NEQUALITY V IOLATIONS
probability to obtain the pair of outputs a, b is hva , vb i2 /n. Since the players win if and only if b = a ⊕ z,
the winning probability on inputs x, y is given by
2 d(a, a ⊕ z) 2 2|z| 2
1 a a⊕z 2 1
∑ hv , v i = n ∑ 1 −
n a∈x n
= 1−
n
,
a∈x
where |z| denotes the Hamming weight of the η-biased string z. Taking expectation and using convexity,
the overall winning probability is
" #
2|z| 2 2|z| 2
E 1− ≥ E 1− = (1 − 2η)2 .
z n z n
5 Appendix: An alternative strategy for HMnNL
√
Here we
p give an alternative and slightly weaker version of Theorem 3.9, with advantage Ω(1/ n) instead
of Ω( (log n)/n).
Proof. Fix arbitrary inputs x, M. Bob always outputs i = 1 and j equal to whatever is matched to i by M.
Consider the following two unit vectors in Rn ,
√
u = (−1)x1 ⊕xk / n k∈[n] , v = ej ,
where e j is the vector with 1 in the jth coordinate and zero elsewhere. Notice that Alice knows u, Bob
√
knows v, and that hu, vi = (−1)x1 ⊕x j / n. The players use shared randomness to choose a random unit
vector w ∈ Rn . Bob outputs d = 0 if hw, vi > 0, and d = 1 otherwise. Alice outputs a = 0log n if hw, ui > 0,
and a uniform a ∈ {0, 1}log n otherwise.
We now analyze the success probability. Assume that x1 ⊕ x j = 0 (the other case being similar). It is
easy to see that the probability of both hw, ui and hw, vi being positive is
1 1
− arccoshu, vi ,
2 2π
as this is essentially a two-dimensional question. They have the same probability of both being negative,
and probability (1/2π) arccoshu, vi to be in each of the two remaining cases. In the two cases that
hw, ui ≤ 0 (an event that happens with probability 1/2), a · (i ⊕ j) is a uniform bit (since i 6= j) and the
players win with probability exactly 1/2. Otherwise (i. e., if hw, ui > 0), the players win if and only if
d = 0 (i. e., if also hw, vi > 0). Hence, using that arccos(z) = π/2 − Θ(z) for small z, the overall winning
probability is
1 1 1 1 1 1
· + − arccoshu, vi = + Θ √ .
2 2 2 2π 2 n
Acknowledgements. We thank Jop Briët, Dejan Dukaric, Carlos Palazuelos, and Thomas Vidick for
useful discussions and comments, and Carlos also for sending us his manuscripts [24, 23]. We also
thank the anonymous ToC referees and John Watrous for their many comments and suggestions, which
improved the presentation of the paper.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 641
H ARRY B UHRMAN , O DED R EGEV, G IANNICOLA S CARPA , AND RONALD DE W OLF
References
[1] Z IV BAR -YOSSEF, T. S. JAYRAM , AND I ORDANIS K ERENIDIS: Exponential separation of quan-
tum and classical one-way communication complexity. SIAM J. Comput., 38(1):366–384, 2008.
Preliminary version in STOC’04. [doi:10.1137/060651835] 626, 632
[2] J OHN S TEWART B ELL: On the Einstein Podolsky Rosen paradox. Physics, 1:195–200, 1964. 624
[3] J OP B RIËT, H ARRY B UHRMAN , T ROY L EE , AND T HOMAS V IDICK: Multiplayer XOR games and
quantum communication complexity with clique-wise entanglement. Quantum Inf. Comput., 2013.
To appear. Preprint (2009) at arXiv. 629
[4] J OP B RIËT AND T HOMAS V IDICK: Explicit lower and upper bounds on the entangled value of
multiplayer XOR games. Communications in Mathematical Physics, 2013. To appear. Preprint
(2011) at arXiv. [doi:10.1007/s00220-012-1642-5] 629
[5] J OHN F. C LAUSER , M ICHAEL A. H ORNE , A BNER S HIMONY, AND R ICHARD A. H OLT: Pro-
posed experiment to test local hidden-variable theories. Phys. Rev. Lett., 23(15):880–884, 1969.
[doi:10.1103/PhysRevLett.23.880] 624
[6] R ICHARD C LEVE , W ILLIAM S LOFSTRA , FALK U NGER , AND S ARVAGYA U PADHYAY: Perfect
parallel repetition theorem for quantum XOR proof systems. Comput. Complexity, 17(2):282–299,
2008. Preliminary version in CCC’07. [doi:10.1007/s00037-008-0250-4] 624
[7] J ULIEN D EGORRE , M ARC K APLAN , S OPHIE L APLANTE , AND J ÉRÉMIE ROLAND: The commu-
nication complexity of non-signaling distributions. Quantum Inf. Comput., 11(7&8):649–676, 2011.
Preliminary version in MFCS’09. Preprint (2008-11) at arXiv. [ACM:2230916.2230924] 625
[8] D EJAN D. D UKARIC: The Hilbertian tensor norm and its connection to quantum information theory.
2010. [arXiv:1008.1948v2] 625, 631
[9] A LBERT E INSTEIN , B ORIS P ODOLSKY, AND NATHAN ROSEN: Can quantum-mechanical de-
scription of physical reality be considered complete? Physical Review, 47(10):777–780, 1935.
[doi:10.1103/PhysRev.47.777] 624
[10] D MITRY G AVINSKY: Classical interaction cannot replace quantum nonlocality. 2009.
[arXiv:0901.0956] 626
[11] D MITRY G AVINSKY, J ULIA K EMPE , I ORDANIS K ERENIDIS , R AN R AZ , AND RONALD DE W OLF:
Exponential separation for one-way quantum communication complexity, with applications to
cryptography. SIAM J. Comput., 38(5):1695–1708, 2009. Preliminary version in STOC’07.
[doi:10.1137/070706550] 626
[12] D MITRY G AVINSKY, J ULIA K EMPE , O DED R EGEV, AND RONALD DE W OLF: Bounded-error
quantum state identification and exponential separations in communication complexity. SIAM J.
Comput., 39(1):1–24, 2009. Preliminary version in STOC’06. [doi:10.1137/060665798] 626
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 642
N EAR -O PTIMAL AND E XPLICIT B ELL I NEQUALITY V IOLATIONS
[13] M ARIUS J UNGE AND C ARLOS PALAZUELOS: Large violation of Bell inequalities with low
entanglement. Communications in Mathematical Physics, 306(3):695–746, 2011. Preprint (2010)
at arXiv. [doi:10.1007/s00220-011-1296-8] 625, 627, 629, 631
[14] M ARIUS J UNGE , C ARLOS PALAZUELOS , DAVID P ÉREZ -G ARCÍA , I GNACIO V ILLANUEVA , AND
M ICHAEL M. W OLF: Unbounded violations of bipartite Bell inequalities via operator space theory.
Communications in Mathematical Physics, 300(3):715–739, 2010. Preprint (2009) at arXiv. Shorter
version appeared in Phys. Rev. Lett. [doi:10.1007/s00220-010-1125-5] 625, 627, 631
[15] J EFF K AHN , G IL K ALAI , AND NATHAN L INIAL: The influence of variables on Boolean functions.
In Proc. 29th FOCS, pp. 68–80. IEEE Comp. Soc. Press, 1988. [doi:10.1109/SFCS.1988.21923]
626, 630
[16] J ULIA K EMPE , H IROTADA KOBAYASHI , K EIJI M ATSUMOTO , B EN T ONER , AND T HOMAS
V IDICK: Entangled games are hard to approximate. SIAM J. Comput., 40(3):848–877, 2011.
Preliminary version in FOCS’08. [doi:10.1137/090751293] 624
[17] J ULIA K EMPE , H IROTADA KOBAYASHI , K EIJI M ATSUMOTO , AND T HOMAS V IDICK: Using
entanglement in quantum multi-prover interactive proofs. Comput. Complexity, 18(2):273–307,
2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0275-3] 624
[18] J ULIA K EMPE , O DED R EGEV, AND B EN T ONER: Unique games with entangled provers are easy.
SIAM J. Comput., 39(7):3207–3229, 2010. Preliminary version in FOCS’08. Preprint (2007-09) at
arXiv. [doi:10.1137/090772885] 624, 627, 628, 640
[19] S UBHASH K HOT: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp.
767–775. ACM Press, 2002. [doi:10.1145/509907.510017] 627
[20] S UBHASH A. K HOT AND N ISHEETH K. V ISHNOI: The unique games conjecture, integrality gap
for cut problems and embeddability of negative type metrics into `1 . In Proc. 46th FOCS, pp. 53–62.
IEEE Comp. Soc. Press, 2005. [doi:10.1109/SFCS.2005.74] 627, 638, 640
[21] M ICHEL L EDOUX AND M ICHEL TALAGRAND: Probability in Banach Spaces. Springer, 1991. 638
[22] RYAN O’D ONNELL: Some topics in analysis of Boolean functions. Technical Report 055, 2008.
Available at ECCC. Paper for invited talk at STOC’08. 629
[23] C ARLOS PALAZUELOS: Bounding the largest Bell violation attainable by a quantum state. 2012.
[arXiv:1206.3695] 629, 641
[24] C ARLOS PALAZUELOS: Superactivation of quantum nonlocality. Phys. Rev. Lett., 109(19):190401,
Nov 2012. Preprint (2012) at arXiv. [doi:10.1103/PhysRevLett.109.190401] 628, 641
[25] DAVID P ÉREZ -G ARCÍA , M ICHAEL M. W OLF, C ARLOS PALAZUELOS , I GNACIO V ILLANUEVA ,
AND M ARIUS J UNGE : Unbounded violations of tripartite Bell inequalities. Communications of
Mathematical Physics, 279:455, 2008. Preprint (2012) at arXiv. [doi:10.1007/s00220-008-0418-4]
629
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 643
H ARRY B UHRMAN , O DED R EGEV, G IANNICOLA S CARPA , AND RONALD DE W OLF
[26] O DED R EGEV: Bell violations through independent bases games. Quantum Inf. Comput., 12(1-2):9–
20, 2012. Preprint (2011) at arXiv. [ACM:2231038] 625
[27] B ORIS S. T SIREL’ SON: Quantum analogues of the Bell inequalities. The case of two spatially
separated domains. J. Math. Sciences, 36(4):557–570, 1987. [doi:10.1007/BF01663472] 625
[28] RONALD DE W OLF: A brief introduction to Fourier analysis on the Boolean cube. Theory of
Computing Library, Graduate Surveys, 1:1–20, 2008. [doi:10.4086/toc.gs.2008.001] 629
AUTHORS
Harry Buhrman
Professor
CWI and University of Amsterdam
buhrman cwi nl
http://homepages.cwi.nl/~buhrman
Oded Regev
Professor
Blavatnik School of Computer Science, Tel Aviv University, and CNRS, ENS Paris.
http://www.cs.tau.ac.il/~odedr
Giannicola Scarpa
Ph. D. student
CWI Amsterdam
g scarpa cwi nl
http://homepages.cwi.nl/~scarpa
Ronald de Wolf
Professor
CWI and University of Amsterdam
rdewolf cwi nl
http://homepages.cwi.nl/~rdewolf
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 644
N EAR -O PTIMAL AND E XPLICIT B ELL I NEQUALITY V IOLATIONS
ABOUT THE AUTHORS
H ARRY B UHRMAN received his Ph. D. from the University of Amsterdam in 1993. His
advisors were Peter van Emde Boas and Steven Homer. He is now group leader of the
Algorithms and Complexity group at CWI and holds a part-time position as full professor
at the University of Amsterdam. His interests include quantum computing, complexity
theory, and computational biology.
O DED R EGEV graduated from Tel Aviv University in 2001 under the supervision of Yossi
Azar. He spent two years as a postdoc at the Institute for Advanced Study, Princeton, and
one year at the University of California, Berkeley. He is currently with the cryptography
group at the École Normale Supérieure, Paris. His research interests include quantum
computation, computational aspects of lattices, and other topics in theoretical computer
science. He also enjoys photography, especially of his baby girl.
G IANNICOLA S CARPA is a Ph. D. student at CWI, Amsterdam, supervised by Ronald de
Wolf. In 2009, he received a Master’s degree in Computer Science from the University
of Salerno, Italy. His research interests include quantum computing, non-locality, combi-
natorial optimization, and game theory. In his free time, he is a devoted movie-goer but
unsuccessful movie maker, he devours short stories, writes some, and he often claims he
is going to lose weight.
RONALD DE W OLF received his Ph. D. from the University of Amsterdam and CWI in
2001. His advisors were Harry Buhrman and Paul Vitányi. After doing a postdoc at
the University of California, Berkeley, he now holds a permanent position at CWI and
a part-time position as full professor at the University of Amsterdam. His CS interests
include quantum computing, complexity theory, and learning theory. He also holds a
degree in philosophy, and enjoys classical music and literature.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 623–645 645