# Robust Bell inequalities
from communication complexity

Sophie Laplante∗, Mathieu Laurière∗, Alexandre Nolin,
Jérémie Roland, Gabriel Senno IRIF, Université Paris-DiderotUniversité Libre
de BruxellesCONICET & Departamento de Computación, FCEN, Universidad de Buenos
Aires

###### Abstract

The question of how large Bell inequality violations can be, for quantum
distributions, has been the object of much work in the past several years. We
say a Bell inequality is normalized if its absolute value does not exceed 1
for any classical (i.e. local) distribution. Upper and (almost) tight lower
bounds have been given in terms of number of outputs of the distribution,
number of inputs, and the dimension of the shared quantum states. In this
work, we revisit normalized Bell inequalities together with another family:
inefficiency-resistant Bell inequalities. To be inefficiency-resistant, the
Bell value must not exceed 1 for any local distribution, including those that
can abort. Both these families of Bell inequalities are closely related to
communication complexity lower bounds. We show how to derive large violations
from any gap between classical and quantum communication complexity, provided
the lower bound on classical communication is proven using these lower bounds.
This leads to inefficiency-resistant violations that can be exponential in the
size of the inputs. Finally, we study resistance to noise and inefficiency for
these Bell inequalities.

##  1 Introduction

The question of achieving large Bell violations has been studied since Bell’s
seminal paper in 1964 [Bel64]. In one line of investigation, proposals have
been made to exhibit families of distributions which admit unbounded
violations [Mer90, LPŻB04, NLP06, PGWP+08]. In another, various measures of
nonlocality have been studied, such as the amount of communication necessary
and sufficient to simulate quantum distributions classically [Mau92, BCT99,
Ste00, TB03, Pir03, DKLR11], or the resistance to detection inefficiencies and
noise. More recently, focus has turned to giving upper and lower bounds on
violations achievable, in terms of various parameters: number of players,
number of inputs, number of outputs, dimension of the quantum state, and
amount of entanglement [DKLR11, JPPG+10b, JP11].

Up until quite recently, violations were studied in the case of specific
distributions (measuring Bell states), or families of distributions. Buhrman
et al. [BRSdW12] gave a construction that could be applied to several problems
which had efficient quantum protocols (in terms of communication) and for
which one could show a trade-off between communication and error in the
classical setting. This still required an ad hoc analysis of communication
problems. Recently Buhrman et al. [BCG+16] proposed the first general
construction of quantum states along with Bell inequalities from any
communication problem. The quantum states violate the Bell inequalities when
there is a sufficiently large gap between quantum and classical communication
complexity (a super-quadratic gap is necessary, unless a quantum protocol
without local memory exists).

Table 1 summarizes the best known upper and lower bounds on quantum violations
achievable with normalized Bell inequalities.

Parameter |  Upper bound |  Ad hoc lower bounds |  Best possible lower bound from [BCG+16]
---|---|---|---
Number of inputs $N{\vphantom{\Big{|}^{0}_{0}}}$ |  $2^{c}\leq N$ |  $\frac{\sqrt{N}}{\log(N)}$ |  $\frac{\sqrt{c}}{q}\leq\log(N)$
|  [LS09, DKLR11, JPPG+10b] |  [JP11] |
Number of outputs $K{\vphantom{\Big{|}^{0}_{0}}}$ |  $O(K)$ |  $\Omega\left(\frac{K}{(\log(K))^{2}}\right)$ |  $\leq\log(K)$
|  [JP11] |  [BRSdW12] |
Dimension $d{\vphantom{\Big{|}^{0}_{0}}}$ |  $O(d)$ |  $\Omega\left(\frac{d}{(\log(d))^{2}}\right)$ |  $\leq\log\log(d)$
|  [JPPG+10b] |  [BRSdW12] |
Table 1: Bounds on quantum violations of bipartite normalized Bell
inequalities, in terms of the dimension $d$ of the local Hilbert space, the
number of settings (or inputs) $N$ and the number of outcomes $K$ (or outputs)
per party. In the fourth column, we compare ad hoc results to the recent
constructions of [BCG+16] (Theorem 2) which gives a lower bound of
$\frac{\sqrt{c}}{q}$, where $c$ (resp. $q$) stands for the classical (resp.
quantum) communication complexity of simulating a distribution. We give upper
bounds on their construction in terms of the parameters $d,N,K$.

###  1.1 Our results

We revisit the question of achieving large Bell violations by exploiting known
connections with communication complexity. Strong lower bounds in
communication complexity, equivalent to the partition bound, amount to finding
inefficiency-resistant Bell inequalities [LLR12]. These are Bell functionals
that are bounded above by 1 on all local distributions that can abort.

First, we study the resistance of normalized Bell inequalities to
inefficiency. We show that, up to a constant factor in the value of the
violation, any normalized Bell inequality can be made resistant to
inefficiency while maintaining the normalization property (Theorem 1).

Second, we show how to derive large Bell violations from any communication
problem for which the partition bound is bounded below and the quantum
communication complexity is bounded above. The problems studied in
communication complexity are far beyond the quantum set, but we show how to
easily derive a quantum distribution from a quantum protocol. The Bell value
we obtain is $2^{c-2q}$, where $c$ is the partition lower bound on the
classical communication complexity of the problem considered, and $q$ is an
upper bound on its quantum communication complexity (Theorem 3 and Corollary
1). The quantum distribution has one extra output per player compared to the
original distribution and uses the same amount of entanglement as the quantum
protocol plus as many EPR pairs as needed to teleport the quantum
communication in the protocol.

We show that these Bell violations can be made noise-resistant, at the cost of
a $2^{2q}$ factor in the number of outcomes for each player (Theorem 4).

Finally, we provide a toolkit to build your own Bell inequalities from
communication lower bounds in the literature. Since discrepancy and
$\gamma_{2}$ bounds are also lower bounds on quantum communication complexity
(at least for Boolean functions), lower bounds used in practice to separate
classical from quantum communication complexity are usually achieved using
corruption bounds and its variants. In Theorem 6, we give an explicit
construction which translates these bounds into a suitable Bell functional.

Table 2 summarizes the new results or the improvements that we obtain in this
work.

Problem |  Normalized Bell violations [BCG+16] |  Inefficiency-resistant Bell violations (this work)
---|---|---
VSP [Raz99, KR11] |  $\Omega\left({\sqrt[6]{n}}/{\sqrt{\log n}}\right)$ $d~{}=~{}2^{\Theta(n\log n)},K=2^{\Theta(n)}$ |  $2^{\Omega(\sqrt[3]{n})-O(\log n)}$ $d~{}=~{}2^{O(\log n)},K=3$
DISJ [Raz92, Raz03, AA05] | N/A |  $2^{\Omega(n)-O(\sqrt{n})}$ $d~{}=~{}2^{O(\sqrt{n})},K=3$
TRIBES [JKS03, BCW98] | N/A |  $2^{\Omega(n)-O(\sqrt{n}\log^{2}n)}$ $d~{}=~{}2^{O(\sqrt{n}\log^{2}n)},K=3$
ORT [She12, BCW98] | N/A |  $2^{\Omega(n)-O(\sqrt{n}\log n)}$ $d~{}=~{}2^{O(\sqrt{n}\log n)},K=3$
Table 2: Comparison of the Bell violations obtained by the general
construction of Buhrman et al. [BCG+16] for normalized Bell violations (second
column) and this work, for inefficiency-resistant Bell violations (see
Propositions 5, 6, LABEL:coro:TribesBellIneq, and LABEL:coro:ORTBellIneq). The
parameter $n$ is the size of the input (so typically, the number of inputs is
$N=2^{n}$.) Explicit Bell inequalities are given in the Appendix. The
construction of Buhrman et al. only yields a violation when the gap between
classical and quantum complexities is more than quadratic. In the case where
the gap is too small to prove a violation, we indicate this with “N/A”.

###  1.2 Related work

The study of the maximum violation of Bell inequalities began with Tsirelson
[Tsi87], who showed that for two-outcome correlation Bell inequalities, the
maximum violation is bounded above by Grothendieck’s constant. Tsirelson also
raised the question of whether one can have unbounded violations of Bell
inequalities. More precisely, he asked whether there exist families of Bell
inequalities for which the amount of the violation grows arbitrarily large.

The first answer to this question came from Mermin [Mer90], who gave a family
Bell inequalities for which a violation exponential in the number of parties
is achieved. In the years that followed, several new constructions appeared
for number of parties and number of inputs [Ard92, Mas02, LPŻB04, NLP06,
PGWP+08].

The study of upper bounds on violations of normalized Bell inequalities
resumed in [DKLR11], where an upper bound of $O(K^{2})$ (with $K$ the number
of outputs per player) and of $2^{c}\leq N$ (with $c$ the communication
complexity and $N$ the number of inputs per player) were proven. In [JPPG+10b]
the authors proved a bound of $O(d)$ in terms of the dimension $d$ of the
local Hilbert space, and in [JP11], the bound in terms of the number of
outputs was improved to $O(K)$. In [JP11], Bell inequalities are constructed
for which a near optimal, but probabilistic, violation of order
$\Omega(\sqrt{m}/\log{m})$, with $N=K=d=m$, is proven. In [BRSdW12], the same
violation, although requiring $N=2^{m}$ inputs, is achieved for a family of
Bell inequalities and quantum distributions built using the quantum advantage
in one-way communication complexity for the Hidden Matching problem (with
$K=d=m$). In the same paper, a violation of order $\Omega(m/(\log m)^{2})$,
with $K=d=m$ and $N=2^{m}/m$ is achieved with the Khot-Vishnoi game. Recently,
an asymmetric version of that game was introduced to allow one of the parties
to only make dichotomic measurements, with a smaller (although almost optimal
for this scenario) violation $\Omega(\sqrt{m}/(\log m)^{2})$ [PY15].

For _inefficiency-resistant_ Bell inequalities, the bounds in [JP11] do not
apply. In fact, Laplante et al. proved in [LLR12] a violation exponential in
the dimension and the number of outputs for this type of Bell functionals,
achieved by a quantum distribution built, as in [BRSdW12], from the Hidden
Matching communication complexity problem.

The connection exhibited in [BRSdW12] between Bell violations and
communication complexity is generalized by Buhrman et al. in [BCG+16] where a
fully general construction is given to go from a quantum communication
protocol for a function $f$ to a Bell inequality and a quantum distribution
which achieves a violation of order
$\Omega\Big{(}\frac{\sqrt{R_{1/3}(f)}}{Q_{1/3}(f)}\Big{)}$. The downside to
this construction is that the quantum distribution has a double exponential
(in the communication) number of outputs and the protocol to implement it uses
an additional double exponential amount of entanglement. Also, this result
does not apply for quantum advantages in a zero-error setting.

##  2 Preliminaries

###  2.1 Quantum nonlocality

Local, quantum, and nonsignaling distributions have been widely studied in
quantum information theory since the seminal paper of Bell [Bel64]. In an
experimental setting, two players share an entangled state and each player is
given a measurement to perform. The outcomes of the measurements are predicted
by quantum mechanics and follow some probability distribution $p(a,b|x,y)$,
where $a$ is the outcome of Alice’s measurement $x$, and $b$ is the outcome of
Bob’s measurement $y$.

We consider bipartite distribution families of the form
$\mathbf{p}=(p(\cdot,\cdot|x,y))_{(x,y)\in\mathcal{X}\times\mathcal{Y}}$ with
inputs $(x,y)\in\mathcal{X}\times\mathcal{Y}$ determining a probability
distribution $p(\cdot,\cdot|x,y)$ over the outcomes
$(a,b)\in\mathcal{A}\times\mathcal{B}$, with the usual positivity and
normalization constraints. The set of probability distribution families is
denoted by ${\cal P}$. For simplicity, we call simply “distributions” such
probability distribution families. The expression “Alice’s marginal” refers to
her marginal output distribution, that is $\sum_{b}p(\cdot,b|x,y)$ (and
similarly for Bob).

The local deterministic distributions, denoted ${\cal L}_{\mathrm{det}}$, are
the ones where Alice outputs according to a deterministic strategy, i.e., a
(deterministic) function of $x$, and Bob independently outputs as a function
of $y$, without communicating. The local distributions ${\cal L}$ are obtained
by taking distributions over the local deterministic strategies.
Operationally, this corresponds to protocols with shared randomness and no
communication. Geometrically, ${\cal L}$ is the convex hull of ${\cal
L}_{\mathrm{det}}$.

A Bell test [Bel64] consists of estimating all the probabilities $p(a,b|x,y)$
and computing a Bell functional, or linear function, on these values. The Bell
functional $B$ is chosen together with a threshold $\tau$ so that any local
classical distribution $\mathbf{\ell}$ verifies the Bell inequality
$B(\mathbf{\ell})\leq\tau$, but the chosen distribution $\mathbf{p}$ exhibits
a Bell violation: $B(\mathbf{p})>\tau$. By normalizing, we can assume without
loss of generality that $\mathbf{\ell}$ verifies $B(\mathbf{\ell})\leq 1$ for
any $\mathbf{\ell}\in{\cal L}$, and $B(\mathbf{p})>1$.

In this paper, we will also consider strategies that are allowed to abort the
protocol with some probability. When they abort, they output the symbol $\bot$
($\bot$ denotes a new symbol which is not in $\mathcal{A}\cup\mathcal{B}$). We
will use the notation ${\cal L}_{\mathrm{det}}^{\bot}$ and ${\cal L}^{\bot}$
to denote local strategies that can abort, where $\bot$ is added to the
possible outputs for both players. When $\ell\in{\cal
L}_{\mathrm{det}}^{\bot}$ or ${\cal L}^{\bot}$, $\ell(a,b|x,y)$ is not
conditioned on $a,b\neq\bot$ since $\bot$ is a valid output for such
distributions.

The quantum distributions, denoted ${\cal Q}$, are the ones that result from
applying measurements $x,y$ to their part of a shared entangled bipartite
state. Each player outputs his or her measurement outcome ($a$ for Alice and
$b$ for Bob). In communication complexity terms, these are zero-communication
protocols with shared entanglement. If the players are allowed to abort, then
the corresponding set of distributions is denoted ${\cal Q}^{\bot}$.

Boolean (and other) functions can be cast as sampling problems. Consider a
boolean function $f:\mathcal{X}\times\mathcal{Y}\rightarrow\\{0,1\\}$ (non-
boolean functions and relations can be handled similarly). First, we split the
output so that if $f(x,y)=0$, Alice and Bob are required to output the same
bit, and if $f(x,y)=1$, they output different bits. Let us further require
Alice’s marginal distribution to be uniform, likewise for Bob, so that the
distribution is well defined. Call the resulting distribution
$\mathbf{p}_{f}$, that is, for any $a,b\in\\{0,1\\}$ and
$(x,y)\in\mathcal{X}\times\mathcal{Y}$, we have

$\displaystyle
p_{f}(a,b|x,y)=\left\\{\begin{array}[]{cl}\frac{1}{2}&\textrm{if }a\oplus
b=f(x,y),\\\ 0&\textrm{otherwise}\end{array}\right.$

where $\oplus$ symbol denotes the $1$-bit XOR.

If $\mathbf{p}_{f}$ were local, $f$ could be computed with one bit of
communication using shared randomness: Alice sends her output to Bob, and Bob
XORs it with his output. If $\mathbf{p}_{f}$ were quantum, there would be a
1-bit protocol with shared entanglement for $f$. In communication complexity,
we are usually interested in distributions having nontrivial communication
complexity, and lie well beyond these sets.

Finally, a distribution is nonsignaling if for each player, its marginal
output distributions, given by $p_{A}(a|x,y)=\sum_{b}p(a,b|x,y)$, for Alice,
and $p_{B}(b|x,y)=\sum_{a}p(a,b|x,y)$, for Bob, do not depend on the other
player’s input. When this is the case, we write the marginals as $p_{A}(a|x)$
and $p_{B}(b|y)$. Operationally, this means that each player cannot influence
the statistics of what the other player observes with his own choice of input.
We note with ${\cal C}$ the set of nonsignaling distributions, also referred
to as the causal set, and we note ${\cal C}^{\bot}$ when we allow aborting.
The well-known inclusion relations between these sets are ${\cal
L}\subset{\cal Q}\subset{\cal C}\subset{\cal P}$.

For any Boolean function $f$, the distribution $\mathbf{p}_{f}$ is
nonsignaling since the marginals are uniform.

A fundamental question of quantum mechanics has been to establish
experimentally whether nature is truly _nonlocal_ , as predicted by quantum
mechanics, or whether there is a purely classical (i.e., _local_) explanation
to the phenomena that have been predicted by quantum theory and observed in
the lab.

###  2.2 Measures of nonlocality

We have described nonlocality as a yes/no property, but some distributions are
somehow more nonlocal than others. To have a robust measure of nonlocality, it
should verify some common sense properties: for a fixed distribution, the
measure should be bounded; it should also be convex, since sampling from the
convex combination of two distributions can be done by first picking randomly
one of the two distributions using shared randomness, and then sampling from
that distribution. We also expect such a measure of nonlocality to have
various equivalent formulations. Several measures have been proposed and
studied: resistance to noise [KGZ+00, ADGL02, PGWP+08, JPPG+10a], resistance
to inefficiency [Mas02, MPRG02, LLR12], amount of communication necessary to
reproduce them [Mau92, BCT99, Ste00, TB03, Pir03, DKLR11], information-
theoretic measures [BCSS11, GWAN12, FWW09], etc.

In the form studied in this paper, normalized Bell inequalities were first
studied in [DKLR11], where they appeared as the dual of the linear program for
a well-studied lower bound on communication complexity, known as the nuclear
norm $\nu$ [LS09] (the definition is given in Section 2.3). There are many
equivalent formulations of this bound. For distributions arising from boolean
functions, it has the mathematical properties of a norm, and it is related to
winning probabilities of XOR games. It can also be viewed as a gauge, that is,
a quantity measuring by how much the local set must be expanded in order to
contain the distribution considered. For more general nonsignaling
distributions, besides having a geometrical interpretation in terms of affine
combinations of local distributions, it has also been shown to be equivalent
to the amount of local noise that can be tolerated before the distribution
becomes local [JPPG+10b].

A subsequent paper [LLR12] studied equivalent formulations of the partition
bound, one of the strongest lower bounds in communication complexity [JK10].
This was also found to have several equivalent formulations: the primal
formulation can be viewed as resistance to detector inefficiency, and the dual
formulation is given in terms of inefficiency-resistant Bell inequality
violations.

In this paper, we show how to deduce large violations on quantum distributions
from large violations on nonsignaling distributions, provided there are
efficient quantum communication protocols for the latter.

###  2.3 Communication complexity and lower bounds

In classical communication complexity (introduced by [Yao79]), two players
each have a share of the input, and they wish to compute a function on the
full input. Communication complexity measures the number of bits they need to
exchange in order to solve this problem in the worst case, over all inputs of
a given size $n$. In this paper we consider a generalization of this model,
where instead of computing a function, they each produce an output, and the
outputs $a,b$ they produce should follow, for each $(x,y)$, some prescribed
distribution $p(a,b|x,y)$ (which depends on their inputs $x,y$). We also
assume that the order in which the players speak does not depend on the
inputs. This is without loss of generality at a cost of a factor of 2 in the
communication.

We use the following notation for communication complexity of distributions.
$R_{\epsilon}(\mathbf{p})$ is the minimum number of bits exchanged in the
worst case to output with the distribution $\mathbf{p}$, up to $\epsilon$ in
total variation distance for all $x,y$. We call total variation distance
between distributions the distance denoted by $|.|_{1}$, and defined as
$|\mathbf{p}-\mathbf{p}^{\prime}|_{1}=\max_{x,y}\sum_{a,b}|p(a,b|x,y)-p^{\prime}(a,b|x,y)|$.

We use $Q$ to denote quantum communication complexity (see [Yao93]), and we
use the superscript $*$ to denote the presence of shared entanglement. For
randomized communication, we assume shared randomness.

To give upper bounds on communication complexity it suffices to give a
protocol and analyze its complexity. Proving lower bounds is often a more
difficult task, and many techniques have been developed to achieve this. The
methods we describe here are complexity measures which can be applied to any
function. To prove a lower bound on communication, it suffices to give a lower
bound on one of these complexity measures, which are bounded above by
communication complexity for any function. We describe here most of the
complexity measures relevant to this work.

The nuclear norm $\nu$, given here in its dual formulation and extended to
nonsignaling distributions, is expressed by the following linear program
[LS09, DKLR11]. (There is a quantum analogue, $\gamma_{2}$, which is not
needed in this work. We refer the interested reader to the definition for
distributions in [DKLR11]).

######  Definition 1 ([LS09, DKLR11]).

The nuclear norm $\nu$ of a nonsignaling distribution $\mathbf{p}\in{\cal C}$
is given by

$\displaystyle\nu(\mathbf{p})=$ $\displaystyle\max_{B}$ $\displaystyle
B(\mathbf{p})$ subject to $\displaystyle\mid\\!B(\mathbf{\ell})\\!\mid\leq 1$
$\displaystyle\quad\forall\mathbf{\ell}\in{\cal L}_{det}.$

With error $\epsilon$,
$\nu_{\epsilon}(\mathbf{p})=\min_{\mathbf{p}^{\prime}\in{\cal
C}:|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon}\nu(\mathbf{p}^{\prime})$.
We call any Bell functional that satisfies the constraint in the above linear
program normalized Bell functional.

In this definition and in the rest of the paper, unless otherwise specified
(see in particular in Lemma 1), the choice of $B$ is over vectors of real
coefficients $B_{a,b,x,y}$ and $B(\mathbf{p})$ denotes
$\sum_{a,b,x,y}B_{a,b,x,y}p(a,b|x,y)$, where $a,b$ ranges over the valid (non-
abort) outputs and $x,y$ ranges over the inputs. To be clear, even when $B$
and $\mathbf{p}$ have coefficients on the abort events, we do not count them.

Table 1 summarizes the known upper and lower bounds on $\nu$ for various
parameters.

We recall that (the log of) the nuclear norm is a lower bound on classical
communication complexity.

######  Proposition 1 ([LS09, DKLR11]).

For any nonsignaling distribution $\mathbf{p}\in{\cal C}$,

$\mathrm{R}_{\epsilon}(\mathbf{p})+1\geq\log(\nu_{\epsilon}(\mathbf{p})),$

and for any boolean function $f$,

$\mathrm{R}_{\epsilon}(f)\geq\log(\nu_{\epsilon}(\mathbf{p}_{f})).$

As lower bounds on communication complexity of Boolean functions go, $\nu$ is
one of the weaker bounds, equivalent to the smooth discrepancy [JK10], and no
larger than the approximate nonnegative rank and the smooth rectangle bounds
[KMSY14]. More significantly for this work, up to small multiplicative
constants, for boolean functions, (the logarithm of) $\nu$ is a lower bound on
quantum communication, so it cannot be used to establish gaps between
classical and quantum communication complexity. (This limitation, together
with the upper bound in terms of the number of outputs on normalized Bell
violations, is a consequence of Grothendieck’s theorem [Gro53].)

The classical and quantum efficiency measures, given here in their dual
formulations, are expressed by the following two convex optimization programs.
The classical bound is a generalization to distributions of the partition
bound of communication complexity [JK10, LLR12]. This bound is one of the
strongest lower bounds known, and can be exponentially larger than $\nu$ (an
example is the Vector in Subspace problem). It is always as least as large as
the relaxed partition bound which is in turn always at least as large as the
smooth rectangle bound [JK10, KLL+15]. Its weaker variants have been used to
show exponential gaps between classical and quantum communication complexity.
The definition we give here is a stronger formulation than the one given in
[LLR12]. We show they are equivalent in Appendix C.

######  Definition 2 ([LLR12]).

The $\epsilon$-error efficiency bound of a distribution $\mathbf{p}\in{\cal
P}$ is given by

$\displaystyle\mathrm{\bf eff}_{\epsilon}(\mathbf{p})=$
$\displaystyle\max_{B,\beta}$ $\displaystyle\beta$ subject to $\displaystyle
B(\mathbf{p}^{\prime})\geq\beta$
$\displaystyle\quad\forall\mathbf{p}^{\prime}\in{\cal
P}\>\rm{\>s.t.\>}|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon,$
$\displaystyle B(\mathbf{\ell})\leq 1$
$\displaystyle\quad\forall\mathbf{\ell}\in{\cal L}_{det}^{\bot}.$

We call any Bell functional that satisfies the second constraint in the above
linear program inefficiency-resistant Bell functional.

The $\epsilon$-error quantum efficiency bound of a distribution
$\mathbf{p}\in{\cal P}$ is given by

$\displaystyle\mathrm{\bf eff}_{\epsilon}^{*}(\mathbf{p})=$
$\displaystyle\max_{B,\beta}$ $\displaystyle\beta$ subject to $\displaystyle
B(\mathbf{p}^{\prime})\geq\beta$
$\displaystyle\quad\forall\mathbf{p}^{\prime}\in{\cal
P}\>\rm{\>s.t.\>}|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon,$
$\displaystyle B(\mathbf{q})\leq 1$
$\displaystyle\quad\forall\mathbf{q}\in{\cal Q}^{\bot}.$

We denote $\mathrm{\bf eff}=\mathrm{\bf eff}_{0}$ and $\mathrm{\bf
eff}^{*}=\mathrm{\bf eff}^{*}_{0}$ the $0$-error bounds.

For any given distribution $\mathbf{p}$, its classical communication
complexity is bounded below by the logarithm of the efficiency. For randomized
communication complexity with error $\epsilon$, the bound is given by
$\log(\mathrm{\bf eff}_{\epsilon})$ and for quantum communication complexity,
the bound is given by $\log(\mathrm{\bf eff}^{*}_{\epsilon}$). Note that for
any $\mathbf{p}\in{\cal Q}$, the quantum communication complexity is 0 and the
$\mathrm{\bf eff}^{*}$ bound is 1. For any function $f$, the efficiency bound
$\mathrm{\bf eff}_{\epsilon}(\mathbf{p}_{f})$ is known to be equivalent to the
partition bound $\mathrm{prt}_{\epsilon}(f)$ [JK10, LLR12].

######  Proposition 2 ([LLR12]).

For any boolean function $f$ and any $0\leq\epsilon<1/2$,

$\mathrm{R}_{\epsilon}(f)\geq\log(\mathrm{\bf
eff}_{\epsilon}(\mathbf{p}_{f}))\text{ and
}Q_{\epsilon}(f)\geq\frac{1}{2}\log(\mathrm{\bf
eff}^{*}_{\epsilon}(\mathbf{p}_{f})).$

For any nonsignaling distribution $\mathbf{p}\in{\cal C}$ and any
$0\leq\epsilon\leq 1$, $\nu_{\epsilon}(\mathbf{p})\leq 2\mathrm{\bf
eff}_{\epsilon}(\mathbf{p}).$

Theorem 3 below involves upper bounds on the quantum efficiency bound. To give
an upper bound on the quantum efficiency of a distribution $\mathbf{p}$, it is
more convenient to use the primal formulation, and upper bounds can be given
by exhibiting a local (or quantum) distribution with abort which satisfies the
following two properties: the probability of aborting should be the same on
all inputs $x,y$, and conditioned on not aborting, the outputs of the protocol
should reproduce the distribution $\mathbf{p}$. The efficiency is inverse
proportional to the probability of not aborting, so the goal is to abort as
little as possible.

######  Proposition 3 ([LLR12]).

For any distribution $\mathbf{p}\in{\cal P}$, $\mathrm{\bf
eff}^{*}(\mathbf{p})=1/\eta^{*}$, with $\eta^{*}$ the optimal value of the
following optimization problem (non-linear, because ${\cal Q}^{\bot}$ is not a
polytope).

$\displaystyle\max_{\zeta,\mathbf{q}\in{\cal Q}^{\bot}}\quad$
$\displaystyle\zeta$ subject to $\displaystyle q(a,b|x,y)=\zeta
p(a,b|x,y)\quad\forall
x,y,a,b\in\mathcal{X}{\times}\mathcal{Y}{\times}\mathcal{A}{\times}\mathcal{B}$

Moreover, for any $0\leq\epsilon\leq 1$, $\mathrm{\bf
eff}_{\epsilon}^{*}(\mathbf{p})=\min_{\mathbf{p}^{\prime}\in{\cal
P}:|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon}\mathrm{\bf
eff}^{*}(\mathbf{p}^{\prime})$.

##  3 Properties of Bell inequalities

Syntactically, there are two differences between the normalized Bell
functionals (Definition 1) and the inefficiency-resistant ones (Definition 2).
The first difference is that the normalization constraint is relaxed: for
inefficiency-resistant functionals, the lower bound on the Bell value for
local distributions is removed. Since this is a maximization problem, this
relaxation allows for larger violations.

This difference alone would not lead to a satisfactory measure of nonlocality,
since one could obtain unbounded violations by shifting and dilating the Bell
functional. The second difference prevents this. The upper bound is required
to hold not only for local distributions, but also those that can abort. This
is a much stronger condition. Notice that a local distribution can selectively
abort on configurations that would otherwise tend to keep the Bell value
small, making it harder to satisfy the constraint.

In this section, we show that normalized Bell violations can be modified to be
resistant to local distributions that abort, while preserving the violation on
any nonsignaling distribution, up to a factor of 3. This means that we can add
the stronger constraint of resistance to local distributions that abort to
Definition 1, incurring a loss of just a factor of 3, and the only remaining
difference between the resulting linear programs is the relaxation of the
lower bound (dropping the absolute value) for local distributions that abort.

######  Theorem 1.

Let $B$ be a normalized Bell functional on
$\mathcal{A}\times\mathcal{B}\times\mathcal{X}\times\mathcal{Y}$ and
$\mathbf{p}\in{\cal C}$ a nonsignaling distribution such that
$B(\mathbf{p})\geq 1$. Then there exists a normalized Bell functional $B^{*}$
on
$(\mathcal{A}\cup\\{\bot\\})\times(\mathcal{B}\cup\\{\bot\\})\times\mathcal{X}\times\mathcal{Y}$
with $0$ coefficients on the $\bot$ outputs such that :

$\displaystyle
B^{*}(\mathbf{p})\geq\frac{1}{3}B(\mathbf{p})-\frac{2}{3},\phantom{1}$
$\displaystyle\quad\forall\mathbf{p}\in{\cal C}$
$\displaystyle|B^{*}(\ell)|\leq
1,\phantom{\frac{1}{3}B(\mathbf{p})-\frac{2}{3}}$
$\displaystyle\quad\forall\ell\in{\cal L}_{\mathrm{det}}^{\bot}$

The rest of this section is devoted to the proof of Theorem 1. First, we show
(see Remark 1) how to rescale a normalized Bell functional so that it
saturates its normalization constraint. Then, Definition 3 adds weights to
abort events to make the Bell functional resistant to inefficiency. Finally,
Lemma 1 removes the weights on the abort events of a Bell functional while
keeping it bounded on the local set with abort, without dramatically changing
the values it takes on the nonsignaling set. Our techniques are similar to the
ones used in [MPRG02].

######  Remark 1.

Let $B$ be a non-constant normalized Bell functional and $\mathbf{p}\in{\cal
C}$ a nonsignaling distribution such that $B(\mathbf{p})\geq 1$. Consider
$\mathbf{\ell}^{-}\in{\cal L}_{\mathrm{det}}$ such that
$B(\mathbf{\ell}^{-})=m=\min\\{B(\mathbf{\ell})|\mathbf{\ell}\in{\cal
L}_{\mathrm{det}}\\}$ and $\mathbf{\ell}^{+}\in{\cal L}_{\mathrm{det}}$ such
that $B(\mathbf{\ell}^{+})=M=\max\\{B(\mathbf{\ell})|\mathbf{\ell}\in{\cal
L}_{\mathrm{det}}\\}$. We have $m<M$ because $B$ is non-constant.

The Bell functional $\tilde{B}$ defined by

$\displaystyle\tilde{B}(\cdot)=\frac{1}{M-m}(2B(\cdot)-M-m)$

is such that $\tilde{B}(\mathbf{\ell}^{+})=1$,
$\tilde{B}(\mathbf{\ell}^{-})=-1$, $|\tilde{B}(\ell)|\leq 1$ for all
$\ell\in{\cal L}_{\mathrm{det}}^{\bot}$, and $\tilde{B}(\mathbf{p})\geq
B(\mathbf{p})$.

######  Definition 3.

For any two families of distributions,
$\mathbf{m}_{A}=(m_{A}(\cdot|x))_{x\in\mathcal{X}}$ over outcomes in
$\mathcal{A}$ for Alice and
$\mathbf{m}_{B}=(m_{B}(\cdot|y))_{y\in\mathcal{Y}}$ over outcomes in
$\mathcal{B}$ for Bob, $f_{\mathbf{m}_{A},\mathbf{m}_{B}}:{\cal
C}^{\bot}\rightarrow{\cal C}$ is the function that replaces abort events on
Alice’s (resp. Bob’s) side by a sample from $\mathbf{m}_{A}$ (resp.
$\mathbf{m}_{B}$).

For $B$ a normalized Bell functional with coefficients only on non-abort
events, the Bell functional $B^{\bot}_{\mathbf{m}_{A},\mathbf{m}_{B}}$ on
$(\mathcal{A}\cup\\{\bot\\})\times(\mathcal{B}\cup\\{\bot\\})\times\mathcal{X}\times\mathcal{Y}$
is given by

$\displaystyle(B^{\bot}_{\mathbf{m}_{A},\mathbf{m}_{B}})_{a,b,x,y}=$
$\displaystyle
B_{a,b,x,y}+\chi_{\\{\bot\\}}(a)\sum_{a^{\prime}\neq\bot}m_{A}(a^{\prime}|x)B_{a^{\prime},b,x,y}+\chi_{\\{\bot\\}}(b)\sum_{b^{\prime}\neq\bot}m_{B}(b^{\prime}|y)B_{a,b^{\prime},x,y}$
$\displaystyle+\chi_{\\{\bot\\}}(a)\chi_{\\{\bot\\}}(b)\sum_{a^{\prime},b^{\prime}\neq\bot}m_{A}(a^{\prime}|x)m_{B}(b^{\prime}|y)B_{a^{\prime},b^{\prime},x,y}$

where $\chi_{\mathcal{S}}$ is the indicator function for set $\mathcal{S}$
taking value $1$ on $\mathcal{S}$ and $0$ everywhere else.

Note that $f_{\mathbf{m}_{A},\mathbf{m}_{B}}$ preserves locality, and
$B^{\bot}_{\mathbf{m}_{A},\mathbf{m}_{B}}(\mathbf{p})=B(f_{\mathbf{m}_{A},\mathbf{m}_{B}}(\mathbf{p})),\
\forall\mathbf{p}\in{\cal C}^{\bot}$, so

$\displaystyle B^{\bot}_{\mathbf{m}_{A},\mathbf{m}_{B}}(\mathbf{p})$
$\displaystyle=B(\mathbf{p}),$ $\displaystyle\forall\mathbf{p}$
$\displaystyle\in{\cal C},$
$\displaystyle|B^{\bot}_{\mathbf{m}_{A},\mathbf{m}_{B}}(\mathbf{\ell})|$
$\displaystyle\leq 1,$ $\displaystyle\forall\mathbf{\ell}$
$\displaystyle\in{\cal L}^{\bot}.$

######  Lemma 1.

Let $B^{\prime}$ be a normalized Bell functional on
$(\mathcal{A}\cup\\{\bot\\})\times(\mathcal{B}\cup\\{\bot\\})\times\mathcal{X}\times\mathcal{Y}$.
($B^{\prime}$ might have weights on abort events.) Then the Bell functional
$B^{\prime\prime}$ on the same set defined by

$B^{\prime\prime}_{a,b,x,y}=B^{\prime}_{a,b,x,y}-B^{\prime}_{a,\bot,x,y}-B^{\prime}_{\bot,b,x,y}+B^{\prime}_{\bot,\bot,x,y},$
(1)

for all
$(a,b,x,y)\in(\mathcal{A}\cup\\{\bot\\})\times(\mathcal{B}\cup\\{\bot\\})\times\mathcal{X}\times\mathcal{Y}$
satisfies :

  1. 1.

If $B^{\prime\prime}_{a,b,x,y}=0$, then $a=\bot\ or\ b=\bot$

  2. 2.

$\forall\mathbf{p}\in{\cal
C},B^{\prime\prime}(\mathbf{p})=B^{\prime}(\mathbf{p})-B^{\prime}(\mathbf{p}_{A,\bot})-B^{\prime}(\mathbf{p}_{\bot,B})+B^{\prime}(\mathbf{p}_{\bot,\bot})$,

where $\mathbf{p}_{A,\bot}\in{\cal L}^{\bot}$ (resp.
$\mathbf{p}_{\bot,B}\in{\cal L}^{\bot}$) is the local distribution obtained
from $\mathbf{p}$ if Bob (resp. Alice) replaces any of his (resp. her) outputs
by $\bot$, and $\mathbf{p}_{\bot,\bot}\in{\cal L}^{\bot}$ is the local
distribution where Alice and Bob always output $\bot$.ÊIn Item 2 above, for
any $\mathbf{p}^{\prime}$,
$B^{\prime}(\mathbf{p}^{\prime})=\sum_{a,b,x,y}B^{\prime}_{a,b,x,y}\mathbf{p}^{\prime}(a,b|x,y)$
where the sum is also over the abort events.

###### Proof.

Item 1 follows from Equation (1), so we only need to prove Item 2.

For $\mathbf{p}\in{\cal C}^{\bot}$ with marginals $\mathbf{p}_{A}$ and
$\mathbf{p}_{B}$, we can write:

$\displaystyle p_{A}(a|x)=\sum_{b\in\mathcal{B}\cup\\{\bot\\}}p(a,b|x,y),\
\forall y\in Y,\quad
p_{B}(b|y)=\sum_{a\in\mathcal{A}\cup\\{\bot\\}}p(a,b|x,y),\ \forall x\in X.$

For the remainder of this proof, summations invlolving $a$ (resp. $b$) are
over $a\in\mathcal{A}\cup\\{\bot\\}$ (resp. $b\in\mathcal{B}\cup\\{\bot\\}$).

By definition, $p_{A,\bot}(a,b|x,y)=p_{A}(a|x)\chi_{\\{\bot\\}}(b),$
$p_{\bot,B}(a,b|x,y)=\chi_{\\{\bot\\}}(a)p_{B}(b|y),$ and
$p_{\bot,\bot}(a,b|x,y)=\chi_{\\{\bot\\}}(a)\chi_{\\{\bot\\}}(b).$ We
decompose $B^{\prime\prime}(\mathbf{p})$ as follows:

$\displaystyle B^{\prime\prime}(\mathbf{p})$
$\displaystyle=\sum_{a,b,x,y}\left[B^{\prime}_{a,b,x,y}-B^{\prime}_{a,\bot,x,y}-B^{\prime}_{\bot,b,x,y}+B^{\prime}_{\bot,\bot,x,y}\right]p(a,b|x,y)$
$\displaystyle=\sum_{a,b,x,y}B^{\prime}_{a,b,x,y}p(a,b|x,y)-\sum_{a,x,y}B^{\prime}_{a,\bot,x,y}\sum_{b}p(a,b|x,y)$
$\displaystyle\qquad-\sum_{b,x,y}B^{\prime}_{\bot,b,x,y}\sum_{a}p(a,b|x,y)+\sum_{x,y}B^{\prime}_{\bot,\bot,x,y}\sum_{a,b}p(a,b|x,y)$
$\displaystyle=B^{\prime}(\mathbf{p})-\sum_{a,x,y}B^{\prime}_{a,\bot,x,y}p_{A}(a|x)-\sum_{b,x,y}B^{\prime}_{\bot,b,x,y}p_{B}(b|y)+\sum_{x,y}B^{\prime}_{\bot,\bot,x,y}$
$\displaystyle=B^{\prime}(\mathbf{p})-B^{\prime}(\mathbf{p}_{A,\bot})-B^{\prime}(\mathbf{p}_{\bot,B})+B^{\prime}(\mathbf{p}_{\bot,\bot}).$

∎

We are now ready to prove Theorem 1.

###### Proof of Theorem 1.

From Remark 1, we can assume that there exists
$\mathbf{\ell}^{-},\mathbf{\ell}^{+}\in{\cal L}_{\mathrm{det}}$ such that
$B(\mathbf{\ell}^{-})=-1$ and $B(\mathbf{\ell}^{+})=1$. If that is not the
case, we just have to replace $B$ by its saturated version $\tilde{B}$.

Since $\mathbf{\ell}^{-}$ and $\mathbf{\ell}^{+}$ are deterministic
distributions, they are product distributions:
$\mathbf{\ell}^{-}=\mathbf{\ell}_{A}^{-}\otimes\mathbf{\ell}_{B}^{-}$ and
$\mathbf{\ell}^{+}=\mathbf{\ell}_{A}^{+}\otimes\mathbf{\ell}_{B}^{+}$, for
some marginals
$\mathbf{\ell}_{A}^{-},\mathbf{\ell}_{B}^{-},\mathbf{\ell}_{A}^{+},$ and
$\mathbf{\ell}_{B}^{+}$.

We consider the two replacing Bell functionals from Definition 3 constructed
from $(B,\mathbf{\ell}_{A}^{-},\mathbf{\ell}_{B}^{-})$ on one hand, and
$(B,\mathbf{\ell}_{A}^{+},\mathbf{\ell}_{B}^{+})$ on the other hand. We take
their average
$B^{\prime}=\frac{1}{2}(B^{\bot}_{\mathbf{\ell}_{A}^{-},\mathbf{\ell}_{B}^{-}}+B^{\bot}_{\mathbf{\ell}_{A}^{+},\mathbf{\ell}_{B}^{+}})$.
We have $|B^{\prime}(\mathbf{\ell})|\leq 1,\ \forall\mathbf{\ell}\in{\cal
L}^{\bot}$, and therefore we can apply Lemma 1 to $B^{\prime}$ to get
$B^{\prime\prime}$.

Since
$B^{\prime}(\mathbf{p}_{\bot,\bot})=\frac{1}{2}(B^{\bot}_{\mathbf{\ell}_{A}^{-},\mathbf{\ell}_{B}^{-}}(\mathbf{p}_{\bot,\bot})+B^{\bot}_{\mathbf{\ell}_{A}^{+},\mathbf{\ell}_{B}^{+}}(\mathbf{p}_{\bot,\bot}))=\frac{1}{2}(B(\mathbf{\ell}^{-})+B(\mathbf{\ell}^{+}))=0$,
we have

$\displaystyle\forall\mathbf{p}\in{\cal C}^{\bot},\
B^{\prime\prime}(\mathbf{p})=B^{\prime}(\mathbf{p})-B^{\prime}(\mathbf{p}_{A,\bot})-B^{\prime}(\mathbf{p}_{\bot,B}).$

Therefore $B^{*}=\frac{1}{3}B^{\prime\prime}$ satisfies all the required
properties. In particular, since $|B^{\prime}(\mathbf{\ell})|\leq 1\
\forall\mathbf{\ell}\in{\cal L}^{\bot}$, we have for any $\mathbf{p}\in{\cal
C}$

$\displaystyle
B^{*}(\mathbf{p})\geq\frac{1}{3}B^{\prime}(\mathbf{p})-\frac{1}{3}|B^{\prime}(\mathbf{p}_{A,\bot})|-\frac{1}{3}|B^{\prime}(\mathbf{p}_{\bot,B})|\geq\frac{1}{3}B^{\prime}(\mathbf{p})-\frac{2}{3},$

and for any local distribution $\mathbf{\ell}\in{\cal L}^{\bot}$

$\displaystyle|B^{*}(\mathbf{\ell})|\leq\frac{1}{3}|B^{\prime}(\mathbf{\ell})|+\frac{1}{3}|B^{\prime}(\mathbf{\ell}_{A,\bot})|+\frac{1}{3}|B^{\prime}(\mathbf{\ell}_{\bot,B})|\leq
1.$

∎

##  4 Exponential violations from communication bounds

In a recent paper, Buhrman et al. gave a general construction to derive
normalized Bell inequalities from any sufficiently large gap between classical
and quantum communication complexity.

######  Theorem 2 ([BCG+16]).

For any function $f$ for which there is a quantum protocol using $q$ qubits of
communication but no prior shared entanglement, there exists a quantum
distribution $\mathbf{q}\in{\cal Q}$ and a normalized Bell functional $B$ such
that

$\displaystyle
B(\mathbf{q})\geq\frac{\sqrt{R_{1/3}(f)}}{6\sqrt{3}q}(1-2^{-q})^{2q}.$

Their construction is quite involved, requiring protocols to be memoryless,
which they show how to achieve in general, and uses multiport teleportation to
construct a quantum distribution. The Bell inequality they construct expresses
a correctness constraint.

In this section, we show how to obtain large inefficiency-resistant Bell
violations for quantum distributions from gaps between quantum communication
and classical communication lower bounds. We first prove the stronger of two
statements, which gives violations of $\frac{\mathrm{\bf
eff}_{\epsilon}(\mathbf{p})}{\mathrm{\bf
eff}_{\epsilon^{\prime}}^{\star}(\mathbf{p})}$.For any problem for which a
classical lower bound $c$ is given using the efficiency or partition bound or
any weaker method (including the rectangle bound and its variants), and any
upper bound $q$ on quantum communication complexity, it implies a violation of
$2^{c-2q}$.

######  Theorem 3.

For any distribution $\mathbf{p}\in{\cal P}$ and any
$0\leq\epsilon^{\prime}\leq\epsilon\leq 1$, if $(B,\beta)$ is a feasible
solution to the dual of $\mathrm{\bf eff}_{\epsilon}(\mathbf{p})$ and
$(\zeta,\mathbf{q})$ is a feasible solution to the primal for $\mathrm{\bf
eff}^{\star}_{\epsilon^{\prime}}(\mathbf{p})$, then there is a quantum
distribution $\overline{\mathbf{q}}\in{\cal Q}$ such that

$B(\overline{\mathbf{q}})\geq\zeta\beta\quad\quad{\rm and}\quad\quad
B(\mathbf{\ell})\leq 1,\quad\forall\mathbf{\ell}\in{\cal L}_{det}^{\bot}\,,$

and in particular, if both are optimal solutions, then

$B(\overline{\mathbf{q}})\geq\frac{\mathrm{\bf
eff}_{\epsilon}(\mathbf{p})}{\mathrm{\bf
eff}_{\epsilon^{\prime}}^{\star}(\mathbf{p})}\,.$

The distribution $\overline{\mathbf{q}}$ has one additional output per player
compared to the distribution $\mathbf{p}$.

###### Proof.

Let $(B,\beta)$ be a feasible solution to the dual of $\mathrm{\bf
eff}_{\epsilon}(\mathbf{p})$, $\mathbf{p}^{\prime}$ be such that $\mathrm{\bf
eff}^{\star}_{\epsilon^{\prime}}(\mathbf{p})=\mathrm{\bf
eff}^{\star}(\mathbf{p}^{\prime})$ with
$|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon^{\prime}$, and
$(\zeta,\mathbf{q})$ be a feasible solution to the primal for $\mathrm{\bf
eff}^{\star}(\mathbf{p}^{\prime})$. From the constraints, we have

$\displaystyle\mathbf{q}\in{\cal Q}^{\bot},$ $\displaystyle q(a,b|x,y)=\zeta
p^{\prime}(a,b|x,y)$
$\displaystyle\forall(a,b,x,y)\in\mathcal{A}\times\mathcal{B}\times\mathcal{X}\times\mathcal{Y},$
$\displaystyle B(\mathbf{\ell})\leq 1$
$\displaystyle\forall\mathbf{\ell}\in{\cal L}_{det}^{\bot},$ $\displaystyle
B(\mathbf{p}^{\prime\prime})\geq\beta$
$\displaystyle\forall\mathbf{p}^{\prime\prime}\textrm{ s.t.
}|\mathbf{p}^{\prime\prime}-\mathbf{p}|_{1}\leq\epsilon.$

Then $B(\mathbf{q})=\zeta B(\mathbf{p}^{\prime})\geq\zeta\beta$. However,
$\mathbf{q}\in{\cal Q}^{\bot}$ but technically we want a distribution in
${\cal Q}$ (not one that aborts). So we add a new (valid) output ‘A’ to the
set of outputs of each player, and they should output ‘A’ instead of aborting
whenever $\mathbf{q}$ aborts. The resulting distribution, say
$\overline{\mathbf{q}}\in{\cal Q}$ (with additional outcomes ‘A’ on both
sides), is such that $B(\overline{\mathbf{q}})=B(\mathbf{q})$ (since the Bell
functional $B$ does not have any weight on $\bot$ or on ‘A’). ∎

Theorem 2 [BCG+16] and Theorem 3 are both general constructions, but there are
a few significant differences worth pointing out. Firstly, our Theorem 3
requires a lower bound on the partition bound in the numerator, whereas
Theorem 2 only requires a lower bound on communication complexity (which could
be exponentially larger). Secondly, Theorem 2 requires a quantum communication
protocol in the denominator, whereas our theorem only requires an upper bound
on the quantum efficiency (which could be exponentially smaller). Thirdly,
although our bound is exponentially larger than Buhrman et al.’s for most
problems considered here, and applies to subquadratic gaps, their bounds are
of the more restricted class of normalized Bell inequalities.

Theorem 3 gives an explicit Bell functional $B$ provided an explicit solution
to the efficiency (partition) bound is given and the quantum distribution is
obtained from a solution to the primal of $\mathrm{\bf eff}^{\star}$
(Proposition 3). Recall that giving a solution to the primal of $\mathrm{\bf
eff}^{\star}$ consists in exhibiting a quantum zero-communication protocol
that can abort, which conditioned on not aborting, outputs following
$\mathbf{p}$.

We can also start from a quantum protocol, as we show below. From the quantum
protocol, we derive a quantum distribution using standard techniques.

######  Corollary 1.

For any distribution $\mathbf{p}\in{\cal P}$ and any
$0\leq\epsilon^{\prime}\leq\epsilon\leq 1$ such that
$R_{\epsilon}(\mathbf{p})\geq\log(\mathrm{\bf eff}_{\epsilon}(\mathbf{p}))\geq
c$ and $Q_{\epsilon^{\prime}}(\mathbf{p})\leq q$, there exists an explicit
inefficiency-resistant $B$ derived from the efficiency lower bound, and an
explicit quantum distribution $\overline{\mathbf{q}}\in{\cal Q}$ derived from
the quantum protocol such that $B(\overline{\mathbf{q}})\geq 2^{c-2q}$.

###### Proof.

Let $(B,\beta)$ be an optimal solution to $\mathrm{\bf
eff}_{\epsilon}(\mathbf{p})$ and let $c$ be such that $\mathrm{\bf
eff}_{\epsilon}(\mathbf{p})=\beta\geq 2^{c}$. By optimality of $B$, we have
$B(\mathbf{p}^{\prime})\geq 2^{c}$ for any $\mathbf{p}^{\prime}$ such that
$|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon$. Since
$Q_{\epsilon^{\prime}}(\mathbf{p})\leq q$, there exists a $q$-qbit quantum
protocol for some distribution $\mathbf{p}^{\prime}$ with
$|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon$. Then, we can use
teleportation to obtain a $2q$ classical bit, entanglement-assisted protocol
for $\mathbf{p}^{\prime}$. We can simulate it without communication by picking
a shared $2q$-bit random string and running the protocol but without sending
any messages. If the measurements do not match the string, output a new symbol
‘A’ (not in the output set of the quantum protocol and different from $\bot$).
We obtain a quantum distribution $\overline{\mathbf{q}}$ such that
$B(\overline{\mathbf{q}})=B(\mathbf{p}^{\prime})/2^{2q}\geq 2^{c-2q}$. ∎

Most often, communication lower bounds are not given as efficiency or
partition bounds, but rather using variants of the corruption bound. We show
in Section 6.1 how to map a corruption bound to explicit Bell coefficients.

##  5 Noise-resistant violations from communication bounds

Normalized Bell inequalities are naturally resistant to any local noise: if
the observed distribution is
$\tilde{\mathbf{p}}=(1-\varepsilon)\mathbf{p}+\varepsilon\mathbf{\ell}$ for
some $\mathbf{\ell}\in{\cal L}$, then
$B(\tilde{\mathbf{p}})\geq(1-\varepsilon)B(\mathbf{p})-\varepsilon$ since
$\mid\\!B(\mathbf{\ell})\\!\mid\leq 1$. In inefficiency-resistant Bell
inequalities, relaxing the absolute value leads to the possibility that
$B(\mathbf{\ell})$ has a large negative value for some local $\mathbf{\ell}$.
(Indeed, such large negative values are inherent to large gaps between $\nu$
and $\mathrm{\bf eff}$.) If this distribution were to be used as adversarial
noise, then the observed distribution,
$(1-\varepsilon)\mathbf{p}+\varepsilon\mathbf{\ell}$, would have a Bell value
that could be much less than 1. This makes inefficiency-resistant Bell
inequalities susceptible to adversarial local noise.

Our construction from Theorem 3 is susceptible to uniform noise since most of
the time, the output is ‘A’. Uniform noise will disproportionately hit the
non-‘A’ outputs, destroying the structure of the distribution. In Theorem 4,
we show that our construction can be made resistant to uniform noise, by
including a (possible) transcript from the protocol in the outputs. (Notice
that this leads to a much larger output set.) Since the transcripts in our
construction are teleportation measurements, they follow a uniform
distribution, making the modified distribution resistant to uniform noise. The
tolerance to noise comes from the error parameter in the classical
communication lower bound.

Let $N_{\varepsilon}(\mathbf{p})$ be the $\varepsilon$-noisy neighbourhood of
$\mathbf{p}$, defined as

$N_{\varepsilon}(\mathbf{p})=\\{(1-\delta)\mathbf{p}+\delta\mathbf{u},\>\delta\in[0,\varepsilon]\\}\subseteq{\cal
P}$

where $\mathbf{u}$ the uniform noise distribution, that is:
$u(a,b|x,y)=\frac{1}{|\mathcal{A}|Ê\cdot|\mathcal{B}|}$ for all
$(a,b)\in\mathcal{A}\times\mathcal{B}$.

######  Theorem 4.

For any distribution $\mathbf{p}\in{\cal P}$ and any
$0\leq\epsilon^{\prime}\leq\epsilon\leq 1$ such that
$R_{\epsilon}(\mathbf{p})\geq\log(\mathrm{\bf eff}_{\epsilon}(\mathbf{p}))\geq
c$ and $Q_{\epsilon^{\prime}}(\mathbf{p})\leq q$, there exists an explicit
inefficiency-resistant $\tilde{B}$ derived from the efficiency lower bound,
and an explicit quantum distribution $\overline{\mathbf{q}}\in{\cal Q}$
derived from the quantum protocol such that
$\tilde{B}(\mathbf{q}^{\prime})\geq 2^{c-2q}$ for any $\mathbf{q}^{\prime}\in
N_{\varepsilon-\varepsilon^{\prime}}(\overline{\mathbf{q}})$.

###### Proof.

Let $\mathcal{A}$ (resp. $\mathcal{B}$) be Alice’s (resp. Bob’s) possible
outputs for $\mathbf{p}$. From a quantum communication protocol for
$\mathbf{p}^{\prime}$ with
$|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon^{\prime}$ using $q$ qubits
of communication, we construct an entanglement-assisted protocol using $2q$
bits of communication and teleportation. Let $\mathcal{M}_{A}$ (resp.
$\mathcal{M}_{B}$) be the set of possible transcripts for Alice (resp. Bob),
with $\mid\\!\mathcal{M}_{A}\\!\mid=M_{A}$ (resp.
$\mid\\!\mathcal{M}_{B}\\!\mid=M_{B}$), and note that $\log M_{A}+\log
M_{B}=2q$

We define the quantum distribution $\overline{\mathbf{q}}$ where Alice’s
possible outputs are $\mathcal{A}\times\mathcal{M}_{A}$ and Bob’s possible
outputs are $\mathcal{B}\times\mathcal{M}_{B}$. Alice proceeds as follows (Bob
proceeds similarly):

  1. 1.

She runs the quantum protocol for $\mathbf{p}^{\prime}$ as if all bits
received from Bob were $0$.

  2. 2.

She outputs $(a,\mu_{A})$, where $\mu_{A}$ is the transcript of the messages
she would have sent to Bob and $a$ is the output she would have produced in
the original protocol.

By definition, this distribution is such that, for all $a,b,x,y$,
$\overline{q}(a,0,b,0|x,y)=\frac{1}{2^{2q}}p^{\prime}(a,b|x,y)$.

Let $\mathrm{\bf eff}_{\varepsilon}(\mathbf{p})\geq 2^{c}$ be achieved by the
Bell functional $B$. By definition, we have

$\displaystyle B(\mathbf{\ell})$ $\displaystyle\leq
1\phantom{2^{c}}\qquad\forall\mathbf{\ell}\in{\cal L}_{det}^{\bot}$
$\displaystyle B(\mathbf{p}^{\prime\prime})$ $\displaystyle\geq
2^{c}\phantom{1}\qquad\forall\mathbf{p}^{\prime\prime}\>such\>that\>|\mathbf{p}^{\prime\prime}-\mathbf{p}|_{1}\leq\varepsilon,$

In particular for any $\mathbf{p}^{\prime\prime}\in
N_{\varepsilon-\varepsilon^{\prime}}(\mathbf{p})$, that is,
$\mathbf{p}^{\prime\prime}=(1-\delta)\mathbf{p}+\delta\mathbf{u}$ for some
$\delta\in[0,\varepsilon-\varepsilon^{\prime}]$, we have
$|\mathbf{p}^{\prime\prime}-\mathbf{p}|_{1}\leq\varepsilon$ and therefore

$\displaystyle
B(\mathbf{p}^{\prime\prime})=(1-\delta)B(\mathbf{p}^{\prime})+\delta
B(\mathbf{u})\geq 2^{c},$

where $B(\mathbf{u})=\frac{1}{AB}\sum_{a,b,x,y}B_{a,b,x,y}$.

Let the Bell functional $\tilde{B}$ for distributions over
$(\mathcal{A}\times\mathcal{M}_{A})\times(\mathcal{B}\times\mathcal{M}_{B})$
be defined as follows

$\displaystyle\tilde{B}_{(a,\mu_{A}),(b,\mu_{B}),x,y}=\left\\{\begin{array}[]{ll}B_{a,b,x,y}&\textrm{if
}\mu_{A}=\mu_{B}=0\\\ 0&\textrm{otherwise.}\end{array}\right.$

Let $\tilde{{\cal L}}_{det}^{\bot}$ be the local set for distributions over
$(\mathcal{A}\times\mathcal{M}_{A})\times(\mathcal{B}\times\mathcal{M}_{B})$.
The new Bell functional satisfies $\tilde{B}(\mathbf{\ell})\leq 1$ for all
$\mathbf{\ell}\in\tilde{{\cal L}}_{det}^{\bot}$ (by assimilating any event
with $\mu_{A}\neq 0$ or $\mu_{B}\neq 0$ to an abort event), as well as
$\tilde{B}(\overline{\mathbf{q}})=\frac{1}{2^{2q}}B(\mathbf{p}^{\prime})$.
Therefore, $\forall\delta\in[0,\varepsilon-\varepsilon^{\prime}]$, we also
have

$\displaystyle(1-\delta)\tilde{B}(\overline{\mathbf{q}})+\delta\tilde{B}(\mathbf{u})$
$\displaystyle=(1-\delta)\frac{1}{2^{2q}}B(\mathbf{p}^{\prime})+\delta\frac{1}{ABM_{A}M_{B}}\sum_{a,\mu_{A},b,\mu_{B},x,y}\tilde{B}_{(a,\mu_{A}),(b,\mu_{B}),x,y}$
$\displaystyle=\frac{1}{2^{2q}}\left[(1-\delta)B(\mathbf{p}^{\prime})+\delta\frac{1}{AB}\sum_{a,b,x,y}B_{a,b,x,y}\right]$
$\displaystyle=\frac{1}{2^{2q}}\big{[}(1-\delta)B(\mathbf{p}^{\prime})+\delta
B(\mathbf{u})\big{]}\geq\frac{2^{c}}{2^{2q}}.$

Therefore, $\forall\mathbf{q}^{\prime}\in
N_{\varepsilon-\varepsilon^{\prime}}(\overline{\mathbf{q}}),\>\tilde{B}(\mathbf{q}^{\prime})\geq
2^{c-2q}$, as claimed. ∎

##  6 Explicit constructions

###  6.1 From corruption bound to Bell inequality violation

We now explain how to construct an explicit Bell inequality violation from the
corruption bound. The corruption bound, introduced by Yao in [Yao83], is a
very useful lower bound technique. It has been used for instance in [Raz92] to
get a tight $\Omega(n)$ lower bound on the randomized communication complexity
of Disjointness (whereas the approximate rank, for example, can only show a
lower bound of $\Theta(\sqrt{n})$).

######  Definition 4.

A rectangle $R$ of the input space $\mathcal{X}\times\mathcal{Y}$ is a subset
of that space of the form $R_{A}\times\mathrm{R}_{B}$ where
$R_{A}\subseteq\mathcal{X}$ and $R_{B}\subseteq\mathcal{Y}$.

######  Theorem 5 ([Yao83, BFS86, KN97]).

Let $f$ be a (possibly partial) Boolean function on
$\mathcal{X}\times\mathcal{Y}$. Given $\gamma,\delta\in(0,1)$, suppose that
there is a distribution $\mu$ on $\mathcal{X}\times\mathcal{Y}$ such that for
every rectangle $R\subseteq\mathcal{X}\times\mathcal{Y}$ with $\mu(R)>\delta$:
$\mu(R\cap f^{-1}(1))>\gamma\mu(R\cap f^{-1}(0)).$ Then, for every
$\epsilon\in(0,1)$,
$2^{R_{\epsilon}(f)}\geq\frac{1}{\delta}\left(\mu(f^{-1}(0))-\frac{\epsilon}{\gamma}\right).$

The reader is referred to, e.g., Lemma 3.5 in [BPSW06] for a rigorous
treatment. For several problems, such a distribution $\mu$ is already known.
We show how to construct a Bell inequality violation from this type of bound.

######  Proposition 4.

Let $f$ be a (possibly partial) Boolean function on
$\mathcal{X}\times\mathcal{Y}$. Given $\gamma\in(0,1)$ and $\delta\in(0,1)$,
suppose that there is a distribution $\mu$ on $\mathcal{X}\times\mathcal{Y}$
such that: for any rectangle $R\subseteq\mathcal{X}\times\mathcal{Y}$ with
$\mu(R)>\delta$,

$\mu(R\cap f^{-1}(1))>\gamma\mu(R\cap f^{-1}(0)).$ (2)

Let $B$ be the Bell functional given by the following coefficients: for all
$a,b,x,y\in\\{0,1\\}\times\\{0,1\\}\times\mathcal{X}\times\mathcal{Y}$,

$B_{a,b,x,y}=\begin{cases}-\frac{1}{2\cdot\delta}\mu(x,y)&\mbox{ if
}f(x,y)=1\quad\land\quad a\oplus b=0,\\\
\frac{\gamma}{2\cdot\delta}\mu(x,y)&\mbox{ if }f(x,y)=0\quad\land\quad a\oplus
b=0,\\\ 0&\mbox{otherwise.}\end{cases}$

Then, $B$ satisfies

$B(\mathbf{\ell})\leq 1,\quad\forall\mathbf{\ell}\in{\cal L}_{det}^{\bot},$
(3) $B(\mathbf{p}_{f})=\frac{\gamma}{2\cdot\delta}\mu(f^{-1}(0))$ (4)

and for any $\mathbf{p}^{\prime}\in{\cal P}$ such that
$|\mathbf{p}^{\prime}-\mathbf{p}_{f}|_{1}\leq\epsilon$ :

$B(\mathbf{p}^{\prime})\geq\frac{1}{2\cdot\delta}\left[\gamma\mu(f^{-1}(0))-\epsilon\left(\gamma\mu(f^{-1}(0))+\mu(f^{-1}(1))\right)\right].$
(5)

###### Proof.

We will use the same value $B_{0,x,y}$ for $B_{a,b,x,y}$ when $a\oplus b=0$,
and similarly for $B_{1,x,y}$ when $a\oplus b=1$. Let us first set
$B_{0,x,y}=B_{a,b,x,y}$ for all $a\oplus b=0$. Let $\mathbf{\ell}\in{\cal
L}_{det}^{\bot}$. Then, we have: $B(\mathbf{\ell})=\sum_{(x,y)\in
R}B_{0,x,y}+\sum_{(x,y)\in S}B_{0,x,y}$ where $R$ and $S$ are the two
rectangles where $\mathbf{\ell}$ outputs $0$. Let us consider a rectangle $R$.
Then : $\sum_{(x,y)\in
R}B_{0,x,y}=\frac{1}{2\cdot\delta}\left(\gamma\mu(f^{-1}(0)\cap
R)-\mu(f^{-1}(1)\cap R)\right)$, which is less than $1/2$ by (2). This proves
(3). Let us now compute $B(\mathbf{p}_{f})$. By linearity of $B$ and the
definition of its coefficients, we have:

$\displaystyle B(\mathbf{p}_{f})$
$\displaystyle=\sum_{a,b,x,y}B_{a,b,x,y}p_{f}(ab|xy)$
$\displaystyle=\frac{1}{2}\sum_{(x,y)\in
f^{-1}(0),a,b}B_{a,b,x,y}\chi_{\\{0\\}}(a\oplus b)+\frac{1}{2}\sum_{(x,y)\in
f^{-1}(1),a,b}B_{a,b,x,y}\chi_{\\{1\\}}(a\oplus b)$
$\displaystyle=\frac{1}{2\cdot\delta}{\gamma\mu(f^{-1}(0))}$

For the third equality, we used the fact that $B_{a,b,x,y}=0$ when $a\oplus
b=1$. This proves (4).

Moreover, for any family of additive error terms $\Delta(a,b|x,y)\in[-1,1]$
such that

$\displaystyle\sum_{a,b}|\Delta(a,b|x,y)|$ $\displaystyle\leq\epsilon$
$\displaystyle\forall x,y\in\mathcal{X}\times\mathcal{Y},$

denoted collectively as $\boldsymbol{\Delta}$, we have

$\displaystyle|B(\boldsymbol{\Delta})|$
$\displaystyle=\frac{1}{2\cdot\delta}\left|\sum_{a,b\,:\,a\oplus
b=0}\left[\sum_{(x,y)\in f^{-1}(1)}(-1)\mu(x,y)\Delta(a,b|x,y)+\sum_{(x,y)\in
f^{-1}(0)}\gamma\mu(x,y)\Delta(a,b|x,y)\right]\right|$
$\displaystyle\leq\frac{1}{2\cdot\delta}\left[\sum_{(x,y)\in
f^{-1}(1)}\mu(x,y)\left(\sum_{a,b}|\Delta(a,b|x,y)|\right)+\sum_{(x,y)\in
f^{-1}(0)}\gamma\mu(x,y)\left(\sum_{a,b}|\Delta(a,b|x,y)|\right)\right]$
$\displaystyle\leq\frac{\epsilon}{2\cdot\delta}\left[\mu(f^{-1}(1))+\gamma\mu(f^{-1}(0))\right].$

From this calculation and (4), we obtain (5) for
$\mathbf{p}^{\prime}=\mathbf{p}_{f}+\boldsymbol{\Delta}$.

∎

For many other problems in the literature, stronger variants of the corruption
bounds are needed to obtain good lower bounds, such as Vector in Subspace, Gap
Hamming Distance and the related problem Gap Orthogonality. These stronger
variants have been shown to be no stronger than the partition bound (more
specifically, the relaxed partition bound) [KLL+15]. A stronger version of
Proposition 4, needed for the examples, is given in Appendix A. (The proof is
very similar).

###  6.2 Some specific examples

Using Corollary 1 and the construction to go from a corruption bound (or its
variants, see Appendix A) to a Bell inequality (Proposition 4), we give
explicit Bell inequalities and violations for several problems studied in the
literature. Since our techniques also apply to small gaps, we include problems
for which the gap between classical and quantum communication complexity is
polynomial.

#### Vector in Subspace

In the Vector in Subspace Problem $\mathrm{VSP}_{0,n}$, Alice is given an
$n/2$ dimensional subspace of an $n$ dimensional space over $\mathbb{R}$, and
Bob is given a vector. This is a partial function, and the promise is that
either Bob’s vector lies in the subspace, in which case the function evaluates
to $1$, or it lies in the orthogonal subspace, in which case the function
evaluates to $0$. Note that the input set of $\mathrm{VSP}_{0,n}$ is
continuous, but it can be discretized by rounding, which leads to the problem
$\widetilde{\mathrm{VSP}}_{\theta,n}$ (see [KR11] for details).

Klartag and Regev [KR11] show that the VSP can be solved with an $O(\log n)$
quantum protocol, but the randomized communication complexity of this problem
is $\Omega(n^{1/3})$. As shown in [KLL+15], this is also a lower bound on the
relaxed partition bound. Hence, as a consequence of Corollary 1, we obtain the
following result.

######  Proposition 5.

There exists a Bell inequality $B$ and a quantum distribution
$\overline{\mathbf{q}}_{VSP}\in{\cal Q}$ such that
$B\left(\overline{\mathbf{q}}_{VSP}\right)\in 2^{\Omega(n^{1/3})-O(\log n)}$
and for all $\mathbf{\ell}\in{\cal L}_{det}^{\bot},\>B(\mathbf{\ell})\leq 1$.

Note that the result of [KR11] (Lemma 4.3) is not of the form needed to apply
our Proposition 4. It is however possible to obtain an explicit Bell
functional $B$ following the proof of Lemma 5.1 in [KLL+15].

#### Disjointness

In the Disjointness problem, the players receive two sets and have to
determine whether they are disjoint or not. More formally, the Disjointness
predicate is defined over $\mathcal{X}=\mathcal{Y}=\mathcal{P}([n])$ by
$\mathrm{DISJ}_{n}(x,y)=1$ iff $x$ and $y$ are disjoint. It is also convenient
to see this predicate as defined over length $n$ inputs, where
$\mathrm{DISJ}_{n}(x,y)=1$ for $x,y\in\\{0,1\\}^{n}$ if and only if
$|\\{i\,:\,x_{i}=1=y_{i}\\}|=0$. The communication complexity for
$\mathrm{DISJ}_{n}$ is $\Omega(n)$ using a corruption bound [Raz92] and there
is a quantum protocol using $O(\sqrt{n})$ communication [AA05]. Combining
these results with ours, we obtain the following.

######  Proposition 6.

There is a quantum distribution $\overline{\mathbf{q}}_{\mathrm{DISJ}}\in{\cal
Q}$ and an explicit Bell inequality $B$ satisfying:
$B(\overline{\mathbf{q}}_{\mathrm{DISJ}})=2^{\Omega(n)-O(\sqrt{n})}$, and for
all $\mathbf{\ell}\in{\cal L}_{det}^{\bot},\>B(\mathbf{\ell})\leq 1$.

The proof is deferred to the Appendix (see Section B.1).

#### Tribes

Let $r\geq 2$, $n=(2r+1)^{2}$. Let
$\mathrm{TRIBES}_{n}:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$ be defined
as:

$\mathrm{TRIBES}_{n}(x,y):=\bigwedge\limits_{i=1}^{\sqrt{n}}\left(\bigvee\limits_{j=1}^{\sqrt{n}}(x_{(i-1)\sqrt{n}+j}\land
y_{(i-1)\sqrt{n}+j})\right).$

The Tribes function has an $\Omega(n)$ classical lower bound [HJ13] using the
smooth rectangle bound and a $O(\sqrt{n}(\log n)^{2})$ quantum protocol
[BCW98]. Combining these results with ours, we obtain the following.

######  Proposition 7.

coro:TribesBellIneq There is a quantum distribution
$\overline{\mathbf{q}}_{\mathrm{TRIBES}}\in{\cal Q}$ and an explicit Bell
inequality $B$ satisfying:
$B(\overline{\mathbf{q}}_{\mathrm{TRIBES}})=2^{\Omega(n)-O(\sqrt{n}(\log
n)^{2})}$, and for all $\mathbf{\ell}\in{\cal
L}_{det}^{\bot},\>B(\mathbf{\ell})\leq 1$.

The proof is deferred to the Appendix (see Section B.2).

#### Gap Orthogonality

The Gap Orthogonality ($\mathrm{ORT}$) problem was introduced by Sherstov as
an intermediate step to prove a lower bound for the Gap Hamming Distance
($\mathrm{GHD}$) problem [She12]. We derive an explicit Bell inequality for
$\mathrm{ORT}$ from Sherstov’s lower bound of $\Omega(n)$, shown in [KLL+15]
to be a relaxed partition bound. (Applying Corollary 1 also gives a (non-
explicit) violation for $\mathrm{GHD}$.) The quantum upper bound is
$O(\sqrt{n}\log n)$ by the general result of [BCW98].

In the Gap Orthogonality problem, the players receive vectors and need to
reliably tell whether they are nearly orthogonal or far from orthogonal. More
formally, we consider the input space $\\{-1,+1\\}^{n}$ instead of
$\\{0,1\\}^{n}$ (to stick to the usual notations for this problem), and we
denote $\langle\cdot,\cdot\rangle$ the scalar product on $\\{-1,+1\\}^{n}$.
Let $\mathrm{ORT}_{n}$ be the partial function over
$\\{-1,+1\\}^{n}\times\\{-1,+1\\}^{n}$ taking values in $\\{-1,+1\\}$, defined
as in [She12] by:

$\mathrm{ORT}_{n}(x,y)=\begin{cases}-1&\mbox{if $|\langle
x,y\rangle|\leq\sqrt{n}$}\\\ +1&\mbox{if $|\langle x,y\rangle|\geq
2\sqrt{n}$}.\end{cases}$

Combining the results mentioned above with ours, we obtain the following.

######  Proposition 8.

coro:ORTBellIneq There is a quantum distribution
$\overline{\mathbf{q}}_{\mathrm{ORT}}\in{\cal Q}$ and an explicit Bell
inequality $B$ satisfying:
$B(\overline{\mathbf{q}}_{\mathrm{ORT}})=2^{\Omega(n)-O(\sqrt{n}\log n)}$, and
for all $\mathbf{\ell}\in{\cal L}_{det}^{\bot},\>B(\mathbf{\ell})\leq 1$.

The proof is deferred to the Appendix (see Section B.3).

##  7 Discussion

We have given three main results. First, we showed that normalized Bell
inequalities can be modified to be bounded in absolute value on the larger set
of local distributions that can abort without significantly changing the value
of the violations achievable with nonsignaling distributions. Then, we showed
how to derive large inefficiency-resistant Bell violations from any gap
between the partition bound and the quantum communication complexity of some
given distribution $\mathbf{p}$. The distributions $\mathbf{q}$ achieving the
large violations are relatively simple (only $3$ outputs for boolean
distributions $\mathbf{p}$) and can be made resistant to uniform noise at the
expense of an increase in the number of outputs exponential in
$Q(\mathbf{p})$. Finally, we showed how to construct explicit Bell
inequalities when the separation between classical and quantum communication
complexity is proven via the corruption bound.

From a practical standpoint, the specific Bell violations we have studied are
probably not feasible to implement, because the parameters needed are still
impractical or the quantum states are infeasible to implement. However, our
results suggest that we could turn our attention to functions with small gaps
in communication complexity, in order to find practical Bell inequalities that
are robust against uniform noise and detector inefficiency.

To be more specific, let us consider an experimental setup with non-abort
probability $\eta$ per side, and $\varepsilon$ uniform noise. Suppose we have
a Boolean function with a lower bound of $c>3\log(1/\eta^{2})$ on classical
communication with $\varepsilon^{\prime}$ error, and an
$(\varepsilon^{\prime}{-}\varepsilon)$-correct quantum protocol, with
$\varepsilon^{\prime}>\varepsilon$, using $q=\log(1/\eta^{2})$ qubits. Our
construction gives an inefficiency-resistant Bell violation of
$2^{c-2q}>1/\eta^{2}$, which is robust against $\varepsilon$ uniform noise.
(The number of outcomes per side increases to $\frac{2}{\eta^{2}}$.) Factoring
in the inefficiency, the observed violation would still be
$\eta^{2}2^{c-2q}>1$.

Regarding upper bounds, since (the logarithm of) efficiency is a lower bound
on communication complexity, inefficiency-resistant Bell violations are
bounded above by the number of inputs per side. For dimension $d$ and number
of outcomes $K$, we can obtain the upper bound $\mathrm{\bf
eff}_{\epsilon}(\mathbf{q})\leq 2^{O((\frac{Kd}{\epsilon})^{2}\log^{2}(K))}$
for quantum distributions, by combining known bounds. Indeed, we know that
$R_{\epsilon}(\mathbf{p})\leq
O((\frac{K\nu(\mathbf{p})}{\epsilon})^{2}\log^{2}(K))$ for any non-signaling
$\mathbf{p}$ (see [DKLR11]). Combining this with the bounds $\mathrm{\bf
eff}_{\epsilon}(\mathbf{p})\leq 2^{R_{\epsilon}(\mathbf{p})}$ (Proposition 2)
on the one hand, and $\nu(\mathbf{q})\leq O(d)$ for any quantum distribution
$\mathbf{q}$ (see [JPPG+10b]) on the other hand, gives the desired upper
bound. We have shown that unbounded violations are possible for $K=3$ outputs
per side.

## Acknowledgements

We would like to acknowledge the following sources of funding for this work:
the European Union Seventh Framework Programme (FP7/2007-2013) under grant
agreement no. 600700 (QALGO), the Argentinian ANPCyT (PICT-2014-3711), the
Laboratoire International Associée INFINIS, the Belgian ARC project COPHYMA
and the Belgian Fonds de la Recherche Scientifique \- FNRS under grant no.
F.4515.16 (QUICTIME), and the French ANR Blanc grant RDAM ANR-12-BS02-005.

## References

  * [AA05] S. Aaronson and A. Ambainis.  Quantum search of spatial regions.  Theory of Computing, 1:47–79, 2005.
  * [ADGL02] A. Acín, T. Durt, N. Gisin, and J. I. Latorre.  Quantum nonlocality in two three-level systems.  Physical Review A, 65:052325, 2002.
  * [Ard92] M. Ardehali.  Bell inequalities with a magnitude of violation that grows exponentially with the number of particles.  Physical Review A, 46:5375–5378, 1992.
  * [BCG+16] H. Buhrman, Ł. Czekaj, A. Grudka, Mi. Horodecki, P. Horodecki, M. Markiewicz, F. Speelman, and S. Strelchuk.  Quantum communication complexity advantage implies violation of a Bell inequality.  Proceedings of the National Academy of Sciences, 113(12):3191–3196, 2016.
  * [BCSS11] N. Brunner, D. Cavalcanti, A. Salles, and P. Skrzypczyk.  Bound nonlocality and activation.  Physical Review Letters, 106:020402, 2011.
  * [BCT99] G. Brassard, R. Cleve, and A. Tapp.  Cost of exactly simulating quantum entanglement with classical communication.  Physical Review Letters, 83(9):1874, 1999.
  * [BCW98] H. Buhrman, R. Cleve, and A. Wigderson.  Quantum vs classical communication and computation.  In Proc. 30th STOC, pages 63–68, 1998.
  * [Bel64] J. S. Bell.  On the Einstein Podolsky Rosen paradox.  Physics, 1:195, 1964.
  * [BFS86] L. Babai, P. Frankl, and J. Simon.  Complexity classes in communication complexity theory.  In Proc. 27th FOCS, pages 337–347. IEEE, 1986.
  * [BPSW06] P. Beame, T. Pitassi, N. Segerlind, and A. Wigderson.  A strong direct product theorem for corruption and the multiparty communication complexity of disjointness.  Computational Complexity, 15(4):391–432, 2006.
  * [BRSdW12] H. Buhrman, O. Regev, G. Scarpa, and R. de Wolf.  Near-optimal and explicit Bell inequality violations.  Theory of Computing, 8(1):623–645, 2012.
  * [DKLR11] J. Degorre, M. Kaplan, S. Laplante, and J. Roland.  The communication complexity of non-signaling distributions.  Quantum information & computation, 11(7-8):649–676, 2011.
  * [FWW09] M. Forster, S. Winkler, and S. Wolf.  Distilling nonlocality.  Physical Review Letters, 102:120401, 2009.
  * [Gro53] A. Grothendieck.  Résumé de la théorie métrique des produits tensoriels topologiques.  Boletim da Sociedade de Matemática de São Paulo, 8:1–79, 1953\.
  * [GWAN12] R. Gallego, L. E. Würflinger, A. Acín, and M. Navascués.  Operational framework for nonlocality.  Physical Review Letters, 109:070401, 2012.
  * [HJ13] P. Harsha and R. Jain.  A Strong Direct Product Theorem for the Tribes Function via the Smooth-Rectangle Bound.  In Procs. 33rd FSTTCS, volume 24, pages 141–152, 2013.
  * [JK10] R. Jain and H. Klauck.  The partition bound for classical communication complexity and query complexity.  In Proc. 25th CCC, pages 247–258, 2010.
  * [JKS03] T. S. Jayram, R. Kumar, and D. Sivakumar.  Two applications of information complexity.  In Proc. 35th STOC, pages 673–682, 2003.
  * [JP11] M. Junge and C. Palazuelos.  Large violation of Bell inequalities with low entanglement.  Communications in Mathematical Physics, 306(3):695–746, 2011.
  * [JPPG+10a] M. Junge, C. Palazuelos, D. Pérez-García, I. Villanueva, and M. M. Wolf.  Operator space theory: A natural framework for Bell inequalities.  Physical Review Letters, 104:170405, 2010.
  * [JPPG+10b] M. Junge, C. Palazuelos, D. Pérez-García, I. Villanueva, and M. M. Wolf.  Unbounded violations of bipartite Bell inequalities via operator space theory.  Communications in Mathematical Physics, 300(3):715–739, 2010.
  * [KGZ+00] D. Kaszlikowski, P. Gnaciński, M. Żukowski, W. Miklaszewski, and A. Zeilinger.  Violations of local realism by two entangled $\mathit{N}$-dimensional systems are stronger than for two qubits.  Physical Review Letters, 85:4418–4421, 2000.
  * [KLL+15] I. Kerenidis, S. Laplante, V. Lerays, J. Roland, and D. Xiao.  Lower bounds on information complexity via zero-communication protocols and applications.  SIAM Journal on Computing, 44(5):1550–1572, 2015.
  * [KMSY14] G. Kol, S. Moran, A. Shpilka, and A. Yehudayoff.  Approximate nonnegative rank is equivalent to the smooth rectangle bound.  In Automata, Languages, and Programming, pages 701–712. Springer, 2014.
  * [KN97] E. Kushilevitz and N. Nisan.  Communication complexity.  Cambridge University Press, 1997.
  * [KR11] B. Klartag and O. Regev.  Quantum one-way communication can be exponentially stronger than classical communication.  In Proc. 43th STOC, pages 31–40, 2011.
  * [LLR12] S. Laplante, V. Lerays, and J. Roland.  Classical and quantum partition bound and detector inefficiency.  In Proc. 39th ICALP, pages 617–628, 2012.
  * [LPŻB04] W. Laskowski, T. Paterek, M. Żukowski, and Č Brukner.  Tight multipartite Bell’s inequalities involving many measurement settings.  Physical Review Letters, 93(20):200401, 2004.
  * [LS09] N. Linial and A. Shraibman.  Lower bounds in communication complexity based on factorization norms.  Random Structures & Algorithms, 34(3):368–394, 2009.
  * [Mas02] S. Massar.  Nonlocality, closing the detection loophole, and communication complexity.  Physical Review A, 65:032121, 2002.
  * [Mau92] T. Maudlin.  Bell’s inequality, information transmission, and prism models.  In PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, pages 404–417. JSTOR, 1992.
  * [Mer90] D. N. Mermin.  Extreme quantum entanglement in a superposition of macroscopically distinct states.  Physical Review Letters, 65(15):1838, 1990.
  * [MPRG02] S. Massar, S. Pironio, J. Roland, and B. Gisin.  Bell inequalities resistant to detector inefficiency.  Physical Review A, 66:052112, 2002.
  * [NLP06] K. Nagata, W. Laskowski, and T. Paterek.  Bell inequality with an arbitrary number of settings and its applications.  Physical Review A, 74(6):062109, 2006.
  * [PGWP+08] D. Pérez-García, M. M. Wolf, C. Palazuelos, I. Villanueva, and M. Junge.  Unbounded violation of tripartite Bell inequalities.  Communications in Mathematical Physics, 279(2):455–486, 2008.
  * [Pir03] S. Pironio.  Violations of Bell inequalities as lower bounds on the communication cost of nonlocal correlations.  Physical Review A, 68(6):062102, 2003.
  * [PY15] C. Palazuelos and Z. Yin.  Large bipartite Bell violations with dichotomic measurements.  Physical Review A, 92:052313, 2015.
  * [Raz92] A. A. Razborov.  On the distributional complexity of disjointness.  Theoretical Computer Science, 106(2):385 – 390, 1992.
  * [Raz99] R. Raz.  Exponential separation of quantum and classical communication complexity.  In Proc. 31th STOC, pages 358–367, 1999.
  * [Raz03] A. A. Razborov.  Quantum communication complexity of symmetric predicates.  Izvestiya: Mathematics, 67(1):145, 2003.
  * [She12] A. A. Sherstov.  The communication complexity of gap hamming distance.  Theory of Computing, 8(1):197–208, 2012.
  * [Ste00] M. Steiner.  Towards quantifying non-local information transfer: finite-bit non-locality.  Physics Letters A, 270(5):239–244, 2000.
  * [TB03] B. F. Toner and D. Bacon.  Communication cost of simulating Bell correlations.  Physical Review Letters, 91(18):187904, 2003.
  * [Tsi87] B. S. Tsirel’son.  Quantum analogues of the Bell inequalities. the case of two spatially separated domains.  Journal of Soviet Mathematics, 36(4):557–570, 1987.
  * [Yao79] A. C. C. Yao.  Some complexity questions related to distributed computing.  In Proc. 11th STOC, pages 209–213, 1979.
  * [Yao83] A. C. C. Yao.  Lower bounds by probabilistic arguments.  In Proc. 24th FOCS, pages 420–428. IEEE, 1983.
  * [Yao93] A. C. C. Yao.  Quantum circuit complexity.  In Proc. 34th FOCS, pages 352–361. IEEE, 1993.

##  Appendix A A general theorem for explicit Bell violations

In this section we prove a generalization of Proposition 4.

######  Theorem 6.

Let $f$ be a (possibly partial) Boolean function on
$\mathcal{X}\times\mathcal{Y}$, where
$\mathcal{X},\mathcal{Y}\subseteq\\{0,1\\}^{n}$. Fix $z\in\\{0,1\\}$. Let
$\mu$ be an input distribution, and $(U_{i})_{i\in I}$ (resp. $(V_{j})_{j\in
J}$) be a family of pairwise nonoverlapping subsets of $f^{-1}(\bar{z})$
(resp. of $f^{-1}(z)$). Assume that there exists $g:\mathbbm{N}\to(0,+\infty)$
such that, for any rectangle $R\subseteq\mathcal{X}\times\mathcal{Y}$

$\sum_{i\in I}u_{i}\mu(R\cap U_{i})\geq\sum_{j\in J}v_{j}\mu(R\cap
V_{j})-g(n).$ (6)

Let $B$ be the Bell functional given by the following coefficients: for all
$a,b,x,y\in\\{0,1\\}\times\\{0,1\\}\times\mathcal{X}\times\mathcal{Y}$,

$B_{a,b,x,y}=\begin{cases}1/2(-u_{i}g(n)^{-1}\mu(x,y))&\mbox{ if }(x,y)\in
U_{i}\text{ and }a\oplus b=z,\\\ 1/2(v_{j}g(n)^{-1}\mu(x,y))&\mbox{ if
}(x,y)\in V_{j}\text{ and }a\oplus b=z,\\\ 0&\mbox{otherwise.}\end{cases}$ (7)

Then, $B$ satisfies

$\displaystyle B(\mathbf{\ell})$ $\displaystyle\leq
1,\quad\forall\mathbf{\ell}\in{\cal L}_{det}^{\bot},$ (8) $\displaystyle
B(\mathbf{p}_{f})$ $\displaystyle=\frac{1}{2\cdot
g(n)}\sum_{j}{v_{j}\mu(V_{j})}$ (9)

and for any $\mathbf{p}^{\prime}\in{\cal P}$ such that
$|\mathbf{p}^{\prime}-\mathbf{p}_{f}|_{1}\leq\epsilon$ :

$B(\mathbf{p}^{\prime})\geq\frac{1}{2\cdot
g(n)}\left[\sum_{j}{v_{j}\mu(V_{j})}-\epsilon\left(\sum_{j}{|v_{j}|\mu(V_{j})}+\sum_{i}{|u_{i}|\mu(U_{i})}\right)\right].$
(10)

For the sake of completeness, we give the proof (which is very similar to the
one of Proposition 4).

###### Proof.

Let us first set $B_{z,x,y}=B_{a,b,x,y}$ for all $a\oplus b=z$. Let
$\mathbf{\ell}\in{\cal L}_{det}^{\bot}$. Then, we have:

$B(\mathbf{\ell})=\sum_{(x,y)\in R}B_{z,x,y}+\sum_{(x,y)\in S}B_{z,x,y}$

where $R$ and $S$ are the two rectangles where $\mathbf{\ell}$ outputs $z$.
Let us take a rectangle $R$. Then :

$\displaystyle\sum_{(x,y)\in R}B_{z,x,y}=$ $\displaystyle\frac{1}{2\cdot
g(n)}\left(\sum_{j}v_{j}\mu(V_{j}\cap R)-\sum_{i}u_{i}\mu(U_{i}\cap
R)\right)\leq 1/2$

with the inequality following from (6). This proves (8). In the last equation,
it was previously written $B_{1,xy}$ instead of $B_{z,x,y}$ but I think this
was a typo, please double-check.

Let us now compute $B(\mathbf{p}_{f})$. By linearity of $B$ and the definition
of its coefficients, we have:

$\displaystyle B(\mathbf{p}_{f})$
$\displaystyle=\sum_{a,b,x,y}B_{a,b,x,y}\mathbf{p}_{f}(a,b|x,y)$
$\displaystyle=\frac{1}{2}\sum_{(x,y)\in
f^{-1}(z),a,b}B_{a,b,x,y}\chi_{\\{z\\}}(a\oplus b)+\frac{1}{2}\sum_{(x,y)\in
f^{-1}(\bar{z}),a,b}B_{a,b,x,y}\chi_{\\{\bar{z}\\}}(a\oplus b)$
$\displaystyle=1/2\sum_{j}\sum_{(x,y)\in V_{j}}v_{j}g(n)^{-1}\mu(x,y)$
$\displaystyle=\frac{1}{2\cdot g(n)}\sum_{j}{v_{j}\mu(V_{j})}$

(for the third equality we used the fact that $B_{a,b,x,y}=0$ when $a\oplus
b=\bar{z}$). This proves (9).

Moreover, for any family of additive error terms $\Delta(a,b|x,y)\in[-1,1]$
such that

$\displaystyle\sum_{a,b}|\Delta(a,b|x,y)|$ $\displaystyle\leq\epsilon$
$\displaystyle\forall x,y\in\mathcal{X}\times\mathcal{Y},$

denoted collectively as $\boldsymbol{\Delta}$, we have

$\displaystyle|B(\boldsymbol{\Delta})|$
$\displaystyle=\left|\sum_{a,b,x,y}B_{a,b,x,y}\Delta(a,b|x,y)\right|$
$\displaystyle=\frac{1}{2\cdot g(n)}\left|\sum_{a,b\,:\,a\oplus
b=z}\left[\sum_{i}\sum_{(x,y)\in
U_{i}}(-u_{i})\mu(x,y)\Delta(a,b|x,y)\right.\right.+$
$\displaystyle\quad\quad\left.\left.\sum_{j}\sum_{(x,y)\in
V_{j}}v_{j}\mu(x,y)\Delta(a,b|x,y)\right]\right|$
$\displaystyle\leq\frac{1}{2\cdot g(n)}\left[\sum_{i}\sum_{(x,y)\in
U_{i}}|u_{i}|\mu(x,y)\left(\sum_{a,b}|\Delta(a,b|x,y)|\right)\right.+$
$\displaystyle\quad\quad\left.\sum_{j}\sum_{(x,y)\in
V_{j}}|v_{j}|\mu(x,y)\left(\sum_{a,b}|\Delta(a,b|x,y)|\right)\right]$
$\displaystyle\leq\frac{\epsilon}{2\cdot
g(n)}\left[\sum_{i}|u_{i}|\mu(U_{i})+\sum_{j}|v_{j}|\mu(V_{j})\right]$

From this calculation and (9), we obtain, for
$\mathbf{p}^{\prime}=\mathbf{p}_{f}+\boldsymbol{\Delta}$ :

$\displaystyle
B(\mathbf{p}^{\prime})=B(\mathbf{p}_{f})+B(\boldsymbol{\Delta})\geq\frac{1}{2\cdot
g(n)}\left[\sum_{j}{v_{j}\mu(V_{j})}-\epsilon\left(\sum_{j}{|v_{j}|\mu(V_{j})}+\sum_{i}{|u_{i}|\mu(U_{i})}\right)\right],$

which proves (10).

∎

Let us formulate a special case that will be useful in the examples. Here
there is just one subset in $f^{-1}(0)$ and one in $f^{-1}(1)$.

######  Corollary 2.

Let $f$ be a (possibly partial) Boolean function on
$\mathcal{X}\times\mathcal{Y}$, where
$\mathcal{X},\mathcal{Y}\subseteq\\{0,1\\}^{n}$. Given $\gamma\in(0,1)$ and
$g:\mathbbm{N}\to(0,1)$, suppose that there is a distribution $\mu$ on
$\mathcal{X}\times\mathcal{Y}$ such that: for any rectangle
$R\subseteq\mathcal{X}\times\mathcal{Y}$,

$\mu(R\cap f^{-1}(1))>\gamma\mu(R\cap f^{-1}(0))-g(n).$ (11)

Then $\mu$ satisfies (6) with $z=0$, $i=j=1$, $U_{1}=f^{-1}(1)$,
$V_{1}=f^{-1}(0)$, $u_{1}=1$, $v_{1}=\gamma$. Let $B$ be defined by (7), that
is: for all
$a,b,x,y\in\\{0,1\\}\times\\{0,1\\}\times\mathcal{X}\times\mathcal{Y}$,

$B_{a,b,x,y}=\begin{cases}-\frac{1}{2\cdot g(n)}\mu(x,y)&\mbox{ if
}f(x,y)=1\text{ and }a\oplus b=0\\\ \frac{\gamma}{2\cdot g(n)}\mu(x,y)&\mbox{
if }f(x,y)=0\text{ and }a\oplus b=0\\\ 0&\mbox{otherwise.}\end{cases}$

Then, $B$ satisfies

$\displaystyle B(\mathbf{\ell})$ $\displaystyle\leq
1,\quad\forall\mathbf{\ell}\in{\cal L}_{det}^{\bot},$ $\displaystyle
B(\mathbf{p}_{f})$ $\displaystyle=\frac{\gamma}{2\cdot g(n)}\mu(f^{-1}(0))$

and for any $\mathbf{p}^{\prime}\in{\cal P}$ such that
$|\mathbf{p}^{\prime}-\mathbf{p}_{f}|_{1}\leq\epsilon$ :

$\displaystyle B(\mathbf{p}^{\prime})\geq\frac{1}{2\cdot
g(n)}\Big{[}\gamma\mu(f^{-1}(0))-\epsilon\big{(}\gamma\mu(f^{-1}(0))+\mu(f^{-1}(1))\big{)}\Big{]}.$

##  Appendix B Explicit examples

###  B.1 Disjointness

In [Raz92], Razborov proved the following.

######  Lemma 2 ([Raz92]).

There exist two distributions $\mu_{0}$ and $\mu_{1}$ with ${\rm
supp}(\mu_{0})\subseteq\mathrm{DISJ}_{n}^{-1}(1)$ and ${\rm
supp}(\mu_{1})\subseteq\mathrm{DISJ}_{n}^{-1}(0)$, such that: for any
rectangle $R$ in the input space,

$\mu_{1}(R)\geq\Omega(\mu_{0}(R))-2^{\Omega(n)}.$

Following his proof, one can check that we actually have:

$\mu_{1}(R)\geq\frac{1}{45}\mu_{0}(R)-2^{-\epsilon n+\log_{2}(2/9)}.$

So, letting $\mu:=(\mu_{0}+\mu_{1})/2$,

$\mu(R\cap f^{-1}(0))\geq\frac{1}{45}\mu(R\cap f^{-1}(1))-2^{-\epsilon
n+\log_{2}(4/9)}.$ (12)

######  Remark 2.

Actually, ${\rm supp}(\mu_{1})=A_{1}:=\\{(x,y)\,:\,|x|=|y|=m,|x\cap
y|=1\\}\subseteq\mathrm{DISJ}_{n}^{-1}(0)$.

Note that by this construction, $\mu(f^{-1}(0))=\mu(f^{-1}(1))=1/2$. Combining
(12) with Corollary 2 (with $g(n)=2^{-\epsilon n+\log_{2}(4/9)}$), we obtain:

######  Corollary 3.

There exists a Bell inequality $B$ satisfying: $\forall\mathbf{\ell}\in{\cal
L}_{det}^{\bot},\>B(\mathbf{\ell})\leq 1$,

$B(\mathbf{p}_{\mathrm{DISJ}_{n}})=\frac{1}{90}2^{\epsilon n-\log_{2}(4/9)},$

and for any distribution $\mathbf{p}^{\prime}\in{\cal P}$ such that
$|\mathbf{p}^{\prime}-\mathbf{p}_{\mathrm{DISJ}_{n}}|_{1}\leq\varepsilon$,

$B(\mathbf{p}^{\prime})\geq 2^{\epsilon
n-\log_{2}(4/9)}\frac{1-46\epsilon}{90}.$

More precisely, Theorem 6 gives an explicit construction of such a Bell
inequality: we can define $B$ as:

$B_{a,b,x,y}=\begin{cases}-2^{\epsilon n-\log_{2}(4/9)}\mu(x,y)&\mbox{ if
}\mathrm{DISJ}_{n}(x,y)=0\text{ and }a\oplus b=1\\\ \frac{1}{45}2^{\epsilon
n-\log_{2}(4/9)}\mu(x,y)&\mbox{ if }\mathrm{DISJ}_{n}(x,y)=1\text{ and
}a\oplus b=1\\\ 0&\mbox{otherwise.}\end{cases}$

To obtain Proposition 6, we use Corollary 1 together with the fact that
$Q_{\varepsilon^{\prime}}(\mathrm{DISJ}_{n})=O(\sqrt{n})$.

###  B.2 Tribes

Let $n=(2r+1)^{2}$ with $r\geq 2$ and let
$\mathrm{TRIBES}_{n}:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$ be defined
as:

$\mathrm{TRIBES}_{n}(x,y):=\bigwedge\limits_{i=1}^{\sqrt{n}}\left(\bigvee\limits_{j=1}^{\sqrt{n}}(x_{(i-1)\sqrt{n}+j}\text{
and }y_{(i-1)\sqrt{n}+j})\right).$

In [HJ13][Sec. 3] the following is proven:

######  Lemma 3.

There exists a probability distribution $\mu$ on
$\\{0,1\\}^{n}\times\\{0,1\\}^{n}$ for which there exist numbers
$\alpha,\lambda,\gamma,\delta>0$ such that for sufficiently large $n$ and for
any rectangle $R$ in the input space:

$\gamma\mu(U_{1}\cap R)\geq\alpha\mu(V_{1}\cap R)-\lambda\mu(V_{2}\cap
R)-2^{-\delta n/2+1}$

where $U_{1}=\mathrm{TRIBES}_{n}^{-1}(0)$, $\\{V_{1},V_{2}\\}$ forms a
partition of $\mathrm{TRIBES}_{n}^{-1}(1)$ and $\mu(U_{1})=1-7\beta^{2}/16$,
$\mu(V_{1})=6\beta^{2}/16$, $\mu(V_{2})=\beta^{2}/16$ with
$\beta=\frac{r+2}{r+1}$.

In [HJ13], the coefficients are $\alpha=0.99,\lambda=\frac{16}{3(0.99)^{2}}$
and $\gamma=\frac{16}{(0.99)^{2}}$ (the authors say these values have not been
optimized).

Combining this result with our Theorem 6 (taking $z=1,i=1,j=2,$
$U_{1},V_{1},V_{2}$ as in Lemma 3, $u_{1}=\gamma,v_{1}=\alpha,v_{2}=-\lambda$,
and $g(n)=2^{-\delta n/2+1}$), we obtain:

######  Corollary 4.

There exists a Bell inequality satisfying: $\forall\mathbf{\ell}\in{\cal
L}_{det}^{\bot},\>B(\mathbf{\ell})\leq 1$,

$B(\mathbf{p}_{\mathrm{TRIBES}_{n}})=2^{\delta
n/2-1}\frac{\beta^{2}}{16}(6\alpha-\lambda),$

and for any distribution $\mathbf{p}^{\prime}\in{\cal P}$ such that
$|\mathbf{p}^{\prime}-\mathbf{p}_{\mathrm{TRIBES}_{n}}|_{1}\leq\varepsilon$,

$B(\mathbf{p}^{\prime})\geq 2^{\delta
n/2-1}\left[\frac{\beta^{2}}{16}(6\alpha-\lambda)-\epsilon(\gamma(1-7\beta^{2}/16)+\lambda\beta^{2}/16+\alpha
6\beta^{2}/16)\right].$

More precisely, Theorem 6 provides a Bell inequality $B$ yielding this bound,
defined as:

$B_{a,b,x,y}=\begin{cases}-\gamma 2^{\delta n/2-1}\mu(x,y)&\text{if }(x,y)\in
U_{1}\text{ and }a\oplus b=1\\\ \alpha 2^{\delta n/2-1}\mu(x,y)&\text{if
}(x,y)\in V_{1}\text{ and }a\oplus b=1\\\ -\lambda 2^{\delta
n/2-1}\mu(x,y)&\text{if }(x,y)\in V_{2}\text{ and }a\oplus b=1\\\
0&\mbox{otherwise.}\end{cases}$

To obtain Proposition LABEL:coro:TribesBellIneq, we use Corollary 1 together
with the fact that
$Q_{\varepsilon^{\prime}}(\mathrm{TRIBES}_{n})=O(\sqrt{n}(\log n)^{2})$.

###  B.3 Gap Orthogonality

Let $f_{n}$ be the partial functions over
$\\{-1,+1\\}^{n}\times\\{-1,+1\\}^{n}$ by
$f_{n}(x,y)=\mathrm{ORT}_{64n}(x^{64},y^{64})$, that is:

$f_{n}(x,y)=\begin{cases}-1&\hbox{if }|\langle x,y\rangle|\leq\sqrt{n}/8\\\
+1&\hbox{if }|\langle x,y\rangle|\geq\sqrt{n}/4.\end{cases}$

In [She12], Sherstov proves the following result.

######  Lemma 4 ([She12]).

Let $\delta>0$ be a sufficiently small constant and $\mu$ the uniform measure
over $\\{0,1\\}^{n}\times\\{0,1\\}^{n}$ . Then,
$\mu(f_{n}^{-1}(+1))=\Theta(1)$ and for all rectangle $R$ in
$\\{0,1\\}^{n}\times\\{0,1\\}^{n}$ such that $\mu(R)>2^{-\delta n}$,

$\mu(R\cap f_{n}^{-1}(+1))\geq\delta\mu(R\cap f_{n}^{-1}(-1)).$

This implies that if we put uniform weight on inputs of $\mathrm{ORT}_{64n}$
of the form $(x^{64},y^{64})$ and put 0 weight on the others, we get a
distribution $\mu^{\prime}$ satisfying the constraints of Corollary 2 for
$\mathrm{ORT}_{64n}$ together with $\gamma=\delta$ from Lemma 4 and
$g(64n)=2^{\delta n}$.

To get a distribution satisfying the constraints of Corollary 2 on inputs of
$\mathrm{ORT}_{64n+l}$ for all $0\leq l\leq 63$ we extend $\mu^{\prime}$ as
follows:

$\tilde{\mu}(xu,yv)=\begin{cases}\mu^{\prime}(x,y)&\hbox{if }u=+1^{l}\text{
and }v=-1^{l}\text{ and }\left(\langle x,y\rangle<-\sqrt{64n}\text{ or
}0\leq\langle x,y\rangle\leq\sqrt{64n}\right)\\\ \mu^{\prime}(x,y)&\hbox{if
}u=+1^{l}\text{ and }v=+1^{l}\text{ and }\left(-\sqrt{64n}\leq\langle
x,y\rangle<0\text{ or }\langle x,y\rangle>\sqrt{64n}\right)\\\
0&\hbox{otherwise}\end{cases}$

Using this distribution $\tilde{\mu}$ together with $\gamma=\delta$ from Lemma
4 and with $g(n)=2^{-\delta n}$ we obtain, from Corollary 2, a Bell inequality
violation for $\mathrm{ORT}_{64n+l}$ for all $0\leq l\leq 63$:

######  Corollary 5.

There exists a Bell inequality $B$ satisfying: $\forall\mathbf{\ell}\in{\cal
L}_{det}^{\bot},\>B(\mathbf{\ell})\leq 1$,

$B(\mathbf{p}_{\mathrm{ORT}_{64n+l}})=2^{\delta
n}\delta\tilde{\mu}(\mathrm{ORT}_{64n+l}^{-1}(-1)),$

and for any distribution $\mathbf{p}^{\prime}\in{\cal P}$ such that
$|\mathbf{p}^{\prime}-\mathbf{p}_{\mathrm{ORT}_{64n+l}}|_{1}\leq\varepsilon$,

$B(\mathbf{p}^{\prime})\geq 2^{\delta
n}\left(\delta\tilde{\mu}(\mathrm{ORT}_{64n+l}^{-1}(-1))-\epsilon\big{[}\delta\tilde{\mu}(\mathrm{ORT}_{64n+l}^{-1}(-1))+\tilde{\mu}(\mathrm{ORT}_{64n+l}^{-1}(+1))\big{]}\right).$

More precisely, Theorem 6 gives an explicit construction of such a Bell
inequality: we can define $B$ as:

$B_{a,b,x,y}=\begin{cases}-2^{\delta n}\tilde{\mu}(x,y)&\mbox{if
}(x,y)\in\mathrm{ORT}_{64n+l}^{-1}(+1)\text{ and }a\oplus b=-1\\\ \delta
2^{\delta n}\tilde{\mu}(x,y)&\mbox{if
}(x,y)\in\mathrm{ORT}_{64n+l}^{-1}(-1)\text{ and }a\oplus b=-1\\\
0&\mbox{otherwise.}\end{cases}$

To obtain Proposition LABEL:coro:ORTBellIneq, we use Corollary 1 together with
the fact that $Q_{\varepsilon^{\prime}}(\mathrm{ORT}_{n})=O(\sqrt{n}\log n)$.

##  Appendix C Equivalent formulations of the efficiency bounds

In [LLR12], the zero-error efficiency bound was defined in its primal and dual
forms as follows

######  Definition 5 ([LLR12]).

The efficiency bound of a distribution $\mathbf{p}\in{\cal P}$ is given by

$\displaystyle\mathrm{\bf eff}(\mathbf{p})=$
$\displaystyle\min_{\zeta,\mu_{\ell}\geq 0}$ $\displaystyle\frac{1}{\zeta}$
subject to $\displaystyle\sum_{\ell\in{\cal
L}_{det}^{\bot}}\mu_{\ell}\ell(a,b|x,y)=\zeta p(a,b|x,y)$
$\displaystyle\forall(a,b,x,y)\in\mathcal{A}{\times}\mathcal{B}{\times}\mathcal{X}{\times}\mathcal{Y}$
$\displaystyle\sum_{\ell\in{\cal L}_{det}^{\bot}}\mu_{\ell}=1$
$\displaystyle=$ $\displaystyle\max_{B}$ $\displaystyle B(\mathbf{p})$ subject
to $\displaystyle B(\mathbf{\ell})\leq 1$
$\displaystyle\forall\mathbf{\ell}\in{\cal L}_{det}^{\bot}$

The $\epsilon$-error efficiency bound was in turn defined as
$\min_{\mathbf{p}^{\prime}\in{\cal
P}|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon}\mathrm{\bf
eff}(\mathbf{p}^{\prime})$. In this appendix, we show that this is equivalent
to the definition used in the present article (Definition 2). In the original
definition, the Bell functional could depend on the particular
$\mathbf{p}^{\prime}$. We show that it is always possible to satisfy the
constraint with the same Bell functional for all $\mathbf{p}^{\prime}$ close
to $\mathbf{p}$.

In order to prove this, we will need the following notions.

######  Definition 6.

A distribution error $\boldsymbol{\Delta}$ is a family of additive error terms
$\Delta(a,b|x,y)\in[-1,1]$ for all
$(a,b,x,y)\in\mathcal{A}{\times}\mathcal{B}{\times}\mathcal{X}{\times}\mathcal{Y}$
such that

$\displaystyle\sum_{a,b}\Delta(a,b|x,y)$ $\displaystyle=0$
$\displaystyle\forall(x,y)\in\mathcal{X}\times\mathcal{Y}.$

For any $0\leq\epsilon\leq 1$, the set $\Delta_{\epsilon}$ is the set of
distribution errors $\boldsymbol{\Delta}$ such that

$\displaystyle\sum_{a,b}|\Delta(a,b|x,y)|$ $\displaystyle\leq\epsilon$
$\displaystyle\forall(x,y)\in\mathcal{X}\times\mathcal{Y}.$

This set is a polytope, so it admits a finite set of extremal points. We
denote this set by $\Delta_{\epsilon}^{ext}$.

We will use the following properties of $\Delta_{\varepsilon}$.

######  Fact 1.

For any distribution $\mathbf{p}\in{\cal P}$, we have

$\displaystyle\\{\mathbf{p}^{\prime}\in{\cal P}|\
|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon\\}\subseteq\\{\mathbf{p}+\boldsymbol{\Delta}|\
\boldsymbol{\Delta}\in\Delta_{\varepsilon}\\}$

The reason why the set on the right hand side might be larger is that
$\mathbf{p}+\boldsymbol{\Delta}$ might not be a valid distribution. In order
to ensure that this is the case, it is sufficient to impose that all obtained
purposed probabilities are nonnegative, leading to the following property.

######  Fact 2.

For any distribution $\mathbf{p}\in{\cal P}$, we have

$\displaystyle\\{\mathbf{p}^{\prime}\in{\cal P}|\
|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon\\}=\\{\mathbf{p}+\boldsymbol{\Delta}|\
\boldsymbol{\Delta}\in\Delta_{\varepsilon}\ \&\ p(a,b|x,y)+\Delta(a,b|x,y)\geq
0\ \forall a,b,x,y\\}$

We are now ready to prove the following theorem.

######  Theorem 7.

Let $\mathbf{p}\in{\cal P}$ be a distribution, $\mathrm{\bf
eff}_{\varepsilon}(\mathbf{p})$ be defined as in Definition 2 and $\mathrm{\bf
eff}(\mathbf{p})$ be defined as in Definition 5. Then, we have

$\displaystyle\mathrm{\bf
eff}_{\varepsilon}(\mathbf{p})=\min_{\mathbf{p}^{\prime}\in{\cal
P}:|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon}\mathrm{\bf
eff}(\mathbf{p}^{\prime}).$

###### Proof.

Let $\overline{\mathrm{\bf
eff}}_{\varepsilon}(\mathbf{p})=\min_{\mathbf{p}^{\prime}\in{\cal
P}:|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon}\mathrm{\bf
eff}(\mathbf{p}^{\prime})$. We first show that $\mathrm{\bf
eff}_{\varepsilon}(\mathbf{p})\leq\overline{\mathrm{\bf
eff}}_{\varepsilon}(\mathbf{p})$. Let $(B,\beta)$ be an optimal feasible point
for $\mathrm{\bf eff}_{\varepsilon}(\mathbf{p})$, so that

$\displaystyle\mathrm{\bf eff}_{\varepsilon}(\mathbf{p})$
$\displaystyle=\beta,$ $\displaystyle B(\mathbf{p}^{\prime})$
$\displaystyle\geq\beta$ $\displaystyle\forall$
$\displaystyle\mathbf{p}^{\prime}\>\rm{\>s.t.\>}|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon,$
$\displaystyle B(\mathbf{\ell})$ $\displaystyle\leq 1$ $\displaystyle\forall$
$\displaystyle\mathbf{\ell}\in{\cal L}_{det}^{\bot}.$

Therefore $(B,\beta)$ is also a feasible point for $\mathrm{\bf
eff}(\mathbf{p}^{\prime})$ for all $\mathbf{p}^{\prime}\in{\cal P}$ such that
$|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon$, so that $\mathrm{\bf
eff}(\mathbf{p}^{\prime})\geq\beta$ for all such $\mathbf{p}^{\prime}$, and
$\overline{\mathrm{\bf eff}}_{\varepsilon}(\mathbf{p})\geq\beta=\mathrm{\bf
eff}_{\varepsilon}(\mathbf{p})$.

It remains to show that $\mathrm{\bf
eff}_{\varepsilon}(\mathbf{p})\geq\overline{\mathrm{\bf
eff}}_{\varepsilon}(\mathbf{p})$. In order to do so, we first use the primal
form of $\mathrm{\bf eff}(\mathbf{p}^{\prime})$ in Definition 5 to express
$\overline{\mathrm{\bf eff}}_{\varepsilon}(\mathbf{p})$ as follows

$\displaystyle\overline{\mathrm{\bf eff}}_{\varepsilon}(\mathbf{p})=$
$\displaystyle\min_{\mathbf{p}^{\prime}\in{\cal
P}:|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon}$
$\displaystyle\mathrm{\bf eff}(\mathbf{p}^{\prime})$ $\displaystyle=$
$\displaystyle\min_{\zeta,\mu_{\ell}\geq 0,\mathbf{p}^{\prime}\in{\cal P}}$
$\displaystyle\frac{1}{\zeta}$ subject to $\displaystyle\sum_{\ell\in{\cal
L}_{det}^{\bot}}\mu_{\ell}\ell(a,b|x,y)=\zeta p^{\prime}(a,b|x,y)$
$\displaystyle\forall(a,b,x,y)\in\mathcal{A}{\times}\mathcal{B}{\times}\mathcal{X}{\times}\mathcal{Y}$
$\displaystyle\sum_{\ell\in{\cal
L}_{det}^{\bot}}\mu_{\ell}=1,\quad|\mathbf{p}^{\prime}-\mathbf{p}|_{1}\leq\epsilon$
$\displaystyle=$ $\displaystyle\min_{\zeta,\mu_{\ell}\geq
0,\boldsymbol{\Delta}\in\Delta_{\varepsilon}}$ $\displaystyle\frac{1}{\zeta}$
subject to $\displaystyle\sum_{\ell\in{\cal
L}_{det}^{\bot}}\mu_{\ell}\ell(a,b|x,y)=$
$\displaystyle\quad\quad\zeta[p(a,b|x,y)+\Delta(a,b|x,y)]$
$\displaystyle\forall(a,b,x,y)\in\mathcal{A}{\times}\mathcal{B}{\times}\mathcal{X}{\times}\mathcal{Y}$
$\displaystyle\sum_{\ell\in{\cal L}_{det}^{\bot}}\mu_{\ell}=1,$

where the last equality follows from Fact 2 and the fact that the first
condition of the program imposes that $p(a,b|x,y)+\Delta(a,b|x,y)$ is
nonnegative (since $\sum_{\ell}\mu_{\ell}\ell(a,b|x,y)$ is nonnegative). Since
$\Delta_{\varepsilon}$ is a polytope, $\overline{\mathrm{\bf
eff}}_{\varepsilon}(\mathbf{p})$ can be expressed as the following linear
program

$\displaystyle\overline{\mathrm{\bf eff}}_{\varepsilon}(\mathbf{p})=$
$\displaystyle\min_{\zeta,\mu_{\ell}\geq 0,\nu_{\Delta}\geq 0}$
$\displaystyle\frac{1}{\zeta}$ subject to $\displaystyle\sum_{\ell\in{\cal
L}_{det}^{\bot}}\mu_{\ell}\ell(a,b|x,y)=\zeta[p(a,b|x,y)+$
$\displaystyle\quad\sum_{\boldsymbol{\Delta}\in\Delta_{\varepsilon}^{ext}}\nu_{\Delta}\Delta(a,b|x,y)]$
$\displaystyle\forall(a,b,x,y)\in\mathcal{A}{\times}\mathcal{B}{\times}\mathcal{X}{\times}\mathcal{Y}$
$\displaystyle\sum_{\ell\in{\cal
L}_{det}^{\bot}}\mu_{\ell}=1,\quad\sum_{\boldsymbol{\Delta}\in\Delta_{\varepsilon}^{ext}}\nu_{\Delta}=1.$

Note that this can be written in standard LP form via the change of variables
$\mu_{\ell}=\zeta w_{\ell}$. By LP duality, we then obtain

$\displaystyle\overline{\mathrm{\bf eff}}_{\varepsilon}(\mathbf{p})=$
$\displaystyle\max_{B,\beta}$ $\displaystyle\beta$ subject to $\displaystyle
B(\mathbf{p}+\boldsymbol{\Delta})\geq\beta$
$\displaystyle\forall\boldsymbol{\Delta}$
$\displaystyle\in\Delta_{\varepsilon},$ $\displaystyle B(\mathbf{\ell})\leq 1$
$\displaystyle\forall\mathbf{\ell}$ $\displaystyle\in{\cal L}_{det}^{\bot}.$

Comparing this to the definition of $\mathrm{\bf
eff}_{\varepsilon}(\mathbf{p})$ (Definition 2) and together with Fact 1, we
therefore have $\overline{\mathrm{\bf
eff}}_{\varepsilon}(\mathbf{p})\leq\mathrm{\bf
eff}_{\varepsilon}(\mathbf{p})$.

∎