Randomness versus nonlocality in the Mermin-Bell
experiment with three parties
Erik Woodhead
1
, Boris Bourdoncle
1
, and Antonio Ac
´
ın
1,2
1
ICFO – Institut de Ci
`
encies Fot
`
oniques, The Barcelona Institute of Science and Technology, 08860 Castelldefels (Barcelona), Spain
2
ICREA – Instituci
´
o Catalana de Recerca i Estudis Avanc¸ats, Lluis Companys 23, 08010 Barcelona, Spain
6 August 2018
The detection of nonlocal correlations in a
Bell experiment implies almost by definition
some intrinsic randomness in the measurement
outcomes. For given correlations, or for a given
Bell violation, the amount of randomness pre-
dicted by quantum physics, quantified by the
guessing probability, can generally be bounded
numerically. However, currently only a few ex-
act analytic solutions are known for violations
of the bipartite Clauser-Horne-Shimony-Holt
Bell inequality. Here, we study the random-
ness in a Bell experiment where three parties
test the tripartite Mermin-Bell inequality. We
give tight upper bounds on the guessing prob-
abilities associated with one and two of the
parties’ measurement outcomes as a function
of the Mermin inequality violation. Finally, we
discuss the possibility of device-independent
secret sharing based on the Mermin inequal-
ity and argue that the idea seems unlikely to
work.
1 Introduction
Quantum theory predicts correlations incompatible
with any local deterministic model [1, 2]. The de-
tection of nonlocal correlations in a Bell experiment
thus implies at least some randomness in the meas-
urement outcomes, regardless of the exact physical
mechanism by which the correlations are produced,
provided that communication between the sites is pro-
hibited. Aside from fundamental interest, this obser-
vation is the basis for device-independent quantum
cryptography protocols, such as device-independent
quantum key distribution [3, 4] and randomness gen-
eration [5–7], in which the detection of nonlocal correl-
ations is a necessary condition in order to guarantee
the randomness of the generated key bits or random
numbers from the perspective of an adversary.
The simplest measure of randomness and typically
the easiest to bound is the guessing probability. This
is defined as the probability that an additional ob-
server, who may have partial access to the underlying
quantum state, can correctly anticipate a given meas-
Erik Woodhead: Erik.Woodhead@icfo.eu
urement outcome or given set of outcomes in advance.
Aside from its direct operational meaning, the guess-
ing probability is a useful quantity in the analysis of
device-independent cryptography protocols: security
proofs of device-independent protocols frequently de-
pend on a lower bound on the min-entropy (a func-
tion of the guessing probability) or the conditional
von Neumann entropy (which the min-entropy is a
lower bound for) [8–13]. In the practically most rel-
evant case where the measurements are made on a
quantum system, a numeric method for deriving an
upper bound on the guessing probability exists, based
on a hierarchy of relaxations of the optimisation prob-
lem to semidefinite programming problems [14–16],
for which reliable optimisation algorithms exist.
Since the determination of guessing-probability
bounds by numerical means is essentially a solved
problem, our interest here is in cases where it is pos-
sible to establish a tight analytic bound. Currently,
only a few tight bounds on the guessing probabil-
ity are known for the Clauser-Horne-Shimony-Holt
(CHSH) [17] inequality. In [6], it was shown that
an adversary (“Eve”)’s probability of guessing one of
one party’s (e.g., “Alice”’s) measurement outcomes is
bounded by
P
g
(A
1
|E) ≤
1
2
+
1
2
p
2 −S
2
/4 (1)
in terms of the CHSH expectation value
S = hA
1
B
1
i + hA
1
B
2
i + hA
2
B
1
i −hA
2
B
2
i (2)
for ±
1
-valued measurements A
x
and B
y
. More re-
cently, Kaniewski and Wehner [18] have derived the
tight upper bound
P
g
(A|B) ≤
1
2
+
1
4
S/2 +
p
2 −S
2
/4
(3)
on an average probability P
g
(
A|
B) =
P
(
A
1
=
B
3
) +
P
(
A
2
=
B
3
)
/
2
that the second party (“Bob”) is
able to guess Alice’s measurement outcome without
knowing which measurement Alice performed, assum-
ing they are chosen equiprobably.
Beyond the CHSH scenario, guessing-probability
bounds have been determined for violations of bipart-
ite and multipartite chained Bell inequalities [19, 20];
Accepted in Quantum 2018-08-02, click title to verify 1
arXiv:1804.09733v2 [quant-ph] 6 Aug 2018
however these are derived assuming only the no-
signalling constraints and they are not generally tight
assuming the scenario is restricted to correlations and
attacks allowed by quantum physics.
Here, we study the amount of randomness that can
be certified in a Bell experiment with three parties
showing a violation of Mermin’s tripartite Bell in-
equality [21]. We report tight bounds for the following
two cases:
• The guessing probability P
g
(
A
1
|
E)
associated
with the measurement outcome at one site, in
terms of two independent Mermin expectation
values.
• The guessing probability P
g
(
A
1
B
1
|
E)
associated
with measurement outcomes at two sites, for a
given violation of one Mermin inequality.
The results, the inequalities (15) and (18), can be
found in section 2, following a summary of the tripart-
ite scenario we consider. We give the proofs of these
in section 3 in the form of sum-of-squares decompos-
itions for families of Bell operators which correspond
to tangents of the bounds, together with quantum
strategies that show that they are attainable. We
found the sum-of-squares decompositions following an
approach similar to [22]. We have also included the
no-signalling bounds in appendix A. Finally, in sec-
tion 4 we discuss the prospect of device-independent
secret-sharing [23], mainly pointing out that the idea
seems unlikely to work due to the presence of untrus-
ted parties participating in the Bell test.
2 Scenario and results
Our results apply to the following adversarial Bell
scenario: three cooperating parties, Alice, Bob, and
Charlie, and an eavesdropper, Eve, share a quantum
state ρ
ABCE
on some Hilbert space H
A
⊗H
B
⊗H
C
⊗
H
E
. Alice, Bob, and Charlie may each perform one of
two measurements indexed x, y, z ∈ {
1
,
2
} on their
part of the state, which yield respective outcomes
a, b, c ∈ {
+
, −}. Eve performs a measurement yield-
ing an outcome e, intended to be correlated with one
or more of Alice’s, Bob’s, and Charlie’s outcomes.
Generally, we will assume, without loss of generality,
that Eve’s measurement has the same number of out-
comes as the number of possible different results that
the cooperating parties may obtain that she wishes to
distinguish between. The joint correlations are sum-
marised by a table of conditional probabilities
P (abce|xyz)
= Tr
Π
A
a|x
⊗ Π
B
b|y
⊗ Π
C
c|z
⊗ Π
E
e
ρ
ABCE
, (4)
where
Π
A
a|x
is the measurement operator associated
with the outcome a when Alice performs the measure-
ment x, and similarly for Bob’s, Charlie’s, and Eve’s
measurement operators
Π
B
b|y
,
Π
C
c|z
, and
Π
E
e
. The meas-
urements can be assumed to be projective, since we
do not assume any limit on the dimension of the un-
derlying Hilbert space. The state and measurements
are all treated as unknown except possibly to Eve.
Eve’s goal in this setting is to be able to guess one or
more of Alice’s, Bob’s and/or Charlie’s measurement
outcomes. The simplest measure of her ability to do
so, the guessing probability, is simply the probabil-
ity that Eve’s guess is correct. In the simplest case
where Eve aims to guess (say) Alice’s x
= 1
meas-
urement outcome, the (“local”) guessing probability
is the probability that Eve’s measurement outcome is
the same as Alice’s,
P
g
(A
1
|E) =
X
a
P
AE
(aa|x = 1) , (5)
where P
AE
(
ae|x
) =
P
bc
P
(
abce|xyz
)
. Other guess-
ing probabilities are straightforward variations of this.
For instance, the guessing probability associated with
Alice’s and Bob’s joint outcomes for measurements
x, y = 1 is
P
g
(A
1
B
1
|E) =
X
a,b
P
ABE
ab(ab)|x = y = 1
, (6)
where we label Eve’s (four) possible measurement out-
comes
(
++
)
,
(
+−
)
,
(
−+
)
, and
(
−−
)
. Alice, Bob, and
Charlie wish to certify that Eve’s ability to guess out-
comes is limited (in mathematical terms, that guess-
ing probabilities like (5) and (6) must be less than one)
using only the information available to them, encapsu-
lated by the marginal distribution P
ABC
(
abc|xyz
) =
P
e
P
(
abce|xyz
)
. A necessary but not necessarily suf-
ficient condition for this is that this marginal distri-
bution does not admit a local hidden variable model,
i.e., it does not admit a factorisation of the form
P
ABC
(abc|xyz)
=
X
λ
p
λ
P
A
(a|x; λ)P
B
(b|y; λ)P
C
(c|z; λ) , (7)
which is detected if the marginal distribution P
ABC
violates a Bell inequality.
Here, we study the amount of randomness that can
be certified in this tripartite scenario if a violation of
the Mermin-Bell inequality is observed. The Mermin
inequality [21] M ≤
2
holds for local-hidden-variable
models, where the Mermin correlator is
M = hA
1
B
1
C
1
i −hA
1
B
2
C
2
i
− hA
2
B
1
C
2
i −hA
2
B
2
C
1
i, (8)
and in turn hOi denotes the expectation value of the
observable quantity O. In the quantum case, hOi
=
Tr
[
Oρ
ABC
]
is given by the expectation value in the
underlying marginal state ρ
ABC
and the dichotomic
operators −1 ≤ A
x
, B
y
, C
z
≤ 1 are related to the
measurement operators by
A
x
= Π
A
+|x
− Π
A
−|x
, B
y
= Π
B
+|y
− Π
B
−|y
,
C
z
= Π
C
+|z
− Π
C
−|z
. (9)
Accepted in Quantum 2018-08-02, click title to verify 2
2 2.5 3 3.5 4
0
0.2
0.4
0.6
0.8
1
M
P
g
P
g
(A
1
|E)
P
g
(A
1
B
1
|E)
P
g
(A
2
B
2
C
2
|E)
Figure 1: Upp er bounds on the guessing probabilities
P
g
(
A
1
|
E),
P
g
(
A
1
B
1
|
E), and
P
g
(
A
2
B
2
C
2
|
E) for expectation
values 2
≤ M ≤
4 of the Mermin expression. The upper
bound for
P
g
(
A
2
B
2
C
2
|
E) was determined numerically at the
level 1 + A
2
+ AB + AC + BC of the NPA hierarchy.
The Mermin inequality is best known for its asso-
ciation with the Greenberger-Horne-Zeilinger (GHZ)
paradox [24]. The maximal quantum (and algebraic)
violation M
= 4
is attained by measuring A
1
=
B
1
=
C
1
=
σ
x
and A
2
=
B
2
=
C
2
=
σ
y
on the GHZ state
|
Ψ
i
= (
|
111
i
+
|
222
i
)
/
√
2. Violations greater than
2
√
2 require entanglement between all three sites [25].
The Mermin expression M can be obtained as the
real part of the quantity
(A
1
+ iA
2
)(B
1
+ iB
2
)(C
1
+ iC
2
)
. (10)
The imaginary part is also a Mermin expression,
M
0
= hA
1
B
1
C
2
i + hA
1
B
2
C
1
i
+ hA
2
B
2
C
1
i −hA
2
B
2
C
2
i, (11)
equivalent to (8) up to relabelling some of the inputs
and outputs. The sum M
+
=
M
+
M
0
is the correlator
appearing in Svetlichny’s inequality [26], which was
constructed to always require nonlocality (and thus
entanglement) between all three parties in order to
violate.
Some randomness bounds, quantified by guessing
probabilities involving one, two, and three parties, are
illustrated in figures 1 and 2 in terms of the Mermin
and Svetlichny expectation values. Of these, we were
able to find the analytic form of the curve for the local
guessing probability P
g
(
A
1
|
E)
in both cases and the
curve for P
g
(
A
1
B
1
|
E)
in terms of the Mermin expect-
ation value.
For given values of the Mermin or Svetlichny cor-
relators, the corresponding upper bounds on the local
guessing probability have the same functional form,
P
g
(A
1
|E) ≤ f (M) (12)
4 4.5 5 5.5
0
0.2
0.4
0.6
0.8
1
M
+
P
g
P
g
(A
1
|E)
P
g
(A
1
B
1
|E)
P
g
(A
1
B
1
C
1
|E)
Figure 2: Guessing probabilities for expectation values 4
≤
M
+
≤
4
√
2
of the Svetlichny expression
M
+
=
M
+
M
0
.
The upper bounds for
P
(
A
1
B
1
|
E) and
P
(
A
1
B
1
C
1
|
E) were
obtained numerically at levels 1 +
AB
+
AC
+
BC
and 1 +
A
2
+ AB + AC + BC of the NPA hierarchy.
and
P
g
(A
1
|E) ≤ f
M
+
/
√
2
, (13)
for the function
f(x) =
(
1
2
+
1
2
p
x(1 −x/4) if x ≥ 2 +
√
2
1 +
1
√
2
− x/4 if x ≤ 2 +
√
2
(14)
in the range
2
√
2 ≤ x ≤
4
. Both are implied by the
tight bound
P
g
(A
1
|E) ≤ f
p
M
2
+ M
02
, (15)
in which the two Mermin expectation values M and
M
0
appear as independent parameters. Note that
since f is a decreasing function in its argument, (15)
is equivalent to stating that
P
g
(A
1
|E) ≤ f
cos(ϕ)M + sin(ϕ)M
0
(16)
holds for all ϕ. The result (15) certifies some intrinsic
randomness for values of M and M
0
satisfying
2
√
2 <
p
M
2
+ M
02
≤ 4 . (17)
For M alone and the Svetlichny combination M
+
=
M
+
M
0
, randomness for one measurement outcome is
certified for M >
2
√
2 and M
+
>
4
. This is what one
would expect, since these are precisely the ranges that
require entanglement between all three parties to at-
tain. At the boundary
√
M
2
+ M
02
= 4
, (15) reduces
to P
g
(
A
1
|
E)
≤
1
/
2
, certifying that the measurement
outcome must be uniformly random.
In the case that the eavesdropper aims to jointly
guess two parties’ measurement outcomes, the guess-
ing probability respects the tight bound
P
g
(A
1
B
1
|E)
≤
(
3
4
−
M
8
+
√
3
q
M
8
1
2
−
M
8
if M ≥ 3
3
2
−
M
4
if M ≤ 3
(18)
Accepted in Quantum 2018-08-02, click title to verify 3
in the range
2
≤ M ≤
4
. In this case, we detect
some randomness as soon as the local bound M ≤
2
is violated. The maximum possible violation M
=
4
implies P
g
(
A
1
B
1
|
E)
≤
1
/
4
, corresponding to the
maximum possible randomness.
Beyond this we did not find any new tight
bounds for violations of the Mermin inequality. The
upper bound for the global guessing probability
P
(
A
1
B
1
C
1
|
E)
in terms of M is exactly the same as
(18), while the upper bound for P
(
A
2
B
2
C
2
|
E)
(which
should attain
1
/
8
if the Mermin inequality is maxim-
ally violated [27, 28]) appears to be the solution to
the maximisation problem
maximise
1
8
1 + 24 cos
3
2
θ
2
αβ
+ 2 cos(3θ
2
)α
2
+ 30β
2
subject to M =
2 cos(3θ
1
) −6 cos(θ
1
+ 2θ
2
)
α
2
−12 cos(θ
1
− θ
2
)β
2
and 2α
2
+ 6β
2
= 1 (19)
over α, β, θ
1
, θ
2
∈ R, which we were unable to signi-
ficantly simplify further (let alone prove). Eq. (18)
also does not generalise in terms of M and M
0
in the
way that the local-guessing-probability bound does.
The upper bound for P
g
(
A
1
B
1
|
E)
in terms of the
Svetlichny combination (illustrated in figure 2) for in-
stance has a different form than (18). This is expected
since the local-guessing-probability bound is already
less than 1 for any violation of the local bound, and
we were not much more successful in attempting to
identify it analytically than we were for P
g
(
A
2
B
2
C
2
|
E)
in terms of M.
For simplicity we have stated the results (15)
and (18) for the guessing probabilities P
g
(
A
1
|
E)
and
P
g
(
A
1
B
1
|
E)
; however symmetries of the Mermin cor-
relator(s) imply that the bounds are the same regard-
less of what measurements are considered. For the
global guessing probabilities there are two inequival-
ent cases, P
g
(
A
1
B
1
C
1
|
E)
and P
g
(
A
2
B
2
C
2
|
E)
, in terms
of M.
In figures 1 and 2 we have also included upper
bounds on guessing probabilities for which we do not
have an exact analytic expression. We derived these
numerically by solving the semidefinite programming
relaxations at the levels of the Navascu´es-Pironio-
Ac´ın (NPA) hierarchy indicated in the figure captions.
We used the arbitrary-precision solver SDPA-GMP
[29, 30] for this purpose. We have made the code
we used to generate the relaxations available online
[31].
3 Tangent Bell expressions
We have asserted that the local and two-party guess-
ing probabilities respect the upper bounds (15) and
(18) and that the bounds are tight. We prove these
assertions in this section.
3.1 General idea illustrated with CHSH
Proving the main results (15) and (18) is equivalent
to proving families of linear inequalities correspond-
ing to tangents of the curves. We illustrate the ap-
proach using CHSH as an example, for which this has
already been done [10, 32]. It was shown in [32] that
the quantum expectation value of a modified CHSH
expression respects the tight upper bound
βhA
1
i + S ≤ 2
√
2
p
1 + β
2
/4 (20)
in the parameter range
0
≤ β ≤
2
, where S
=
hA
1
B
1
+
A
1
B
2
+
A
2
B
1
−A
2
B
2
i is the CHSH expectation value.
Eq. (20) can be rewritten as an upper bound
hA
1
i ≤
1
β
2
√
2
p
1 + β
2
/4 −S
(21)
for hA
1
i. Assuming that S ≥
2
, minimising the right-
hand side over β produces the tightest possible bound
hA
1
i ≤
p
2 −S
2
/4 . (22)
This bound has two key characteristics. First, since
the CHSH expression remains unchanged under (for
example) the replacements A
x
7→ −A
x
and B
y
7→
−B
y
, the same upper bound holds for −hA
1
i as well as
hA
1
i. Second, the right-hand side is by construction
concave in S, since it is derived by minimising over
a family of hyperplanes. Using these properties and
that P
A
(
+|x
) = (1 +
hA
x
i
)
/
2
and P
A
(
−|x
) = (1
−
hA
x
i)/2, the result is quickly obtained:
P
g
(A
1
|E) =
X
a
P
AE
(aa|x = 1)
=
X
a
P
E
(a)P
A|E
(a|x = 1, e = a)
≤
X
a
P
E
(a)
1
2
1 +
q
2 −S
2
|a
/4
≤
1
2
+
1
2
p
2 −S
2
/4 , (23)
where S
|a
in the third line is the CHSH expectation
value conditioned on Eve obtaining the outcome e
=
a.
In passing, we mention that the bound (3) for
P
g
(
A|
B) =
1
2
+
1
4
h
(
A
1
+
A
2
)
B
3
i can similarly be de-
rived from the inequality
αh(A
1
+ A
2
)B
3
i + S ≤ 2
p
1 + (1 + α)
2
(24)
for α ≥
0
. The inequality (24) itself is implied by the
tight quantum bound derived for the I
β
α
expression in
[32], since there is clearly no advantage for the oper-
ator B
3
to be different from B
1
in order to maximise
the left-hand side.
The same general approach works for the main res-
ults of section 2. The Mermin expectation values M
and M
0
are both symmetric under the transforma-
tions A
x
, C
z
7→ −A
x
, −C
z
and B
y
, C
z
7→ −B
y
, −C
z
.
Accepted in Quantum 2018-08-02, click title to verify 4
These can be used to map the probability P
A
(
+|
1)
to P
A
(
−|
1)
and the probability P
AB
(
++|
11)
to any
of the probabilities P
AB
(
+−|
11)
, P
AB
(
−+|
11)
, and
P
AB
(
−−|
11)
, and vice versa. Consequently, in order
to derive upper bounds on P
g
(
A
1
|
E)
and P
g
(
A
1
B
1
|
E)
,
we need only derive concave upper bounds for
P
A
(+|1) =
1
2
1 + hA
1
i
(25)
and
P
AB
(++|11) =
1
4
1 + hA
1
i + hB
1
i + hA
1
B
1
i
. (26)
3.2 Local guessing probability linearisation
Similarly to the derivation for CHSH summarised
above, the local-guessing-probability bound (15) for
√
M
2
+ M
02
≥ 2
√
2 is implied by the linearisation
cos(θ)hA
1
i +
1
2
sin(θ)
cos(ϕ)M + sin(ϕ)M
0
≤ 1 + sin(θ) , (27)
which holds for θ in the range π/
4
≤ θ ≤ π/
2
and for
all ϕ. We can see that (27) is tight by observing that
is attained if (for example) the measurements
A
1
= B
1
= σ
x
, A
2
= B
2
= σ
y
(28)
and
C
1
= cos(ϕ)σ
x
− sin(ϕ)σ
y
, (29)
C
2
= sin(ϕ)σ
x
+ cos(ϕ)σ
y
(30)
are performed on the state
|Ψi = cos(
θ
2
)
1
√
2
|+++i + |+−−i
+ sin(
θ
2
)
1
√
2
|−+−i + |−−+i
, (31)
where |±i
= (
|
1
i ±|
2
i
)
/
√
2 are the eigenstates of the
σ
x
operator and θ is the same angle as in (27). With
this state and measurements, one can readily verify
that hA
1
i
=
cos
(
θ
)
and
1
2
cos
(
ϕ
)
M
+
sin
(
ϕ
)
M
0
=
1 + sin(θ), which attain (27).
The linearisation (27) ceases to apply for θ < π/
4
.
It is violated, for instance, by measuring
A
1
= 1 , A
2
= −1 , (32)
B
1
= σ
x
, B
2
= σ
y
, (33)
and
C
1
= cos(ϕ)σ
x
− sin(ϕ)σ
y
, (34)
C
2
= sin(ϕ)σ
x
+ cos(ϕ)σ
y
(35)
on a state |
Ψ
0
i
=
|χi
A
|ψi
BC
, where |χi is any state
on Alice’s subsystem and Bob and Charlie share the
state
|ψi =
1
√
2
e
−i
π
8
|11i + e
i
π
8
|22i
. (36)
This strategy yields hA
1
i = 1 and
cos(ϕ)M + sin(ϕ)M
0
= 2
√
2 , (37)
and the right-hand side of (27) attains cos
(
θ
) +
√
2 sin
(
θ
)
. Importantly, for θ
=
π/
4
, we see that (27)
can be attained with a strategy for which Alice’s A
1
measurement produces a deterministic outcome.
We prove the linearisation (27) by showing that the
operator
T =
1 + sin(θ)
1 −cos(θ)A
1
−
1
2
sin(θ)
cos(ϕ)
ˆ
M + sin(ϕ)
ˆ
M
0
(38)
is positive semidefinite, where
ˆ
M = A
1
B
1
C
1
− A
1
B
2
C
2
− A
2
B
1
C
2
− A
2
B
2
C
1
, (39)
ˆ
M
0
= A
1
B
1
C
2
+ A
1
B
2
C
1
+ A
2
B
1
C
1
− A
2
B
2
C
2
. (40)
A sum-of-squares decomposition that shows this is
T = |P
+
1
|
2
+ |P
+
2
|
2
+ |P
−
1
|
2
+ |P
−
2
|
2
(41)
where |O|
2
= O
†
O,
P
+
1
= αR
+
1
+ βR
+
2
− βR
+
3
− αR
+
4
, (42)
P
+
2
= γR
+
1
− δR
+
3
, (43)
P
−
1
= βR
−
1
+ αR
−
2
+ αR
−
3
+ βR
−
4
, (44)
P
−
2
= δR
−
1
+ γR
−
3
, (45)
R
±
i
are the operators
R
+
1
= cos(ϕ)(B
1
+ C
1
) + sin(ϕ)(B
2
+ C
2
)
− A
1
(B
1
+ C
1
) , (46)
R
+
2
= cos(θ)(B
2
+ C
2
) −A
1
(B
2
+ C
2
)
+ sin(θ)A
2
(B
1
+ C
1
) , (47)
R
+
3
= sin(ϕ)(B
1
+ C
1
) −cos(ϕ)(B
2
+ C
2
)
− A
1
(B
2
+ C
2
) , (48)
R
+
4
= cos(θ)(B
1
+ C
1
) −A
1
(B
1
+ C
1
)
− sin(θ)A
2
(B
2
+ C
2
) , (49)
R
−
1
= cos(ϕ)(B
1
− C
1
) + sin(ϕ)(B
2
− C
2
)
+ A
1
(B
1
− C
1
) , (50)
R
−
2
= cos(θ)(B
2
− C
2
) −A
1
(B
2
− C
2
)
+ sin(θ)A
2
(B
1
− C
1
) , (51)
R
−
3
= sin(ϕ)(B
1
− C
1
) −cos(ϕ)(B
2
− C
2
)
+ A
1
(B
2
− C
2
) , (52)
R
−
4
= cos(θ)(B
1
− C
1
) −A
1
(B
1
− C
1
)
− sin(θ)A
2
(B
2
− C
2
) , (53)
Accepted in Quantum 2018-08-02, click title to verify 5
and the coefficients α, β, γ, δ are related to θ and ϕ
by
α =
sin
ϕ
2
4 cos
θ
2
, (54)
β =
cos
ϕ
2
4 cos
θ
2
, (55)
γ =
1
4
h
sin(θ) + cos(θ) cos(ϕ)
− sin(ϕ)
p
−cos(2θ)
i
1/2
, (56)
δ =
s
4
h
sin(θ) − cos(θ) cos(ϕ)
+ sin(ϕ)
p
−cos(2θ)
i
1/2
, (57)
where s = ±1 in the last line is the sign
s = −sign
cos(θ) sin(ϕ) +cos(ϕ)
p
−cos(2θ)
. (58)
The R
±
i
s have been grouped by whether or not they
change sign under the replacements
τ :
B
1
7→ C
1
B
2
7→ C
2
C
1
7→ B
1
C
2
7→ B
2
, (59)
which is a symmetry of (38).
The parameters γ and δ are chosen to solve the
simultaneous equations
8γ
2
+ 8δ
2
− sin(θ) = 0 , (60)
8 cos(ϕ)γ
2
− 16 sin(ϕ)γδ
− 8 cos(ϕ)δ
2
− cos(θ) = 0 , (61)
which we encountered when searching for a decompos-
ition. They are solvable for real-valued γ and δ (and
(56) and (57) are solutions) if sin
(
θ
)
is positive and
greater than |cos
(
θ
)
|, which is the case for the range
π/
4
≤ θ ≤ π/
2
of values of θ for which we need to
show that the linearisation (27) holds. It is not diffi-
cult to check in this case that
sin(θ) − |cos(θ) cos(ϕ)| ≥ |sin(ϕ)|
p
−cos(2θ) (62)
holds for arbitrary ϕ, verifying that the expressions
under the outer square roots in (56) and (57) are non-
negative. The operators P
±
i
are then all Hermitian
and |P
±
i
|
2
can be simplified to P
±2
i
.
The Python script pa1 mermin sos.py supplied
with this article uses the SymPy library [33] to verify
symbolically that the sum-of-squares decomposition
(41) expands to (38), under the assumption that the
operators P
±
i
are Hermitian and that the conditions
(60) and (61) for γ and δ can be satisfied.
3.3
Two-party guessing probability linearisation
For M ≥
2
, the guessing-probability bound (18) fol-
lows from the linearisation
βhA
1
+ B
1
+ A
1
B
1
i + αM ≤ γ , (63)
where
β = (λ − µ)(λ + 3µ) , (64)
α = 4λµ , (65)
γ = (3λ + µ)(λ + 3µ) , (66)
which holds for parameters λ and µ satisfying
3µ ≥ λ ≥ µ . (67)
In the extreme cases λ
= 3
µ and λ
=
µ, (63) reduces
respectively to
4P
AB
(++|11) + M ≤ 6 , (68)
which corresponds to the linear part of (18), and to
the bound M ≤
4
for the Mermin correlator itself,
where the gradient of (18) is infinite. (Eq. (63) also
appears to hold for
0
≤ λ < µ; however (63) then
translates to a lower bound on P
AB
(
++|
11)
, which
we did not interest ourselves in.) Eq. (63) is attained
with equality by measuring A
1
=
B
1
=
C
1
=
σ
x
and
A
2
= B
2
= C
2
= σ
y
on the state
|Ψi = λ|+++i+µ
|+−−i+ |−+−i+ |−−+i
, (69)
with λ and µ scaled to satisfy λ
2
+3
µ
2
= 1
so that the
state is properly normalised. In this case P
AB
(
++|
11)
and M work out to
P
AB
(++|11) = λ
2
, (70)
and
M = (λ + 3µ)
2
; (71)
these are related by
P
AB
(++|11) =
3
4
−
M
8
+
√
3
r
M
8
1
2
−
M
8
, (72)
corresponding to the nonlinear part of (18). The con-
dition
3
µ ≥ λ ≥ µ and normalisation λ
2
+3
µ
2
= 1
also
translate to precisely the ranges
1
/
4
≤ P
(
++|
11)
≤
3
/
4
and
3
≤ M ≤
4
to which the nonlinear part of
(18) applies.
With the same state (69) and optimal measure-
ments, we also have P
ABC
(
+++|
111) =
λ
2
=
P
AB
(
++|
11)
. This implies that the upper bound
(18) for P
g
(
A
1
B
1
|
E)
is also the tight upper bound for
P
g
(A
1
B
1
C
1
|E).
The linearisation (63) is equivalent to the operator
inequality
T = γ1 − β(A
1
+ B
1
+ A
1
B
1
) −α
ˆ
M ≥ 0 . (73)
Accepted in Quantum 2018-08-02, click title to verify 6
This is shown by the sum-of-squares decomposition
T =
P
++
1
2
+
P
++
2
2
+
P
++
3
2
+
P
++
4
2
+
P
+−
2
2
+
P
−+
1
2
+
P
−+
2
2
+
P
−−
1
2
+
P
−−
3
2
, (74)
where
P
++
1
=
√
λ + µ
4
√
µ
(3µ −λ)R
++
1
, (75)
P
++
2
=
1
4
√
µ
p
(λ
2
− µ
2
)(3µ −λ)
×
R
++
1
+ 2R
++
2
, (76)
P
++
3
=
√
3µ −λ
2
√
µ(λ + µ)
R
++
3
, (77)
P
++
4
=
1
2
√
λµ
λ −µ
λ + µ
R
++
3
+ R
++
4
, (78)
P
+−
2
=
1
2
p
λ(λ −µ)R
+−
2
, (79)
P
−+
1
=
1
2
√
λ
√
2µ
p
(λ −µ)
2
+ 4µ
2
R
−+
1
, (80)
P
−+
2
=
1
2
s
λ(3µ −λ)
µ(λ + µ)
R
−+
2
, (81)
P
−−
1
=
r
λ(λ −µ)
2
R
−−
1
, (82)
P
−−
3
=
p
λ(λ −µ)
2(λ + µ)
R
−−
2
+ R
−−
3
, (83)
and
R
++
1
= (A
1
+ B
1
)(1 −C
1
) , (84)
R
++
2
= C
1
− A
1
B
1
, (85)
R
++
3
= (λ −µ)
2
1 + (λ + µ)
2
C
1
− (λ
2
− µ
2
)(A
1
+ B
1
) + 4λµ A
2
B
2
, (86)
R
++
4
= (λ −µ)
2
1 + µ(λ + µ)(A
1
+ B
1
)
− (λ
2
− µ
2
)C
1
+ 2λµ (A
2
+ B
2
)C
2
, (87)
R
+−
1
= (λ −µ)
2
(A
2
+ B
2
) −2(λ − µ)
2
C
2
− (λ
2
− µ
2
)(A
2
+ B
2
)C
1
+ (λ
2
− µ
2
)(A
1
+ B
1
)C
2
, (88)
R
+−
2
= (A
2
+ B
2
) −2C
2
− (A
1
B
2
+ A
2
B
1
)
+ (A
1
+ B
1
)C
2
, (89)
R
−+
1
= (A
1
− B
1
)(1 + C
1
) , (90)
R
−+
2
= (λ + µ)(A
1
− B
1
) −2µ(A
2
− B
2
)C
2
, (91)
R
−−
1
= (A
2
− B
2
)(1 −C
1
) , (92)
R
−−
2
= 2µ(A
2
− B
2
) −(λ + µ)(A
1
− B
1
)C
2
, (93)
R
−−
3
= (λ −µ)(A
2
− B
2
)
+ (λ + µ)(A
1
B
2
− A
2
B
1
) . (94)
The R
±±
0
i
s are grouped according to whether they
change sign under the replacements
τ
1
:
A
1
7→ B
1
A
2
7→ B
2
B
1
7→ A
1
B
2
7→ A
2
, τ
2
:
A
2
7→ −A
2
B
2
7→ −B
2
C
2
7→ −C
2
. (95)
Note that we have included an operator, R
+−
1
, among
the list of R
±±
0
i
s that we attempted to construct a
sum-of-squares decomposition out of, although ulti-
mately we did not use it.
The Python script pa1b1 mermin sos.py checks
that the sum-of-squares decomposition (74) expands
to (73).
3.4 Method
We initially determined the upper bounds on the
guessing probabilities P
g
(
A
1
|
E)
and P
g
(
A
1
B
1
|
E)
nu-
merically in terms of the Mermin expectation value
M. It was quickly apparent that the nonlinear parts
of the bounds were consistently being attained with
anticommuting measurements. From there it was not
difficult to guess the optimal states and see that the
numeric bounds seemed to coincide with the (at this
point, conjectured) analytic forms (15) and (18) given
in section 2. Experimenting a little, we found that the
bounds seemed to be attained respectively at the NPA
hierarchy levels
1 +
AB
+
AC and
1 +
AB
+
AC
+
BC;
this told us that we should be able to find sum-of-
squares decompositions out of the operators at these
levels for the tangents of the bounds.
We searched for sum-of-squares decompositions fol-
lowing a method similar to [22]. The idea is essen-
tially to write the general form of a candidate sum-of-
squares decomposition in terms of unknown paramet-
ers, assert that it should expand to the operator we
want to show is positive semidefinite, and then find
parameters for which the assertion becomes true.
Using the tangents of the local-guessing-probability
bound as an example, we were searching for a solution
to the problem
T −
X
i
P
s 2
i
= 0 , (96)
where T is the target expansion (38), for operators
P
±
i
of the form
P
s
i
=
X
j
c
s
ij
R
s
j
, (97)
where the c
s
ij
s are unknown real-valued coefficients
and the R
s
j
s form a basis of the space of linear com-
binations of the operators at level
1 +
AB
+
AC with
the property
R
s
j
|Ψi = 0 (98)
for the (conjectured) optimal measurements A
x
, B
y
,
C
z
and state |
Ψ
i described in subsection 3.2. Such a
basis of R
s
j
s is given by Eqs. (46)–(53).
Accepted in Quantum 2018-08-02, click title to verify 7
We have applied some simplifications to the prob-
lem above, following [22]. In particular, writing
X
i
P
†
i
P
i
=
X
jkrs
M
rs
jk
R
r †
j
R
s
k
(99)
with
M
rs
jk
=
X
i
c
r ∗
j
c
s
k
(100)
for the potentially more general problem with
P
i
=
X
js
c
s
ij
R
s
j
, (101)
we have used that it is not restrictive to assume that
the coefficients c
s
ij
are real-valued and that the sym-
metry of the target operator (38) under the transform-
ation τ (59) can be used to block diagonalise the mat-
rix of elements M
rs
jk
.
We also applied another simplification: one can
choose to set c
s
ij
= 0
for (for instance) i < j or i > j.
This corresponds to choosing a Cholesky factorisation
of the matrix of elements M
s
jk
=
P
i
c
s
ij
c
s
ik
.
Expanding the candidate sum-of-squares decom-
position on the left-hand side of (96) and requiring
operator-by-operator that the left-hand side is zero
translates to imposing a number of quadratic equality
constraints on the coefficients c
s
ij
. We used a Python
module divars.py, which we have included with this
article, together with SymPy, to automate this pro-
cedure and help simplify the resulting constraints. We
then repeatedly searched numerically for solutions to
the constraints, guessing and gradually introducing
constraints on the coefficients (e.g., trying c
s
ij
= 0
for
some coefficient or imposing that two coefficients are
equal to each other) until the numeric search seemed
to consistently return the same solution. Solving
the remaining constraints by hand got us the sum-
of-squares decomposition given in subsection 3.2.
4 Attacks against device-independent
secret sharing
Aside from fundamental interest, a second more prac-
tical motivation to conduct the previous analysis was
to construct a device-independent secret-sharing pro-
tocol based on the Mermin inequality. However, we
found obstacles to this idea which we describe in the
following section.
4.1 Overview
Secret sharing is a cryptographic task in which a
secret (e.g., a cryptographic key) is distributed among
two or more parties in such a way that a specified
minimum number of parties must work together in or-
der to reconstruct it. Hillery, Buˇzek, and Berthiaume
(HBB) [23] proposed a quantum version of secret shar-
ing, analogous to the concept of quantum key dis-
tribution, in which the security of the protocol is
guaranteed by quantum physics. In the three-party
scheme of [23], Alice, Bob, and Charlie share a GHZ
state |
Ψ
i
=
1
√
2
|
111
i
+
|
222
i
and choose inputs
x, y, z ∈ {
1
,
2
} and measure A
x
, B
y
, and C
z
, where
A
1
=
B
1
=
C
1
=
σ
x
and A
2
=
B
2
=
C
2
=
σ
y
. In
all cases, Bob’s and Charlie’s measurement outcomes
individually are uncorrelated with Alice’s. However,
if Alice, Bob, and Charlie all measure σ
x
, or any one
of them measures σ
x
and the other two measure σ
y
,
then Bob and Charlie can together determine Alice’s
result from the product of their own measurement res-
ults. Quantum secret-sharing protocols can also be
devised for more than three parties, but we will dis-
cuss explicitly only the three-party version here.
The state and measurements, and resulting correla-
tions, of this protocol are precisely those that maxim-
ally violate the Mermin-Bell inequality. For readers fa-
miliar with both, it may seem natural to ask whether
the security of the HBB scheme can be proved device
independently, i.e., without assuming that the par-
ticipants’ devices are necessarily measuring σ
x
and
σ
y
. There have indeed been proposals to design a
device-independent secret-sharing protocol based on
the GHZ-paradox or other correlations arising from
GHZ states [20, 34, 35]. However, we found that the
HBB scheme is completely insecure from a device-
independent point of view. The reason is that the
secret-sharing protocol is intended to still work, se-
curely, if either Bob or Charlie (but not both) are dis-
honest, and this differs from the usual Bell scenario
where all the parties participating in the Bell test are
trusted.
If (say) Charlie is dishonest, he could attack the
protocol in the usual ways considered in the secur-
ity analyses of device-independent protocols (particu-
larly, he could prepare a different state than the GHZ
state and/or arrange for Alice’s and Bob’s devices
to perform different measurements than σ
x
and σ
y
).
Moreover, since Charlie is also involved in the para-
meter estimation (e.g., the estimation of the Mermin
expectation value), he could also act in ways that
don’t respect the normal conditions of a Bell test:
1. Charlie could wait until Bob declares which basis
y he measured in before declaring his own input
z and output c, and could perform different meas-
urements on his system depending on which input
y Bob declared.
2. Charlie could introduce correlations between his
choice of input z and the system prepared for
the protocol, instead of choosing z randomly and
independently, for instance by performing a four-
outcome measurement to determine both his in-
put z and output c, or by implementing a hidden-
variable model in which the hidden variable λ is
Accepted in Quantum 2018-08-02, click title to verify 8
correlated with z.
3. Charlie could perform a different measurement to
attempt to guess Alice’s outcome than he does in
the parameter estimation rounds.
The possibility of an attack combining 1 and 3
is already known to be fatal for even the device-
dependent HBB scheme (i.e., Charlie can learn Alice’s
outcome, without being detected, even assuming that
Alice and Bob are measuring σ
x
and σ
y
). It and a pos-
sible remedy, in which Bob and Charlie are required
to declare their outputs before either are allowed to
declare their inputs, is discussed in [36].
In the following we describe how a dishonest party
could go about attacking an HBB-type protocol, in
either the quantum or no-signalling scenarios, without
needing to learn Bob’s input. We have not at-
tempted to be exhaustive or general; we merely de-
scribe the simplest pathological cases that would need
to be ruled out, which already show that the situ-
ation is much worse for secret sharing in the device-
independent scenario.
4.2 Hidden variable models
Similarly to other device-independent cryptographic
protocols, the simplest way a dishonest Charlie could
try to attack a secret-sharing protocol would be to
attempt to implement a deterministic hidden-variable
model replicating the observed correlations. This is
possible if the probabilities P
(
abc|xyz
)
of the protocol
can be expressed in the form
P (abc|xyz)
=
X
λ
p
λ|z
P
A
(a|x; λ)P
B
(b|y; λ)P
C
(c|z; λ) . (102)
Note that, in this case, there is no reason for Charlie
to arrange for the hidden variable λ and his own input
z to be uncorrelated. (In the language of Bell locality,
the so-called “free will” assumption is not justified.)
We reflect this in (102) by allowing the probability
distribution p
λ|z
to depend arbitrarily on z. Eq. (102)
thus does not have the form of a local hidden-variable
model of the kind normally considered in Bell-type
theorems, and it is not sufficient for the probabilities
P
(
abc|xyz
)
to violate a Bell inequality, such as the
Mermin inequality, in order to rule out a local hidden-
variable model of the form above.
It is easy to show that the existence of a decompos-
ition of the form (102) is equivalent to the existence
of a local hidden-variable model of the form
P (ab|xy; cz)
=
X
λ
p
0
λ|cz
P
(cz)
A
(a|x; λ)P
(cz)
B
(b|y; λ) (103)
for each of the probability distributions P
(
ab|xy
;
cz
)
conditioned on Charlie’s different possible outputs
and inputs c and z. This gives a bare minimum
condition in order for there to be any hope that a
device-independent secret-sharing scheme might be
secure: at least one of the conditional distributions
P
(
ab|xy
;
cz
)
(for some c and z) must be nonlocal. This
condition is not met for the GHZ correlations that
the HBB protocol is based on: in that case all of the
conditional distributions P
(
ab|xy
;
cz
)
exhibit perfect
correlation or no correlation at all depending on the
inputs, and admit trivial local hidden-variable mod-
els. This makes it clear that secret sharing cannot
be done securely and device independently using only
the correlations of the GHZ paradox.
4.3 No-signalling attacks
Security analyses of device-independent protocols are
sometimes undertaken using only the no-signalling
constraints, since this is typically much simpler,
though typically at the cost of significantly worse tol-
erance to noise. We are aware of at least two pro-
posals [20, 34] to design device-independent secret-
sharing protocols using GHZ states (but not neces-
sarily the GHZ-paradox correlations) using only no-
signalling constraints. In this case, the situation is
significantly worse, since in the no-signalling scenario,
a dishonest Charlie could implement arbitrary steer-
ing. More precisely, suppose Charlie wishes to pro-
duce the no-signalling distribution P
(
abc|xyz
)
in the
parameter estimation rounds. If the marginal distri-
bution P
(
ab|xy
) =
P
c
P
(
abc|xyz
)
can be expressed
as a convex sum
P (ab|xy) =
X
λ
p
λ
P
(λ)
(ab|xy) (104)
of no-signalling distributions P
(λ)
(
ab|xy
)
then Charlie
could prepare the extended distribution
P
0
(abc|xyz) =
(
P (abc|xyz) if z 6= ⊥
p
c
P
(c)
(ab|xy) if z = ⊥
(105)
where ⊥ is an additional input that Charlie can use
in the secret bit generation rounds, when he is not
asked to publicly disclose his input and outcome. It
is easy to verify that the extended distribution (105)
still satisfies the no-signalling constraints.
The above observation means that, in the no-
signalling scenario, the security or insecurity of a
device-independent secret-sharing protocol against a
dishonest Charlie is determined entirely by the mar-
ginal distribution P
(
ab|xy
)
between Alice and Bob.
If this marginal distribution is in the local polytope
then the protocol is completely insecure against no-
signalling attacks. A special case worth remarking
is that no device-independent secret-sharing protocol
based on the GHZ state can be proved secure using
only the no-signalling conditions: the marginals of the
GHZ state are all separable and the marginal probab-
ility distributions will always be in the local polytope,
Accepted in Quantum 2018-08-02, click title to verify 9
regardless of what or how many measurements are
performed by the parties.
4.4 Outlook
To summarise: we have pointed out that a device-
independent version of the HBB protocol would be
completely insecure against a dishonest party, and
that any protocol for which the marginal probability
distributions are in the local polytope (for example,
any protocol using a GHZ state) cannot be proved
secure using only the no-signalling constraints. This
does not rule out that a device-independent secret-
sharing protocol could be designed, for instance based
on different correlations and/or using stronger con-
straints than only the no-signalling conditions in the
security proof. However, one should consider the fol-
lowing points:
• It is already known that if one can do quantum
key distribution then one can do secret sharing.
For instance, Alice could do device-independent
key distribution separately with Bob and Charlie
and xor the two keys. More generally, secret shar-
ing can be done securely using classical protocols
if the parties can do one-time-pad encryption,
which happens to be precisely what key distri-
bution schemes are intended to generate crypto-
graphic keys for.
• As with key distribution, or any secure protocol
involving parties communicating remotely, the
parties would need to authenticate themselves.
This is normally done in key distribution using
classical authentication schemes which require
preshared keys; part of the generated key can
then be used to do the authentication the next
time. Consequently, it seems to us that one
would need to be able to do key distribution any-
way in order to do secret sharing, if only to gener-
ate the authentication keys needed after the first
use of the protocol.
Given these issues, the usefulness of a device-
independent secret-sharing protocol that does not re-
duce to a direct application of device-independent
quantum key distribution is unclear to us.
5 Conclusion
We considered the Mermin-Bell experiment with
three parties and we identified and proved tight up-
per bounds on the guessing probabilities associated
with the measurement outcomes of one and two of
the parties. The results are fundamental tradeoffs
between the amount of intrinsic randomness and non-
locality, as measured by the violation of the Mermin
inequality, imposed by the structure of quantum phys-
ics. The linearisations in section 3 can also be read as
inequalities identifying parts of the boundary of the
set of quantum correlations. The results reveal that
part of the boundary of the quantum set is flat, a char-
acteristic that has previously been remarked upon in
[35, 37].
It may be interesting to study how our results gen-
eralise to Bell experiments involving more parties.
We guessed one possible generalisation of the upper
bound (18) for P
g
(
A
1
B
1
|
E)
to n parties, which can
be found in appendix B. We did not attempt to prove
it, though we tested the cases for n
= 4
and
5
parties
numerically.
While we are not aware of an obvious practical ap-
plication of our results, we believe there is some merit
to finding the analytic form of randomness vs. nonloc-
ality tradeoffs more generally where it could be feas-
ible to do so, particularly where the result might be
used in the security proof of a device-independent pro-
tocol. From this point of view, our work has explored
the feasibility of searching for sum-of-squares decom-
positions for problems somewhat larger than was con-
sidered in [22]. The cases where the method is likely to
work are probably those where the problem is “simple”
in some same key respects as the problems we studied.
In particular: it was reasonably easy for us to guess
the upper bounds and the states and measurements
that attained them, we found that the optimal solu-
tion was attained at a level of the hierarchy that was
not prohibitively high, and symmetries of the problem
allowed us to reduce the number of variables in the
searches for sum-of-squares decompositions.
Acknowledgements
E.W. thanks Cedric Bamps and Stefano Pironio
for helpful discussions concerning sum-of-squares de-
compositions. This work was supported by the
Spanish MINECO (QIBEQI FIS2016-80773-P and
Severo Ochoa grant SEV-2015-0522), the General-
itat de Catalunya (CERCA Program and SGR 1381),
the Fundaci´o Privada Cellex, the AXA Chair in
Quantum Information Science, and the ERC CoG
QITBOX. B.B. acknowledges support from the Sec-
retaria d’Universitats i Recerca del Departament
d’Economia i Coneixement de la Generalitat de
Catalunya and the European Social Fund (FEDER).
References
[1] J. S. Bell, Physics 1, 195 (1964).
[2] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani,
and S. Wehner, Rev. Mod. Phys. 86, 419 (2014),
arXiv:1303.2849 [quant-ph].
[3] D. Mayers and A. Yao, in Proceedings of the 39th
Annual Symposium on Foundations of Computer
Science (IEEE Computer Society, Los Alamitos,
1998) pp. 503–509, arXiv:quant-ph/9809039.
Accepted in Quantum 2018-08-02, click title to verify 10
[4] A. Ac´ın, N. Brunner, N. Gisin, S. Massar, S. Piro-
nio, and V. Scarani, Phys. Rev. Lett. 98, 230501
(2007), arXiv:quant-ph/0702152.
[5] R. Colbeck, Quantum And Relativistic Pro-
tocols For Secure Multi-Party Computation,
Ph.D. thesis, University of Cambridge (2006),
arXiv:0911.3814 [quant-ph].
[6] S. Pironio, A. Ac´ın, S. Massar, A. Boyer de
La Giroday, D. N. Matsukevich, P. Maunz,
S. Olmschenk, D. Hayes, L. Luo, T. A. Man-
ning, and C. Monroe, Nature 464, 1021 (2010),
arXiv:0911.3427 [quant-ph].
[7] R. Colbeck and A. Kent, J. Phys. A: Math. Theor.
44, 095305 (2011), arXiv:1011.4474 [quant-ph].
[8] R. Renner, N. Gisin, and B. Kraus, Phys. Rev. A
72, 012332 (2005), arXiv:quant-ph/0502064.
[9] R. Renner, Security of Quantum Key Dis-
tribution, Ph.D. thesis, ETH Zurich (2005),
arXiv:quant-ph/0512258.
[10] L. Masanes, S. Pironio, and A. Ac´ın, Nat. Com-
mun. 2, 238 (2011), arXiv:1009.1567 [quant-ph].
[11] S. Pironio and S. Massar, Phys. Rev. A 87,
012336 (2013), arXiv:1111.6056 [quant-ph].
[12] S. Pironio, L. Masanes, A. Leverrier, and A. Ac´ın,
Phys. Rev. X 3, 031007 (2013), arXiv:1211.1402
[quant-ph].
[13] R. Arnon-Friedman, F. Dupuis, O. Fawzi,
R. Renner, and T. Vidick, Nat. Commun. 9, 459
(2018).
[14] M. Navascu´es, S. Pironio, and A. Ac´ın, Phys.
Rev. Lett. 98, 010401 (2007), arXiv:quant-
ph/0607119.
[15] O. Nieto Silleras, S. Pironio, and J. Silman,
New J. Phys. 16, 013035 (2014), arXiv:1309.3930
[quant-ph].
[16] J.-D. Bancal, L. Sheridan, and V. Scarani, New J.
Phys. 16, 033011 (2014), arXiv:1309.3894 [quant-
ph].
[17] J. F. Clauser, M. A. Horne, A. Shimony, and
R. A. Holt, Phys. Rev. Lett. 23, 880 (1969).
[18] J. Kaniewski and S. Wehner, New J. Phys. 18,
055004 (2016), arXiv:1601.06752 [quant-ph].
[19] J. Barrett, A. Kent, and S. Pironio, Phys.
Rev. Lett. 97, 170409 (2006), arXiv:quant-
ph/0605182.
[20] L. Aolita, R. Gallego, A. Cabello, and
A. Ac´ın, Phys. Rev. Lett. 108, 100401 (2012),
arXiv:1109.3163 [quant-ph].
[21] N. D. Mermin, Phys. Rev. Lett. 65, 1838 (1990).
[22] C. Bamps and S. Pironio, Phys. Rev. A 91,
052111 (2015), arXiv:1504.06960 [quant-ph].
[23] M. Hillery, V. Buˇzek, and A. Berthiaume,
Phys. Rev. A 59, 1829 (1999), arXiv:quant-
ph/9806063.
[24] D. M. Greenberger, M. A. Horne, A. Shimony,
and A. Zeilinger, Am. J. Phys. 58, 1131 (1990).
[25] J.-D. Bancal, N. Gisin, Y.-C. Liang, and S. Piro-
nio, Phys. Rev. Lett. 106, 250404 (2011),
arXiv:1102.0197 [quant-ph].
[26] G. Svetlichny, Phys. Rev. D 35, 3066 (1987).
[27] V. Scarani and N. Gisin, J. Phys. A: Math. Gen.
34, 6043 (2001), arXiv:quant-ph/0103068.
[28] R. F. Werner and M. M. Wolf, Phys. Rev. A 64,
032112 (2001), arXiv:quant-ph/0102024.
[29] “SDPA official page”, http://sdpa.
sourceforge.net/ (2011).
[30] M. Nakata, in 2010 IEEE International Sym-
posium on Computer-Aided Control System
Design (IEEE, 2010) pp. 29–34.
[31] “GitHub - ewoodhead/npa-hierarchy”, https:
//github.com/ewoodhead/npa-hierarchy
(2018).
[32] A. Ac´ın, S. Massar, and S. Pironio, Phys.
Rev. Lett. 108, 100402 (2012), arXiv:1107.2754
[quant-ph].
[33] A. Meurer, C. P. Smith, M. Paprocki, O.
ˇ
Cert´ık,
S. B. Kirpichev, M. Rocklin, A. Kumar,
S. Ivanov, J. K. Moore, S. Singh, T. Rathnayake,
S. Vig, B. E. Granger, R. P. Muller, F. Bonazzi,
H. Gupta, S. Vats, F. Johansson, F. Pedre-
gosa, M. J. Curry, A. R. Terrel, v. Rouˇcka,
A. Saboo, I. Fernando, S. Kulal, R. Cimrman,
and A. Scopatz, PeerJ Computer Science 3, e103
(2017).
[34] S. Gogioso and W. Zeng, “Generalised
Mermin-type non-locality arguments”, (2017),
arXiv:1702.01772 [quant-ph].
[35] R. Ramanathan and P. Mironowicz, “Trade-offs
in multi-party Bell inequality violations in qubit
networks”, (2017), arXiv:1704.03790 [quant-ph].
[36] A. Karlsson, M. Koashi, and N. Imoto, Phys. Rev.
A 59, 162 (1999).
[37] K. T. Goh, J. Kaniewski, E. Wolfe, T. V´ertesi,
X. Wu, Y. Cai, Y.-C. Liang, and V. Scarani, Phys.
Rev. A 97, 022104 (2018), arXiv:1710.05892
[quant-ph].
[38] J. Silman, S. Pironio, and S. Massar, Phys.
Rev. Lett. 110, 100504 (2013), arXiv:1211.5921
[quant-ph].
[39] S. Pironio, J.-D. Bancal, and V. Scarani, J.
Phys. A: Math. Theor. 44, 065303 (2011),
arXiv:1101.2477 [quant-ph].
A No-signalling bounds
The main text gave tight bounds on the guessing prob-
ability assuming all the measurements are performed
on a quantum system. The tightest bound that can be
derived for the local guessing probability using only
the no-signalling constraints is
P
g
(A
1
|E) ≤
3
2
−
1
8
|M| −
1
8
|M
0
|. (106)
Accepted in Quantum 2018-08-02, click title to verify 11
For the two-party guessing probability there are two
distinct tight bounds,
P
g
(A
1
B
1
|E) ≤
3
2
−
1
4
|M| (107)
and
P
g
(A
1
B
1
|E) ≤
7
4
−
1
4
|M| −
1
8
|M
0
|, (108)
as well as the same bounds with M and M
0
swapped.
Finally, there are three bounds for the global guessing
probability,
P
g
(A
1
B
1
C
1
|E) ≤
3
2
−
1
4
|M|, (109)
P
g
(A
1
B
1
C
1
|E) ≤
7
4
−
1
4
|M| −
1
8
|M
0
|, (110)
P
g
(A
1
B
1
C
1
|E) ≤
7
4
−
1
16
|M| −
5
16
|M
0
|. (111)
The same upper bounds hold for P
g
(
A
1
B
2
C
2
|
E)
,
P
g
(
A
2
B
1
C
2
|
E)
, and P
g
(
A
2
B
2
C
1
|
E)
. The up-
per bounds for P
g
(
A
1
B
1
C
2
|
E)
, P
g
(
A
1
B
2
C
1
|
E)
,
P
g
(
A
2
B
1
C
1
|
E)
, and P
g
(
A
2
B
2
C
2
|
E)
are the same ex-
cept with M and M
0
swapped.
Following an approach similar to [38], the local-
guessing-probability bound (106) is implied by the
eight inequalities
1 −hA
1
i + hB
1
C
1
i −hA
1
B
1
C
1
i ≥ 0 , (112)
1 −hA
1
i + hB
1
C
2
i −hA
1
B
1
C
2
i ≥ 0 , (113)
1 −hA
1
i + hB
2
C
1
i −hA
1
B
2
C
1
i ≥ 0 , (114)
1 −hA
1
i −hB
2
C
2
i + hA
1
B
2
C
2
i ≥ 0 , (115)
1 + hA
2
i −hB
1
C
1
i −hA
2
B
1
C
1
i ≥ 0 , (116)
1 −hA
2
i −hB
1
C
2
i + hA
2
B
1
C
2
i ≥ 0 , (117)
1 −hA
2
i −hB
2
C
1
i + hA
2
B
2
C
1
i ≥ 0 , (118)
1 + hA
2
i + hB
2
C
2
i + hA
2
B
2
C
2
i ≥ 0 . (119)
Each of these is in turn implied by two positivity con-
straints. For example, (112) is just stating that
4P (−++|111) + 4P (−−−|111) ≥ 0 . (120)
The inequalities (112) to (119) sum to
8 −4hA
1
i −M − M
0
≥ 0 (121)
which, together with symmetries of the problem, im-
plies (106).
The upper bound P
g
(
A
1
B
1
|
E)
≤
3
/
2
−M/
4
is sim-
ilarly implied by the five inequalities
1 + hC
1
i −hA
1
B
1
i −hA
1
B
1
C
1
i ≥ 0 , (122)
1 −hA
1
i −hB
2
C
2
i + hA
1
B
2
C
2
i ≥ 0 , (123)
1 −hB
1
i −hA
2
C
2
i + hA
2
B
1
C
2
i ≥ 0 , (124)
1 −hC
1
i −hA
2
B
2
i + hA
2
B
2
C
1
i ≥ 0 , (125)
1 + hA
2
B
2
i + hA
2
C
2
i + hB
2
C
2
i ≥ 0 (126)
(the last of these is just stating that
4P (+++|222) + 4P (−−−|222) ≥ 0 ), (127)
which sum to
6 −4P
AB
(++|11) −M ≥ 0 . (128)
The second upper bound (108) for P
g
(
A
1
B
1
E)
is im-
plied by the inequalities
2 + 2hC
1
i −2hA
1
B
1
i −2hA
1
B
1
C
1
i ≥ 0 , (129)
1 −hA
1
i + hB
1
C
2
i −hA
1
B
1
C
2
i ≥ 0 , (130)
1 −hC
1
i + hA
1
B
2
i −hA
1
B
2
C
1
i ≥ 0 , (131)
1 −hB
1
i + hA
2
C
1
i −hA
2
B
1
C
1
i ≥ 0 , (132)
2 −hA
1
i −hC
2
i −hA
1
B
2
i
− hB
2
C
2
i + 2hA
1
B
2
C
2
i ≥ 0 , (133)
2 −hA
2
i −hB
1
i −hA
2
C
2
i
− hB
1
C
2
i + 2hA
2
B
1
C
2
i ≥ 0 , (134)
2 −hB
2
i −hC
1
i −hA
2
B
2
i
− hA
2
C
1
i + 2hA
2
B
2
C
1
i ≥ 0 , (135)
1 + hA
2
i + hB
2
i + hC
2
i + hA
2
B
2
i
+ hA
2
C
2
i + hB
2
C
2
i + hA
2
B
2
C
2
i ≥ 0 , (136)
which sum to
14 −8P
AB
(++|11) −2M − M
0
≥ 0 . (137)
Each of the eight inequalities above can be obtained
from up to three positivity constraints. For instance,
the left-hand side of (133) is equal to
4P (+−−|122) + 8P (−+−|122)
+ 4P (−−+|122) . (138)
The first two upper bounds (109) and (110) on
the three-outcome guessing probability P
g
(
A
1
B
1
C
1
|
E)
are implied by (107) and (108). Using symmetries of
the problem, the remaining inequality (111) reduces
to showing that
max
P (+++|111), P (−−−|222)
≤
7
4
−
1
16
M −
1
16
M
0
. (139)
One can readily verify that
7
4
− P (+++|111) −
1
16
M −
5
16
M
0
=
1
4
P (++−|111) +
1
4
P (+−+|111)
+
1
4
P (−++|111) +
3
4
P (−−−|111)
+ P (+−+|112) + P (−++|112)
+
1
2
P (−−−|112)
+ P (++−|121) + P (−++|121)
+
1
2
P (−−−|121)
+ P (++−|211) + P (+−+|211)
+
1
2
P (−−−|211)
Accepted in Quantum 2018-08-02, click title to verify 12
+
1
2
P (+−−|122) +
1
2
P (−+−|212)
+
1
2
P (−−+|221)
+
1
4
P (+++|222) +
3
4
P (+−−|222)
+
3
4
P (−+−|222) +
3
4
P (−−+|222)
≥ 0 (140)
and
7
4
− P (−−−|111) −
1
16
M −
5
16
M
0
=
1
2
P (+++|111)
+
1
4
P (++−|112) + P (+−+|112)
+ P (−++|112) +
1
4
P (−−−|112)
+ P (++−|121) +
1
4
P (+−+|121)
+ P (−++|121) +
1
4
P (−−−|121)
+ P (++−|211) + P (+−+|211)
+
1
4
P (−++|211) +
1
4
P (−−−|211)
+
1
4
P (+++|122) +
1
4
P (+−−|122)
+
1
4
P (+++|212) +
1
4
P (−+−|212)
+
1
4
P (+++|221) +
3
4
P (−−+|221)
+
1
2
P (−−−|221)
+ P (+−−|222) + P (−+−|222)
+
1
2
P (−−+|222)
≥ 0 (141)
under the no-signalling constraints.
The bounds given here are the tightest that can
be derived given that there are no-signalling distribu-
tions for which
P
g
(A
1
|E), M, M
0
∈
1, 0, ±
0
4
,
1, ±4, 0
,
1
2
, ±4, ±
0
4
, (142)
P
g
(A
1
B
1
|E), M, M
0
∈
1, ±2, ±
0
2
,
1
2
, ±2, ±
0
4
,
1
2
, ±4, ±
0
2
,
1
4
, ±4, ±
0
4
, (143)
and
P
g
(A
1
B
1
C
1
|E), M, M
0
∈
1, ±2, ±
0
2
,
1
2
, ±4, ±
0
2
,
1
2
, 0, ±
0
4
,
1
4
, ±4, ±
0
4
, (144)
The only case that might not be immediately obvi-
ous is that there are no-signalling distributions for
which simultaneously P
g
(
A
1
B
1
|
E) = 1
/
2
, M
=
±
4
,
and M
0
=
±
0
2
; these can be attained with vertices of
class 34 according to the classification used in table 1
of [39].
B Possible bound for n > 3 parties
In section 3.3 we showed that the upper bound (18)
on the two-party guessing probability P
g
(
A
1
B
1
|
E)
is
tight and the nonlinear part M ≥
3
can be attained if
the parties measure σ
x
and σ
y
on a state of the form
|Ψi = λ|+++i+µ
|+−−i+|−+−i+|−−+i
. (145)
We mention a possible extension here for the n-partite
Mermin correlator
M
n
= Re
D
n
Y
p=1
A
(p)
1
+ iA
(p)
2
E
, (146)
where A
(p)
x
are the pth party’s measurement operators,
whose local and quantum bounds are respectively [21]
L
n
=
(
2
(n−1)/2
if n odd
2
n/2
if n even
(147)
and
Q
n
= 2
n−1
(148)
(although the local bound M
n
≤ L
n
is a facet of the
local polytope only for odd n).
The obvious generalisation of the strategy of sec-
tion 3.3 is for the n parties to measure
A
(p)
1
= σ
x
, A
(p)
2
= σ
y
(149)
on an n-partite state of the form
|Ψi = λ|+i
⊗n
+ µ
X
s∈S
|si, (150)
where S ⊂ {
+
, −}
×n
is the subset of all vectors of n
signs with a nonzero even number of minuses. The
state is normalised if
λ
2
+ (Q
n
− 1)µ
2
= 1 . (151)
In terms of λ and µ, the probability that the first n−
1
parties (or all n of them, for that matter) obtain the
result ‘+’ if they measure σ
x
is
P
A
(+|1) = λ
2
(152)
and the Mermin expectation value is
M
n
=
λ + (Q
n
− 1)µ
2
. (153)
Relating P
A
(
+|1
) =
λ
2
to M
n
yields the dependence
P
A
(1|1) = P
n
(M
n
), where
P
n
(M
n
) = 1 −
1
Q
n
−
Q
n
− 2
Q
2
n
M
n
+ 2
√
Q
n
− 1
Q
2
n
p
M
n
(Q
n
− M
n
) . (154)
By suitably mixing this strategy with a deterministic
strategy with P
A
(
1|1
) = 1
and M
n
=
L
n
, we obtain a
Accepted in Quantum 2018-08-02, click title to verify 13
strategy for which the guessing probability and Mer-
min expectation value are related by
P
g
(A
1
|E) =
(
P
n
(M
n
) if M
n
≥ M
th
n
Γ
n
(M
n
) if M
n
≤ M
th
n
, (155)
where
Γ
n
(M
n
) =
L
n
(Q
n
− 1) − (L
n
− 1)M
n
L
n
(Q
n
− L
n
)
. (156)
The threshold M
th
n
in (155) is the point where the
linear interpolation
Γ
n
(
M
n
)
coincides with the curve
P
n
(
M
n
)
and their derivatives are the same. This oc-
curs at
M
th
n
=
L
2
n
(Q
n
− 1)
L
2
n
− 2L
n
+ Q
n
, (157)
at which point
P
g
(A
1
|E) =
Q
n
− 1
L
2
n
− 2L
n
+ Q
n
. (158)
For odd n, we remark that L
n
=
√
Q
n
and in that
case (157) reduces to the average M
th
n
= (
L
n
+
Q
n
)
/
2
of the local and quantum bounds.
The strategy we have described here shows that the
upper bound on the guessing probability cannot be
better than (155). For n
= 4
and
5
parties, some
numerical tests we carried out seemed to support that
the upper bound on the guessing probability coincides
with (155), although we did not attempt to prove this.
Accepted in Quantum 2018-08-02, click title to verify 14