Contextuality in multipartite pseudo-telepathy
graph games
Anurag Anshu1 , Peter Høyer2 , Mehdi Mhalla3 , and Simon Perdrix4

arXiv:1609.09689v2 [quant-ph] 24 Jun 2017

1

3

Centre for Quantum Technologies, National University of Singapore
2
University of Calgary, Canada
Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG, F-38000 Grenoble France
4
CNRS, LORIA, Université de Lorraine, Nancy, France

Abstract. Analyzing pseudo-telepathy graph games, we propose a way
to build contextuality scenarios exhibiting the quantum supremacy using
graph states. We consider the combinatorial structures that generate
equivalent scenarios. We introduce a new tool called multipartiteness
width to investigate which scenarios are harder to decompose and show
that there exist graphs generating scenarios with a linear multipartiteness
width.

1

Introduction

Contextuality is an active area of research that describes models of correlations
and interpretations, and links to some fundamental questions about the natural
world. It also provides a framework where one can utilize the understanding
of quantum mechanics (and quantum information) in order to better analyze,
understand, and interpret macroscopic phenomena [5, 11, 12, 22, 30].
The theoretical and experimental study of quantum world has proven that a
scenario involving many parties (each having access to a local information) can
contain correlations that do not possess any classical interpretation that relies
on decomposition of these correlations using local functions. Contextuality can
be viewed as a tool to describe the combinatorial structures present in these
correlations.
A model of contextuality scenario is due to Abramsky and Brandenburger [1]
and uses sheaf theory to naturally translate the consistency of interpretation
by the pre-sheaf structure obtained by a distribution functor on the sheaf of
events. The authors introduce three levels of contextuality: (i) Probabilistic
contextuality, which corresponds to the possibility of simulating locally and
classically a probability distribution. It extends the celebrated Bell’s theorem [7]
which shows that quantum probabilities are inconsistent with the predictions of
any local realistic theory; (ii) Logical contextuality or possibilistic contextuality,
which extends Hardy’s construction [20] and considers only the support of a
probability distribution; (iii) Strong contextuality, which extends the properties
of the GHZ state [16] and relies on the existence of a global assignment consistent
with the support.

More recently Acı́n, Fritz, Leverrier, and Belén Sainz [3] have presented
contextuality scenarios defined as hypergraphs, in which vertices are called
outcomes and hyperedges are called measurements. A general interpretation
model is an assignment of non negative reals to the vertices that can be interpreted
as a probability distribution for any hyperedge (weights of the vertices of each
hyperedge sum to 1). Each hypergraph H admits a set C(H) (resp. Q(H), G(H))
of classical (resp. quantum, general probabilistic) models with C(H) ⊆ Q(H) ⊆
G(H).
They have shown that the Foulis Randall product of hypergraphs [13] allows
one to describe the set of no-signaling models in product scenarios G(H1 ⊗ H2 ).
They have also investigated the multipartite case, showing that the different
products for composition produce models that are observationally equivalent.
A particular case of contextuality scenarios is the pseudo-telepathy games [9],
which are games that can be won by non-communicating players that share
quantum resources, but cannot be won classically without communication. A
family of pseudo-telepathy games based on graph states have been introduced
in [4]. The pseudo-telepathy game associated with a graph G of order n (on n
vertices), is a collaborative n-player game where each player receives a binary
input (question) and is asked to provide, without communication, a binary output
(answer). Some global pairs of (answers—questions) are forbidden and correspond
to losing positions. Given such a scenario, to quantify its multipartiteness, we
define the multipartiteness width: a model on n parties has a multipartiteness
width less than k if it has an interpretation (assignment of real positive numbers to
the vertices) that can be obtained using as ressources interpretations of contextual
scenarios on less than k parties.
It has been shown in [10] that even though GHZ type scenarios are maximally
non local (strongly contextual), they can be won with 2 partite nonlocal boxes. So
the multipartiteness width is different from the usual measures of contextuality
[2, 15]. However, it has potential application for producing device independent
witnesses for entanglement depth [25].
In section 2, we define the graph pseudo-telepathy games, investigate in detail
the quantum strategy and link them to contextuality scenarios. We show in section
3 that provided that the players share multipartite randomness, it is enough
to surely win the associated pseudo-telepathy game, in order to simulate the
associated quantum probability distribution. In section 4, we prove that graphs
obtained by a combinatorial graph transformation called pivoting correspond
to equivalent games. Finally, we prove that there exist graphs for which the
multipartiteness width is linear in the number of players, improving upon the
previous logarithmic bound given in [4].
Note that even though the rules of these graph games appear non-trivial, they
naturally correspond to the correlations present in outcomes of a quantum process
that performs X and Z measurements on a graph state. Thus, they might be
easy to produce empirically. Furthermore even if the space of events is quite large,
the scenarios have the advantage of possessing concise descriptions, quite similar
to the separating scenarios using Johnson graphs in [14]. Requiring such large
structures to achieve possibilistic contextuality for quantum scenarios seems to

be unavoidable. Indeed, it has been shown that multiparty XOR type inequalities
involving two-body correlation functions cannot achieve pseudo-telepathy [17].

2

Pseudo-telepathy graph games, multipartiteness and
contextuality scenarios

Graph notations. We consider finite simple undirected graphs. Let G = (V, E)
be a graph. For any vertex u ∈ V , NG (u) = {v ∈ V | (u, v) ∈ E} is the
neighborhood of u. For any D ⊆ V , the odd neighborhood of D is the set
of all vertices which are oddly connected to D in G: Odd(D) = {v ∈ V :
|D ∩ N (v)| = 1 mod 2}. Even(D) = V \ Odd(D) is the even neighborhood of D,
and loc(D) = D ∪ Odd(D) is the local set of D which consists of the vertices
in D and those oddly connected to D. For any D ⊆ V , G[D] = (D, E ∩ D×D)
is the subgraph induced by D, and |G[D]| its size, i.e. the number of edges
of G[D]. Note that Odd can be realized as linear map (where we consider
subsets as binary vectors), which implies that for any two subset of vertices A, B,
Odd(A ⊕ B) = Odd(A) ⊕ Odd(B) where ⊕ denotes the symmetric difference.
We introduce the notion of involvement:
Definition 1 (Involvement). Given a graph G = (V, E), a set D ⊆ V of
vertices is involved in a binary labelling x ∈ {0, 1}V of the vertices if D ⊆
supp(x) ⊆ Even(D), where supp(x) = {u ∈ V, xu = 1}.
In other words, D is involved in the binary labelling x, if all the vertices in D
are labelled with 1 and all the vertices in Odd(D) are labelled with 0. Notice
that when G[D] is not a union of Eulerian graphs1 , there is no binary labelling
in which D is involved. On the other hand, if G[D] is a union of Eulerian graphs,
there are 2|Even(D)|−|D| binary labellings in which D is involved.
Collaborative games. A multipartite collaborative game G for a set V of
players is a scenario characterised by a set L ⊆ {0, 1}V × {0, 1}V of losing pairs:
each player u is asked a binary question xu and has to produce a binary answer au .
The collaborative game is won by the players if for a given question x ∈ {0, 1}V
they produce an answer a ∈ {0, 1}V such that the pair formed by a and x,
denoted (a|x), is not a losing pair, i.e. (a|x) ∈
/ L.
A game is pseudo-telepathic if classical players using classical resources cannot
perfectly win the game (unless they cheat by exchanging messages after receiving
the questions) whereas using entangled states as quantum resources the players
can perfectly win the game, giving the impression to a quantum non believer
that they are telepathic (as the only classical explanation to a perfect winning
strategy is that they are communicating).
Example 1: ThePlosing set associatedP
with thePMermin parity game [26] is
LMermin = {(a|x) :
xi = 0 mod 2 and
ai + ( xi )/2 = 1 mod 2}. Notice
1

The following three properties are equivalent: (i) D ⊆ Even(D); (ii) every vertex
of G[D] has an even degree; (iii) G[D] is a union of Eulerian graphs. Notice that
D ⊆ Even(D) does not imply that G[D] is Eulerian as it may not be connected.

that the losing set admits the following simpler description: LMermin = {(a|x) :
2|a| = |x| + 2 mod 4}, where |x| = |supp(x)| is the Hamming weight of x.
Collaborative graph games MCG(G): A multipartite collaborative game
MCG(G) associated with a graph G = (V, E), where V is a set of players, is the
collaborative
P game where the set of losing pairs is LG := {(a|x) : ∃D involved
in x s.t. u∈loc(D) au = |G[D]| + 1 mod 2}. In other words, the collaborative
game is won by the players if for a given question x ∈ {0, 1}V they
P produce an
answer a ∈ {0, 1}V such that for any non-empty D involved in x, u∈loc(D) au =
|G[D]| mod 2.
Example 2: Consider MCG(Kn ) the collaborative game associated with
the complete graph Kn of order n. When a question x contains an even number
of 1s the players trivially win since there is no non-empty subset of vertices
involved in such a question. When x has an odd number of 1s, the set of players
(vertices) involved in this question is D = supp(x). In this case, all the players
are either in D or Odd(D) thus the sum of all the answers has to be equal to
|G[D]| = |D|(|D|−1)
= |D|−1
mod 2. Thus for the complete graph Kn , LKn =
2
2
{(a|x) : |x| = 1 mod 2 and |a| = |x|−1
2 +1 mod 2} = {(a|x) : 2|a| = |x|+1 mod 4}.
Note that for this particular graph, the constraints are global in the sense that
the sum of the answers of all the players is used for all the questions. Notice also
that the set of losing pairs LKn = {(a|x) : 2|a| = |x| + 1 mod 4} is similar to the
one of the Mermin parity game, LMermin = {(a|x) : 2|a| = |x| + 2 mod 4}. In
section 4, we actually show the two games simulate each other.
Quantum strategy (Qstrat): In the following we show that for any graph G,
the corresponding multipartite collaborative game can be won by the players if
they share a particular quantum state.
P More precisely the state they share is the
so-called graph state |Gi = √ 1|V | y∈{0,1}V (−1)|G[supp(y)]| |yi, and they apply
2
the following strategy: every player u measures his qubit according to X if xu = 1
or according to Z if xu = 0. Every player answers the outcome au ∈ {0, 1} of
this measurement.
This quantum strategy QStrat, not only produces correct answers, but
provides all the good answers uniformly:

Lemma 1. Given a graph G = (V, E) and question x ∈ {0, 1}V , the probability
p(a|x) to observe the outcome a ∈ {0, 1}V when each qubit u of a graph state |Gi
is measured according to Z if xu = 0 or according to X if xu = 1 satisfies:

(
p(a|x) =

0
|{D involved in x}|
2|V |

if (a|x) ∈ L
otherwise.

Proof. According to the Born rule, the probability to get the answer a ∈ {0, 1}V
to a given question x ∈ {0, 1}V is:

 

av
O
O I + (−1)au Xu
I
+
(−1)
Z
v
⊗
 |Gi
p(a|x) = hG| 
2
2
v∈V \supp(x)

u∈supp(x)

P
1 X
(−1) u∈D au hG| ZD\supp(x) XD∩supp(x) |Gi
= n
2
D⊆V

The basic property which makes this strategy work is that for any u ∈ V ,
Xu |Gi = ZN (u) |Gi. As a consequence, since X and Z anti-commute and X 2 =
Z 2 = I, for any D ⊆ V , XD |Gi = (−1)|G[D]| ZOdd(D) |Gi. Thus,
P
1 X
(−1)|G[D∩supp(x)]|+ u∈D au hG| Z(Odd(D∩supp(x)))⊕(D∩\supp(x)) |Gi
n
2

p(a|x) =

D⊆V

(
1 if C = ∅
,
Where ⊕ denotes the symmetric difference. Since hG| ZC |Gi =
0 otherwise
p(a|x) =

1
2n

1
= n
2
1
= n
2
=
(x,a)

1
2n

X

P

(−1)|G[D∩supp(x)]|+

u∈D

au

D⊆V,D\supp(x)=Odd(D∩supp(x))

X

P

(−1)|G[D1 ]|+

X

u∈D0 ∪D1

au

D1 ⊆supp(x) D0 ⊆V \supp(x),D0 =Odd(D1 )
P

(−1)|G[D1 ]|+

X

u∈loc(D1 )

au

D1 ⊆supp(x),Odd(D1 )∩supp(x)=∅
(x,a)

X

P

(−1)|G[D1 ]|+

u∈loc(D1 )

D1 involved in x

=

|R0

(x,a)

| − |R1
2n

|

P

/
u∈loc(D) au = d mod 2}. If (a|x) ∈
|{D involved in x}|
L, then
= ∅, so p(a|x) =
> 0 since ∅ is involved in
2n
(x,a)
(x,a)
x. Otherwise, there exists D0 ∈ R1 . Notice that R0
is a vector space
(x,a)
(x,a)
(x,a)
(x,a)
(∀D1 , D2 ∈ R0 , D1 ⊕ D2 ∈ R0 ) and R1
an affine space R1
= {D0 ⊕
(x,a)
(x,a)
(x,a)
D | D ∈ R0 }. Thus |R0 | = |R1 | which implies p(a|x) = 0.
t
u
where Rd

= {D involved in x : |G[D]| +

au

(x,a)
R1

The probability distribution produced by QStrat depends on the number
of sets D involved in a given question x. Notice that a set D ⊆ supp(x) is
involved in x if and only if D ∈ Ker(Lx ), where Lx linearly2 maps A ⊆ supp(x)
to Odd(A) ∩ supp(x). Thus |{D involved in x}| = 2|x|−rkG (x) , where rkG (x) =
log2 (|{Lx (A) : A ⊆ supp(x))}|) is the rank of Lx = A 7→ Odd(A) ∩ supp(x).
2

Lx is linear for the symmetric difference: Lx (D1 ⊕ D2 ) = Lx (D1 ) ⊕ Lx (D2 )

Contextuality scenario. Following the hypergraph model of [3], we associate
with every graph G a contextuality scenario, where each vertex is a pair (a|x)
and each hyperedge corresponds, roughly speaking, to a constraint. There are
two kinds of hyperedges, those (HNsigV ) which guarantee no-signaling and those
(HG ), depending on the graph G, which avoid the losing pairs.
– HNsigV is the hypergraph representing the no-signaling polytope. It corresponds [3] to the Bell scenario BV,2,2 where |V | parties have access to 2 local
measurements each, each of which has 2 possible outcomes (see Figure 1),
which is obtained as a product3 of the elementary scenario B1,2,2 .

Fig. 1. HNsig2 : hyperedges of the Bell
scenario B2,2,2 from [14]

Fig. 2. Paley Graph of order 13

– The hypergraph HG defined on the same vertex set, corresponds to the game
constraints: for each question4 x ∈ {0, 1}V we associate an hyperedge ex
containing all the answers which make the players win on x i.e., ex = {(a|x) ∈
{0, 1}V × {0, 1}V , (a|x) ∈
/ L}.
Given a graph G = (V, E), MCG(G) is a pseudo-telepathy game if it admits a
quantum model (Q(HG ∪ HNsigV ) 6= ∅) but no classical model (C(HG ∪ HNsigV ) =
∅). It has been proven in [4] that MCG(G) is pseudo-telepathic if and only if G
is not bipartite.
3

4

The Foulis Randall product of scenarios [3] is the scenario HA ⊗ HB with vertices
V (HA ⊗ HB ) = V (HA ) × V (HB ) and edges E(HA ⊗ HB ) = EA→B ∪ EA←B where
EA→B := {∪a∈eA {a} × f (a) : ea ∈ EA , f : eA → EB } and EA←B := {∪b∈eA f (b) ×
{b} : eb ∈ Eb , f : EB → EA }. In the multipartite case there are several ways to
define products, however they all correspond to the same non-locality constraints [3].
Therefore one can just consider the minimal product min ⊗n
i=1 Hi which has vertices in
the cartesian product V = ΠVi and edges ∪k∈[1,n] Ek where Ek = {(v1 . . . , vn ), vi ∈
→
ei ∀i =
6 k, vk ∈ f (−
v )} for some edge ei ∈ E(Hi ) for every party i 6= k and a function
−
→
−
→
→
v 7→ f ( v ) which assigns to every joint outcome −
v = (v1 . . . vk−1 , vk+1 , . . . vn ) an
→
edge f (−
v ) ∈ E(Hk ) (the kth vertex is replaced by a function of the others).
Note that for the questions x for which there exists no D involved in x, all the answers
are allowed thus the constraints represented by the associated edge is a hyperedge of
no-signaling scenario HN sig .

Example 3: In a complete graph Kn of order n, there exists a non-empty set
D involved in a question x ∈ {0, 1}V if and only if |x| = 1 mod 2. With each such
question x, the associated hyperedge is ex = {(a|x) ∈ {0, 1}V × {0, 1}V s.t. 2|a| =
6
|x| + 1 mod 4}.
Example 4: In the graph Paley 13 (see Figure 2), Odd({0, 1, 4}) =
{2, 7, 8, 9, 11, 12} thus if {0, 1, 4} is involved in x i.e. xi = 1 for i ∈ {0, 1, 4}
and xi = 0 for i ∈ {2, 7, 8, 9, 11, 12} then the associatedP
pseudo-telepathy game
requires that the sum of the outputs of these nine players i6∈{3,5,6,10} ai has to be
odd. This corresponds to 8 hyperedges
ejkl for j, k, l ∈ {0, 1} in the contextuality
P
scenario where ejkl = {(a|x), i6∈{5,6,10} ai = 1 mod 2, xi = 1 for i ∈ {0, 1, 4},
xi = 0 for i ∈ {2, 7, 8, 9, 11, 12}, x5 = j, x6 = k, x10 = l}.
The probabilistic contextuality is what was considered in [4] as it corresponds
to investigating the possibility of simulating a probability distribution of a
quantum strategy playing with graph states. The two other levels of contextuality
gain some new perspectives when viewed as games: indeed the possibilistic
contextuality coincides with the fact that the players cannot give all the good
answers with non zero probability using classical local strategies, and strong
contextuality just means that classical players cannot win the game (even by
giving a strict subset of the good answers).
Definition 2. An interpretation p : {0, 1}V × {0, 1}V → [0, 1] is k-multipartite
if it can be obtained by a strategy without communication using nonlocal boxes
that are at most k-partite: for any set I ⊂ V with |I| ≤ k, each player has access
to one bit of a variable λI (aI |xI ) that has a no-signaling probability distribution.
In other words, a k-multipartite interpretation can be obtained with nosignaling correlations involving at most k players. For example the strategy to
win the Mermin game proposed in [10] where each pair among n players share a
(2-partite) non localbox and each player outputs the sum of his boxes’ ouputs
is a 2-multipartite interpretation. Similarly, the result in [8] where they prove
that a probability distribution that can be obtained by 5 players measuring a
quantum state cannot be simulated without communication using any number of
bi-partite non local boxes shows that it is not a 2-multipartite interpretation.5
Definition 3 (multipartiteness width). A scenario has a multipartiteness
width k if it admits a k-multipartite interpretation but no (k − 1)-multipartite
interpretation.
In a contextual scenario, the more hyperedges one adds the less possible
interpretations exist. A scenario has a multipartiteness width k if its hyperedges
already forbids all the interpretations of a product of Bell scenarios on less
than k parties. For a scenario, having a classical interpretation means being
decomposable : one can think of the probability distribution as local actors acting
each on his bit and that’s a classical interpretation. The multipartiteness width
5

The probability distribution described in [8] corresponds to the quantum winning
strategy on the graph state obtained from a cycle with 5 vertices.

measure how non-decomposable a scenario is : it can not be decomposed with
interpretations where each subspace has a small width.
It implies that the players cannot perfectly win the game if they have only
quantum systems on less than k qubits, this corresponds to using k seprable
states as ressources as defined in [19].
Note that from the observations in [4] the multipartiteness width of the
scenario generated by the Paley graph on 13 (see figure 2) is strictly larger than
4.
In the next section, we will show how for the scenarios we describe, being able
to give only good answers allows for simulation of the quantum distribution with
random variables. Thus, the contextuality lies in the combinatorial structure of
the graph and the three levels collapse for these games.

3

Simulating a probability distribution is the same as
winning the pseudo-telepathy graph game

In [4] it was proven that for some graphs, the probability distributions of the
quantum strategy using the graph states cannot be simulated using non local
boxes on less than k parties, we show here that any strategy that allows to win
the game can be extended using random variables shared between neighbors (in
the graph) to simulate this uniform probability distribution coming from the
quantum strategy.
We start by describing a classical strategy CStrat based on shared random
variables rather than quantum states. We show that CStrat is a winning strategy
if and only if the graph is bi-partite. We also show that CStrat can be used to
make any winning strategy a uniform winning strategy, i.e. each valid answer to
a given question are equiprobable. We show that CStrat can be locally adapted
to collaborative games on graphs that can be obtained by a sequence of local
complementations.
Classical strategy (Cstrat): Given a graph G = (V, E), pick uniformly at
V
random
bits (λu , µu ), where
Pλ ∈ {0, 1} . Each player u ∈ V receives a pair of
µu = v∈NG (u) λu mod 2. Given a question x ∈ {0, 1}V , each player u ∈ V
locally computes and answers au = (1 − xu ).λu + xu .µu mod 2.
Lemma 2. Given a graph G = (V, E) and a question x ∈ {0, 1}V , CStrat
produces an answer uniformly at random in {a ∈ {0, 1}V | ∃D ⊆ S, (A ⊕
Odd(A ⊕ D))∩S = ∅ where A = supp(a) and S = supp(x)}.
Proof. Given a graph G = (V, E), a question x ∈ {0, 1}V and a ∈ {0, 1}V , the
probability that CStrat outputs a is
p(a|x) = p (∀u ∈ V \S, au = λu ) p(∀u ∈ S, au =

X

λv mod 2 | ∀u ∈ V \S, au = λu )

v∈N (u)

= p (A \ S = Λ \ S) p(A ∩ S = Odd(Λ) ∩ S|A \ S = Λ \ S)

where S = supp(x), A = supp(a) and Λ = supp(λ). Since p (A \ S = Λ \ S) =
1
,
2n−|x|
p(a|x) =
=

1
2n−|x|

p (A ∩ S = Odd(Λ ∩ S ⊕ Λ \ S) ∩ S|A \ S = Λ \ S)

1
p (A ∩ S = Odd(D ⊕ (A \ S)) ∩ S|A \ S = Λ \ S)
2n−|x|

where D = Λ ∩ S. If A ∩ S 6= Odd(D ⊕ (A \ S)) ∩ S for all D ⊆ S, then p(a|x) = 0.
Otherwise, the set of subsets D of S which satisfy the condition is the affine
space {D0 ⊕ D| D ⊆ S ∧ Odd(D) ∩ S = ∅}, where D0 is a fixed set which satisfies
1
A ∩ S = Odd(D0 ⊕ A \ S) ∩ S. Thus the p(a|x) = 2n−|x|
. |{D⊆S|Odd(D)∩S=∅}|
=
2|x|
|x|−rkG (x)−n
2
, which is independent of a, proving the uniformity of the answer.
Finally notice ∃D0 ⊆ S, A ∩ S = Odd(D0 ⊕ (A \ S)) ∩ S if and only if
∃D1 ⊆ S, (A ⊕ Odd(A ⊕ D1 ))∩S = ∅, by taking D1 = D0 ⊕ (A ∩ S).
t
u
We consider some standard graph transformations : Given a graph G = (V, E)
the local complementation on a vertex u ∈ V produces the graph G ∗ u =
(V, E ⊕ KN (v) ) where the sum is taken modulo 2 (it is the symmetric difference)
and KU is the complete graph on U ⊂ V . G ∗ u is obtained from G by exchanging
the edges by non edges and vice versa in the neighborhood of the vertex u.
Pivoting using an edge (u, v), is a sequence of three local complementations
G ∧ uv = G ∗ u ∗ v ∗ u. We denote by δloc (G) (δpiv (G)) the minimum degree
taken over all graphs that can be obtained from G through some sequence of
local complementations (edge pivots).
Given the shared randomness (λv , µv )v∈V associated with G, if player u
replaces its first bit by the XOR of its two bits, and each of his neighbors replaces
his second bit by the XOR of his two bits, one gets the shared randomness
associated with G ∗ u.
Lemma 3. Given the probability distribution (λv , µv )v∈V associated with G, if
player u replaces its first bit by the XOR of its two bits, and each of its neighbors
replaces their second bit by the XOR of their two bits, one gets the probability
distribution associated with G ∗ u.
(
λu + µu mod 2 if u = v
0
Proof. For any v ∈ V , let λv =
and
λv
otherwise
(
µv + λv mod 2 if v ∈ NG (u)
µ0v =
.
µv
otherwise
(
NG (v) ⊕ NG (u) ⊕ {v} if v ∈ NG (u)
Since NG∗u (v) =
, one gets that for
NG (v)
otherwise
P
P
0
any v ∈
/ NG (u), µ0v = µv =
w∈NG (v) λw mod 2 =P w∈NG∗u (v) λw mod 2
0
and for any v ∈ NG (u), µv = µv + λv = λv + w∈NG (v) λw mod 2 =
P
P
P
λv + µu + w∈NG (v) λ0w mod 2 = λv + w∈NG (u) λ0w + w∈NG (v) λ0w mod 2 =
P
0
t
u
w∈NG∗u (v) λw mod 2.

Thus the probability distribution corresponding to the classical strategy
for G can be locally transformed into the probability distribution associated
with the G ∗ u, thus one can use local complementation to optimise the cost of
preparing the shared randomness. For instance the classical strategy CStrat
for a graph G requires shared random bits on at most ∆loc (G) + 1 players,
where ∆loc (G) = min(∆(G0 ), s.t. ∃u1 , . . . , uk , G0 = G ∗ u1 ∗ . . . ∗ uk ) and ∆(G)
is its maximum degree. If there is no pre-shared random bits, the probability
distribution can be prepared using at most 2|G|loc communications in-between
the players, where |(G)|loc = min(|G0 |, s.t. ∃u1 , . . . , uk , G0 = G ∗ u1 ∗ . . . ∗ uk ) is
the minimum number of edges by local complementation.
Now we show how, using the classical strategy CStrat , one can simulate the
quantum strategy QStrat given an oracle that provides only good answers.
Lemma 4. For any collaborative game on a graph G, for any strategy Q that
never loses, there exists a strategy Q0 using the outputs of Q and shared random
variables that simulate QStrat .
Proof. Given a collaborative graph game on a graph G, let Q be a strategy that
always outputs permissible outputs for any set of inputs x, so we have pairs
(a|x) 6∈ L. We consider the strategy which combines Q and CStrat for this graph:
For a given question x, Q0 outputs the XOR of the Q answer and CStrat answer
for x. First we prove that such an answer is a valid answer and then the uniform
probability among the possible answer to a given question. Given a question
x ∈ {0, 1}V , suppose Q0 outputs a0 ∈ {0, 1}V : ∀u ∈ V , a0u = au +(1−xu )λu +xu µu
where au is the answer produced by Q and λ and µ are as defined in the classical
strategy.
assume (a0 |x) ∈ L, so there exists D involved in x such that
P By contradiction,
0
u∈loc(D) au = |G[D]| + 1 mod 2
X

a0u =

u∈loc(D)

X

(au + (1 − xu )λu + xu µu ) mod 2

u∈loc(D)

=

X
u∈loc(D)

=

X

au +

X
u∈loc(D)

=

X

X

λu +

X
u∈Odd(D)

µu mod 2

u∈loc(D)∩supp(x)

X X

λv mod 2

u∈D v∈N (u)

u∈Odd(D)

au +

X

λu +

u∈loc(D)\supp(x)

u∈loc(D)

=

X

au +

λu +

X

λv mod 2

v∈Odd(D)

au mod 2

u∈loc(D)

Thus (a|x) ∈ L which is a contradiction thus p(a0 |x) = 0 if (a0 |x) ∈ L
Now we prove that p(a0 |x) = 2|x|−n−rkG (x) . First assume Q is
determinist, thus p(a0 |x) is the probability that the classical strategy outputs a + a0 := (au + a0u mod 2)u∈V . Since this probability is

|x|−n−rkG (x)
non
. If Q is probabilistic, p(a0 |x) =
P zero it must be 2
0
≤
a∈{0,1}V p(Q outputs a on x)p(classical strategy outputs a + a on x)
P
|x|−n−rkG (x)
|x|−n−rkG (x)
2
≤ 2
. Thus each
a∈{0,1}V p(Q outputs a on x)
answer a produced by the strategy on a given question x is s.t.
(a|x) ∈
/ L and occurs with probability at most 2|x|−n−rkG (x) . Since
|{a ∈ {0, 1}V | (a|x) ∈
/ L}| = 2|x|−n−rkG (x) , each of the possible answers
is produced by the strategy and occurs with probability 2|x|−n−rkG (x) .
t
u

4

Locally equivalent games

A pseudo telepathy game G locally simulates another pseudo telepathy game G 0
if any winning strategy for G can be locally turned into a winning strategy for G 0 :
Definition 4 (Local Simulation). Given two pseudo telepathy games G and
G 0 on a set V of players which sets of losing pairs are respectively LG and LG 0 ,
G locally simulates G 0 if for all u ∈ V , there exist f1 , . . . , fn : {0, 1} → {0, 1}
and g1 , . . . , gn : {0, 1} × {0, 1} → {0, 1} s.t. ∀x, a ∈ {0, 1}V (g(a, x), x) ∈ LG 0 ⇒
(a|f (x)) ∈ LG where f (x) = (fu (xu ))u∈V and g(a, x) = (gu (au , xu ))u∈V .
Assuming G locally simulates G 0 and that the players have a strategy to win
G, the strategy for G 0 is as follows: given an input x of G 0 , each player u applies
the preprocessing fu turning her input xu into fu (xu ), then they collectively play
the game G with this input f (x) getting an output a s.t. (a|f (x)) ∈
/ LG . Finally
each player u applies a postprocessing gu which depends on her output au and
her initial input xu to produce the output gu (au , xu ) to the game G 0 . This output
is valid since, by contradiction, (g(a, x), x) ∈ LG 0 would imply (a|f (x)) ∈ LG .
Definition 5 (Local Equivalence). G and G 0 are locally equivalent games if
G locally simulates G 0 and G 0 locally simulates G.
In the following we give two examples of locally equivalent games : first we
show that the games associated with the complete graphs are locally equivalent to
Mermin parity games, and then that pivoting, a graph theoretical transformation,
produces a graph game locally equivalent to the original one:
Lemma 5. For any n, the game associated with the complete graph Kn is locally
equivalent to the Mermin parity game on n players.
Proof. The set of losing pairs of the two games are LMermin = {(a|x), 2|a| =
|x| + 2 mod 4} (see example 1 ) and LKn = {(a|x), 2|a| = |x| + 1 mod 4} (see
example 2 ).
[Kn simulates
Mermin] Let u ∈ V be a fixed (
player. We define for all v ∈ V ,
(
1 − xv if v = u
av + xv − 2av xv if v = u
fv (xv ) =
and gv (av , xv ) =
. If
xv
otherwise
av
otherwise
(g(a, x), x) ∈ LMermin then 2|g(a, x)| = |x|+2 mod 4 which implies 2(|a|−au +au +
xu −2au xu ) = 2|a|+2xu = |x|+2 mod 4, so 2|a| = |x|+2−2xu = |f (x)|+1 mod 4,
thus (a|f (x)) ∈ LKn .

[Mermin simulates Kn ] Let u ∈ V be a fixed player. f and g are defined like in
the previous case except gu (au , xu ) = 1 − au − xu + 2au xu . If (g(a, x), x) ∈ LKn
then 2|g(a, x)| = |x| + 1 mod 4 which implies 2(|a| − au + 1 − au − xu + 2au xu ) =
2|a| + 2 − 2xu = |x| + 1 mod 4, so 2|a| = |x| + 1 − 2xu + 2 = |f (x)| + 2 mod 4,
thus (a|f (x)) ∈ LMermin .
t
u
Lemma 6. Given a graph G = (V, E) and (u, v) ∈ E, the games associated with
G and G ∧ uv are locally equivalent.
Proof. Since pivoting is its self inverse ((G ∧ uv) ∧ uv = G) it is enough to prove
that G locally simulates G ∧ uv. The proof is based on the existence of a quantum
strategy for any graph G which consists in sharing the quantum state |Gi, and
for each player w, in measuring her qubit according to X if xw = 1 or according
to Z if xw = 0, and then output the outcome aw ∈ {0, 1} of this measurement.
A quantum strategy for G can be turned into a quantum strategy for G ∧ uv due
to the following property of graph states: |G ∧ uvi = Hu,v ZN (u)∩N (v) |Gi [27].
The unitary map H exchanges X- and Z- measurements – i.e. for any state
|φi, apply H on |φi followed by a Z-measurement (resp. X) produces the same
classical outcome as measuring |φi according to X (resp. Z) – while the unitary
Z leaves invariant the classical outcomes of a Z-measurement and exchanges
the two possible outcomes of a X-measurement. As a consequence, (g(a, x), x) ∈
L
(G∧uv ⇒ (a|f (x)) ∈ LG , where f and
( g are defined as follows fw (xw ) =
1−xw if w∈{u, v}
aw +xw −2aw xw if w∈N (u)∩N (v)
and gw (aw , xw ) =
xw
otherwise
aw
otherwise
t
u
Therefore, the important quantity for the pre-shared randomness for the strategies defined with a graph is ∆piv (G) = min{∆(G0 ), G0 pivot equivalent to G}.

5

Scenarios with linear multipartiteness width

We prove that there exist contextuality scenarios with linear multipartiteness
width. We use a graph property called k-odd domination which is related [4]
to the classical simulation of the quantum probability distribution obtained by
playing the associated graph game. Since bipartite graphs correspond to graph
games that can be won classically [4], we focus on the non-bipartite case by
showing that there exist non-bipartite 0.11n-odd dominated graphs of order n.
Definition 6 (k-odd domination
[4]). A graph G = (V, E) is k-odd dominated

(k-o.d.) iff for any S ∈ Vk , there exists a labelling of the vertices in S =
{v1 , . . . , vk } and C1 , . . . Ck , s.t. ∀i, Ci ⊆ V \ S and Odd(Ci ) ∩ {vi , . . . vk } = {vi }
and Ci ⊆ Even(Ci ).
Lemma 7. For any k ≥ 0, r ≥ 0 and any graph G = (V, E) a graph of order
n having two distinct independent sets V0 and V1 of order |V0 | = |V1 | = b n−r
2 c,
G is k-odd dominated if for any i ∈ {0, 1}, and any non-empty D ⊆ V \ Vi ,
|OddG (D) ∩ Vi | > k − |D|

Proof. Given S0 ⊆ V0 , S1 ⊆ V1 , and S2 ⊆ V2 = V \(V0 ∪V1 ) s.t. |S0 |+|S1 |+|S2 | =
k, we show that for any u ∈ S = S0 ∪ S1 ∪ S2 , there exists Cu ⊆ V \ S s.t.
Odd(Cu ) ∩ S = {u} and Cu ⊆ Even(Cu ). For any u ∈ S, there exists i ∈ {0, 1}
s.t. u ∈ Si ∪ S2 . Let Li : 2Si ∪S2 → 2V1−i \S1−i be the function which maps
D ⊆ Si ∪ S2 to Li (D) = OddG (D) ∩ (V1−i \ S1−i ).
Li is linear according to the symmetric difference. Li is injective: for any
D ⊆ Si ∪ S2 , Odd(D) ∩ (V1−i \ S1−i ) = ∅ implies Odd(D) ∩ V1−i ⊆ S1−i , thus
|Odd(D) ∩ V1−i | ≤ |S1−i |. notice that |D| ≤ |Si | + |S2 |, so |Odd(D) ∩ V1−i | ≤
|S1−i | ≤ |S0 | + |S1 | + |S2 | − |D| = k − |D|, so D = ∅.
The matrix representing Li is nothing but the submatrix Γ[Si ∪S2 ,V1−i \S1−i ]
of the adjacency matrix Γ of G. So its transpose Γ[V1−i \S1−i ,Si ∪S2 ] is surjective
which means that the corresponding linear map LTi : 2V1−i \S1−i → 2Si ∪S2 = C 7→
OddG (C) ∩ (V1−i \ S1−i ) is surjective, so ∃Cu ⊆ V1−i \ S1−i s.t. OddG (Cu ) ∩ (Si ∪
S2 ) = {u}, which implies, since V1−i is an independent set, that OddG (Cu ) ∩ S =
{u} and Cu ⊆ Even(Cu ).
t
u
Theorem 1. For any even n > n0 , there exists a non-bipartite b0.110nc-odd
dominated graph of order n.
Proof. Given n, r ≤ n s.t. r = n mod 2, and k ≥ 0. Let p = (n − r)/2, and
let G = (V0 ∪ V1 ∪ V2 , E) s.t. |V0 | = |V1 | = p, |V2 | = r be a random graph on
n vertices s.t. for any u ∈ Vi , v ∈ Vj there is an edge between u and v with
probability 0 if i = j and with probability 1/2 otherwise.
(i)
For any i ∈ {0, 1}, and any non empty D ⊆ V \ Vi s.t. |D| ≤ k, let AD be
the bad event |OddG (D) ∩ Vi | ≤ k − |D|. Since each vertex of Vi is in OddG (D)
k−|D|
Pk−|D| p −p
(i)
with probability 1/2, P r(AD ) = j=0
≤ 2p[H( p )−1] .
j 2
Another bad event is that G is bipartite which occurs with probability less
than ( 78 )pr . Indeed, the probability that given u ∈ V0 , v ∈ V1 , w ∈ V2 , (u, v, w)
do not form a triangle is 78 , so given a bijection f : V0 → V1 , the probability that
∀u ∈ V0 , ∀w ∈ V2 , (u, f (u), w) do not form a triangle is ( 78 )pr .
Let X be the number of bad events.
 k−d  
k 
X
7
p + r X p −p
2 + ( )pr
E[X] = 2
j
d
8
j=0
d=1

≤2

k
X

d

2(p+r)H( p+r )+pH(

k−d
p )−p

d=1

≤2

k
X
d=1

d

2pH( p+r )+pH(

k−d
p )−p+r

7
+ ( )pr
8
7
+ ( )pr
8

d
The function d 7→ pH( p+r
) + pH( k−d
p ) − p + r is maximal for d =
k
2pH( 2p+r
)−p+r

k(p+r)
2p+r .

Thus,

E[X] ≤ 2k2
+ ( 78 )pr .
By taking r = 1, and k = 0.11n = 0.11(2p + 1), E[X] < 1 when p large
enough, thus G has no bad event with a non zero probability.
t
u

Corollary 1. There exist contextuality scenarios with linear multipartiteness
width: for any even n > n0 , there exist graph games on n players producing
contextuality scenarios of multipartiteness width at least b0.11nc.
Proof. Using the result from [4], for any non bipartite graph of order n being 0.11no.d ensures that the probability distribution obtained by using the quantum
strategy cannot be simulated using non local boxes involving at most 0.11n
parties. Thus lemma 4 allows to conclude that the associated pseudo-telepathy
game cannot be won classically. Therefore there is no interpretation that is
k-multipartite with k < 0.11n which means that the contextuality scenario has
linear width.
t
u

6

Conclusion

We have shown that there exist graphs with linear multipartiteness width, however
the proof is non constructive and the best known bound for explicit families
is logarithmic.A natural future direction of research would be to find explicit
families with linear multipartiteness width or to improve the bounds proven
for the Paley graph states. An other important question is to consider lower
bounds for the scenarios associated with the graph games.A promising area of
investigation for multipartite scenarios is: what happens if we limit the width
of shared randomness? Indeed, for the proof of how winning the game allows to
simulate the quantum probability distributions, one needs only shared random
variables that are correlated in local neighborhoods in the graph. One can
also consider the link with building entanglement witnesses for graph states,
generalizing the construction of [21]. It would be also very interesting to link the
multipartiteness width with the structures of the groups of the associated binary
linear system defining the two-player bipartite non-local games [28]. Finally, one
can expect that the multipartiteness width of the Paley graph states might have
cryptographic applications to ensure security against cheating for some protocols
for example.

References
1. S. Abramsky and A. Brandenburger The sheaf theoretic structure of non locality
and contextuality. New Journal of Physics 13 113036 (2011)
2. S. Abramsky, R.S. Barbosa and S. Mansfield Quantifying contextuality via linear
programming, Informal Proceedings of Quantum Physics & Logic, (2016)
3. A. Acı́n, T. Fritz, A. Leverrier, and A. Belén Sainz A combinatorial approach to
nonlocality and contextuality. Comm. Math. Phys. 334(2), 533-628 (2015)
4. A. Anshu and M. Mhalla Pseudo-telepathy games and genuine NS k-way nonlocality
using graph states Quantum Information and Computation, Vol. 13, No. 9, 10
0833-0845 Rinton Press (2013)
5. A. Badanidiyuru, J. Langford, A. Slivkins Resourceful Contextual Bandits.
http://arxiv.org/abs/1402.6779, COLT (2014)
6. J. Barrett, S. Pironio, J. Bancal and N. Gisin, The definition of multipartite
nonlocality. Phys. Rev. A 88, 014102 (2013)

7. J.S. Bell On the Einstein-Podolsky-Rosen paradox. Physics 1 195-200 (1964)
8. J. Barrett and S. Pironio, Popescu-Rohrlich correlations as a unit of nonlocality.
Phys. Rev. Lett. 95, 140401, (2005)
9. G. Brassard, A. Broadbent and A. Tapp Multi-Party Pseudo-Telepathy 8th International Workshop, WADS 2003, Ottawa, Ontario, Canada, July 30 - August 1,
Proceedings (2003).
10. A. Broadbent and A. A. Methot, On the power of non-local boxes Theoretical
Computer Science C 358: 3-14, (2006)
11. B. Coecke From quantum foundations via natural language meaning to a theory of
everything. arXiv:1602.07618v1 (2016)
12. E. Dzhafarov , S. Jordan , R. Zhang , V. Cervante Contextuality from Quantum
Physics to Psychology. Advanced Series on Mathematical Psychology: Volume 6
(2016)
13. D. J. Foulis and C. H. Randall, Empirical logic and tensor products. J. Mathematical
Phys. 5 , 9:20. MR683888. (1981)
14. T. Fritz, A. B. Sainz, R. Augusiak, J. Bohr Brask, R. Chaves, A. Leverrier, and A.
Acı́n Local orthogonality as a multipartite principle for quantum correlations Nature
Communications 4, 2263 (2013)
15. A. Grudka, K. Horodecki, M. Horodecki, P. Horodecki, R. Horodecki, P. Joshi, W.
Klobus, A. Wójcik Quantifying contextuality Phys. Rev. Lett. 112, 120401 (2014)
16. D. M. Greenberger, M. A. Horne, A. Shimony, and A. Zeilinger, Bell’s theorem
without inequalities. American Journal of Physics 58 , 1131.(1990)
17. P. Gnaciński, M. Rosicka, R. Ramanathan, K. Horodecki, M. Horodecki, P.
Horodecki, S. Severini Linear game non-contextuality and Bell inequalities - a
graph-theoretic approach. e-print arXiv:1511.05415 Nov (2015)
18. C. Godsil, G. Royle. Algebraic graph theory, volume 207 of Graduate Texts in
Mathematics. volume 207 of Graduate Texts in Mathematics - Springer-Verlag,
(2001)
19. O. Gühne, G.Tóth, H.J. Briegel Multipartite entanglement in spin chains. New
Journal of Physics, 7(1), 229. (2005)
20. L. Hardy Nonlocality for two particles without inequalities for almost all entangled
states. Physical Review Letters 71 , 1665:1668.(1993)
21. M. Hein,W. Dür, J. Eisert, R. Raussendorf, M. Nest and H. J. Briegel Entanglement
in graph states and its applications. arXiv preprint quant-ph/0602096. (2006)
22. M. Howard, J.J. Wallman, V. Veitch and J. Emerson Contextuality supplies the
”magic” for quantum computation. Nature 510, 351-355 (2014)
23. V. Kumar. Algorithms for constraint-satisfaction problems: A survey. AI magazine,
13(1):32, (1992).
24. R. Luce and H. Rai. Games and Decisions: Introduction and Critical Survey.
Doverbooks on advanced mathematics, Dover Publications (1957)
25. Y.-C.Liang, D. Rosset, J-D. Bancal, G.Pütz, T.J. Barnea and N. Gisin Family of
Bell-like inequalities as device-independent witnesses for entanglement depth. Physical
review letters, 114(19), 190401. (2015)
26. N. D. Mermin, Extreme quantum entanglement in a superposition of macroscopically
distinct states. Physical Review Letters, 65(15):1838-1849, (1990).
27. M. Mhalla and S. Perdrix Graph States, Pivot Minor, and universality of (X-Z)
Measurements. IJUC 9 (1-2) : 153-171, (2013).
28. W. Slofstra Tsirelson’s problem and an embedding theorem for groups arising from
non-local games e-print arXiv:1606.03140 (2106)
29. N. Pflueger. Graph reductions, binary rank, and pivots in gene assembly. Discrete
Applied Mathematics, 2011.

30. W. Zeng and P. Zahg, Contextuality and the weak axiom of the theory of choice
Quantum Interactions proc. Volume 9535 of the series Lecture Notes in Computer
Science pp 24-35, (2016)

Acknowledgements.
We would like to thanks an anonymous reviewer for noticing a mistake in an
earlier version and helpful comments.

