# Near-Optimal and Explicit Bell Inequality Violations

Harry Buhrman CWI and University of Amsterdam<EMAIL_ADDRESS>Supported by a
Vici grant from NWO, and EU-grant QCS. Oded Regev Blavatnik School of Computer
Science, Tel Aviv University, and CNRS, ENS Paris. 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. Giannicola Scarpa CWI Amsterdam<EMAIL_ADDRESS>Supported by a Vidi grant from NWO, and EU-grant QCS. Ronald de Wolf CWI and
University of Amsterdam<EMAIL_ADDRESS>Supported by a Vidi grant from NWO,
and EU-grant QCS.

###### Abstract

Bell inequality violations correspond to behavior of entangled quantum systems
that cannot be simulated classically. 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 quantum 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 $\frac{1}{2}$ by at most $O(\log n/\sqrt{n})$.

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 to win the game with probability $1/(\log
n)^{2}$, while the best winning probability without entanglement is $1/n$.
This near-linear ratio (“Bell inequality violation”) is near-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, i.e., by “local hidden-variable theories.”
This was first noted by Bell [Bel64] in response to Einstein-Podolsky-Rosen’s
challenge to the completeness of quantum mechanics [EPR35]. 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 doesn’t travel faster than the speed of
light) and “realistic” (meaning that 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 quantum predictions, 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 “quantum correlations” can deviate
from what is achievable classically. The setup for a game $G$ is as follows.
Two space-like separated parties, called Alice and Bob, receive inputs $x$ and
$y$ according to some fixed and known probability distribution $\pi$, and are
required to produce outputs $a$ and $b$, respectively. There is a predicate
specifying which outputs $a,b$ “win” the game on inputs $x,y$. The definition
of the game $G$ consists of this predicate and the distribution $\pi$. The
goal is to design games where entanglement-based 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 [KKM+08, KKMV08], parallel repetition
[CSUU07, KRT08], and cryptography.

Quantum 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_ $\omega^{*}(G)$ of the
game is the supremum of the expected winning probability, taken over all
entangled strategies. When restricting to strategies that use entanglement of
local dimension $n$, the value is denoted $\omega^{*}_{n}(G)$. This should be
contrasted with the _classical value_ $\omega(G)=\omega^{*}_{0}(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 “quantum correlations” cannot
be simulated classically, corresponds to the fact that there are games $G$
where the entangled value $\omega^{*}(G)$ is strictly larger than the
classical value $\omega(G)$. For reasons explained in Section 2, such examples
are known in the physics literature as “Bell inequality violations.” The CHSH
game is one particularly famous example [CHSH69]. Here the inputs
$x\in\\{0,1\\}$ and $y\in\\{0,1\\}$ are uniformly distributed, and Alice and
Bob win the game if their respective outputs $a\in\\{0,1\\}$ and
$b\in\\{0,1\\}$ satisfy $a\oplus b=x\wedge y$; in other words, $a$ should
equal $b$ unless $x=y=1$. The classical value of this game is $\omega(G)=3/4$,
while the entangled value is $\omega^{*}(G)=\cos(\pi/8)^{2}\approx 0.85$. The
entangled value is achieved already with 2-dimensional entanglement (i.e., one
EPR-pair), so $\omega^{*}(G)=\omega^{*}_{2}(G)$ for this game [Tsi87].

In the physics literature it is common to quantify the violation demonstrated
by a given game $G$ by the ratio of entangled and classical values. The larger
this ratio the better, both for philosophical reasons (to show the divergence
between classical and quantum worlds) and for practical reasons (a larger
violation is typically more noise-resistant and easier to realize in the noisy
circumstances of an actual laboratory). To be precise, Bell violations are
defined for a slight generalization of the notion of a game, which we call a
_Bell functional_ 111There is unfortunately no good name for this notion in
the literature. It is often called “Bell inequality,” but this is a misnomer
since (1) it is not an inequality, and (2) the term Bell inequality is used to
describe upper bounds on the classical value., where roughly speaking, some
outputs might lead to a loss (or a negative gain) to the players. Since this
discussion is not too relevant for our main results, we postpone it to Section
2. For now, suffice it to say that when considering the violation exhibited by
a game, instead of comparing the maximum winning probabilities as we did
above, one can also compare the maximum achievable deviation of the winning
probability from (say) $1/2$. This is exactly what we will do in our first
game in Section 3.

In two recent papers, Junge et al. [JPP+10, JP11] studied how large a Bell
inequality violation one can obtain. In terms of upper bounds, [JPP+10] proved
that the maximum Bell inequality violation $\omega^{*}_{n}(G)/\omega(G)$
obtainable with entangled strategies of local dimension $n$, is at most
$O(n)$, and [JP11, Theorem 6.8] proved that if Alice and Bob have at most $k$
possible outputs each, then the violation $\omega^{*}(G)/\omega(G)$ is at most
$O(k)$, irrespective of the amount of entanglement they can use. (This
improved an earlier $O(k^{2})$ upper bound due to Degorre et al. [DKLR09], and
was also obtained for the special case of games by Dukaric [Duk10, Theorem
4].) These upper bounds hold for all Bell functionals, and not just for games.
In terms of lower bounds, [JPP+10] showed the existence of a Bell inequality
violation of order $\sqrt{n}/(\log n)^{2}$, where $n$ is both the
entanglement-dimension and the number of outputs of Alice and Bob. This was
recently improved to $\sqrt{n}/\log n$ in [JP11]. Both constructions are
probabilistic, and the proofs show that with high probability the constructed
Bell functionals exhibit a large violation. 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 [Reg11].)

Our main result in this paper is to exhibit two stronger and fully explicit
Bell inequality violations. Interestingly, both of our games address a
question in theoretical physics but are inspired by theoretical computer
science (communication complexity and unique games, respectively), and the
tools used to analyze them are very much the tools from theoretical computer
science. In fact, one aim of this paper is to export our techniques to
mathematical physics.

In the remainder of this introduction we provide an overview of our two non-
local games, followed by some discussion and comparison.

###  1.1 The Hidden Matching game

The “Hidden Matching” problem was introduced in quantum communication
complexity by Bar-Yossef et al. [BJK08], and many variants of it were
subsequently studied [GKRW09, GKK+08, Gav09]. The original version is as
follows. Let $n$ be a power of 2. Alice is given input $x\in\\{0,1\\}^{n}$ and
Bob is given a perfect matching $M$ (i.e., a partition of $[n]$ into $n/2$
disjoint pairs $(i,j)$). Both inputs are uniformly distributed.222All our
results also hold with minor modifications for the case that Bob’s matching is
chosen uniformly from the set $\\{M_{k}~{}|~{}k\in\\{0,\ldots,n/2-1\\}\\}$,
where the matching $M_{k}$ consists of the pairs $(i,j)$ where $i\leq n/2$ and
$j=n/2+1+(i+k-1\mbox{ mod }n/2)$. This has the advantage of lowering the
number of possible inputs to Bob to $n/2$. We allow one-way communication from
Alice to Bob, and Bob is required to output a pair $(i,j)\in M$ and a bit
$v\in\\{0,1\\}$. They win if $v=x_{i}\oplus x_{j}$.

In Section 3.1 we show that if Alice sends Bob a $c$-bit message, then their
optimal winning probability is $\frac{1}{2}+\Theta(\frac{c}{\sqrt{n}})$. Bar-
Yossef et al. [BJK08] earlier proved this for $c=\Theta(\sqrt{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” [KKL88] from
Fourier analysis of Boolean functions (see [O’D08, Wol08] for surveys of this
area). 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 $x_{i}\oplus x_{j}$ well for many $(i,j)$ pairs. His matching $M$ is
uniformly distributed, independent of $x$, and contains only $n/2$ of all
${n\choose 2}$ 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 [GKK+08], though their
analysis is different and more complicated because their variant is a promise
problem with a non-product input distribution.

The non-local game based on Hidden Matching is as follows: the inputs $x$ and
$M$ are the same as before, but now Alice and Bob don’t communicate. Instead,
Alice outputs an $a\in\\{0,1\\}^{\log n}$, Bob outputs $d\in\\{0,1\\}$ and
$(i,j)\in M$, and they win the game if the outputs satisfy the relation
$(a\cdot(i\oplus j))\oplus d=x_{i}\oplus x_{j}$, where the dot indicates inner
product (modulo 2) of two $\log n$-bit strings. Observe that Alice has $n$
possible outputs and Bob also has $2\cdot n/2=n$ possible outputs.

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$: Alice sends Bob the $\log n$-bit output $a$ from the
non-local strategy, allowing Bob to compute $v=(a\cdot(i\oplus j))\oplus d$.
Since $v=x_{i}\oplus x_{j}$ with probability $p$, Bob can now output
$(i,j),v$. 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(\frac{\log n}{\sqrt{n}})$.

In contrast, there is a strategy that wins with probability 1 using $\log n$
EPR-pairs, which shows $\omega^{*}_{n}(G)=1$.333The 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’s also the number of possible outputs for each player, _and_ the
local dimension of the entangled state that our quantum protocol uses (though
we don’t claim that this entanglement-dimension $n$ is needed to achieve the
best-possible entangled value). This game therefore exhibits a Bell violation
of $\Omega(\sqrt{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. [JPP+10, JP11], 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 losing the $\log n$ factor; however in Theorem 6 we exhibit a classical
strategy with winning probability $1/2+\Omega(\sqrt{\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 [KV05] on
the famous _Unique Games Conjecture_ (UGC), which was introduced by Khot
[Kho02]. The UGC is a hardness-of-approximation assumption for a specific
graph labeling problem, the details of which need not concern us here. The
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 exhibited a large integrality gap for the standard
semidefinite programming (SDP) relaxation of this labeling problem, showing
that at least SDP-solvers will not be able to efficiently approximate the
value of the optimal labeling. We use essentially the same set-up for our
game, though for our purposes we will not have to worry about SDPs or the UGC.
Kempe, Regev, and Toner [KRT08] already observed that they could combine their
“quantum rounding” technique with the game of [KV05] to get a Bell inequality
violation of $n^{\varepsilon}$ for some small constant $\varepsilon>0$, where
$n$ is the entanglement dimension and the number of possible outputs. 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, showing that, somewhat surprisingly, nearly optimal
violations can be obtained using this method.

The game is parameterized by an integer $n$, which we assume to be a power of
2, and a “noise-parameter” $\eta\in[0,1/2]$. Consider the group
$\\{0,1\\}^{n}$ of all $n$-bit strings with ‘$\oplus$’ denoting bitwise
addition mod 2, and let $H$ be the subgroup containing the $n$ Hadamard
codewords. This subgroup partitions $\\{0,1\\}^{n}$ into $2^{n}/n$ cosets of
$n$ elements each. Alice receives a uniformly random coset $x$ as input, which
we can think of as $u\oplus H$ for uniformly random $u\in\\{0,1\\}^{n}$. Bob
receives a coset $y$ obtained from Alice’s by adding a string of low Hamming
weight, namely $y=x\oplus z=u\oplus z\oplus H$, where each bit of
$z\in\\{0,1\\}^{n}$ is set to 1 with probability $\eta$, independently of the
other bits. Notice that 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$, which is typically around $\eta 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\in x$, Bob outputs $b\in y$, and they win the game iff $a\oplus
b=z$.444Note that the winning condition for this game is a “randomized
predicate”, as there are $n$ possible predicates (one for each $z$ in $x\oplus
y$) corresponding to each pair of inputs $x,y$. However, it is easy to see
that with very high probability exactly one of these $n$ constraints dominates
(namely, the one corresponding to a $z$ of Hamming weight around $\eta n$).
This allows one to modify the game in a straightforward manner, making it a
game with a deterministic predicate (although there is usually no reason to do
so). Notice that the number of possible inputs to each player is $2^{n}/n$ and
the number of possible outputs for each player is $n$.

Based on the integrality gap analysis of Khot and Vishnoi, we show that no
classical strategy can win this game with probability greater than
$1/n^{\eta/(1-\eta)}$. We also sketch a classical strategy that achieves
roughly this winning probability. In contrast, using a simplified version of
the “quantum rounding” technique of [KRT08], we exhibit a quantum strategy
that uses the $n$-dimensional maximally entangled state and wins with
probability at least $(1-2\eta)^{2}$. This strategy follows from the
observation that each coset of $H$ defines an orthonormal basis of
$\mathbb{R}^{n}$ in which we can do a measurement. Summarizing, we have
entangled value $\omega^{*}_{n}(G)\geq(1-2\eta)^{2}$ and classical value
$\omega(G)\leq 1/n^{\eta/(1-\eta)}$ for this game. Setting the noise-rate to
$\eta=1/2-1/\log n$, the entangled value is roughly $1/(\log n)^{2}$ while the
classical value is roughly $1/n$, leading to a Bell inequality violation
$\omega^{*}_{n}(G)/\omega(G)=\Omega(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.

###  1.3 Discussion and open problems

The main advantage of the Khot-Vishnoi game is its strong, near-linear Bell
inequality violation of about $n/(\log n)^{2}$. This is quadratically stronger
than the violation of $\sqrt{n}/\log n$ given by Hidden Matching and by [JP11]
and almost matches the $O(n)$ bound proved in [JPP+10] for arbitrary Bell
inequality violations with entangled states of local dimension $n$. One open
question is to tweak the KV game (or define another game) to get rid of the
polylogarithmic term in the ratio, making it optimal up to a constant factor.
A second advantage of KV over HM is that the value is just the winning
probability rather than the bias from $1/2$. This might make the KV game more
relevant for physical non-locality experiments, as it is the probability of
winning that matters most there. This also means that the corresponding Bell
functional (see Section 2) is nonnegative, a case that has been investigated
in [JP11].

One advantage of HM over KV is that the entangled strategy wins the game with
probability 1. In contrast, the entangled strategy for KV wins only with
probability about $1/(\log n)^{2}$, which means any quantum experiment needs
to be repeated about $(\log n)^{2}$ times before we expect to see the first
win. Another advantage is that HM’s description is a bit simpler than KV’s.

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 $\sqrt{n}/\log n$
presented by Junge and Palazuelos [JP11] 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
worthy goal. Pérez-García et al. [PWP+08] 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 roughly $\sqrt{d}$ using an entangled state in
dimensions $d\times D\times D$ (with $D\gg d$).555They also showed that using
GHZ states cannot give a superconstant Bell inequality violation for XOR games
(see also [BBLV09]). 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 Hidden Matching: Alice
gets input $x\in\\{0,1\\}^{n}$, Bob gets input $y\in\\{0,1\\}^{n}$, and
Charlie gets a matching $M$ as input (all uniformly distributed). The goal is
that Alice outputs $a\in\\{0,1\\}^{\log n}$, Bob outputs $b\in\\{0,1\\}^{\log
n}$, Charlie outputs $d\in\\{0,1\\}$ and $(i,j)\in M$, such that $((a\oplus
b)\cdot(i\oplus j))\oplus d=x_{i}\oplus x_{j}\oplus y_{i}\oplus 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 $(\log n)^{2}/n$.
So going from two to three parties roughly 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+\Omega(1/n)$.

##  2 A more formal look at Bell violations

Before we precisely analyze the two games mentioned above, let us first say
something more about the mathetical treatment of general Bell inequalities.
Readers who are happy 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 observed behavior of the players (whether they use a classical or
an entangled strategy) can be summarized in terms of $n^{2}$ probability
distributions, each on the set $[k]\times[k]$. We denote by $P(ab|xy)$ the
probability of producing outputs $a$ and $b$ when given inputs $x$ and $y$. As
described in the introduction, a game is defined by a probability distribution
$\pi$ on the input set $[n]\times[n]$, as well as a (possibly randomized)
predicate on $[k]\times[k]$ for each input pair $(x,y)$.The winning
probability of the players can be written as

$\langle{M},{P}\rangle=\sum_{abxy}M^{ab}_{xy}P(ab|xy).$

where $M_{xy}^{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=(M_{xy}^{ab})$ the _Bell functional corresponding to
the game_. More generally, a _Bell functional_ is an arbitrary tensor
$M=(M_{xy}^{ab})$ containing $n^{2}k^{2}$ real numbers.

We define the _classical value_ of a Bell functional $M$ as

$\omega(M)=\sup_{P}|\langle{M},{P}\rangle|,$

where the supremum is over all classical strategies. Similarly, the _entangled
value_ of $M$ is defined as

$\omega^{*}(M)=\sup_{P}|\langle{M},{P}\rangle|,$

where the supremum now is over all quantum strategies (using an entangled
state of arbitrary dimension). If the entangled state is restricted to local
dimension $n$, the value is denoted $\omega^{*}_{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 $\omega(M)$ for some Bell functional
$M$; it shows a limitation of _classical_ strategies.666An upper bound on
$\omega^{*}(M)$ is known as a _Tsirelson inequality_ , and shows a limitation
of entangled strategies. The _Bell inequality violation_ demonstrated by a
Bell functional $M$ is defined as the ratio between the entangled and the
classical value

$\frac{\omega^{*}(M)}{\omega(M)}.$

This provides a convenient quantitative way to measure the extra power
provided by entangled strategies. This definition of Bell violation enjoys a
rich mathematical structure (as witnessed by the numerous connections found to
Banach space and operator space theory [JPP+10, JP11, Duk10]), and also has a
beautiful geometrical interpretation as the “distance” between the set of all
classical strategies and the set of all quantum strategies (see Section 6.1 in
[JP11]).

Clearly, any game $G$ for which $\omega^{*}(G)\geq K\omega(G)$ gives a Bell
violation of $K$ by just taking the functional corresponding to $G$. A more
interesting case is when we consider the largest deviation of the winning
probability from (say) $1/2$. We claim that if $G$ is a game for which the
winning probability of any classical strategy cannot deviate from $1/2$ by
more than $\delta_{1}$ and, moreover, there is a quantum strategy obtaining
winning probability at least $1/2+\delta_{2}$, then we obtain a Bell violation
of $\delta_{2}/\delta_{1}$. To see why, let $M$ be the functional
corresponding to the game, and let $M^{\prime}$ be the functional obtained by
subtracting from each $M_{xy}^{ab}$ half the probability of input pair
$(x,y)$. Then it is easy to see that for each strategy $P$,
$\langle{M^{\prime}},{P}\rangle=\langle{M},{P}\rangle-1/2$. Hence,
$\omega(M^{\prime})$ and $\omega^{*}(M^{\prime})$ measure the largest possible
deviation of the winning probability from $1/2$ of classical and entangled
strategies, respectively. The claim follows. The converse to this statement is
also true: any Bell functional can be converted to a game (by simply scaling
and adding a constant) in such a way that the Bell violation demonstrated by
the functional is equal to the ratio between the largest possible deviation of
winning probability from $1/2$ obtainable by classical and entangled
strategies.

##  3 Hidden Matching problem

In this section we define and analyze the Hidden Matching 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 [BJK08].

######  Definition 1 (Hidden Matching (HM)).

Let $n$ be a power of 2 and ${\cal M}_{n}$ be the set of all perfect matchings
on the set $[n]=\\{1,\ldots,n\\}$ (a perfect matching is a partition of $[n]$
into $n/2$ disjoint pairs $(i,j)$). Alice is given $x\in\\{0,1\\}^{n}$ and Bob
is given $M\in{\cal M}_{n}$, distributed according to the uniform
distribution. We allow one-way communication from Alice to Bob, and Bob
outputs an $(i,j)\in M$ and $v\in\\{0,1\\}$. They win if $v=x_{i}\oplus
x_{j}$.

######  Theorem 1.

There is a protocol for HM with $\log n$ qubits of one-way communication that
wins with probability 1 (i.e., $v=x_{i}\oplus x_{j}$ always holds).

###### Proof.

The protocol is the following:

  1. 1.

Alice sends Bob the state
$|\psi\rangle=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}(-1)^{x_{i}}|i\rangle$.

  2. 2.

Bob measures $|\psi\rangle$ in the $n$-element basis
$B=\\{\frac{1}{\sqrt{2}}(|i\rangle\pm|j\rangle)\mid(i,j)\in M\\}$. If the
outcome of the measurement is a state
$\frac{1}{\sqrt{2}}(|i\rangle+|j\rangle)$ then Bob outputs $(i,j)$ and $v=0$.
If the outcome of the measurement is a state
$\frac{1}{\sqrt{2}}(|i\rangle-|j\rangle)$, Bob outputs $(i,j)$ and $v=1$.

For each $(i,j)\in M$, the probability to get
$\frac{1}{\sqrt{2}}(|i\rangle+|j\rangle)$ is $2/n$ if $x_{i}\oplus x_{j}=0$
and 0 otherwise, and similarly for $\frac{1}{\sqrt{2}}(|i\rangle-|j\rangle)$.
Hence Bob’s output is always correct. ∎

####  3.1.1 Limits of classical protocols for HM

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

Every classical deterministic protocol for HM with $c$ bits of one-way
communication, where Bob outputs $(i,j),v$, has

$\Pr[v=x_{i}\oplus x_{j}]\leq\frac{1}{2}+O\left(\frac{c}{\sqrt{n}}\right).$

The intuition behind the proof is the following. If the communication $c$ is
small, the set $X_{m}$ of inputs $x$ for which Alice sends message $m$, will
typically be large (of size about $2^{n-c}$), meaning Bob has little knowledge
of most of the bits of $x$. By the KKL inequality, this implies that for most
of the ${n\choose 2}$ $(i,j)$-pairs, Bob cannot guess the parity $x_{i}\oplus
x_{j}$ well. Of course, Bob has some freedom in which $(i,j)$ he outputs, but
that freedom is limited to the $n/2$ $(i,j)$-pairs 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\in\\{0,1\\}^{c}$, let
$X_{m}\subseteq\\{0,1\\}^{n}$ be the set of Alice’s inputs for which she sends
message $m$. These sets $X_{m}$ together partition Alice’s input space
$\\{0,1\\}^{n}$. Define $p_{m}=\frac{|X_{m}|}{2^{n}}$. Note that
$\sum_{m}p_{m}=1$, so $\\{p_{m}\\}$ is a probability distribution over the
$2^{c}$ messages $m$. Define $\varepsilon$ such that
$\Pr_{\mathcal{U}}[v=x_{i}\oplus x_{j}]=\frac{1}{2}+\varepsilon$, and
$\varepsilon_{m}$ such that $\Pr_{\mathcal{U}}[v=x_{i}\oplus
x_{j}\mid\mbox{Bob received }m]=\frac{1}{2}+\varepsilon_{m}$. Then
$\varepsilon=\sum_{m}p_{m}\varepsilon_{m}$.

For each $m$, define the following probability distribution over all
$(i,j)\in[n]^{2}$:

$q_{m}(i,j)=\Pr_{M\in{\cal M}_{n}}[\mbox{Bob outputs }(i,j)\mid\mbox{Bob
received }m].$

We have $q_{m}(i,j)\leq\frac{1}{n-1}$, because we assume Bob always outputs an
element from $M$ and for fixed $i\neq j$ we have $\Pr_{M}[(i,j)\in M]=1/(n-1)$
(each $j$ is equally likely to be paired up with $i$). The best Bob can do
when guessing $x_{i}\oplus x_{j}$ given message $m$, is to output the value of
$x_{i}\oplus x_{j}$ that occurs most often among the $x\in X_{m}$. Define
$\beta^{m}_{ij}=\mathop{\mathbb{E}}_{x\in
X_{m}}[(-1)^{x_{i}}\cdot(-1)^{x_{j}}]$. The fraction of $x\in X_{m}$ where
$x_{i}\oplus x_{j}=0$ is $1/2+\beta^{m}_{ij}/2$, hence Bob’s optimal success
probability when guessing $x_{i}\oplus x_{j}$ is $1/2+|\beta^{m}_{ij}|/2$.
This implies, for fixed $m$,

$\mathop{\mathbb{E}}_{(i,j)\sim
q_{m}}\left[\frac{1}{2}+\frac{|\beta^{m}_{ij}|}{2}\right]\geq\Pr_{\stackrel{{\scriptstyle
x\in X_{m}}}{{M\in{\cal M}_{n}}}}[v=x_{i}\oplus
x_{j}]=\frac{1}{2}+\varepsilon_{m},$

where the notation $x\sim Q$ stands for “$x$ chosen according to probability
distribution $Q$.”

As explained in [Wol08, Section 4.1], it follows from the KKL inequality
[KKL88] that

$\sum_{i,j:i\neq j}(\beta^{m}_{ij})^{2}\leq
O\left(\log\frac{1}{p_{m}}\right)^{2}.$ (1)

This allows us to upper bound $\varepsilon_{m}$:

$2\varepsilon_{m}\leq\mathop{\mathbb{E}}_{(i,j)\sim
q_{m}}[|\beta^{m}_{ij}|]=\sum_{i,j}q_{m}(i,j)|\beta^{m}_{ij}|\stackrel{{\scriptstyle(*)}}{{\leq}}\sqrt{\sum_{i,j}q_{m}(i,j)^{2}}\cdot\sqrt{\sum_{i,j}(\beta^{m}_{ij})^{2}}\stackrel{{\scriptstyle(**)}}{{\leq}}\frac{1}{\sqrt{n-1}}\cdot
O\left(\log\frac{1}{p_{m}}\right),$

where $(*)$ is Cauchy-Schwarz and $(**)$ follows from
$\sum_{i,j}q_{m}(i,j)^{2}\leq\max_{i,j}q_{m}(i,j)\cdot\sum_{i,j}q_{m}(i,j)\leq\max_{i,j}q_{m}(i,j)\leq\frac{1}{n-1}$
and Eq. (1). Now we can bound $\varepsilon$:

$\varepsilon=\sum_{m}p_{m}\varepsilon_{m}\leq\sum_{m}p_{m}\frac{O(\log(1/p_{m}))}{\sqrt{n-1}}=\frac{1}{\sqrt{n-1}}\sum_{m}p_{m}O(\log(1/p_{m}))=\frac{1}{\sqrt{n-1}}O(H(p))=O\left(\frac{c}{\sqrt{n}}\right)$

where $H$ denotes the binary entropy function, and $H(p)\leq c$ since the
distribution $\\{p_{m}\\}$ is on $2^{c}$ elements. ∎

###  3.2 Classical protocol for HM

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.

For every positive integer $c\leq\sqrt{n}$, there exists a classical protocol
for HM with $c$ bits of one-way communication, such that for all inputs $x,M$,

$\Pr[v=x_{i}\oplus x_{j}]=\frac{1}{2}+\Omega\left(\frac{c}{\sqrt{n}}\right).$

###### Proof.

Assume for simplicity that $c$ is even and sufficiently large. Alice and Bob
use shared randomness to choose two disjoint subsets $S_{1},S_{2}$ of $[n]$ of
size $\sqrt{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 subset. Alice and Bob use shared randomness to produce $2^{c/2}$
random $\sqrt{n}$-bit strings $y^{(1)},\ldots,y^{(2^{c/2})}$. For each $\ell$,
the distance $d(y,y^{(\ell)})$ is distributed binomially, as the sum of
$\sqrt{n}$ fair coin flips. There exists a constant $\delta>0$ such that
$\Pr[d(y,y^{(\ell)})\leq\sqrt{n}/2-\beta n^{1/4}]\geq 2^{-\delta\beta^{2}}$
(this can be seen for instance by estimating ${k\choose k/2-\beta\sqrt{k}}$
using Stirling’s approximation). Hence with probability close to 1, there will
be an $\ell$ such that $y$ and $y^{(\ell)}$ are at relative distance $\leq
1/2-\Omega(c^{1/2}/n^{1/4})$. If so, Alice sends Bob the first such $\ell$,
and otherwise she tells him there is no such $\ell$. 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 $\leq 1/2-\Omega(c^{1/2}/n^{1/4})$.

It is easy to see that with probability at least 1/2, Bob’s matching $M$
contains an $(i,j)$ with $i$ in $S_{1}$ and $j$ in $S_{2}$. Bob can predict
$x_{i}$ with success probability $1/2+\Omega(c^{1/2}/n^{1/4})$ from his
approximation of $y$, and can predict $x_{j}$ with success probability
$1/2+\Omega(c^{1/2}/n^{1/4})$ from his approximation of $z$. These success
probabilities are independent, hence he can predict $x_{i}\oplus x_{j}$ with
success probability $1/2+\Omega(c/\sqrt{n})$. If there is no such $(i,j)\in
M$, or if he didn’t get good approximations to $y$ or $z$, then Bob just
outputs any $(i,j)\in 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+\Omega(c/\sqrt{n})$. ∎

###  3.3 Non-local version of Hidden Matching, and a quantum protocol

We now port our results to the non-local setting. The following non-local
version of HM and the subsequent protocol for it were originally due to
Buhrman, and related problems were studied in [GKRW09, Gav09].

######  Definition 2 (Non-Local Hidden Matching ($\mbox{\rm HM}_{nl}$)).

Let $n$ be a power of 2 and ${\cal M}_{n}$ be the set of all perfect matchings
on the set $[n]$. Alice is given $x\in\\{0,1\\}^{n}$ and Bob is given
$M\in{\cal M}_{n}$, distributed according to the uniform distribution. Alice’s
output is a string $a\in\\{0,1\\}^{\log n}$ and Bob’s output is an $(i,j)\in
M$ and $d\in\\{0,1\\}$. They win the game if and only if

$(a\cdot(i\oplus j))\oplus d=x_{i}\oplus x_{j}.$ (2)

######  Theorem 4.

There exists a quantum protocol for $\mbox{\rm HM}_{nl}$ using a maximally
entangled state with local dimension $n$, such that condition (2) is always
satisfied.

###### Proof.

The protocol is as follows. Alice and Bob share
$|\psi\rangle=\frac{1}{\sqrt{n}}\sum_{i\in\\{0,1\\}^{\log
n}}|i\rangle|i\rangle.$

  1. 1.

Alice performs a phase-flip according to her input $x$. The state becomes
$\frac{1}{\sqrt{n}}\sum_{i\in\\{0,1\\}^{\log
n}}(-1)^{x_{i}}|i\rangle|i\rangle$.

  2. 2.

Bob performs a projective measurement with projectors $P_{ij}=|i\rangle\langle
i|+|j\rangle\langle j|$, with $(i,j)\in M$. The state collapses to
$\frac{1}{\sqrt{2}}[(-1)^{x_{i}}|i\rangle|i\rangle+(-1)^{x_{j}}|j\rangle|j\rangle]$
for some $(i,j)\in M$ known to Bob.

  3. 3.

Both players apply Hadamard transforms $H^{\otimes\log{n}}$, and the state
becomes

$\frac{1}{\sqrt{2}n}\sum_{a,b\in\\{0,1\\}^{\log n}}\left((-1)^{x_{i}+a\cdot
i+b\cdot i}+(-1)^{x_{j}+a\cdot j+b\cdot j}\right)|a\rangle|b\rangle.$

Notice that in the latter state, any pair $a,b$ with nonzero amplitude must
satisfy that

$(a\cdot(i\oplus j))\oplus(b\cdot(i\oplus j))=x_{i}\oplus x_{j}.$

Hence, if the players measure the state, Alice outputs $a$, and Bob outputs
$(i,j)$ and the bit $d=b\cdot(i\oplus j)$, they win the game with certainty. ∎

######  Theorem 5.

The winning probability of any classical protocol for $\mbox{\rm HM}_{nl}$
differs from $\frac{1}{2}$ by at most $O\left(\log{n}/{\sqrt{n}}\right)$.

###### Proof.

A protocol that wins $\mbox{\rm HM}_{nl}$ with success probability
$1/2+\varepsilon$ can be turned into a protocol for HM with $\log{n}$ bits of
communication and the same probability to win: the players play $\mbox{\rm
HM}_{nl}$, with Alice producing $a$ and Bob producing $i,j,d$; Alice then
sends $a$ to Bob, who outputs $i,j,(a\cdot(i\oplus j))\oplus d$. The latter
bit equals $x_{i}\oplus x_{j}$ with probability $1/2+\varepsilon$. This
requires $c=\log{n}$ bits of communication, so Theorem 2 gives the upper bound
on the winning probability. The lower bound follows similarly. ∎

###  3.4 Classical protocols for $\mbox{\rm HM}_{nl}$

Next we show that our upper bound on the success probability of classical
strategies for $\mbox{\rm HM}_{nl}$ is nearly optimal: we can achieve
advantage at least $\Omega(\sqrt{\log(n)/n})$. (In Appendix A we also give an
alternative protocol with a slightly weaker advantage $\Omega(1/\sqrt{n})$.)

######  Theorem 6.

There exists a classical deterministic protocol for $\mbox{\rm HM}_{nl}$ with
winning probability $\frac{1}{2}+\Omega\left(\sqrt{\frac{\log n}{n}}\right)$
(under the uniform input distribution).

###### Proof.

The protocol is as follows. Given $x$, Alice finds an $a\in\\{0,1\\}^{\log n}$
that maximizes $J_{ax}:=|\\{j\neq 1\mid a\cdot j=x_{1}\oplus x_{j}\\}|$. Bob
outputs $(1,j)$, where $j$ is the unique element matched to 1 by $M$, and
$d=0$. With these choices, and letting the number 1 correspond to the string
$0^{\log n}$, the winning condition $(a\cdot(i\oplus j))\oplus d=x_{i}\oplus
x_{j}$ is equivalent to $a\cdot j=x_{1}\oplus x_{j}$. Accordingly, for fixed
$x$ and uniformly distributed $M$ (and hence uniformly distributed
$j\in[n]\backslash\\{0^{\log n}\\}$), the winning probability equals
$p_{x}:=\max_{a}J_{ax}/(n-1)$. Below we use the second moment method to show
$\mathop{\mathbb{E}}_{x}[p_{x}]\geq 1/2+\Omega(\sqrt{\log(n)/n})$.

For a fixed $a$ and uniformly random $x\in\\{0,1\\}^{n}$, $J_{ax}$ behaves
like the sum of $n-1$ fair 0/1-valued coin flips. Let $Z_{a}$ be the indicator
random variable for the event that $J_{ax}\geq(n-1)/2+\beta\sqrt{n}$. Choosing
$\beta$ a sufficiently small constant multiple of $\sqrt{\log n}$, we have
$\mathop{\mathbb{E}}_{x}[Z_{a}]\geq 1/\sqrt{n}$ for each $a$ (this follows
from the $2^{-\delta\beta^{2}}$ probability lower bound mentioned in the proof
of Theorem 3). Let $Z=\sum_{a}Z_{a}$, then
$\mathop{\mathbb{E}}_{x}[Z]\geq\sqrt{n}$ by linearity of expectation. For
$a\neq b$, the covariance $\mbox{Cov}[Z_{a},Z_{b}]$ is non-positive,
informally because if $x$ is “well-aligned” with the string $(a\cdot j)_{j}$
then it’s less likely to be well-aligned with the orthogonal string $(b\cdot
j)_{j}$. Hence we can bound the variance of $Z$:

$\mbox{Var}[Z]=\sum_{a}\mbox{Var}[Z_{a}]+\sum_{a\neq
b}\mbox{Cov}[Z_{a},Z_{b}]\leq\sum_{a}\mbox{Var}[Z_{a}]\leq\sum_{a}\mathop{\mathbb{E}}_{x}[Z_{a}^{2}]=\sum_{a}\mathop{\mathbb{E}}_{x}[Z_{a}]=\mathop{\mathbb{E}}_{x}[Z].$

By Chebyshev’s inequality, we have

$\Pr[Z=0]\leq\Pr\left[|Z-\mathop{\mathbb{E}}_{x}[Z]|\geq\mathop{\mathbb{E}}_{x}[Z]\right]\leq\Pr\left[|Z-\mathop{\mathbb{E}}_{x}[Z]|\geq\sqrt{\mathop{\mathbb{E}}_{x}[Z]}\sqrt{\mbox{Var}[Z]}\right]\leq\frac{1}{\mathop{\mathbb{E}}_{x}[Z]}\leq\frac{1}{\sqrt{n}}.$

Hence with probability at least $1-1/\sqrt{n}$ over the choice of $x$, we have
$Z>0$, meaning there is at least one $a$ with
$J_{ax}\geq(n-1)/2+\beta\sqrt{n}$, and hence $p_{x}\geq
1/2+\Omega(\sqrt{\log(n)/n})$. This implies

$\mathop{\mathbb{E}}_{x}[p_{x}]\geq\left(1-\frac{1}{\sqrt{n}}\right)\left(1/2+\Omega(\sqrt{\log(n)/n})\right)=1/2+\Omega(\sqrt{\log(n)/n}).$

∎

##  4 The Khot-Vishnoi game

###  4.1 The classical value

In this section we analyze the classical value of the Khot-Vishnoi game. Our
main result is an upper bound on the classical value of $1/n^{\eta/(1-\eta)}$,
based on the analysis from [KV05].

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 roughly
$1/n^{\eta/(1-\eta)}$. To get some intuition for this game, first think of
$\eta$ 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\oplus z$ to also be of high Hamming weight (because it
is close to $a$ in Hamming distance), and so Bob is somewhat likely to pick
it. We now give a brief back-of-the-envelope calculation suggesting that the
winning probability of this strategy is of order $1/n^{\eta/(1-\eta)}$; since
it is not required for our main result, we will not attempt to make this
argument rigorous.

Let $t\geq 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 a binomial distribution
$B(n,p)$ can be approximated by the normal distribution $N(np,np(1-p))$, and
that the probability that a normal variable is greater than its mean by $s$
standard deviations is approximately $e^{-s^{2}/2}$, we can essentially choose
$t$ to be the solution to $e^{-t^{2}/(2n)}=1/n$ (so $t=\sqrt{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\oplus z$ has
the highest weight among Bob’s $n$ elements, which we heuristically
approximate by the event that $a\oplus z$ has Hamming weight at least
$(n+t)/2$. The Hamming weight of $a\oplus z$ is distributed as the sum of
$B((n+t)/2,1-\eta)$ and $B((n-t)/2,\eta)$, which can be approximated as above
by the normal distribution $N((n+t)/2-\eta t,n\eta(1-\eta))$. Hence for the
Hamming weight of $a\oplus z$ to be at least $(n+t)/2$, the normal variable
needs to be greater than its mean by $\eta t/\sqrt{n\eta(1-\eta)}$ standard
deviations, and the probability of this happening is approximately
$e^{-\eta^{2}t^{2}/(2n\eta(1-\eta))}=1/n^{\eta/(1-\eta)}$, as claimed.

Now we show that no classical strategy can be substantially better. The main
technical tool used in the proof is the so-called Bonami-Beckner
hypercontractive inequality, which is applicable to our setting because we
choose $u$ uniform and $u\oplus z$ may be viewed as a “noisy version” of $u$.

######  Theorem 7.

For any $n$ which is a power of 2, and any $\eta\in[0,1/2]$, every classical
strategy for the Khot-Vishnoi game (as defined in Section 1.2) has winning
probability at most $1/n^{\eta/(1-\eta)}$.

###### Proof.

Recall that the inputs are generated as follows: we choose a uniformly random
$u\in\\{0,1\\}^{n}$ and an $\eta$-biased $z\in\\{0,1\\}^{n}$, and define the
respective inputs to be the cosets $u\oplus H$ and $u\oplus z\oplus H$. We can
assume without loss of generality that Alice’s and Bob’s behavior is
deterministic. Define functions $A,B:\\{0,1\\}^{n}\to\\{0,1\\}$ by $A(u)=1$ if
and only if Alice’s output on $u\oplus H$ is $u$, and similarly for Bob.
Notice that by definition, these functions attain the value $1$ on exactly one
element of each coset. 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$, $\sum_{h\in
H}A(u\oplus h)B(u\oplus z\oplus h)$ is $1$ if the players win on input pair
$u\oplus H,u\oplus z\oplus H$ and $0$ otherwise. Therefore, the winning
probability is given by

$\displaystyle\mathop{\mathbb{E}}_{u,z}\left[\sum_{h\in H}A(u\oplus
h)B(u\oplus z\oplus h)\right]$ $\displaystyle=\sum_{h\in
H}\mathop{\mathbb{E}}_{u,z}\left[A(u\oplus h)B(u\oplus z\oplus h)\right]$
$\displaystyle=n\mathop{\mathbb{E}}_{u,z}[A(u)B(u\oplus z)],$

where the second equality uses the fact that for all $h$, $u\oplus h$ is
uniformly distributed.

We use the framework of hypercontractivity (see e.g. [O’D08, Wol08]), which we
briefly explain now. Specifically, for a function
$F:\\{0,1\\}^{n}\rightarrow\mathbb{R}$, define its $p$-norm by
${\left\|{F}\right\|}_{p}=(\mathop{\mathbb{E}}_{x}[|F(u)|^{p}])^{1/p}$, where
the expectation is uniform over all $u\in\\{0,1\\}^{n}$. The _noise-operator_
$T_{1-2\eta}$ adds “$\eta$-noise” to each of $F$’s input bits; more precisely,
$(T_{1-2\eta}F)(u)=\mathop{\mathbb{E}}_{z}[F(u\oplus z)]$, where $z$ is an
$\eta$-biased “noise string.” The linear operator $T_{\rho}$ is diagonal in
the Fourier basis: it just multiplies each character function $\chi_{S}$
($S\subseteq[n]$) by the factor $\rho^{|S|}$. It is easy to see that
$\mathop{\mathbb{E}}_{u}[F(u)\cdot(T_{\rho}G)(u)]=\mathop{\mathbb{E}}_{u}[(T_{\sqrt{\rho}}F)(u)\cdot(T_{\sqrt{\rho}}G)(u)]$.
The Bonami-Beckner inequality implies
${\left\|{T_{\rho}F}\right\|}_{2}\leq{\left\|{F}\right\|}_{1+\rho^{2}}$ for
all $\rho\in[0,1]$. We now have,

$\displaystyle\mathop{\mathbb{E}}_{u,z}[A(u)B(u\oplus z)]$
$\displaystyle=\mathop{\mathbb{E}}_{u}[A(u)(T_{1-2\eta}B)(u)]$
$\displaystyle=\mathop{\mathbb{E}}_{u}[(T_{\sqrt{1-2\eta}}A)(u)\cdot(T_{\sqrt{1-2\eta}}B)(u)]$
$\displaystyle\leq{\left\|{T_{\sqrt{1-2\eta}}A}\right\|}_{2}\cdot{\left\|{T_{\sqrt{1-2\eta}}B}\right\|}_{2}$
$\displaystyle\leq{\left\|{A}\right\|}_{2-2\eta}\cdot{\left\|{B}\right\|}_{2-2\eta}$
$\displaystyle=\left(\mathop{\mathbb{E}}_{u}[A(u)]\right)^{1/(2-2\eta)}\cdot\left(\mathop{\mathbb{E}}_{u}[B(u)]\right)^{1/(2-2\eta)}$
$\displaystyle=\frac{1}{n^{1/(1-\eta)}}.$

Here the first inequality is Cauchy-Schwarz, and the second is the
hypercontractive inequality. We complete the proof by noting that
$n/n^{1/(1-\eta)}=1/n^{\eta/(1-\eta)}$. ∎

###  4.2 Lower bound on the entangled value

In this section we describe a good quantum strategy for the Khot-Vishnoi game,
following the ideas of Kempe, Regev, and Toner [KRT08] and the SDP-solution of
[KV05].

######  Theorem 8.

For any $n$ which is a power of 2, and any $\eta\in[0,1/2]$, there exists a
quantum strategy that wins the Khot-Vishnoi game with probability at least
$(1-2\eta)^{2}$, using a maximally entangled state with local dimension $n$.

###### Proof.

For $a\in\\{0,1\\}^{n}$, let $v^{a}\in\mathbb{R}^{n}$ denote the unit vector
$((-1)^{a_{i}}/\sqrt{n})_{i\in[n]}$. Notice that for all $a,b$, we have
$\langle{v^{a}},{v^{b}}\rangle=1-2d(a,b)/n$, where $d(a,b)$ denotes the
Hamming distance between $a$ and $b$. In particular, the $n$ vectors $v^{a}$,
as $a$ ranges over a coset of $H$, form an orthonormal basis of
$\mathbb{R}^{n}$.

The quantum strategy is as follows. Alice and Bob start with the
$n$-dimensional maximally entangled state. Alice, given coset $x=u\oplus H$ as
input, performs a projective measurement in the orthonormal basis given by
$\\{v^{a}\mid a\in x\\}$ and outputs the value $a$ given by the measurement.
Bob proceeds similarly with the basis $\\{v^{b}\mid b\in y\\}$ induced by his
coset $y=x\oplus z\oplus H$. A standard calculation now shows that the
probability to obtain the pair of outputs $a,b$ is
$\langle{v^{a}},{v^{b}}\rangle^{2}/n$. Since the players win iff $b=a\oplus
z$, the winning probability on inputs $x,y$ is given by

$\frac{1}{n}\sum_{a\in x}\langle{v^{a}},{v^{a\oplus
z}}\rangle^{2}=\frac{1}{n}\sum_{a\in x}(1-2d(a,a\oplus
z)/n)^{2}=(1-2|z|/n)^{2},$

where $|z|$ denotes the Hamming weight (number of 1s) of the $\eta$-biased
string $z$. Taking expectation and using convexity, the overall winning
probability is

$\mathop{\mathbb{E}}_{z}[(1-2|z|/n)^{2}]\geq\left(\mathop{\mathbb{E}}_{z}[1-2|z|/n]\right)^{2}=(1-2\eta)^{2}.$

∎

##### Acknowledgements.

We thank Jop Briët, Dejan Dukaric, Carlos Palazuelos, and Thomas Vidick for
useful discussions and comments.

## References

  * [BBLV09] J. Briët, H. Buhrman, T. Lee, and T. Vidick.  Multiplayer XOR games and quantum communication complexity with clique-wise entanglement.  arXiv:0911.4007, 2009.
  * [Bel64] J. S. Bell.  On the Einstein-Podolsky-Rosen paradox.  Physics, 1:195–200, 1964.
  * [BJK08] Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis.  Exponential separation of quantum and classical one-way communication complexity.  SIAM Journal on Computing, 38(1):366–384, 2008.  Earlier version in STOC’04.
  * [CHSH69] J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt.  Proposed experiment to test local hidden-variable theories.  Physical Review Letters, 23(15):880–884, 1969.
  * [CSUU07] R. Cleve, W. Slofstra, F. Unger, and S. Upadhyay.  Strong parallel repetition theorem for quantum XOR proof systems.  In Proceedings of 22nd IEEE Conference on Computational Complexity, pages 282–299, 2007.  quant-ph/0608146.
  * [DKLR09] J. Degorre, M. Kaplan, S. Laplante, and J. Roland.  The communication complexity of non-signaling distributions.  In Proceedings of 34th MFCS, pages 270–281, 2009.  arXiv:0804.4859.
  * [Duk10] D. Dukaric.  The Hilbertian tensor norm and its connection to quantum information theory.  arXiv:1008.1948v2, 2010.
  * [EPR35] A. Einstein, B. Podolsky, and N. Rosen.  Can quantum-mechanical description of physical reality be considered complete?  Physical Review, 47:777–780, 1935.
  * [Gav09] D. Gavinsky.  Classical interaction cannot replace quantum nonlocality.  arXiv:0901.0956, 2009.
  * [GKK+08] D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf.  Exponential separation for one-way quantum communication complexity, with applications to cryptography.  SIAM Journal on Computing, 38(5):1695–1708, 2008.  Earlier version in STOC’07. quant-ph/0611209.
  * [GKRW09] D. Gavinsky, J. Kempe, O. Regev, and R. de Wolf.  Bounded-error quantum state identification and exponential separations in communication complexity.  SIAM Journal on Computing, 39(1):1–24, 2009.  Special issue on STOC’06. quant-ph/0511013.
  * [JP11] M. Junge and C. Palazuelos.  Large violation of Bell inequalities with low entanglement.  Communications in Mathematical Physics, 2011.  To appear. Preprint at arXiv:1007.3043v2.
  * [JPP+10] M. Junge, C. Palazuelos, D. Pérez-García, I. Villanueva, and M. Wolf.  Unbounded violations of bipartite Bell inequalities via Operator Space theory.  Communications in Mathematical Physics, 300(3):715–739, 2010.  arXiv:0910.4228. Shorter version appeared in PRL 104:170405, arXiv:0912.1941.
  * [Kho02] S. Khot.  On the power of unique 2-prover 1-round games.  In Proceedings of 34th ACM STOC, pages 767––775, 2002.
  * [KKL88] J. Kahn, G. Kalai, and N. Linial.  The influence of variables on Boolean functions.  In Proceedings of 29th IEEE FOCS, pages 68–80, 1988.
  * [KKM+08] J. Kempe, H. Kobayashi, K. Matsumoto, B. Toner, and T. Vidick.  Entangled games are hard to approximate.  In Proceedings of 49th IEEE FOCS, pages 447–456, 2008.
  * [KKMV08] J. Kempe, H. Kobayashi, K. Matsumoto, and T. Vidick.  Using entanglement in quantum multi-prover interactive proofs.  In Proceedings of 23th IEEE Complexity, pages 211–222, 2008.
  * [KRT08] J. Kempe, O. Regev, and B. Toner.  Unique games with entangled provers are easy.  In Proceedings of 49th IEEE FOCS, pages 457–466, 2008.  arXiv:0710.0655.
  * [KV05] S. Khot and N. Vishnoi.  The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into $\ell_{1}$.  In Proceedings of 46th IEEE FOCS, pages 53–62, 2005.
  * [O’D08] R. O’Donnell.  Some topics in analysis of boolean functions.  Technical report, ECCC Report TR08–055, 2008.  Paper for an invited talk at STOC’08.
  * [PWP+08] D. Pérez-García, M.M. Wolf, C. Palazuelos, I. Villanueva, and M. Junge.  Unbounded violations of tripartite Bell inequalities.  Communications of Mathematical Physics, 279:455, 2008.  quant-ph/0702189.
  * [Reg11] O. Regev.  Bell violations through independent bases games.  arXiv:1101.0576, 3 Jan 2011.
  * [Tsi87] B. S. Tsirelson.  Quantum analogues of the bell inequalities. the case of two spatially separated domains.  Journal of Soviet Mathematics, 36:557–570, 1987.
  * [Wol08] R. de Wolf.  A brief introduction to Fourier analysis on the Boolean cube.  Theory of Computing, 2008.  ToC Library, Graduate Surveys 1.

##  Appendix A An alternative strategy for $\mbox{\rm HM}_{nl}$

Here we give an alternative and slightly weaker version of Theorem 6, with
advantage $\Omega(1/\sqrt{n})$ instead of $\Omega(\sqrt{\log(n)/n})$.

###### Proof.

Fix arbitrary inputs $x,M$. Bob always outputs $i=1$ and $j$ is whatever is
matched to $i$ by $M$. Consider the following two unit vectors in
$\mathbb{R}^{n}$,

$u=\left((-1)^{x_{1}\oplus x_{k}}/\sqrt{n}\right)_{k=1}^{n}\qquad\qquad
v=e_{j}$

where $e_{j}$ is the vector with $1$ in the $j$th coordinate and zero
elsewhere. Notice that Alice knows $u$, Bob knows $v$, and that
$\langle{u},{v}\rangle=(-1)^{x_{1}\oplus x_{j}}/\sqrt{n}$. The players use
shared randomness to choose a random unit vector $w\in\mathbb{R}^{n}$. Bob
outputs $d=0$ if $\langle{w},{v}\rangle>0$, and $d=1$ otherwise. Alice outputs
$a=0^{\log n}$ if $\langle{w},{u}\rangle>0$, and a uniform
$a\in\\{0,1\\}^{\log n}$ otherwise.

We now analyze the success probability. Assume that $x_{1}\oplus x_{j}=0$ (the
other case being similar). It is easy to see that the probability of both
$\langle{w},{u}\rangle$ and $\langle{w},{v}\rangle$ being positive is
$\frac{1}{2}-\frac{1}{2\pi}\arccos\langle{u},{v}\rangle$, as this is
essentially a two-dimensional question. They have the same probability of both
being negative, and probability $\frac{1}{2\pi}\arccos\langle{u},{v}\rangle$
to be in each of the two remaining cases. In the two cases that
$\langle{w},{u}\rangle\leq 0$ (an event that happens with probability $1/2$),
$a\cdot(i\oplus j)$ is a uniform bit (since $i\neq j$) and the players win
with probability exactly $1/2$. Otherwise (i.e., if
$\langle{w},{u}\rangle>0$), the players win if and only if $d=0$ (i.e., if
also $\langle{w},{v}\rangle>0$). Hence, using that
$\arccos(z)=\pi/2-\Theta(z)$ for small $z$, the overall winning probability is

$\frac{1}{2}\cdot\frac{1}{2}+\frac{1}{2}-\frac{1}{2\pi}\arccos\langle{u},{v}\rangle=\frac{1}{2}+\Theta\left(\frac{1}{\sqrt{n}}\right).$

∎