Genuinely Multipartite Noncausality
Alastair A. Abbott
1
, Julian Wechs
1
, Fabio Costa
2
, and Cyril Branciard
1
1
University Grenoble Alpes, CNRS, Grenoble INP, Institut Néel, 38000 Grenoble, France
2
Centre for Engineered Quantum Systems, School of Mathematics and Physics, The University of Queensland, St Lucia, QLD 4072,
Australia
December 7, 2017
The study of correlations with no definite
causal order has revealed a rich structure
emerging when more than two parties are in-
volved. This motivates the consideration of
multipartite “noncausal” correlations that can-
not be realised even if noncausal resources are
made available to a smaller number of parties.
Here we formalise this notion: genuinely N-
partite noncausal correlations are those that
cannot be produced by grouping N parties
into two or more subsets, where a causal or-
der between the subsets exists. We prove that
such correlations can be characterised as ly-
ing outside a polytope, whose vertices corre-
spond to deterministic strategies and whose
facets define what we call “2-causal” inequal-
ities. We show that genuinely multipartite
noncausal correlations arise within the process
matrix formalism, where quantum mechanics
holds locally but no global causal structure is
assumed, although for some inequalities no vi-
olation was found. We further introduce two
refined definitions that allow one to quantify,
in different ways, to what extent noncausal
correlations correspond to a genuinely multi-
partite resource.
1 Introduction
Understanding the correlations between events, or be-
tween the parties that observe them, is a central ob-
jective in science. In order to provide an explanation
for a given correlation, one typically refers to the no-
tion of causality and embeds events (or parties) into a
causal structure, that defines a causal order between
them [1, 2]. Correlations that can be explained in
such a way, i.e., that can be established according to
a definite causal order, are said to be causal [3].
The study of causal correlations has gained a lot
of interest recently as a result of the realisation that
more general frameworks can actually be considered,
where the causal assumptions are weakened and in
which noncausal correlations can be obtained [4]. In-
vestigations of causal versus noncausal correlations
first focused on the simplest bipartite case [4, 5], and
were soon extended to multipartite scenarios, where
a much richer situation is found [69]—this opens, for
instance, the possibility for causal correlations to be
established following a dynamical causal order, where
the causal order between events may depend on events
occurring beforehand [10]. When analysing noncausal
correlations in a multipartite setting, however, a nat-
ural question arises: is the noncausality of these cor-
relations a truly multipartite phenomenon, or can it
be reduced to a simpler one, that involves fewer par-
ties? The goal of this paper is precisely to address this
question, and provide criteria to justify whether one
really deals with genuinely multipartite noncausality
or not.
To make things more precise, let us start with
the case of two parties, A and B. Each party re-
ceives an input x, y, and returns an output a, b, re-
spectively. The correlations shared by A and B are
described by the conditional probability distribution
P (a, b|x, y). If the two parties’ events (returning an
output upon receiving an input) are embedded into
a fixed causal structure, then one could have that A
causally precedes B—a situation that we shall denote
by A B, and where B’s output may depend on A’s
input but not vice versa: P (a|x, y) = P (a|x)—or that
B causally precedes AB A, where P (b|x, y) =
P (b|y). (It can also be that the correlation is not due
to a direct causal relation between A and B, but to
some latent common cause; such a situation is how-
ever still compatible with an explanation in terms of
A B or B A, and is therefore encompassed in the
previous two cases.) A causal correlation is defined as
one that is compatible with either A B or B A, or
with a convex mixture thereof, which would describe
a situation where the party that comes first is selected
probabilistically in each run of the experiment [3, 4].
Adding a third party C with input z and output c,
and taking into account the possibility of a dynamical
causal order, a tripartite causal correlation is defined
as one that is compatible with one party acting first—
which one it is may again be chosen probabilistically—
and such that whatever happens with that first party,
the reduced bipartite correlation shared by the other
two parties, conditioned on the input and output of
the first party, is causal (see Definition 1 below for
a more formal definition, and its recursive generalisa-
tion to N parties) [8, 9]. In contrast, a noncausal tri-
Accepted in Quantum 2017-12-06, click title to verify 1
arXiv:1708.07663v2 [quant-ph] 13 Dec 2017
partite correlation P (a, b, c|x, y, z) cannot for instance
be decomposed as
P (a, b, c|x, y, z) = P (a|x) P
x,a
(b, c|y, z) (1)
with bipartite correlations P
x,a
(b, c|y, z) that are
causal for each x, a. Nevertheless, such a decompo-
sition may still be possible for a tripartite noncausal
correlation if one does not demand that (all) the bi-
partite correlations P
x,a
(b, c|y, z) are causal. Without
this constraint, the correlation (1) is thus compatible
with the “coarse-grained” causal order A {B, C},
if B and C are grouped together to define a new “ef-
fective party” and act “as one”. This illustrates that
although a multipartite correlation may be noncausal,
there might still exist some definite causal order be-
tween certain subsets of parties; the intuition that mo-
tivates our work is that such a correlation would there-
fore not display genuinely multipartite noncausality.
This paper is organised as follows. In Sec. 2, we in-
troduce the notion of genuinely N-partite noncausal
correlations in opposition to what we call 2-causal
correlations, which can be established whenever two
separate groups of parties can be causally ordered;
we furthermore show how such correlations can be
characterised via so-called 2-causal inequalities. In
Sec. 3, as an illustration we analyse in detail the sim-
plest nontrivial tripartite scenario where these con-
cepts make sense; we present explicit 2-causal inequal-
ities for that scenario, investigate their violations in
the process matrix framework of Ref. [4], and gener-
alise some of them to N-partite inequalities. In Sec. 4,
we propose two possible generalisations of the notion
of 2-causal correlations, which we call M -causal and
size-S-causal correlations, respectively. This allows
one to refine the analysis, and provides two differ-
ent hierarchies of criteria that quantify the extent to
which the noncausality of a correlation is a genuinely
multipartite phenomenon.
2 Genuinely N -partite noncausal cor-
relations
The general multipartite scenario that we consider in
this paper, and the notations we use, are the same as
in Ref. [9]. A finite number N 1 of parties A
k
each
receive an input x
k
from some finite set (which can
in principle be different for each party) and generate
an output a
k
that also belongs to some finite set (and
which may also differ for each input). The vectors of
inputs and outputs are denoted by ~x = (x
1
, . . . , x
N
)
and ~a = (a
1
, . . . , a
N
). The correlations between the
N parties are given by the conditional probability
distribution P(~a|~x). For some (nonempty) subset
K = {k
1
, . . . , k
|K|
} of N
:
= {1, . . . , N }, we denote
by ~x
K
= (x
k
1
, . . . , x
k
|K|
) and ~a
K
= (a
k
1
, . . . , a
k
|K|
)
the vectors of inputs and outputs of the parties in K;
with this notation, ~x
N \K
and ~a
N \K
(or simply ~x
N \k
and ~a
N \k
for a singleton K = {k}) denote the vectors
of inputs and outputs of all parties that are not in K.
For simplicity we will identify the parties’ names with
their labels, so that N = {1, . . . , N } {A
1
, . . . , A
N
},
and similarly for any subset K.
2.1 Definitions
The assumption that the parties in such a scenario
are embedded into a well-defined causal structure re-
stricts the correlations that they can establish. In
Refs. [8, 9], the most general correlations that are
compatible with a definite causal order between the
parties were studied and characterised. Such correla-
tions include those compatible with causal orders that
are probabilistic or dynamical—that is, the operations
of parties in the past can determine the causal order
of parties in the future. These so-called causal cor-
relations—which, for clarity, we shall often call fully
causal here—can be defined iteratively in the follow-
ing way:
Definition 1 ((Fully) causal correlations).
For N = 1, any valid probability distribution
P (a
1
|x
1
) is (fully) causal;
For N 2, an N-partite correlation is (fully)
causal if and only if it can be decomposed in the
form
P (~a|~x) =
X
k∈N
q
k
P
k
(a
k
|x
k
) P
k,x
k
,a
k
(~a
N \k
|~x
N \k
)
(2)
with q
k
0 for each k,
P
k
q
k
= 1,
where (for each k) P
k
(a
k
|x
k
) is a single-party
probability distribution and (for each k, x
k
, a
k
)
P
k,x
k
,a
k
(~a
N \k
|~x
N \k
) is a (fully) causal (N1)-
partite correlation.
As the tripartite example in the introduction shows,
there can be situations in which no overall causal or-
der exists, but where there still is a (“coarse-grained”)
causal order between certain subsets of parties, ob-
tained by grouping certain parties together. The cor-
relations that can be established in such situations
are more general than causal correlations, but never-
theless restricted due to the existence of this partial
causal ordering. If we want to identify the idea of
noncausality as a genuinely N-partite phenomenon,
we should, however, exclude such correlations, and
characterise correlations for which no subset of par-
ties can have a definite causal relation to any other
subset. This idea was already suggested in Ref. [9];
here we define the concept precisely.
Note that if several different nonempty subsets do
have definite causal relations to each other, then
clearly there will be two subsets having a definite
causal relation between them—one can consider the
subset that comes first and group the remaining sub-
sets together into the complementary subset, which
Accepted in Quantum 2017-12-06, click title to verify 2
then comes second. We shall for now consider parti-
tions of N into just two (nonempty) subsets K and
N \K, and we thus introduce the following definition:
Definition 2 (2-causal correlations). An N -partite
correlation (for N 2) is said to be 2-causal if and
only if it can be decomposed in the form
P (~a|~x) =
X
(K(N
q
K
P
K
(~a
K
|~x
K
)P
K,~x
K
,~a
K
(~a
N \K
|~x
N \K
)
(3)
where the sum runs over all nonempty strict subsets K
of N , with q
K
0 for each K,
P
K
q
K
= 1, and where
(for each K) P
K
(~a
K
|~x
K
) is a valid probability distri-
bution for the parties in K and (for each K, ~x
K
,~a
K
)
P
K,~x
K
,~a
K
(~a
N \K
|~x
N \K
) is a valid probability distribu-
tion for the remaining N −|K| parties.
For N = 2, the above definition reduces to the stan-
dard definition of bipartite causal correlations [4],
which is equivalent to Definition 1 above. In
the general multipartite case, it can be understood
in the following way: each individual summand
P
K
(~a
K
|~x
K
)P
K,~x
K
,~a
K
(~a
N \K
|~x
N \K
) for each bipartition
{K, N \K} describes correlations compatible with all
the parties in K acting before all the parties in N \K,
since the choice of inputs for the parties in N \K does
not affect the outputs for the parties in K. The con-
vex combination in Eq. (3) then takes into account
the possibility that the subset K acting first can be
chosen randomly.
1
For correlations that are not 2-causal, we introduce
the following terminology:
Definition 3 (Genuinely N-partite noncausal corre-
lations). An N-partite correlation that is not 2-causal
is said to be genuinely N -partite noncausal.
Thus, genuinely N-partite noncausal correlations are
those for which it is impossible to find any defi-
nite causal relation between any two (complementary)
subsets of parties, even when taking into considera-
tion the possibility that the subset acting first may
be chosen probabilistically.
2.2 Characterisation of the set of 2-causal cor-
relations as a convex polytope
As shown in Ref. [5] for the bipartite case and in
Refs. [8, 9] for the general N-partite case, any fully
1
One can easily see that it is indeed sufficient to
consider just one term per bipartition {K, N \K} in the
sum (3). That is, for some given K, some corre-
lations P
0
(~a|~x) = P
0
K
(~a
K
|~x
K
) P
0
K,~x
K
,~a
K
(~a
N \K
|~x
N \K
) and
P
00
(~a|~x) = P
00
K
(~a
K
|~x
K
) P
00
K,~x
K
,~a
K
(~a
N \K
|~x
N \K
), and some
weights q
0
, q
00
0 with q
0
+ q
00
= 1, the convex mix-
ture P (~a|~x) = q
0
P
0
(~a|~x) + q
00
P
00
(~a|~x) is also of the same
form P (~a|~x) = P
K
(~a
K
|~x
K
) P
K,~x
K
,~a
K
(~a
N \K
|~x
N \K
) (with
P
K
(~a
K
|~x
K
) = q
0
P
0
K
(~a
K
|~x
K
) + q
00
P
00
K
(~a
K
|~x
K
) and P
K,~x
K
,~a
K
=
P (~a|~x)/P
K
(~a
K
|~x
K
)). This already implies, in particular, that
2-causal correlations form a convex set.
causal correlation can be written as a convex combina-
tion of deterministic fully causal correlations. As the
number of such deterministic fully causal correlations
is finite (for finite alphabets of inputs and outputs),
they correspond to the extremal points of a convex
polytope—the (fully) causal polytope. The facets of
this polytope are given by linear inequalities, which
define so-called (fully) causal inequalities.
As it turns out, the set of 2-causal correlations can
be characterised as a convex polytope in the same
way:
Theorem 4. The set of 2-causal correlations forms a
convex polytope, whose (finitely many) extremal points
correspond to deterministic 2-causal correlations.
Proof. For a given nonempty strict subset K of N ,
P
K
(~a
K
|~x
K
)P
K,~x
K
,~a
K
(~a
N \K
|~x
N \K
) defines an “effec-
tively bipartite” correlation, that is, a bipartite cor-
relation between an effective party K with input ~x
K
and output ~a
K
and an effective party N \K with input
~x
N \K
and output ~a
N \K
, which are formed by group-
ing together all parties in the respective subsets. That
effectively bipartite correlation is compatible with the
causal order
2
K N \K. As mentioned above, the set
of such correlations forms a convex polytope whose
extremal points are deterministic, effectively bipar-
tite causal correlations [5]—which, according to Defi-
nition 2, define deterministic 2-causal N-partite cor-
relations.
Eq. (2) then implies that the set of 2-causal cor-
relations is the convex hull of all such polytopes for
each nonempty strict subset K of N ; it is thus itself
a convex polytope, whose extremal points are indeed
deterministic 2-causal correlations.
As any fully causal correlation is 2-causal, but not
vice versa, the fully causal polytope is a strict subset
of what we shall call the 2-causal polytope (see Fig. 1).
Every vertex of the 2-causal polytope corresponds to a
deterministic function ~α that assigns a list of outputs
~a = ~α(~x) to the list of inputs ~x, such that the corre-
sponding probability distribution P
det
~α
(~a|~x) = δ
~a,~α(~x)
is 2-causal, and thus satisfies Eq. (3). Since P
det
~α
(~a|~x)
can only take values 0 or 1, there is only one term
in the sum in Eq. (3), and it can be written such
that there is a single (nonempty) strict subset K that
acts first. That is, ~α is such that the outputs ~a
K
of
the parties in K are determined exclusively by their
inputs ~x
K
, while the outputs ~a
N \K
of the remaining
parties are determined by all inputs ~x. The facets
of the 2-causal polytope are linear inequalities that
2
The notation K
1
K
2
(or simply A
k
1
A
k
2
for sin-
gletons K
j
= {A
k
j
}), already used in the introduction, for-
mally means that the correlation under consideration satis-
fies P (~a
K
1
|~x) = P (~a
K
1
|~x
N \K
2
). It will also be extended to
more subsets, with K
1
K
2
· · · K
m
meaning that
P (~a
K
1
∪···∪K
j
|~x) = P (~a
K
1
∪···∪K
j
|~x
N \(K
j+1
∪···∪K
m
)
) for all
j = 1, . . . , m 1.
Accepted in Quantum 2017-12-06, click title to verify 3
2-causal
2-causal inequality
(fully) causal
genuinely N-partite
noncausal
not 2-causal
causal inequality
Figure 1: Sketch of the fully causal and 2-causal polytopes
(the shading should be interpreted as indicating that the
latter contains the former). The vertices of the polytopes
correspond to deterministic fully causal and 2-causal corre-
lations, and their facets correspond to causal and 2-causal
inequalities, respectively. Correlations that are outside of the
fully causal polytope are simply noncausal; correlations that
are outside of the 2-causal polytope are genuinely N-partite
noncausal.
are satisfied by all 2-causal correlations; we shall call
these 2-causal inequalities (see Fig. 1).
3 Analysis of the tripartite “lazy sce-
nario”
In this section we analyse in detail, as an illustration,
the polytope of 2-causal correlations for the simplest
nontrivial scenario with more than two parties. In
Ref. [9] it was shown that this scenario is the so-called
tripartite “lazy scenario”, in which each party A
k
re-
ceives a binary input x
k
, has a single constant output
for one of the inputs, and a binary output for the
other. By convention we consider that for each k, on
input x
k
= 0 the output is always a
k
= 0, while for
x
k
= 1 we take a
k
{0, 1}. The set of fully causal
correlations was completely characterised for this sce-
nario in Ref. [9], which will furthermore permit us to
compare the noncausal and genuinely tripartite non-
causal correlations in this concrete example.
As is standard (and as we did in the introduc-
tion), we will denote here the three parties by A,
B, C, their inputs x, y, z, and their outputs a,
b and c. Furthermore, we will denote the com-
plete tripartite probability distribution by P
ABC
[i.e.,
P
ABC
(abc|xyz)
:
= P (abc|xyz)] and the marginal dis-
tributions for the indicated parties by P
AB
, P
A
, etc.
[e.g., P
AB
(ab|xyz) =
P
c
P
ABC
(abc|xyz)].
3.1 Characterisation of the polytope of 2-
causal correlations
3.1.1 Complete characterisation
We characterise the polytope of 2-causal correlations
in much the same way as the polytope of fully causal
correlations was characterised in Ref. [9], where we
refer the reader for a more in-depth presentation.
Specifically, the vertices of the polytope are found
by enumerating all deterministic 2-causal probability
distributions P
ABC
, i.e., those which admit a decom-
position of the form (3) with (because they are deter-
ministic) a single term in the sum (corresponding to
a single group of parties acting first). One finds that
there are 1520 such distributions, and thus vertices.
In order to determine the facets of the polytope,
which in turn correspond to tight 2-causal inequali-
ties, a parametrisation of the 19-dimensional polytope
must be fixed and the convex hull problem solved. We
use the same parametrisation as in Ref. [9], and again
use cdd [11] to compute the facets of the polytope.
We find that the polytope has 21154 facets, each cor-
responding to a 2-causal inequality, the violation of
which would certify genuinely tripartite noncausality.
Many inequalities, however, can be obtained from oth-
ers by either relabelling outputs or permuting parties,
and as a result it is natural to group the inequalities
into equivalence classes, or “families”, of inequalities.
Taking this into account, we find that there are 476
families of facet-inducing 2-causal inequalities, 3 of
which are trivial, as they simply correspond to pos-
itivity constraints on the probabilities (and are thus
satisfied by any valid probability distribution). While
the 2-causal inequalities all detect genuinely N-partite
noncausality, it is interesting to note that all except
22 of them can be saturated by fully causal correla-
tions (and all but 37 even by correlations compatible
with a fixed causal order).
We provide the complete list of these inequalities,
organised by their symmetries and the types of dis-
tribution required to saturate them, in the Supple-
mentary Material [24], and will analyse in more de-
tail a few particularly interesting examples in what
follows. First, however, it is interesting to note that
only 2 of the 473 nontrivial facets are also facets of the
(fully) causal polytope for this scenario (one of which
is Eq. (8) analysed below), and hence the vast major-
ity of facet-inducing inequalities of the causal poly-
tope do not single out genuinely tripartite noncausal
correlations. Moreover, none of the 2-causal inequal-
ities we obtain here differ from facet-inducing fully
causal inequalities only in their bound, and, except
for the aforementioned cases, our 2-causal inequali-
ties thus represent novel inequalities.
Accepted in Quantum 2017-12-06, click title to verify 4
3.1.2 Three interesting inequalities
Of the nontrivial 2-causal inequalities, those that dis-
play certain symmetries between the parties are par-
ticularly interesting since they tend to have compar-
atively simple forms and often permit natural inter-
pretations (e.g., as causal games [4, 5]).
For example, three nontrivial families of 2-causal
inequalities have forms (i.e., certain versions of the
inequality within the corresponding equivalence class)
that are completely symmetric under permutations of
the parties. One of these is the inequality
I
1
=
P
A
(1|100) + P
B
(1|010) + P
C
(1|001)
+
P
AB
(11|110) + P
BC
(11|011) + P
AC
(11|101)
P
ABC
(111|111) 0, (4)
which can be naturally expressed as a causal game.
Indeed, it can be rewritten as
P
˜a
˜
b˜c = xyz
3/4, (5)
where ˜a = 1 if x = 0, ˜a = a if x = 1 (i.e.,
˜a = xa x 1, where denotes addition modulo 2),
and similarly for
˜
b and ˜c, and where it is implicitly as-
sumed that all inputs occur with the same probability.
This can be interpreted as a game in which the goal
is to collaborate such that the product of the nontriv-
ial outputs (i.e., those corresponding to an input 1)
is equal to the product of the inputs, and where the
former product is taken to be 1 if all inputs are 0 and
there are therefore no nontrivial outputs (in which
case the game will always be lost). The probability
of success for this game can be no greater than 3/4 if
the parties share a 2-causal correlation. This bound
can easily be saturated by a deterministic, even fully
causal, distribution: if every party always outputs 0
then the parties will win the game in all cases, except
when the inputs are all 0 or all 1.
Another party-permutation-symmetric 2-causal in-
equality is the following:
I
2
= 1 + 2
P
A
(1|100) + P
B
(1|010) + P
C
(1|001)
P
AB
(11|110) + P
BC
(11|011) + P
AC
(11|101)
0,
(6)
whose interpretation can be made clearer by rewriting
it as
P
A
(1|100) + P
B
(1|010) P
AB
(11|110)
+P
B
(1|010) + P
C
(1|001) P
BC
(11|011)
+P
A
(1|100) + P
C
(1|001) P
AC
(11|101) 1. (7)
The left-hand side of this inequality is simply the
sum of three terms corresponding to conditional “lazy
guess your neighbour’s input” (LGYNI) inequali-
ties [9], one for each pair of parties (conditioned on
the remaining party having input 0), while the neg-
ative bound on the right-hand side accounts for the
fact that any pair of parties that are grouped together
in a bipartition may maximally violate the LGYNI in-
equality between them (and thus reach the minimum
algebraic bound 1). This inequality can be inter-
preted as a “scored game” (as opposed to a “win-or-
lose game”) in which each pair of parties scores one
point if they win their respective bipartite LGYNI
game and the third party’s input is 0, and where the
goal of the game is to maximise the total score, given
by the sum of all three pairs’ individual scores. The
best average score (when the inputs are uniformly dis-
tributed) for a 2-causal correlation is 5/4, correspond-
ing to the 2-causal bounds of 0 in Eq. (6) and 1 in
Eq. (7).
3
It is also clear from the form of Eq. (7)
that for fully causal correlations the left-hand side is
lower-bounded by 0. This inequality is thus amongst
the 22 facet-inducing 2-causal inequalities that cannot
be saturated by fully causal distributions.
In addition to the inequalities that are symmetric
under any permutation of the parties, there are four
further nontrivial families containing 2-causal inequal-
ities which are symmetric under cyclic exchanges of
parties. One interesting such example is the follow-
ing:
I
3
= 2 + [P
A
(1|100) + P
B
(1|010) + P
C
(1|001)
P
A
(1|101) + P
B
(1|110) + P
C
(1|011)
0. (8)
This inequality can again be interpreted as a causal
game in the form (where we again implicitly assume
a uniform distribution of inputs for all parties)
P
x(y 1)(a z) = y(z 1)(b x)
= z(x 1)(c y) = 0
7/8, (9)
where the goal of the game is for each party, whenever
they receive the input 1 and their right-hand neigh-
bour has the input 0, to output the input of their
left-hand neighbour (with C being considered, in a
circular manner, to be to the left of A).
4
This in-
equality is of additional interest as it is one of the two
nontrivial inequalities which is also a facet of the stan-
dard causal polytope for this scenario. (The second
such inequality, which lacks the symmetry of this one,
is presented in the Supplementary Material [24].)
3
The bound of these inequalities, and the best average
score of the corresponding game, can be reached by a 2-causal
strategy in which one party, say A, has a fixed causal or-
der with respect to the other two parties grouped together,
who share a correlation maximally violating the corresponding
LGYNI inequality. For example, the distribution P (abc|xyz) =
δ
a,0
δ
b,yz
δ
c,yz
, where δ is the Kronecker delta function, is com-
patible with the order A {B, C} (or with {B, C} A) and
saturates Eqs. (6) and (7).
4
The bound of 7/8 on the probability of success can, for
instance, be reached by the fully causal (and hence 2-causal)
distribution P (abc|xyz) = δ
a,x
δ
b,xy
δ
c,yz
, compatible with the
order A B C, which wins the game in all cases except
when (x, y, z) = (1, 0, 0).
Accepted in Quantum 2017-12-06, click title to verify 5
3.2 Violations of 2-causal inequalities by pro-
cess matrix correlations
One of the major sources of interest in causal inequal-
ities has been the potential to violate them in more
general frameworks, in which causal restrictions are
weakened. There has been a particular interest in one
such model, the process matrix formalism, in which
quantum mechanics is considered to hold locally for
each party, but no global causal order between the
parties is assumed [4]. In this framework, the (pos-
sibly noncausal) interactions between the parties are
described by a process matrix W , which, along with
a description of the operations performed by the par-
ties, allows the correlations P (~a|~x) to be calculated.
It is well-known that process matrix correlations
can violate causal inequalities [47, 9], although the
physical realisability of such processes remains an
open question [12, 13]. In Ref. [9] it was shown that all
the nontrivial fully causal inequalities for the tripar-
tite lazy scenario can be violated by process matrices.
However, for most inequalities violation was found to
be possible using process matrices W
{A,B}≺C
that are
compatible with C acting last, which means the cor-
relations they produced were necessarily 2-causal. It
is therefore interesting to see whether process matri-
ces are capable of violating 2-causal inequalities in
general, and thus of exhibiting genuinely N-partite
noncausality. We will not present the process ma-
trix formalism here, and instead simply summarise
our findings; we refer the reader to Refs. [4, 14] for
further details on the technical formalism.
Following the same approach as in Refs. [5, 9]
we looked for violations of the 2-causal inequalities.
Specifically, we focused on two-dimensional (qubit)
systems and applied the same “see-saw” algorithm to
iteratively perform semidefinite convex optimisation
over the process matrix and the instruments defining
the operations of the parties.
As a result, we were able to find process matrices
violating all but 2 of the 473 nontrivial families of
tight 2-causal inequalities (including Eqs. (4) and (8)
above) using qubits, and in all cases where a violation
was found, the best violation was given by the same
instruments that provided similar results in Ref. [9].
We similarly found that 284 families of these 2-causal
inequalities (including Eq. (8)) could be violated by
completely classical process matrices,
5
a phenomenon
that is not present in the bipartite scenario where clas-
sical processes are necessarily causal [4].
While the violation of 2-causal inequalities is again
rather ubiquitous, the existence of two inequalities for
which we found no violation is curious. One of these
inequalities is precisely Eq. (6), and its decomposition
5
Incidentally, exactly the same number of families of fully
causal inequalities were found to be violable with classical pro-
cess matrices in Ref. [9]. It remains unclear whether this is
merely a coincidence or the result of a deeper connection.
in Eq. (7) into three LGYNI inequalities helps provide
an explanation. In particular, the seemingly best pos-
sible violation of a (conditional) LGYNI inequality us-
ing qubits is approximately 0.2776 [5, 9], whereas it
is clear that a process matrix violating Eq. (7) must
necessarily violate a conditional LGYNI inequality be-
tween one pair of parties by at least 1/3. Moreover,
in Ref. [5] it was reported that no better violation
was found using three- or four-dimensional systems,
indicating that Eq. (7) can similarly not be violated
by such systems. It nonetheless remains unproven
whether such a violation is indeed impossible, and the
convex optimisation problem for three parties quickly
becomes intractable for higher dimensional systems,
making further numerical investigation difficult. The
second inequality for which no violation was found can
similarly be expressed as a sum of three different forms
(i.e., relabellings) of a conditional LGYNI inequality,
and a similar argument thus explains why no violation
was found. Recall that, as they can be expressed as
a sum of three conditional LGYNI inequalities with a
negative 2-causal bound, these two 2-causal inequali-
ties cannot be saturated by fully causal distributions;
it is interesting that the remaining inequalities that
require noncausal but 2-causal distributions to sat-
urate can nonetheless be violated by process matrix
correlations.
3.3 Generalised 2-causal inequalities for N par-
ties
Although it quickly becomes intractable to completely
characterise the 2-causal polytope for more compli-
cated scenarios with more parties, inputs and/or out-
puts, as is also the case for fully causal correlations,
it is nonetheless possible to generalise some of the 2-
causal inequalities into inequalities that are valid for
any number of parties N.
The inequality (4), for example, can naturally be
generalised to give a 2-causal inequality valid for all
N 2.
6
Specifically, one obtains
J
1
(N) =
X
(K(N
P
~a
K
=
~
1| ~x
K
=
~
1, ~x
N \K
=
~
0
P
~a =
~
1| ~x =
~
1
0 (10)
where
~
1 = (1, . . . , 1) and
~
0 = (0, . . . , 0), which can
be written analogously to Eq. (5) as a game (again
implicitly defined with uniform inputs) of the form
P
k
˜a
k
= Π
k
x
k
) 1 2
N+1
. (11)
We leave the proof of this inequality and its 2-causal
bound to Appendix A. It is interesting to ask if this
6
We continue to focus on the lazy scenario defined earlier
for concreteness, but we note that the proofs of the generalised
inequalities (10) and (12) in fact hold in any nontrivial scenario,
of which the lazy one is the simplest example. The bounds
for the corresponding causal games and whether or not the
inequalities define facets will, however, generally depend on the
scenario considered.
Accepted in Quantum 2017-12-06, click title to verify 6
inequality is tight (i.e., facet inducing) for all N. For
N = 2 it reduces to the LGYNI inequality which
is indeed tight, and for N = 3 it was also found to
be a facet. By explicitly enumerating the vertices of
the 2-causal polytope for N = 4 (of which there are
136818592) we were able to verify that J
1
(4) 0
is indeed also a facet, and we conjecture that this is
true for all N. Note that, as for the tripartite case it
is trivial to saturate the inequality for all N by con-
sidering the (fully causal) strategy where each party
always outputs 0.
It is also possible to generalise inequality (7) to N
parties—which will prove more interesting later—by
considering a scored game in which every pair of par-
ties gets one point if they win their respective bipar-
tite LGYNI game and all other parties’ inputs are
0, and the goal of the game is to maximise the to-
tal score of all pairs. If two parties belong to the
same subset in a bipartition, then they can win their
respective LGYNI game perfectly, whereas they are
limited by the causal bound 0 if they belong to two
different groups. The 2-causal bound on the inequal-
ity is thus given by the maximum number of pairs
of parties that belong to a common subset over all
bipartitions, times the maximal violation of the bi-
partite LGYNI inequality. Specifically, we obtain the
2-causal inequality
J
2
(N) =
X
{i,j}⊂N
L
N
(i, j)
N 1
2
(12)
where
n
2
= n(n1)/2 is a binomial coefficient and
L
N
(i, j) =P
a
i
= 1|x
i
x
j
= 10, ~x
N \{i,j}
=
~
0
+ P
a
j
= 1|x
i
x
j
= 01, ~x
N \{i,j}
=
~
0
P
a
i
a
j
= 11|x
i
x
j
= 11, ~x
N \{i,j}
=
~
0
.
(13)
Each term L
N
(i, j) defines a bipartite conditional
LGYNI inequality with the causal bound L
N
(i, j)
0, and the minimum algebraic bound (i.e. the maxi-
mal violation) 1. The minimum algebraic bound of
J
2
(N) is thus
N
2
. The validity of inequality (12)
for 2-causal correlations (which corresponds to a max-
imal average score of (2N1)(N1)/2
N
—compared
to the maximal algebraic value of 2N(N1)/2
N
—for
the corresponding game with uniform inputs) is again
formally proved in Appendix A.
We note that in contrast to Eq. (10), J
2
(4) 3 is
not a facet of the 4-partite 2-causal polytope, and thus
the inequality is not tight in general. Inequality (12)
can nonetheless be saturated by 2-causal correlations
for any N. For example, consider K = {1, . . . , N 1}
and take the distribution
P (~a|~x) = δ
~a
K
,f(~x
K
)
δ
a
N
,0
(14)
with f(~x
K
) = ~x
K
if ~x
K
contains exactly two inputs 1,
and f(~x
K
) =
~
0 otherwise. P (~a|~x) is clearly 2-causal
A
6
A
2
A
5
A
k
A
8
A
3
A
1
A
4
A
7
A
N
A
1
A
4
A
2
A
3
...
A
|P|
...
Figure 2: The N parties A
k
are grouped into |P| disjoint
subsets A
`
, according to the partition P = {A
1
, . . . , A
|P|
}.
The parties in a subset A
`
act “as one”, thus defin-
ing an “effective party”. To define P-causal correla-
tions, the N -partite correlation P (a
1
, . . . , a
N
|x
1
, . . . , x
N
)
is considered as an effectively |P|-partite correlation
P (~a
A
1
, . . . , ~a
A
|P|
|~x
A
1
, . . . , ~x
A
|P|
).
since it is compatible with the causal order K N \K
(indeed, also with N \K K). One can then easily
verify that P(~a|~x) saturates (12), since all
N1
2
pairs
of parties in K can win their respective conditional
LGYNI game perfectly, and therefore contribute with
a term of 1 to the sum in Eq. (12).
4 Refining the definition of genuinely
multipartite noncausal correlations
So far we only discussed correlations that can or can-
not arise given a definite causal order between two
subsets of parties. It makes sense to consider more re-
fined definitions that discriminate, among noncausal
correlations, to what extent and in which way they
represent a genuinely multipartite resource. The idea
will again be to see if a given correlation can be es-
tablished by letting certain groups of parties act “as
one”, while retaining a definite causal order between
different groups. The number and size of the groups
for which this is possible can be used to give two dis-
tinct characterisations of how genuinely multipartite
the observed noncausality is.
4.1 P-causal correlations
We first want to characterise the correlations that can
be realised when a definite causal order exists between
certain groups of parties, while no constraint is im-
posed on the correlations within each group.
Let us consider for this purpose a partition P =
{A
1
, . . . , A
|P|
} of N —i.e., a set of |P| nonempty dis-
joint subsets A
`
of N , such that
`
A
`
= N , see Fig. 2.
Note that if P contains at least two subsets, then for
a given subset A
`
N , P\{A
`
} also represents a par-
tition of N \A
`
. Let us then introduce the following
definition:
Accepted in Quantum 2017-12-06, click title to verify 7
Definition 5 (P-causal correlations). For a given
partition P of N , an N-partite correlation P is said
to be P-causal if and only if P is causal when consid-
ered as an effective |P|-partite correlation, where each
subset in P defines an effective party.
More precisely, analogously to Definition 1:
For |P| = 1, any N -partite correlation P is P-
causal;
For |P| 2, an N-partite correlation P is P-
causal if and only if it can be decomposed in the
form
P (~a|~x) =
X
A
`
∈P
q
A
`
P
A
`
(~a
A
`
|~x
A
`
)
× P
A
`
,~x
A
`
,~a
A
`
(~a
N \A
`
|~x
N \A
`
) (15)
with q
A
`
0 for each A
`
,
P
A
`
q
A
`
= 1, where
(for each A
`
) P
A
`
(~a
A
`
|~x
A
`
) is a valid probabil-
ity distribution for the parties in A
`
and (for
each A
`
, ~x
A
`
,~a
A
`
) P
A
`
,~x
A
`
,~a
A
`
(~a
N \A
`
|~x
N \A
`
) is
a (P\{A
`
})-causal correlation for the remaining
N |A
`
| parties.
In the extreme case of a single-set partition P =
{N } (|P| = 1), any correlation is by definition triv-
ially P-causal; at the other extreme, for a partition of
N into N singletons (|P| = N), the definition of P-
causal correlations above is equivalent to that of fully
causal correlations, Definition 1 [8, 9]. Between these
two extreme cases, a P-causal correlation identifies
the situation where, with some probability, all parties
within one group act before all other parties; con-
ditioned on their inputs and outputs, another group
acts second (before all remaining parties) with some
probability; and so on. We emphasise that no con-
straint is imposed on the correlations that can be gen-
erated within each group, since we allow them to share
the most general resource conceivable—in particular,
there might be no definite causal order between the
parties inside a group.
Since the definition of P-causal correlations above
matches that of causal correlations for the |P| effec-
tive parties defined by P, all basic properties of causal
correlations (see Ref. [9]) generalise straightforwardly
to P-causal correlations. Note in particular that the
definition captures the idea of dynamical causal or-
der, where the causal order between certain subsets of
parties in P may depend on the inputs and outputs
of other subsets of parties that acted before them.
The following result also follows directly from what is
known about causal correlations [8, 9]:
Theorem 6. For any given P, the set of P-causal
correlations forms a convex polytope, whose (finitely
many) extremal points correspond to deterministic P-
causal correlations.
We shall call this polytope the P-causal polytope;
its facets define P-causal inequalities. Theorem 6 im-
plies that any P-causal correlation can be obtained
as a probabilistic mixture of deterministic P-causal
correlations. It is useful to note that, similarly to
Ref. [9], deterministic P-causal correlations can be
interpreted in the following way: a set A
t
1
of parties
acts with certainty before all others, with their out-
puts being a deterministic function of all inputs in
that set but independent of the inputs of any other
parties, ~a
A
t
1
= ~α
A
t
1
(~x
A
t
1
). The inputs of the first set
also determine which set comes second, A
t
~x
2
, where
t
~x
2
= t
2
(~x
A
t
1
), whose outputs can depend on all in-
puts of the first and second sets; and so on, until all
the sets in the partition are ordered. As one can see,
each possible vector of inputs ~x thus determines (in a
not necessarily unique way) a given causal order for
the sets of parties in P.
4.2 Non-inclusion relations for P-causal poly-
topes
As suggested earlier, our goal is to quantify the extent
to which a noncausal resource is genuinely multipar-
tite in terms of the number or size of the subsets one
needs to consider in a partition P to make a given
correlation P-causal. A natural property to demand
of such a quantification is that it defines nested sets
of correlations: if a correlation is genuinely multipar-
tite noncausal “to a certain degree”, it should also be
contained in the sets of “less genuinely multipartite
noncausal” correlations (and, eventually, the set of
simply noncausal correlations). It is therefore useful,
before providing the relevant definitions in the next
subsections, to gather a better understanding of the
inclusion relations between P-causal polytopes.
One might intuitively think that there should in-
deed be nontrivial inclusion relations among those
polytopes. For example, one might think that a P-
causal correlation should also be P
0
-causal if P
0
is
a “coarse-graining” of P (i.e., P
0
is obtained from P
by grouping some of its groups to define fewer but
larger subsets)—or, more generally, when P
0
contains
fewer subsets than P, i.e. |P
0
| < |P|. This, how-
ever, is not true. For example, in the tripartite case,
a fully causal correlation (i.e., a P-causal one for
P = {{A
1
}, {A
2
}, {A
3
}}) compatible with the fixed
order A
1
A
2
A
3
, where A
2
comes between A
1
and
A
3
, may not be P
0
-causal for P
0
= {{A
1
, A
3
}, {A
2
}},
since one cannot order A
2
with respect to {A
1
, A
3
}
when those are taken together. In fact, no nontriv-
ial inclusion exists among P-causal polytopes, as es-
tablished by the following theorem, proved in Ap-
pendix B.
Theorem 7. Consider an N -partite scenario where
each party has at least two possible inputs and at least
two possible outputs for one value of the inputs. Given
two distinct nontrivial
7
partitions P and P
0
of N with
7
If one of the two partitions is trivial, say P
0
= {N }, then
the P-causal polytope is of course contained in the trivial P
0
-
Accepted in Quantum 2017-12-06, click title to verify 8
|P|, |P
0
| > 1, the P-causal polytope is not contained
in the P
0
-causal one, nor vice versa.
One may also ask whether, for a given P-causal
correlation P , there always exists a partition P
0
with
2 |P
0
| < |P| such that P is also P
0
-causal (re-
call that the case |P
0
| = 1 is trivial). The answer
is negative when mixtures of different causal orders
are involved: e.g., in the tripartite case with P =
{{A
1
}, {A
2
}, {A
3
}}, a fully causal correlation of the
form P =
1
6
(P
A
1
A
2
A
3
+P
A
1
A
3
A
2
+P
A
2
A
1
A
3
+
P
A
2
A
3
A
1
+ P
A
3
A
1
A
2
+ P
A
3
A
2
A
1
), where each
correlation in the sum is compatible with the corre-
sponding causal order, may not be P
0
-causal for any
P
0
of the form P
0
= {{A
i
, A
j
}, {A
k
}}
i6=j6=k
, as there is
always a term in P above for which A
k
comes between
A
i
and A
j
. For an explicit example one can take the
correlation P above to be a mixture of 6 correlations
P
det
P
introduced in Appendix B.
8
The above results tell us that P-causal polytopes
do not really define useful classes to directly quan-
tify how genuinely multipartite the noncausality of a
correlation is. One may wonder whether considering
convex hulls of P-causal polytopes allows one to avoid
these issues. For example, is it the case that any P-
causal correlation P is contained in the convex hull of
all P
0
j
-causal correlations for all partitions P
0
j
with a
fixed value of |P
0
j
| = m
0
< |P|?
9
For m
0
= 1 this is
trivial, and this remains true for m
0
= 2: any P-causal
correlation P can be decomposed as a convex combi-
nation of P
0
j
-causal correlations for various partitions
P
0
j
with |P
0
j
| = 2. Eq. (15) is indeed such a decompo-
sition, with the partitions P
0
`
= {A
`
, N \A
`
}. This is
also true, for any value of m
0
, for P-causal correlations
that are compatible with a fixed causal order between
the subsets in P (or convex mixtures thereof): indeed,
such a correlation is also P
0
-causal for any coarse-
grained partition P
0
of P where consecutive subsets
(as per the causal order in question, or per each causal
order in a convex mixture) of P are grouped together.
However, this is not true in general for m
0
> 2 when
dynamical causal orders are involved. It is indeed
possible to find a 4-partite, fully causal correlation
that cannot be expressed as a convex combination of
causal one (which contains all valid probability distributions).
Note that for N = 2 there is only one nontrivial partition; the
theorem is thus only relevant for scenarios with N 3.
8
To see that P thus defined is indeed not P
0
-causal for
any such bipartition, first note that, by symmetry, it suf-
fices to show it is not P
0
-causal for P
0
= {{A
1
}, {A
2
, A
3
}}.
One can readily show that all such P
0
-causal inequalities must
obey the LGYNI-type inequality P
A
1
(1|100)+P
A
2
A
3
(11|011)
P
A
1
A
2
A
3
(111|111) 0 (which, moreover, is a facet of the P
0
-
causal polytope). It is easily verified that P violates this in-
equality with the left-hand side obtaining the value 1/3.
9
Note that a convex combination of P
0
j
-causal correlations
for various partitions P
0
j
with a fixed number of subsets |P
0
j
| =
m
0
is not necessarily P
0
-causal for any single partition P
0
with
the same value of |P
0
| = m
0
.
P
0
j
-causal correlations with all |P
0
j
| = 3; an explicit
counterexample is presented in Appendix C.
From these observations we conclude that, although
grouping parties into m subsets seems to be a stronger
constraint than grouping parties into some m
0
< m
subsets, the fact that a correlation is P-causal for
some |P| = m 4 (or more generally, that it is a
convex combination of various P
j
-causal correlations
with all |P
j
| = m 4) does not guarantee that it
is also P
0
-causal for some |P
0
| = m
0
< m—unless
m
0
= 2 (or m
0
= 1, trivially)—nor that it can be de-
composed as a convex combination of P
0
j
-causal corre-
lations with all |P
0
j
| = m
0
. In particular, fully causal
correlations may not be P
0
-causal for any P
0
with
2 < |P
0
| < N , or convex combinations of such P
0
-
causal correlations. This remark motivates the defi-
nitions in the next subsection.
4.3 M -causal correlations
4.3.1 Definition and characterisation
With the previous discussion in mind, we propose the
following definition, as a first refinement between the
definitions of fully causal and 2-causal correlations.
Definition 8 (M -causal correlations). An N-partite
correlation is said to be M-causal (for 1 M N)
if and only if it is a convex combination of P-causal
correlations, for various partitions P of N into |P|
M subsets.
More explicitly: P is M -causal if and only if it can
be decomposed as
P (~a|~x) =
X
P: |P|≥M
q
P
P
P
(~a|~x), (16)
where the sum is over all partitions P of N into M
subsets or more, with q
P
0 for each P,
P
P
q
P
= 1,
and where each P
P
(~a|~x) is a P-causal correlation.
For M = 1, any correlation is trivially 1-causal,
since for P = {N } any correlation is P-causal. For
M = N, the definition of M-causal correlations above
is equivalent to that of fully causal correlations, Def-
inition 1 [8, 9].
For M = 2, the above definition is equivalent to
that of 2-causal correlations as introduced through
Definition 2. To see this, recall first (from the discus-
sion in the previous subsection), that any P-causal
correlation with |P| 2 can be written as a convex
combination of some P
0
-causal correlations, for var-
ious bipartitions P
0
with |P
0
| = 2. It follows that,
for M = 2, it would be equivalent to have the con-
dition |P| = 2 instead of |P| 2 in Definition 8 of
M-causal correlations. Definition 2 is then recovered
when writing the bipartitions in the decomposition
as P = {K, N \K}, using Eq. (15) from the defi-
nition of P-causal correlations, and rearranging the
terms in the decomposition. Hence, Definition 2 is
Accepted in Quantum 2017-12-06, click title to verify 9
(fully) causal
N-causal
3-causal
(N–1)-causal
...
2-causal
genuinely N-partite
noncausal
not 2-causal
Figure 3: Sketch of the full hierarchy of nested M-causal
polytopes, that allows one to refine the characterisation rep-
resented in Fig. 1. The vertices of each M -causal polytope
correspond to deterministic M -causal correlations, and their
facets correspond to M-causal inequalities. An M -causal
correlation is also M
0
-causal for any M
0
M ; the largest
M for which a correlation P is M-causal quantifies how gen-
uinely multipartite its noncausality is.
in fact equivalent to saying that 2-causal correlations
are those that can be written as a convex mixture of
P-causal correlations, for different partitions P of N
into |P| 2 subsets, thus justifying further our def-
inition of genuinely N -partite noncausal correlations
as those that cannot be written as such a convex mix-
ture (or equivalently, those that are not M-causal for
any M > 1). Note that since we used the constraint
|P| M rather than |P| = M in Eq. (16),
10
our def-
inition establishes a hierarchy of correlations as de-
sired, with M-causal M
0
-causal if M M
0
.
With the above definition of M-causal correlations,
we have the following:
Theorem 9. For any given value of M (with 1
M N ), the set of M-causal correlations forms a
convex polytope, whose (finitely many) extremal points
correspond to deterministic P-causal correlations, for
all possible partitions P with |P| M—that is, de-
terministic M -causal correlations.
Proof. According to Eq. (16), the set of M-causal cor-
relations is the convex hull of the polytopes of P-
causal correlations with |P| M. Since there is a
finite number of such polytopes, the set of M -causal
correlations is itself a convex polytope; its extremal
10
Replacing the condition |P| M by |P| = M in Defini-
tion 8 for arbitrary M, we could define (=M)-causal correla-
tions”, which would be distinct from M-causal correlations for
2 < M < N . We would also have that (=M)-causal corre-
lations” form a convex polytope; however, the various (=M )-
causal polytopes” would not necessarily be included in one an-
other for distinct values of M, as discussed in the previous
subsection.
points are those of the various P-causal polytopes
with |P| M, namely deterministic P-causal cor-
relations (see Theorem 6).
We thus obtain a family of convex polytopes—
which we shall call M-causal polytopes—included in
one another, see Fig. 3. The facets of these polytopes
are M-causal inequalities, which define a hierarchy of
criteria: e.g., if all M-causal inequalities are satisfied,
then so are all M
0
-causal inequalities if M
0
M—or
equivalently: if some M
0
-causal inequality is violated,
then some M-causal inequality must also be violated
if M M
0
. Given a correlation P , one can in prin-
ciple test to which set it belongs. The largest M for
which P is M-causal can be used as a measure of how
genuinely multipartite its noncausality is: it means
that P can be obtained as a convex combination of
P-causal correlations with all |P| M, but not with
all |P| > M—indeed, if M < N then P violates some
M
0
-causal inequality for any M
0
> M (with M
0
N ).
If that M is 1, P is a genuinely N-partite noncausal
correlation; if it is N, then P is fully causal, hence
it displays no noncausality (genuinely multipartite or
not).
4.3.2 A family of M-causal inequalities
The general N -partite 2-causal inequality (12) can
easily be modified to give an M-causal inequality that
is valid—although not tight in general, as observed
before—for all N and M (with 1 M N), simply
by changing the bound. Indeed, this bound is derived
from the largest possible number of pairs of parties
that can be in a single subset of a given partition,
and this can easily be recalculated for M-subset par-
titions rather than bipartitions. We thus obtain that
J
2
(N) =
X
{i,j}⊂N
L
N
(i, j)
N M + 1
2
(17)
for any M-causal correlation. This updated bound is
proved in Appendix A.
As for Eq. (12) it is easy to see that, for any
N, M , there are M-causal correlations saturating the
inequality (17). Consider, for instance, the partition
P = {A
1
, . . . , A
M
} of N with A
1
= {1, . . . , N M +
1} and A
`
= {N M + `} for 2 ` M, and take
the distribution
P (~a|~x) = δ
~a
A
1
,f(~x
A
1
)
δ
~a
N \A
1
,
~
0
, (18)
where we use the same function f as in Eq. (14).
Analogous reasoning shows that this correlation in-
deed reaches the bound (17).
Since this (reachable) lower bound is different for
each possible value of M, this implies, in particular,
that (for the N-partite lazy scenario) all the inclu-
sions N-causal (N1)-causal · · · 3-causal
2-causal in the hierarchy of M-causal polytopes are
Accepted in Quantum 2017-12-06, click title to verify 10
strict. In fact, redas for inequalities (10) and (12)
(see Footnote 6), the proof of Eq. (17) holds in any
nontrivial scenario (with arbitrarily many inputs and
outputs), of which the lazy scenario is the simplest ex-
ample for all N. Moreover, one can saturate it in such
scenarios by trivially extending the M-causal correla-
tion (18) (e.g., by producing a constant output on all
other inputs) and thus these inclusions are strict in
general.
4.4 Size-S-causal correlations
In the previous subsection we used the number of sub-
sets needed in a partition to quantify how genuinely
multipartite the noncausality of a correlation is. Here
we present an alternative quantification, based on the
size of the biggest subset in a partition, rather than
the number of subsets.
Intuitively, the bigger the subsets in a partition
P needed to reproduce a correlation, the more gen-
uinely multipartite noncausal the corresponding P-
causal correlations are. However, the discussion of
Sec. 4.2 implies that, as was the case with M-causal
correlations, it is not sufficient to simply ask whether
a given correlation is P-causal for some partition P
with subsets of a particular size. We therefore fo-
cus on classes of correlations that can be written as
mixtures of P-causal ones whose largest subset is not
larger than some number S. For convenience, we in-
troduce the notation
s(P)
:
= max
A∈P
|A| . (19)
We then take the following definition:
Definition 10 (Size-S-causal correlations). An N -
partite correlation is said to be size-S-causal (for 1
S N) if and only if it is a convex combination of
P-causal correlations, for various partitions P whose
subsets are no larger than S.
More explicitly: P is size-S-causal if and only if it
can be decomposed as
P (~a|~x) =
X
P: s(P)S
q
P
P
P
(~a|~x), (20)
where the sum is over all partitions P of N with no
subset of size larger than S, with q
P
0 for each P,
P
P
q
P
= 1, and where each P
P
(~a|~x) is a P-causal
correlation.
Any N-partite correlation is trivially size-N-causal,
while size-1-causal correlations coincide with fully
causal correlations. Furthermore, noting that s(P)
N 1 if and only if |P| 2, we see that the set of
size-(N1)-causal correlations coincides with that of
2-causal correlations. Hence, the definition of size-S-
causal correlations is another possible generalisation
of that of 2-causal ones. From this new perspective,
2-causal correlations can be seen as those that can be
realised using (probabilistic mixtures of) noncausal
resources available to groups of parties of size N1
or less. This further strengthens the definition of 2-
causal correlations as the largest set of correlations
that do not possess genuinely N -partite noncausality.
Without repeating in full detail, it is clear that size-
S-causal correlations define a structure similar to that
of M-causal correlations: for each S, size-S-causal
correlations define size-S-causal polytopes whose ver-
tices are deterministic size-S-causal correlations and
whose facets define size-S-causal inequalities. For
S S
0
, all size-S-causal correlations are also size-
S
0
-causal, so that the various size-S-causal polytopes
are included in one another. The lowest S for which
a correlation is size-S-causal also provides a measure
of how genuinely multipartite the corresponding non-
causal resource is, distinct to that defined by M-
causal correlations.
It is also possible here to generalise inequality (12)
to size-S-causal correlations by changing the bound.
As proven in Appendix A, we thus obtain the size-S-
causal inequality
J
2
(N)
N
S
S
2
N
N
S
S
2
(21)
(where bxc denotes the largest integer smaller than or
equal to x). Although, once again, this inequality is
not tight in the sense that it does not define a facet
of the size-S-causal polytope, its lower bound can be
saturated by a size-S-causal correlation for each value
of S, for instance by considering the partition P =
{A
1
, . . . , A
b
N
S
c
(, A
b
N
S
c
+1
)} of N into
N
S
groups of
S parties, and (if N is not a multiple of S) a last
group with the remaining N
N
S
S parties, and by
taking the deterministic correlation
P (~a|~x) =
Y
`
δ
~a
A
`
,f(~x
A
`
)
(22)
(with again the same function f as in Eq. (14)). Since
the (reachable) lower bounds in Eq. (21) are differ-
ent for all possible values of S, this implies, again,
that all the inclusions size-1-causal size-2-causal
· · · size-(N1)-causal in the hierarchy of size-
S-causal polytopes are strict in general.
4.5 Comparing the polytopes of M -causal and
size-S-causal correlations
A relation between M-causal and size-S-causal cor-
relations can be established through the following,
straightforwardly verifiable, inequalities:
|P| 1 + s(P) N |P| s(P). (23)
From these it follows that, for N parties:
Accepted in Quantum 2017-12-06, click title to verify 11
M = 6
S = 1
(fully causal)
S = 2
S = 3
S = 4
M = 4
M = 3
M = 5
M = 2
S = 5
(2-causal)
M = 1
S = 6
(all correlations)
Figure 4: Diagram of polytope inclusion relations for N = 6
parties. Each node in the diagram represents the polytope of
M-causal or size-S-causal correlations for the corresponding
value of M or S. Arrows represent (strict) inclusion rela-
tions: the polytope at the start of an arrow is included in
the polytope at the end of the arrow. The paths ascending
the left and right sides of the diagram show the inclusion
relations implied by the fact that the M-causal and size-
S-causal polytopes respectively form strict hierarchies. The
“cross-arrows” between these paths are the inclusions im-
plied by Theorem 11. The dotted arrows can be implied by
transitivity from other arrows and are thus redundant. The
inclusion relations shown in the diagram are complete, in the
sense that there is no inclusion not represented by an arrow
or a sequence of arrows.
Theorem 11.
If a correlation is M-causal, then it is size-S-
causal for all S NM+1.
If a correlation is size-S-causal, then it is M-
causal for all M
N
S
(where dxe denotes the
smallest integer larger than or equal to x).
It is furthermore possible to show that the inclusion
relations between M-causal and size-S-causal poly-
topes implied by Theorem 11 are complete, in the
sense that no other inclusion exists that is not im-
plied by the theorem. We prove this in Appendix D.
Together with the respective inclusion relations of
each hierarchy separately, this result thus fully char-
acterises the inclusion relations of all the classes of
noncausal correlations that we introduced; the situa-
tion is illustrated in Fig. 4 for the 6-partite case as an
example.
5 Discussion
The possibility that nature might allow for correla-
tions incompatible with a definite causal order opens
exciting questions. It has been suggested that such
correlations might arise in the context of quantum
theories of gravity [15] or in space-time geometries
with closed time-like curves [16, 17], although these
possibilities, like that of observing noncausal correla-
tions in laboratory experiments, are as yet unverified.
Motivated by the fact that noncausal resources exhibit
interesting new features in multipartite scenarios [6
9], we aimed here to clarify when noncausal correla-
tions can be considered to be a genuinely multipartite
resource.
In addressing this task, we first proposed a criterion
to decide whether a given correlation shared by N par-
ties is “genuinely N-partite noncausal”—i.e., its non-
causality is indeed a genuinely N-partite resource—or
not. We then refined our approach into two distinct
criteria quantifying the extent to which the noncausal-
ity of a correlation is a genuinely multipartite re-
source. Both criteria are based around asking whether
the correlation under consideration is compatible with
certain subsets being grouped together—which are
thus able to share arbitrary noncausal resources—
and with a well-defined causal order existing between
these groups of parties. The first criterion is based
on the largest number M of such subsets that can be
causally ordered while reproducing the correlation in
question: the smaller M , the more genuinely multi-
partite the noncausality exhibited by the correlation.
If M = 1, then no subset of parties has a well-defined
causal relation with any other, and the correlation is
genuinely N-partite noncausal. The second criterion
instead looks at how large the subsets that can be
causally ordered are: if an N-partite correlation can
be reproduced with subsets containing no more than
S N parties, then S-partite noncausal resources
are sufficient to reproduce the correlation. Thus, the
larger S required, the more genuinely multipartite the
correlation. If S = N , then again the correlation is
genuinely N-partite noncausal. Although these two
criteria define different classes of correlations in gen-
eral, they coincide on the edge cases and thus lead
to exactly the same definition of genuinely N-partite
noncausal correlations, adding support to the robust-
ness of our definition. It nonetheless remains to be
seen as to which measure of genuine multipartiteness
is the most appropriate (or, in what situations one is
more pertinent than the other).
All the classes of correlations we introduced
through these criteria conveniently form polytopes,
whose vertices are deterministic correlations and
whose facets define different classes of inequalities.
Of particular interest are the “2-causal” correlations,
which are the most general correlations that are not
genuinely N -partite noncausal. We completely char-
Accepted in Quantum 2017-12-06, click title to verify 12
acterised the 2-causal polytope for the simplest non-
trivial tripartite scenario and found that almost all of
the 473 nontrivial classes of 2-causal inequalities can
be violated by process matrix correlations. However,
we were unable to find any violation for 2 of those in-
equalities; this stands in contrast to previous studies
of causal inequalities, where violations with process
matrices were always found
11
[47, 9]. Although it
remains to be confirmed whether this is simply a fail-
ure of the search method we used, we provided some
intuition why such a violation would in fact be a sur-
prise.
Our definition of genuinely N-partite noncausality
is analogous to the corresponding notion for nonlocal-
ity originally due to Svetlichny [1921]. It is known,
however, that that notion harbours some issues: for
example, it is not robust under local operations, a nec-
essary requirement for an operational resource theory
of nonlocality [22, 23]. In order to overcome these is-
sues, additional constraints must be imposed on the
correlations shared by subsets of parties when defin-
ing correlations that are not genuinely multipartite
nonlocal. In the case of noncausality, however, there
appears to be no clear reason to impose any addi-
tional such constraints. For nonlocal resources, issues
arise in particular from the possibility that different
parties might access the resource at different times,
with an earlier party then communicating with a later
one. This type of issue is not pertinent for noncausal
resources, where the causal order (be it definite or
indefinite) between parties is determined by the re-
source itself, and additional communication beyond
what the resource specifies seems to fall outside the
relevant framework. More generally, however, an op-
erational framework and understanding of the rele-
vant “free operations” for noncausal resources remains
to be properly developed.
Finally, in this paper we only considered correla-
tions from a fully theory- and device-independent per-
spective; it would be interesting to develop similar no-
tions within specific physical theories like the process
matrix framework, where quantum theory holds lo-
cally for each party. Process matrices that cannot be
realised with a definite causal order are called causally
nonseparable [4], and it would be interesting to study
a notion of genuinely multipartite causal nonsepara-
bility. It should, however, be noted that different pos-
sible notions of multipartite causal (non)separability
have been proposed [8, 14], so a better understand-
ing of their significance would be necessary in order
to extend the notions we have developed here to that
framework.
11
At least for standard causal inequalities that bound prob-
abilities directly; for entropic causal inequalities, which only
provide a relaxed characterisation of the set of causal correla-
tions, no violations were found so far [18]. It would nevertheless
also be interesting to investigate how genuinely multipartite
noncausality can be characterised with the entropic approach.
Acknowledgements
A.A.A., J.W. and C.B. acknowledge support through
the ‘Retour Post-Doctorants’ program (ANR-13-
PDOC-0026) of the French National Research Agency.
F.C. acknowledges support through an Australian Re-
search Council Discovery Early Career Researcher
Award (DE170100712). This publication was made
possible through the support of a grant from the John
Templeton Foundation. The opinions expressed in
this publication are those of the authors and do not
necessarily reflect the views of the John Templeton
Foundation. F.C. acknowledges the traditional own-
ers of the land on which the University of Queensland
is situated, the Turrbal and Jagera people.
References
[1] H. Reichenbach, The direction of time (Univer-
sity of California Press, Berkeley, 1956).
[2] J. Pearl, Causality (Cambridge University Press,
Cambridge, 2009).
[3] Č. Brukner, Quantum causality, Nat. Phys. 10,
259–263 (2014).
[4] O. Oreshkov, F. Costa, and Č. Brukner, Quan-
tum correlations with no causal order, Nat. Com-
mun. 3, 1092 (2012).
[5] C. Branciard, M. Araújo, A. Feix, F. Costa, and
Č. Brukner, The simplest causal inequalities and
their violation, New J. Phys. 18, 013008 (2016).
[6] Ä. Baumeler and S. Wolf, Perfect signaling
among three parties violating predefined causal
order, in 2014 IEEE International Symposium on
Information Theory (ISIT) (IEEE, Piscataway,
NJ, 2014) pp. 526–530.
[7] Ä. Baumeler, A. Feix, and S. Wolf, Maxi-
mal incompatibility of locally classical behavior
and global causal order in multi-party scenarios,
Phys. Rev. A 90, 042106 (2014).
[8] O. Oreshkov and C. Giarmatzi, Causal and
causally separable processes, New J. Phys. 18,
093020 (2016).
[9] A. A. Abbott, C. Giarmatzi, F. Costa, and
C. Branciard, Multipartite causal correlations:
Polytopes and inequalities, Phys. Rev. A 94,
032131 (2016).
[10] L. Hardy, Probability theories with dynamic
causal structure: a new framework for quantum
gravity, (2005), arXiv:gr-qc/0509120.
[11] K. Fukuda, cdd, v0.94g, (2012), https://www.
inf.ethz.ch/personal/fukudak/cdd_home/.
[12] M. Araújo, A. Feix, M. Navascués, and Č.
Brukner, A purification postulate for quantum
mechanics with indefinite causal order, Quantum
1, 10 (2017).
[13] A. Feix, M. Araújo, and Č. Brukner,
Causally nonseparable processes admitting a
causal model, New J. Phys. 18, 083040 (2016).
Accepted in Quantum 2017-12-06, click title to verify 13
[14] M. Araújo, C. Branciard, F. Costa, A. Feix,
C. Giarmatzi, and Č. Brukner, Witnessing
causal nonseparability, New J. Phys. 17, 102001
(2015).
[15] L. Hardy, Towards quantum gravity: a frame-
work for probabilistic theories with non-fixed
causal structure, J. Phys. A: Math. Gen. 40, 3081
(2007).
[16] Ä. Baumeler, F. Costa, T. C. Ralph, S. Wolf,
and M. Zych, Reversible time travel with freedom
of choice, (2017), arXiv:1703.00779 [gr-qc].
[17] M. Araújo, P. A. Guérin, and Ä. Baumeler,
Quantum computation with indefinite causal
structures, Phys. Rev. A 96, 052315 (2017).
[18] N. Miklin, A. A. Abbott, C. Branciard,
R. Chaves, and C. Budroni, The entropic ap-
proach to causal correlations, New J. Phys. 19,
113041 (2017).
[19] G. Svetlichny, Distinguishing three-body from
two-body nonseparability by a Bell-type inequal-
ity, Phys. Rev. D 35, 3066 (1987).
[20] M. Seevinck and G. Svetlichny, Bell-type inequal-
ities for partial separability in N -particle systems
and quantum mechanical violations, Phys. Rev.
Lett. 89, 060401 (2002).
[21] D. Collins, N. Gisin, S. Popescu, D. Roberts,
and V. Scarani, Bell-type inequalities to detect
true n-body nonseparability, Phys. Rev. Lett. 88,
170405 (2002).
[22] R. Gallego, L. E. Würflinger, A. Acín, and
M. Navascués, Operational framework for non-
locality, Phys. Rev. Lett. 109, 070401 (2012).
[23] J.-D. Bancal, J. Barrett, N. Gisin, and S. Piro-
nio, Definitions of multipartite nonlocality, Phys.
Rev. A 88, 014102 (2013).
[24] See Supplementary Material in the arXiv ‘ancil-
lary files’ for the full list of 2-causal inequalities
in the tripartite lazy scenario and further analy-
sis.
A Proof of the generalised 2-causal in-
equalities and their bounds
A.1 Proof of inequality (10)
To prove that Eq. (10) is a valid 2-causal inequal-
ity for all N , it suffices to show that it holds
for all deterministic 2-causal correlations. For a
nonempty strict subset K of N , let P
det
(~a|~x) =
P
det
(~a
K
|~x
K
)P
det
~x
K
,~a
K
(~a
N \K
|~x
N \K
) be an arbitrary de-
terministic correlation compatible with the causal
order K N \K. Then, since P
det
(~a
K
|~x) =
P
det
(~a
K
|~x
K
), it follows that
P
det
~a
K
=
~
1| ~x
K
=
~
1, ~x
N \K
=
~
0
= P
det
~a
K
=
~
1| ~x =
~
1
P
det
~a =
~
1| ~x =
~
1
(24)
and hence P
det
~a
K
=
~
1| ~x
K
=
~
1, ~x
N \K
=
~
0
P
det
~a =
~
1| ~x =
~
1
0. Since J
1
(N) is then
obtained by adding some more nonnegative terms
P
det
~a
K
0
=
~
1| · · · ) 0, this proves the validity of
Eq. (10) for any 2-causal correlation.
A.2 Proof of inequalities (12), (17) and (21)
for M -causal and size-S-causal correlations
The M -causal inequality (17) and the size-S-causal
inequality (21) are defined as different bounds for the
expression J
2
(N) =
P
{i,j}⊂N
L
N
(i, j), with the sum-
mands defined in Eq. (13), while the 2-causal inequal-
ity (12) coincides with the particular cases M = 2 and
S = N 1. We shall first prove a bound for J
2
(N)
that holds for P-causal correlations, for any partition
P, and then use this bound to derive the correspond-
ing M-causal, size-S-causal (and consequently the 2-
causal) bounds.
Firstly, let us note that the observation made at the
end of Sec. 4.1 that the response function determin-
ing the outputs of a deterministic P-causal correlation
can be seen as processing deterministically one input
after another and consequently defining a (dynamical)
causal order between the subsets in P, also implies the
following result (which will be used below and in the
subsequent appendices):
Proposition 12. For a deterministic P-causal cor-
relation P , given two subsets A
`
and A
m
in P, the
vector of inputs ~x
N \(A
`
∪A
m
)
for the parties that are
neither in A
`
nor in A
m
determines a (not necessarily
unique) causal order between A
`
and A
m
, A
`
A
m
or A
m
A
`
.
More technically: for any ~x
\`m
:
= ~x
N \(A
`
∪A
m
)
, a
deterministic P-causal correlation P satisfies either
P (~a
A
`
|~x
\`m
, ~x
A
`
, ~x
A
m
) = P (~a
A
`
|~x
\`m
, ~x
A
`
, ~x
0
A
m
) for
all ~x
A
`
, ~x
A
m
, ~x
0
A
m
,~a
A
`
, or P (~a
A
m
|~x
\`m
, ~x
A
`
, ~x
A
m
) =
P (~a
A
m
|~x
\`m
, ~x
0
A
`
, ~x
A
m
) for all ~x
A
m
, ~x
0
A
`
, ~x
A
m
,~a
A
m
i.e., in short, either P(~a
A
`
|~x) = P (~a
A
`
|~x
N \A
m
) or
P (~a
A
m
|~x) = P (~a
A
m
|~x
N \A
`
).
To derive a P-causal bound for J
2
(N) for a given
partition P = {A
1
, . . . , A
|P|
}, it is sufficient to find a
bound that holds for any deterministic P-causal cor-
relation P . We will bound J
2
(N) by bounding each
individual term L
N
(i, j) in the sum. There are two
cases to be considered: whether i) the parties A
i
and
A
j
are in different subsets of P, i.e. i A
`
, j A
m
with ` 6= m; or ii) both parties are in the same subset:
i, j A
`
.
i) According to Proposition 12, the inputs
~x
N \(A
`
∪A
m
)
=
~
0 imply either the order A
`
A
m
, or A
m
A
`
for P . In the first case,
P
a
i
= 1|x
i
x
j
= 10, ~x
N \{i,j}
=
~
0
= P
a
i
= 1|x
i
x
j
= 11, ~x
N \{i,j}
=
~
0
, (25)
Accepted in Quantum 2017-12-06, click title to verify 14
which implies
P
a
i
= 1|x
i
x
j
= 10, ~x
N \{i,j}
=
~
0
P
a
i
a
j
= 11|x
i
x
j
= 11, ~x
N \{i,j}
=
~
0
0,
(26)
and therefore (after adding a nonnegative term)
L
N
(i, j) 0. An analogous argument shows that
L
N
(i, j) 0 also in the case that one has A
m
A
`
for P when ~x
N \(A
`
∪A
m
)
=
~
0.
ii) If the parties A
i
and A
j
belong to the same
subset A
`
, they can share arbitrary correlations
and thus win the (conditional) LGYNI game per-
fectly. In that case we have L
N
(i, j) 1, which
is the minimum algebraic bound.
Combining the two cases, we thus have, for any P-
causal correlation,
J
2
(N) =
X
{i,j}⊂N
L
N
(i, j)
X
{i,j}∈A
`
for some A
`
∈P
(1)
=
X
A
`
∈P
|A
`
|
2
:
= L(P). (27)
In order to prove the M-causal bound (17), we shall
now prove that among all partitions P containing a
fixed number m of subsets, the quantity L(P) defined
above is minimal when P consists of m 1 singletons,
and one subset containing the remaining N m + 1
parties. Assume for the sake of contradiction that this
is not the case, so that the minimum is obtained for
a partition P that contains at least two subsets A
`
and A
m
that are not singletons, for which we assume
|A
`
| |A
m
| ( 2). Let then k A
m
, and define the
partition P
0
obtained from P by replacing A
`
and A
m
by A
0
`
= A
`
{k} and A
0
m
= A
m
\{k}, respectively
(note that the assumption that |A
m
| 2 ensures that
A
0
m
remains nonempty). One then has
L(P
0
) L(P)
=
h
|A
0
`
|
2
+
|A
0
m
|
2
i
+
h
|A
`
|
2
+
|A
m
|
2
i
= −|A
`
| + |A
m
| 1 < 0, (28)
in contradiction with the assumption that P min-
imised L. For a given N it then follows that
min
P:|P|=m
L(P) =
N m + 1
2
, (29)
and therefore, from Eq. (27),
J
2
(N)
N |P| + 1
2
. (30)
Finally, we note that |P| M implies
N−|P|+1
2
NM +1
2
, which concludes the proof that Eq. (17)
holds for all M-causal correlations.
In order now to prove the bound (21) for size-S-
causal correlations, we show that among all partitions
P with s(P) S, L(P) from Eq. (27) is minimised
for the partition containing
N
S
groups of S parties,
and (if N is not a multiple of S) a last group with the
remaining N
N
S
S parties—for which L(P) is in-
deed equal to the right-hand side of Eq. (21). Assume
again for the sake of contradiction that this is not the
case, so that the minimum is obtained for a partition
P containing at least two subsets A
`
and A
m
of less
than S parties, for which we take |A
m
| |A
`
| < S. If
|A
m
| > 1, one can follow the same reasoning as in the
proof of the M-causal bound above: take k A
m
and
consider the partition P
0
obtained by replacing A
`
and A
m
by A
0
`
= A
`
{k} and A
0
m
= A
m
\{k}, respec-
tively. Note that since we assumed |A
`
| < S, we have
|A
0
`
| S and s(P
0
) S. Eq. (28) then holds again, in
contradiction with the assumption that P minimised
L. In the case when |A
m
| = 1, consider instead the
partition P
0
formed by merging A
`
and A
m
into a new
subset A
0
`
= A
`
A
m
(so that |A
0
`
| = |A
`
| + 1 S
and we still have s(P
0
) S). We then have
L(P
0
) L(P) =
|A
0
`
|
2
+
|A
`
|
2
= −|A
`
| < 0, (31)
again in contradiction with the assumption that P
minimised L, which concludes the proof that Eq. (21)
holds for all size-S-causal correlations.
B Separation of P-causal polytopes
In this appendix we shall prove Theorem 7, which
states that there are no nontrivial inclusions among
P-causal polytopes. Before that, we start by intro-
ducing a useful family of deterministic P-causal cor-
relations.
B.1 A family of deterministic P-causal corre-
lations
The N-partite correlations P
det
P
we introduce here are
defined for a given partition P = {A
1
, . . . , A
|P|
} of N
and a given permutation σ of its |P| elements.
We consider the lazy scenario, where each party has
a binary input x
k
= 0, 1 with a fixed output a
k
= 0
for x
k
= 0, and a binary output a
k
= 0, 1 for x
k
= 1.
For each subset A P and a vector of inputs ~x, we
define the bit
z
A
:
=
Y
k∈A
x
k
. (32)
We then define the deterministic response function
~α
P
such that, for each party A
k
belonging to a sub-
Accepted in Quantum 2017-12-06, click title to verify 15
set A
`
of P, we have
~α
P
(~x)
k
:
=
Y
m: σ(m)σ(`)
z
A
m
. (33)
The correlation P
det
P
is then defined as
P
det
P
(~a|~x)
:
= δ
~a,~α
P
(~x)
. (34)
In other words, each party A
k
in some subset A
`
P outputs the product of the inputs of all parties that
came before itself according to the partition P and the
causal order A
σ(1)
A
σ(2)
· · · A
σ(|P|)
defined by
the permutation σ, including all parties in the same
subset A
`
. Clearly the correlation P
det
P
is compatible
with this fixed causal order, and is therefore P-causal;
as it is deterministic, it corresponds to a vertex of the
P-causal polytope.
Note that each party outputs a
k
= 0 whenever x
k
=
0, as required in the lazy scenario. The correlations
P
det
P
can also straightforwardly be generalised to more
complex scenarios with more inputs and outputs, by
simply never outputting the other possible outputs,
and, e.g., always outputting 0 for any other possible
input. Hence, the proofs below, which use P
det
P
as
an explicit example, apply to any scenario where each
party has at least two possible inputs, and at least
two possible outputs for one of their inputs.
B.2 Proof of Theorem 7
Coming back to the theorem, we shall prove that the
P-causal polytope is not contained in the P
0
-causal
one by exhibiting a P-causal correlation (from the
family introduced above) that is not P
0
-causal. The
proof that the P
0
-causal polytope is not contained in
the P-causal one then follows by symmetry. We dis-
tinguish two cases, whether i) P
0
is a coarse-graining
of P or ii) P
0
is not a coarse-graining of P.
i) If P
0
(with |P
0
| > 1) is a coarse-graining of
P, then one can find two subsets A
`
and A
`
0
in P that are grouped together in some sub-
set A
0
``
0
in P
0
, and a third subset A
m
in P
that is contained in a different subset A
0
m
of
P
0
. Let σ be a permutation of P which defines
a causal order between its elements such that
A
`
A
m
A
`
0
. The correlation P
det
P
as defined
in Eq. (34) is then P-causal, but not P
0
-causal.
Intuitively, this is because we cannot order A
0
``
0
(in which A
`
and A
`
0
are grouped together)
against A
0
m
(which contains A
m
). More specifi-
cally, for ~x
N \(A
`
∪A
`
0
∪A
m
)
=
~
1 (so that in partic-
ular, ~x
N \(A
0
``
0
∪A
0
m
)
=
~
1), the response function
~α
P
defined in Eq. (33) gives a
k
=
~α
P
(~x)
k
=
z
A
`
z
A
m
z
A
`
0
if k A
`
0
and a
k
=
~α
P
(~x)
k
=
z
A
`
z
A
m
if k A
m
. Hence, P (~a
A
0
``
0
|~x) depends
nontrivially on ~x
A
0
m
(via z
A
m
) while P (~a
A
0
m
|~x)
A
B
3
B
2
B
3
B
1
B
2
B
1
B
2
B
3
B
1
B
3
B
1
B
2
B
1
B
1
B
2
B
2
B
3
B
3
x = 1
x = 3
x = 2
x = 4
x = 6
x = 5
x
Figure 5: The causal structure sketched above provides an
example of a 4-partite fully causal correlation that is not a
convex mixture of P
0
j
-causal correlations with |P
0
j
| = 3 (see
text for details).
depends nontrivially on ~x
A
0
``
0
(via z
A
`
). Accord-
ing to Proposition 12, this implies that P
det
P
in-
deed cannot be P
0
-causal.
ii) If P
0
is not a coarse-graining of P, then one can
find two parties A
i
, A
j
that belong to the same
subset A
ij
of P, but belong to two distinct sub-
sets of P
0
, i.e. A
i
A
0
i
, A
j
A
0
j
. Let now σ
be any permutation of P. The correlation P
det
P
as defined in Eq. (34) is then P-causal, but not
P
0
-causal. Intuitively, this is because the par-
ties A
i
and A
j
cannot be separated in the defini-
tion of P
det
P
. More specifically, for ~x
N \{i,j}
=
~
1
(so that in particular, ~x
N \(A
0
i
∪A
0
j
)
=
~
1), the re-
sponse function ~α
P
gives a
k
=
~α
P
(~x)
k
=
z
A
ij
= x
i
x
j
for both k = i and k = j. Hence,
P (~a
A
0
i
|~x) depends nontrivially on ~x
A
0
j
(via x
j
)
while P (~a
A
0
j
|~x) depends nontrivially on ~x
A
0
i
(via
x
i
). According to Proposition 12, this implies
that P
det
P
indeed cannot be P
0
-causal.
C A 4-partite fully causal correlation
with dynamical order that is not a con-
vex mixture of P
0
j
-causal correlations
with |P
0
j
| = 3.
We provide here an explicit counterexample to the
question raised at the end of Sec. 4.2, of whether
a P-causal correlation can always be written as a
convex combination of P
0
j
-causal correlations for var-
ious partitions P
0
j
with a fixed number of subsets
|P
0
j
| = m
0
< |P|.
As we noted, such a counterexample requires m
0
3
(and hence |P| 4), as well as a dynamical causal
order. Consider thus a 4-partite scenario, with par-
ties A, B
1
, B
2
and B
3
. Party A receives as input a
6-valued variable x (and has no output); A’s input
determines the causal order of the three subsequent
Accepted in Quantum 2017-12-06, click title to verify 16
parties B
k
(see Fig. 5), with each possible value of x
corresponding to one of the six possible permutations,
denoted by σ
x
. For parties B
k
we consider the lazy
scenario, with inputs y
k
{0, 1} and outputs b
k
= 0
if y
k
= 0, b
k
{0, 1} if y
k
= 1. We then define the de-
terministic correlation P
det
by the response functions
b
σ
x
(1)
=0, b
σ
x
(2)
=y
σ
x
(1)
y
σ
x
(2)
, b
σ
x
(3)
=y
σ
x
(2)
y
σ
x
(3)
.
(35)
While the correlation P
det
thus obtained is fully
causal (i.e., it is P-causal for the “full partition” P
such that |P| = N = 4), it is not P
0
-causal for any
3-subset partition P
0
of {A, B
1
, B
2
, B
3
}—which also
implies, since P
det
is deterministic, that it is not de-
composable as a convex combination of P
0
-causal cor-
relations for various 3-subset partitions P
0
either. In-
deed, such a P
0
would contain (2 singletons and) a
pair of parties grouped together, {A, B
i
} or {B
i
, B
j
}.
Consider the first case first: as P
det
is determinis-
tic, and the outputs of all parties B
k
depend on x,
any P
0
-causal correlation should be compatible with
the subset {A, B
i
} being first, with therefore b
i
in-
dependent of y
k
for k 6= i; this, however, cannot be
because, for every i = 1, 2, 3, we can find x such that
i = σ
x
(2), so that b
i
= y
σ
x
(1)
y
i
, which depends on
y
k
with k = σ
x
(1) 6= i. In the second case where
P
0
= {{A}, {B
i
, B
j
}, {B
k
}}, according to Proposi-
tion 12, a deterministic P
0
-causal correlation must be
such that for each given value of x one must either
have that b
i
and b
j
should be independent of y
k
, or
that b
k
is independent of y
i
and y
j
; this is however
not satisfied for the value of x such that σ
x
(1) = i,
σ
x
(2) = k, σ
x
(3) = j.
In short, for any pair of parties there exists some
input x of party A for which a third party must act
in between the said pair, so that this pair of parties
cannot be causally ordered with the other two (single-
tons of) parties. This shows that the correlation P
det
defined above is indeed not P
0
-causal for any 3-subset
partition P
0
—and as said above, being deterministic,
it is not a convex mixture of P
0
-causal partitions for
various such partitions P
0
either.
D Proof of completeness of Theo-
rem 11
In order to prove that Theorem 11 completely char-
acterises the possible inclusions between M-causal
and size-S-causal polytopes, we first prove the follow-
ing lemma regarding non-inclusions between P-causal
polytopes (which is perhaps of interest in and of it-
self).
Lemma 13. Given a partition P and a set of parti-
tions {P
0
1
, . . . , P
0
r
}, none of which is a coarse-graining
of P, the convex hull of the P
0
j
-causal polytopes, j =
1, . . . , r, does not contain the P-causal polytope.
Proof. It suffices here to show that, if no partition
among P
0
1
, . . . , P
0
r
is a coarse-graining of a partition
P, it is possible to find a deterministic P-causal corre-
lation that is not P
0
j
-causal for any j = 1, . . . , r. The
given correlation being deterministic, this will indeed
imply that it is also not a convex mixture of P
0
j
-causal
correlations.
We can again take the correlation P
det
P
defined in
Eq. (34), for any choice of the permutation σ. Recall
that for this correlation the output of each party de-
pends nontrivially on the inputs of all parties in the
same subset. As already established for case ii) in Ap-
pendix B.2, no such correlation is P
0
j
-causal for any
partition P
0
j
that is not a coarse-graining of P, which
proves the result.
Note that the assumption that none of the parti-
tions P
0
j
is a coarse-graining of P is crucial in the
above proof, and the conclusion of the theorem does
not necessarily hold otherwise: as noted in Sec. 4.2
already, Eq. (15) indeed shows that a P-causal corre-
lation, with P = {A
`
}
`
, can be written as a convex
combination of P
0
`
-causal correlations, with the parti-
tions P
0
`
= {A
`
, N \A
`
} being coarse-grainings of P.
Let us now prove the completeness of Theorem 11.
To this end, let us consider first a partition P with
|P| = M that consists of M 1 singletons and an
(NM+1)-partite subset. Such a partition saturates
the first inequality in Eq. (23), i.e., it satisfies s(P) =
N M +1. Let us then take S < N M +1. The size-
S-causal polytope is, by definition, the convex hull
of all P
0
j
-causal polytopes for all partitions P
0
j
with
s(P
0
j
) S. None of these partitions can be a coarse-
graining of P, as this would imply (since coarse-
graining can only increase the size of the largest subset
in a partition) s(P
0
j
) s(P) = N M + 1 > S, in
contradiction with s(P
0
j
) S. But then Lemma 13
shows that the P-causal polytope is not contained in
the size-S-causal polytope, and (since |P| = M) this
thus implies that the M-causal polytope is not con-
tained in the size-S-causal polytope.
Similarly, consider a partition P with s(P) = S,
that consists of
N
S
groups of S parties and, if N is
not a multiple of S, a final group containing the re-
maining N
N
S
S parties. Such a partition thus con-
tains |P| =
N
S
subsets. Let us now take M >
N
S
.
The M-causal polytope is, again by definition, the
convex hull of all P
0
j
-causal polytopes for all parti-
tions P
0
j
with |P
0
j
| M. None of these partitions
can be a coarse-graining of P, as this would imply
(since coarse-graining can only decrease the number
of subsets in a partition) |P
0
j
| |P| =
N
S
< M, in
contradiction with |P
0
j
| M. Lemma 13 then again
shows that the P-causal polytope is not contained in
the M-causal polytope, and (since s(P) = S) this
then implies that the size-S-causal polytope is not
contained in the M-causal polytope, which completes
the proof.
Accepted in Quantum 2017-12-06, click title to verify 17
Finally, let us also note that since no partition P
0
with |P
0
| M
0
> M is a coarse-graining of any parti-
tion P with |P| = M, and since no partition P
0
with
s(P
0
) S
0
< S is a coarse-graining of any partition
P with s(P) = S, invoking Lemma 13 also provides a
proof (as an alternative to our use of the families of M-
causal and size-S-causal inequalities (17) and (21) be-
fore) that all inclusions among M-causal and among
size-S-causal polytopes are strict.
Accepted in Quantum 2017-12-06, click title to verify 18