# Genuinely Multipartite Noncausality

Alastair A. Abbott  University Grenoble Alpes, CNRS, Grenoble INP, Institut
Néel, 38000 Grenoble, France  Julian Wechs  University Grenoble Alpes, CNRS,
Grenoble INP, Institut Néel, 38000 Grenoble, France  Fabio Costa  Centre for
Engineered Quantum Systems, School of Mathematics and Physics, The University
of Queensland, St Lucia, QLD 4072, Australia  Cyril Branciard  University
Grenoble Alpes, CNRS, Grenoble INP, Institut Néel, 38000 Grenoble, France

(December 7, 2017)

###### Abstract

The study of correlations with no definite causal order has revealed a rich
structure emerging when more than two parties are involved. This motivates the
consideration of multipartite “noncausal” correlations that cannot 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 order between the subsets exists. We prove that such
correlations can be characterised as lying outside a polytope, whose vertices
correspond to deterministic strategies and whose facets define what we call
“2-causal” inequalities. 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 violation 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 multipartite resource.

##  1 Introduction

Understanding the correlations between events, or between the parties that
observe them, is a central objective in science. In order to provide an
explanation for a given correlation, one typically refers to the notion 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]. Investigations 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 [6, 7, 8, 9]—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
natural question arises: is the noncausality of these correlations a truly
multipartite phenomenon, or can it be reduced to a simpler one, that involves
fewer parties? 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 receives an input $x$, $y$, and returns an output $a$,
$b$, respectively. 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\prec 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
$A$—$B\prec 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 however still compatible with an explanation
in terms of $A\prec B$ or $B\prec A$, and is therefore encompassed in the
previous two cases.) A causal correlation is defined as one that is compatible
with either $A\prec B$ or $B\prec 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 [4, 3].

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 generalisation to $N$ parties) [8, 9]. In contrast, a
_noncausal_ tripartite 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 decomposition may still be possible for a tripartite
noncausal correlation if one does not demand that (all) the bipartite
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\prec\\{B,C\\}$, if $B$ and $C$ are grouped together to define a new
“effective party” and act “as one”. This illustrates that although a
multipartite correlation may be noncausal, there might still exist some
definite causal order between certain subsets of parties; the intuition that
motivates our work is that such a correlation would therefore not display
genuinely multipartite noncausality.

This paper is organised as follows. In Sec. 2, we introduce 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 simplest nontrivial
tripartite scenario where these concepts make sense; we present explicit
2-causal inequalities for that scenario, investigate their violations in the
process matrix framework of Ref. [4], and generalise 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 different hierarchies of criteria that quantify the
extent to which the noncausality of a correlation is a genuinely multipartite
phenomenon.

##  2 Genuinely $N$-partite noncausal correlations

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\geq 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
$\vec{x}=(x_{1},\ldots,x_{N})$ and $\vec{a}=(a_{1},\ldots,a_{N})$. The
correlations between the $N$ parties are given by the conditional probability
distribution $P(\vec{a}|\vec{x})$. For some (nonempty) subset
$\mathcal{K}=\\{k_{1},\ldots,k_{|\mathcal{K}|}\\}$ of
$\mathcal{N}\coloneqq\\{1,\ldots,N\\}$, we denote by
$\vec{x}_{\mathcal{K}}=(x_{k_{1}},\ldots,x_{k_{|\mathcal{K}|}})$ and
$\vec{a}_{\mathcal{K}}=(a_{k_{1}},\ldots,a_{k_{|\mathcal{K}|}})$ the vectors
of inputs and outputs of the parties in $\mathcal{K}$; with this notation,
$\vec{x}_{\mathcal{N}\backslash\mathcal{K}}$ and
$\vec{a}_{\mathcal{N}\backslash\mathcal{K}}$ (or simply
$\vec{x}_{\mathcal{N}\backslash k}$ and $\vec{a}_{\mathcal{N}\backslash k}$
for a singleton $\mathcal{K}=\\{k\\}$) denote the vectors of inputs and
outputs of all parties that are not in $\mathcal{K}$. For simplicity we will
identify the parties’ names with their labels, so that
$\mathcal{N}=\\{1,\ldots,N\\}\equiv\\{A_{1},\ldots,A_{N}\\}$, and similarly
for any subset $\mathcal{K}$.

###  2.1 Definitions

The assumption that the parties in such a scenario are embedded into a well-
defined causal structure restricts 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
correlations 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
correlations—which, for clarity, we shall often call fully causal here—can be
defined iteratively in the following way:

######  Definition 1 ((Fully) causal correlations).

  * •

For $N=1$, any valid probability distribution $P(a_{1}|x_{1})$ is (fully)
causal;

  * •

For $N\geq 2$, an $N$-partite correlation is (fully) causal if and only if it
can be decomposed in the form

$P(\vec{a}|\vec{x})=\sum_{k\in\mathcal{N}}\ q_{k}\ P_{k}(a_{k}|x_{k})\
P_{k,x_{k},a_{k}}(\vec{a}_{\mathcal{N}\backslash
k}|\vec{x}_{\mathcal{N}\backslash k})$ (2)

with $q_{k}\geq 0$ for each $k$, $\sum_{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}}(\vec{a}_{\mathcal{N}\backslash
k}|\vec{x}_{\mathcal{N}\backslash k})$ is a (fully) causal $(N{-}1)$-partite
correlation.

As the tripartite example in the introduction shows, there can be situations
in which no overall causal order exists, but where there still is a (“coarse-
grained”) causal order between certain subsets of parties, obtained by
grouping certain parties together. The correlations that can be established in
such situations are more general than causal correlations, but nevertheless
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 parties 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 subsets together into the complementary subset,
which then comes second. We shall for now consider partitions of $\mathcal{N}$
into just two (nonempty) subsets $\mathcal{K}$ and
$\mathcal{N}\backslash\mathcal{K}$, and we thus introduce the following
definition:

######  Definition 2 ($2$-causal correlations).

An $N$-partite correlation (for $N\geq 2$) is said to be $2$-causal if and
only if it can be decomposed in the form

$P(\vec{a}|\vec{x})=\sum_{\emptyset\subsetneq\mathcal{K}\subsetneq\mathcal{N}}q_{\mathcal{K}}\,P_{\mathcal{K}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})\,P_{\mathcal{K},\vec{x}_{\mathcal{K}},\vec{a}_{\mathcal{K}}}(\vec{a}_{\mathcal{N}\backslash\mathcal{K}}|\vec{x}_{\mathcal{N}\backslash\mathcal{K}})$
(3)

where the sum runs over all nonempty strict subsets $\mathcal{K}$ of
$\mathcal{N}$, with $q_{\mathcal{K}}\geq 0$ for each $\mathcal{K}$,
$\sum_{\mathcal{K}}q_{\mathcal{K}}=1$, and where (for each $\mathcal{K}$)
$P_{\mathcal{K}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})$ is a valid
probability distribution for the parties in $\mathcal{K}$ and (for each
$\mathcal{K},\vec{x}_{\mathcal{K}},\vec{a}_{\mathcal{K}}$)
$P_{\mathcal{K},\vec{x}_{\mathcal{K}},\vec{a}_{\mathcal{K}}}(\vec{a}_{\mathcal{N}\backslash\mathcal{K}}|\vec{x}_{\mathcal{N}\backslash\mathcal{K}})$
is a valid probability distribution for the remaining $N{-}|\mathcal{K}|$
parties.

For ${N=2}$, the above definition reduces to the standard 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_{\mathcal{K}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})\,P_{\mathcal{K},\vec{x}_{\mathcal{K}},\vec{a}_{\mathcal{K}}}(\vec{a}_{\mathcal{N}\backslash\mathcal{K}}|\vec{x}_{\mathcal{N}\backslash\mathcal{K}})$
for each bipartition $\\{\mathcal{K},\mathcal{N}\backslash\mathcal{K}\\}$
describes correlations compatible with all the parties in $\mathcal{K}$ acting
before all the parties in $\mathcal{N}\backslash\mathcal{K}$, since the choice
of inputs for the parties in $\mathcal{N}\backslash\mathcal{K}$ does not
affect the outputs for the parties in $\mathcal{K}$. The convex combination in
Eq. (3) then takes into account the possibility that the subset $\mathcal{K}$
acting first can be chosen randomly.111One can easily see that it is indeed
sufficient to consider just one term per bipartition
$\\{\mathcal{K},\mathcal{N}\backslash\mathcal{K}\\}$ in the sum (3). That is,
for some given $\mathcal{K}$, some correlations
$P^{\prime}(\vec{a}|\vec{x})=P^{\prime}_{\mathcal{K}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})\,P^{\prime}_{\mathcal{K},\vec{x}_{\mathcal{K}},\vec{a}_{\mathcal{K}}}(\vec{a}_{\mathcal{N}\backslash\mathcal{K}}|\vec{x}_{\mathcal{N}\backslash\mathcal{K}})$
and
$P^{\prime\prime}(\vec{a}|\vec{x})=P^{\prime\prime}_{\mathcal{K}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})\,P^{\prime\prime}_{\mathcal{K},\vec{x}_{\mathcal{K}},\vec{a}_{\mathcal{K}}}(\vec{a}_{\mathcal{N}\backslash\mathcal{K}}|\vec{x}_{\mathcal{N}\backslash\mathcal{K}})$,
and some weights $q^{\prime},q^{\prime\prime}\geq 0$ with
$q^{\prime}+q^{\prime\prime}=1$, the convex mixture
$P(\vec{a}|\vec{x})=q^{\prime}P^{\prime}(\vec{a}|\vec{x})+q^{\prime\prime}P^{\prime\prime}(\vec{a}|\vec{x})$
is also of the same form
$P(\vec{a}|\vec{x})=P_{\mathcal{K}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})\,P_{\mathcal{K},\vec{x}_{\mathcal{K}},\vec{a}_{\mathcal{K}}}(\vec{a}_{\mathcal{N}\backslash\mathcal{K}}|\vec{x}_{\mathcal{N}\backslash\mathcal{K}})$
(with
$P_{\mathcal{K}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})=q^{\prime}P^{\prime}_{\mathcal{K}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})+q^{\prime\prime}P^{\prime\prime}_{\mathcal{K}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})$
and
$P_{\mathcal{K},\vec{x}_{\mathcal{K}},\vec{a}_{\mathcal{K}}}=P(\vec{a}|\vec{x})/P_{\mathcal{K}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})$).
This already implies, in particular, that 2-causal correlations form a convex
set.

For correlations that are not 2-causal, we introduce the following
terminology:

######  Definition 3 (Genuinely $N$-partite noncausal correlations).

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 definite causal relation between any two
(complementary) subsets of parties, even when taking into consideration the
possibility that the subset acting first may be chosen probabilistically.

###  2.2 Characterisation of the set of 2-causal correlations 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 causal correlation can be written as a
convex combination 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 $\mathcal{K}$ of $\mathcal{N}$,
$P_{\mathcal{K}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})\,P_{\mathcal{K},\vec{x}_{\mathcal{K}},\vec{a}_{\mathcal{K}}}(\vec{a}_{\mathcal{N}\backslash\mathcal{K}}|\vec{x}_{\mathcal{N}\backslash\mathcal{K}})$
defines an “effectively bipartite” correlation, that is, a bipartite
correlation between an effective party $\mathcal{K}$ with input
$\vec{x}_{\mathcal{K}}$ and output $\vec{a}_{\mathcal{K}}$ and an effective
party $\mathcal{N}\backslash\mathcal{K}$ with input
$\vec{x}_{\mathcal{N}\backslash\mathcal{K}}$ and output
$\vec{a}_{\mathcal{N}\backslash\mathcal{K}}$, which are formed by grouping
together all parties in the respective subsets. That effectively bipartite
correlation is compatible with the causal order222The notation
$\mathcal{K}_{1}\prec\mathcal{K}_{2}$ (or simply $A_{k_{1}}\prec A_{k_{2}}$
for singletons $\mathcal{K}_{j}=\\{A_{k_{j}}\\}$), already used in the
introduction, formally means that the correlation under consideration
satisfies
$P(\vec{a}_{\mathcal{K}_{1}}|\vec{x})=P(\vec{a}_{\mathcal{K}_{1}}|\vec{x}_{\mathcal{N}\backslash\mathcal{K}_{2}})$.
It will also be extended to more subsets, with
$\mathcal{K}_{1}\prec\mathcal{K}_{2}\prec\cdots\prec\mathcal{K}_{m}$ meaning
that
$P(\vec{a}_{\mathcal{K}_{1}\cup\cdots\cup\mathcal{K}_{j}}|\vec{x})=P(\vec{a}_{\mathcal{K}_{1}\cup\cdots\cup\mathcal{K}_{j}}|\vec{x}_{\mathcal{N}\backslash(\mathcal{K}_{j+1}\cup\cdots\cup\mathcal{K}_{m})})$
for all $j=1,\ldots,m-1$. $\mathcal{K}\prec\mathcal{N}\backslash\mathcal{K}$.
As mentioned above, the set of such correlations forms a convex polytope whose
extremal points are deterministic, effectively bipartite causal correlations
[5]—which, according to Definition 2, define deterministic 2-causal
$N$-partite correlations.

Eq. (2) then implies that the set of 2-causal correlations is the convex hull
of all such polytopes for each nonempty strict subset $\mathcal{K}$ of
$\mathcal{N}$; it is thus itself a convex polytope, whose extremal points are
indeed deterministic 2-causal correlations. ∎

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 correlations, 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.

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 $\vec{\alpha}$ that assigns a list of outputs
$\vec{a}=\vec{\alpha}(\vec{x})$ to the list of inputs $\vec{x}$, such that the
corresponding probability distribution
$P_{\vec{\alpha}}^{\text{det}}(\vec{a}|\vec{x})=\delta_{\vec{a},\vec{\alpha}(\vec{x})}$
is 2-causal, and thus satisfies Eq. (3). Since
$P_{\vec{\alpha}}^{\text{det}}(\vec{a}|\vec{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 $\mathcal{K}$ that acts first.
That is, $\vec{\alpha}$ is such that the outputs $\vec{a}_{\mathcal{K}}$ of
the parties in $\mathcal{K}$ are determined exclusively by their inputs
$\vec{x}_{\mathcal{K}}$, while the outputs
$\vec{a}_{\mathcal{N}\backslash\mathcal{K}}$ of the remaining parties are
determined by all inputs $\vec{x}$. The facets of the 2-causal polytope are
linear inequalities that are satisfied by all 2-causal correlations; we shall
call these 2-causal inequalities (see Fig. 1).

##  3 Analysis of the tripartite “lazy scenario”

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}$ receives 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}\in\\{0,1\\}$. The set of fully causal correlations was completely
characterised for this scenario in Ref. [9], which will furthermore permit us
to compare the noncausal and genuinely tripartite noncausal correlations in
this concrete example.

As is standard (and as we did in the introduction), 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 complete tripartite
probability distribution by $P_{ABC}$ [i.e., $P_{ABC}(abc|xyz)\coloneqq
P(abc|xyz)$] and the marginal distributions for the indicated parties by
$P_{AB}$, $P_{A}$, etc. [e.g., $P_{AB}(ab|xyz)=\sum_{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 decomposition
of the form (3) with (because they are deterministic) a single term in the sum
(corresponding to a single group of parties acting first). One finds that
there are $1\,520$ such distributions, and thus vertices.

In order to determine the facets of the polytope, which in turn correspond to
tight 2-causal inequalities, 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 $21\,154$ facets, each
corresponding to a 2-causal inequality, the violation of which would certify
genuinely tripartite noncausality. Many inequalities, however, can be obtained
from others 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 positivity 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
correlations (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 distribution required to saturate them, in the
Supplementary Material [24], and will analyse in more detail 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 majority of facet-inducing inequalities of
the causal polytope do not single out genuinely tripartite noncausal
correlations. Moreover, none of the 2-causal inequalities we obtain here
differ from facet-inducing fully causal inequalities only in their bound, and,
except for the aforementioned cases, our 2-causal inequalities thus represent
novel inequalities.

####  3.1.2 Three interesting inequalities

Of the nontrivial 2-causal inequalities, those that display certain symmetries
between the parties are particularly interesting since they tend to have
comparatively simple forms and often permit natural interpretations (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

$\displaystyle I_{1}$
$\displaystyle=\big{[}P_{A}(1|100)+P_{B}(1|010)+P_{C}(1|001)\big{]}$
$\displaystyle+\big{[}P_{AB}(11|110)+P_{BC}(11|011)+P_{AC}(11|101)\big{]}$
$\displaystyle-P_{ABC}(111|111)\geq 0,$ (4)

which can be naturally expressed as a causal game. Indeed, it can be rewritten
as

$P\big{(}\tilde{a}\tilde{b}\tilde{c}=xyz\big{)}\ \leq\ 3/4\,,$ (5)

where $\tilde{a}=1$ if $x=0$, $\tilde{a}=a$ if $x=1$ (i.e.,
$\tilde{a}=xa\oplus x\oplus 1$, where $\oplus$ denotes addition modulo 2), and
similarly for $\tilde{b}$ and $\tilde{c}$, and where it is implicitly assumed
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
nontrivial 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 inequality is the following:

$\displaystyle I_{2}=1+2\big{[}P_{A}(1|100)+P_{B}(1|010)+P_{C}(1|001)\big{]}$
$\displaystyle-\big{[}P_{AB}(11|110)+P_{BC}(11|011)+P_{AC}(11|101)\big{]}$
$\displaystyle\geq 0,$ (6)

whose interpretation can be made clearer by rewriting it as

$\displaystyle P_{A}(1|100)+P_{B}(1|010)-P_{AB}(11|110)$
$\displaystyle+\,P_{B}(1|010)+P_{C}(1|001)-P_{BC}(11|011)$
$\displaystyle+\,P_{A}(1|100)+P_{C}(1|001)-P_{AC}(11|101)$
$\displaystyle\geq-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)
inequalities [9], one for each pair of parties (conditioned on the remaining
party having input $0$), while the negative 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 inequality between them (and thus
reach the minimum algebraic bound $-1$). This inequality can be interpreted 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 distributed) for a 2-causal
correlation is $5/4$, corresponding to the 2-causal bounds of $0$ in Eq.
(3.1.2) and $-1$ in Eq. (3.1.2).333The 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 order 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)=\delta_{a,0}\,\delta_{b,yz}\,\delta_{c,yz}$, where $\delta$ is the
Kronecker delta function, is compatible with the order $A\prec\\{B,C\\}$ (or
with $\\{B,C\\}\prec A$) and saturates Eqs. (3.1.2) and (3.1.2). It is also
clear from the form of Eq. (3.1.2) 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
inequalities which are symmetric under cyclic exchanges of parties. One
interesting such example is the following:

$\displaystyle I_{3}$
$\displaystyle=2+[P_{A}(1|100)+P_{B}(1|010)+P_{C}(1|001)\big{]}$
$\displaystyle-\big{[}P_{A}(1|101)+P_{B}(1|110)+P_{C}(1|011)\big{]}\geq 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)

$\displaystyle P\big{(}x(y\oplus 1)(a\oplus z)=y(z\oplus 1)(b\oplus x)$
$\displaystyle\hskip 56.9055pt=z(x\oplus 1)(c\oplus y)=0\big{)}\ \leq\ 7/8\,,$
(9)

where the goal of the game is for each party, whenever they receive the input
1 and their right-hand neighbour 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$).444The 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)=\delta_{a,x}\,\delta_{b,xy}\,\delta_{c,yz}$, compatible with the
order $A\prec B\prec C$, which wins the game in all cases except when
$(x,y,z)=(1,0,0)$. This inequality is of additional interest as it is one of
the two nontrivial inequalities which is also a facet of the standard causal
polytope for this scenario. (The second such inequality, which lacks the
symmetry of this one, is presented in the Supplementary Material [24].)

###  3.2 Violations of 2-causal inequalities by process matrix correlations

One of the major sources of interest in causal inequalities 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 (possibly noncausal)
interactions between the parties are described by a process matrix $W$, which,
along with a description of the operations performed by the parties, allows
the correlations $P(\vec{a}|\vec{x})$ to be calculated.

It is well-known that process matrix correlations can violate causal
inequalities [9, 6, 7, 5, 4], 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 tripartite lazy scenario can
be violated by process matrices. However, for most inequalities violation was
found to be possible using process matrices $W^{\\{A,B\\}\prec C}$ that are
compatible with $C$ acting last, which means the correlations they produced
were necessarily 2-causal. It is therefore interesting to see whether process
matrices are capable of violating 2-causal inequalities in general, and thus
of exhibiting genuinely $N$-partite noncausality. We will not present the
process matrix formalism here, and instead simply summarise our findings; we
refer the reader to Refs. [14, 4] 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. (3.1.2)
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,555Incidentally, exactly the same number of families of fully
causal inequalities were found to be violable with classical process matrices
in Ref. [9]. It remains unclear whether this is merely a coincidence or the
result of a deeper connection. a phenomenon that is not present in the
bipartite scenario where classical 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. (3.1.2), and its decomposition in Eq.
(3.1.2) into three LGYNI inequalities helps provide an explanation. In
particular, the seemingly best possible violation of a (conditional) LGYNI
inequality using qubits is approximately $0.2776$ [9, 5], whereas it is clear
that a process matrix violating Eq. (3.1.2) must necessarily violate a
conditional LGYNI inequality between 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. (3.1.2) 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 inequalities cannot be saturated
by fully causal distributions; it is interesting that the remaining
inequalities that require noncausal but 2-causal distributions to saturate can
nonetheless be violated by process matrix correlations.

###  3.3 Generalised 2-causal inequalities for $N$ parties

Although it quickly becomes intractable to completely characterise the
2-causal polytope for more complicated scenarios with more parties, inputs
and/or outputs, 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 (3.1.2), for example, can naturally be generalised to give a
2-causal inequality valid for all $N\geq 2$.666We continue to focus on the
lazy scenario defined earlier for concreteness, but we note that the proofs of
the generalised inequalities (3.3) 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. Specifically, one
obtains

$\displaystyle J_{1}(N)=$
$\displaystyle\sum_{\emptyset\subsetneq\mathcal{K}\subsetneq\mathcal{N}}P\big{(}\vec{a}_{\mathcal{K}}=\vec{1}\,|\,\vec{x}_{\mathcal{K}}=\vec{1},\vec{x}_{\mathcal{N}\backslash\mathcal{K}}=\vec{0}\big{)}\qquad$
$\displaystyle\hskip
62.59605pt-P\big{(}\vec{a}=\vec{1}\,|\,\vec{x}=\vec{1}\big{)}\geq 0$ (10)

where $\vec{1}=(1,\dots,1)$ and $\vec{0}=(0,\dots,0)$, which can be written
analogously to Eq. (5) as a game (again implicitly defined with uniform
inputs) of the form

$P(\Pi_{k}\tilde{a}_{k}=\Pi_{k}x_{k})\leq 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 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
$136\,818\,592$) we were able to verify that $J_{1}(4)\geq 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
considering the (fully causal) strategy where each party always outputs 0.

It is also possible to generalise inequality (3.1.2) to $N$ parties—which will
prove more interesting later—by considering a scored game in which every pair
of parties gets one point if they win their respective bipartite LGYNI game
and all other parties’ inputs are 0, and the goal of the game is to maximise
the total 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 inequality 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 bipartite LGYNI inequality.
Specifically, we obtain the 2-causal inequality

$J_{2}(N)=\sum_{\\{i,j\\}\subset\mathcal{N}}L_{N}(i,j)\geq-\binom{N-1}{2}$
(12)

where $\binom{n}{2}=n(n{-}1)/2$ is a binomial coefficient and

$\displaystyle L_{N}(i,j)=\,$ $\displaystyle
P\big{(}a_{i}=1|x_{i}x_{j}=10,\vec{x}_{\mathcal{N}\backslash\\{i,j\\}}=\vec{0}\big{)}$
$\displaystyle\\!\\!+P\big{(}a_{j}=1|x_{i}x_{j}=01,\vec{x}_{\mathcal{N}\backslash\\{i,j\\}}=\vec{0}\big{)}$
$\displaystyle\\!\\!-P\big{(}a_{i}a_{j}=11|x_{i}x_{j}=11,\vec{x}_{\mathcal{N}\backslash\\{i,j\\}}=\vec{0}\big{)}.$
(13)

Each term $L_{N}(i,j)$ defines a bipartite conditional LGYNI inequality with
the causal bound $L_{N}(i,j)\geq 0$, and the minimum algebraic bound (i.e. the
maximal violation) $-1$. The minimum algebraic bound of $J_{2}(N)$ is thus
$-\binom{N}{2}$. The validity of inequality (12) for 2-causal correlations
(which corresponds to a maximal average score of
$(2N{-}1)(N{-}1)/2^{N}$—compared to the maximal algebraic value of
$2N(N{-}1)/2^{N}$—for the corresponding game with uniform inputs) is again
formally proved in Appendix A.

We note that in contrast to Eq. (3.3), $J_{2}(4)\geq-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 $\mathcal{K}=\\{1,\dots,N-1\\}$ and take the
distribution

$P(\vec{a}|\vec{x})=\delta_{\vec{a}_{\mathcal{K}},f(\vec{x}_{\mathcal{K}})}\,\delta_{a_{N},0}$
(14)

with $f(\vec{x}_{\mathcal{K}})=\vec{x}_{\mathcal{K}}$ if
$\vec{x}_{\mathcal{K}}$ contains exactly two inputs 1, and
$f(\vec{x}_{\mathcal{K}})=\vec{0}$ otherwise. $P(\vec{a}|\vec{x})$ is clearly
2-causal since it is compatible with the causal order
$\mathcal{K}\prec\mathcal{N}\backslash\mathcal{K}$ (indeed, also with
$\mathcal{N}\backslash\mathcal{K}\prec\mathcal{K}$). One can then easily
verify that $P(\vec{a}|\vec{x})$ saturates (12), since all $\binom{N-1}{2}$
pairs of parties in $\mathcal{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 cannot arise given a
definite causal order between two subsets of parties. It makes sense to
consider more refined 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 established 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 distinct
characterisations of how genuinely multipartite the observed noncausality is.

###  4.1 $\mathcal{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 imposed on the correlations within each group.

Figure 2: The $N$ parties $A_{k}$ are grouped into $|\mathcal{P}|$ disjoint
subsets $\mathcal{A}_{\ell}$, according to the partition
$\mathcal{P}=\\{\mathcal{A}_{1},\ldots,\mathcal{A}_{|\mathcal{P}|}\\}$. The
parties in a subset $\mathcal{A}_{\ell}$ act “as one”, thus defining an
“effective party”. To define $\mathcal{P}$-causal correlations, the
$N$-partite correlation $P(a_{1},\ldots,a_{N}|x_{1},\ldots,x_{N})$ is
considered as an effectively $|\mathcal{P}|$-partite correlation
$P({\vec{a}}_{\mathcal{A}_{1}},\ldots,{\vec{a}}_{\mathcal{A}_{|\mathcal{P}|}}|{\vec{x}}_{\mathcal{A}_{1}},\ldots,{\vec{x}}_{\mathcal{A}_{|\mathcal{P}|}})$.

Let us consider for this purpose a partition
$\mathcal{P}=\\{\mathcal{A}_{1},\ldots,\mathcal{A}_{|\mathcal{P}|}\\}$ of
$\mathcal{N}$—i.e., a set of $|\mathcal{P}|$ nonempty disjoint subsets
$\mathcal{A}_{\ell}$ of $\mathcal{N}$, such that
$\cup_{\ell}\mathcal{A}_{\ell}=\mathcal{N}$, see Fig. 2. Note that if
$\mathcal{P}$ contains at least two subsets, then for a given subset
$\mathcal{A}_{\ell}\subset\mathcal{N}$,
$\mathcal{P}\backslash\\{\mathcal{A}_{\ell}\\}$ also represents a partition of
$\mathcal{N}\backslash\mathcal{A}_{\ell}$. Let us then introduce the following
definition:

######  Definition 5 ($\mathcal{P}$-causal correlations).

For a given partition $\mathcal{P}$ of $\mathcal{N}$, an $N$-partite
correlation $P$ is said to be $\mathcal{P}$-causal if and only if $P$ is
causal when considered as an effective $|\mathcal{P}|$-partite correlation,
where each subset in $\mathcal{P}$ defines an effective party.

More precisely, analogously to Definition 1:

  * •

For $|\mathcal{P}|=1$, any $N$-partite correlation $P$ is
$\mathcal{P}$-causal;

  * •

For $|\mathcal{P}|\geq 2$, an $N$-partite correlation $P$ is
$\mathcal{P}$-causal if and only if it can be decomposed in the form

$\displaystyle P(\vec{a}|\vec{x})=$
$\displaystyle\sum_{{\mathcal{A}_{\ell}}\in\mathcal{P}}q_{\mathcal{A}_{\ell}}\,P_{\mathcal{A}_{\ell}}(\vec{a}_{\mathcal{A}_{\ell}}|\vec{x}_{\mathcal{A}_{\ell}})\hskip
85.35826pt$ $\displaystyle\hskip 5.69054pt\times
P_{\mathcal{A}_{\ell},\vec{x}_{\mathcal{A}_{\ell}},\vec{a}_{\mathcal{A}_{\ell}}}(\vec{a}_{\mathcal{N}\backslash{\mathcal{A}_{\ell}}}|\vec{x}_{\mathcal{N}\backslash{\mathcal{A}_{\ell}}})\quad$
(15)

with $q_{\mathcal{A}_{\ell}}\geq 0$ for each $\mathcal{A}_{\ell}$,
$\sum_{\mathcal{A}_{\ell}}q_{\mathcal{A}_{\ell}}=1$, where (for each
$\mathcal{A}_{\ell}$)
$P_{\mathcal{A}_{\ell}}(\vec{a}_{\mathcal{A}_{\ell}}|\vec{x}_{\mathcal{A}_{\ell}})$
is a valid probability distribution for the parties in $\mathcal{A}_{\ell}$
and (for each
$\mathcal{A}_{\ell},\vec{x}_{\mathcal{A}_{\ell}},\vec{a}_{\mathcal{A}_{\ell}}$)
$P_{\mathcal{A}_{\ell},\vec{x}_{\mathcal{A}_{\ell}},\vec{a}_{\mathcal{A}_{\ell}}}(\vec{a}_{\mathcal{N}\backslash{\mathcal{A}_{\ell}}}|\vec{x}_{\mathcal{N}\backslash{\mathcal{A}_{\ell}}})$
is a $(\mathcal{P}\backslash\\{\mathcal{A}_{\ell}\\})$-causal correlation for
the remaining $N-|\mathcal{A}_{\ell}|$ parties.

In the extreme case of a single-set partition $\mathcal{P}=\\{\mathcal{N}\\}$
($|\mathcal{P}|=1$), any correlation is by definition trivially
$\mathcal{P}$-causal; at the other extreme, for a partition of $\mathcal{N}$
into $N$ singletons ($|\mathcal{P}|=N$), the definition of
$\mathcal{P}$-causal correlations above is equivalent to that of fully causal
correlations, Definition 1 [8, 9]. Between these two extreme cases, a
$\mathcal{P}$-causal correlation identifies the situation where, with some
probability, all parties within one group act before all other parties;
conditioned on their inputs and outputs, another group acts second (before all
remaining parties) with some probability; and so on. We emphasise that no
constraint is imposed on the correlations that can be generated 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 $\mathcal{P}$-causal correlations above matches that
of causal correlations for the $|\mathcal{P}|$ effective parties defined by
$\mathcal{P}$, all basic properties of causal correlations (see Ref. [9])
generalise straightforwardly to $\mathcal{P}$-causal correlations. Note in
particular that the definition captures the idea of dynamical causal order,
where the causal order between certain subsets of parties in $\mathcal{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 $\mathcal{P}$, the set of $\mathcal{P}$-causal correlations
forms a convex polytope, whose (finitely many) extremal points correspond to
deterministic $\mathcal{P}$-causal correlations.

We shall call this polytope the _$\mathcal{P}$ -causal polytope_; its facets
define _$\mathcal{P}$ -causal inequalities_. Theorem 6 implies that any
$\mathcal{P}$-causal correlation can be obtained as a probabilistic mixture of
deterministic $\mathcal{P}$-causal correlations. It is useful to note that,
similarly to Ref. [9], deterministic $\mathcal{P}$-causal correlations can be
interpreted in the following way: a set $\mathcal{A}_{t_{1}}$ of parties acts
with certainty before all others, with their outputs being a deterministic
function of all inputs in that set but independent of the inputs of any other
parties,
$\vec{a}_{{\mathcal{A}_{t_{1}}}}=\vec{\alpha}_{{\mathcal{A}_{t_{1}}}}(\vec{x}_{{\mathcal{A}_{t_{1}}}})$.
The inputs of the first set also determine which set comes second,
$\mathcal{A}_{t^{\vec{x}}_{2}}$, where
$t^{\vec{x}}_{2}=t_{2}(\vec{x}_{{\mathcal{A}_{t_{1}}}})$, whose outputs can
depend on all inputs 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 $\vec{x}$ thus determines (in a not necessarily unique way) a given
causal order for the sets of parties in $\mathcal{P}$.

###  4.2 Non-inclusion relations for $\mathcal{P}$-causal polytopes

As suggested earlier, our goal is to quantify the extent to which a noncausal
resource is genuinely multipartite in terms of the number or size of the
subsets one needs to consider in a partition $\mathcal{P}$ to make a given
correlation $\mathcal{P}$-causal. A natural property to demand of such a
quantification is that it defines nested sets of correlations: if a
correlation is genuinely multipartite 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 $\mathcal{P}$-causal polytopes.

One might intuitively think that there should indeed be nontrivial inclusion
relations among those polytopes. For example, one might think that a
$\mathcal{P}$-causal correlation should also be $\mathcal{P}^{\prime}$-causal
if $\mathcal{P}^{\prime}$ is a “coarse-graining” of $\mathcal{P}$ (i.e.,
$\mathcal{P}^{\prime}$ is obtained from $\mathcal{P}$ by grouping some of its
groups to define fewer but larger subsets)—or, more generally, when
$\mathcal{P}^{\prime}$ contains fewer subsets than $\mathcal{P}$, i.e.
$|\mathcal{P}^{\prime}|<|\mathcal{P}|$. This, however, is not true. For
example, in the tripartite case, a fully causal correlation (i.e., a
$\mathcal{P}$-causal one for
$\mathcal{P}=\\{\\{A_{1}\\},\\{A_{2}\\},\\{A_{3}\\}\\}$) compatible with the
fixed order $A_{1}\prec A_{2}\prec A_{3}$, where $A_{2}$ comes between $A_{1}$
and $A_{3}$, may not be $\mathcal{P}^{\prime}$-causal for
$\mathcal{P}^{\prime}=\\{\\{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 nontrivial inclusion exists among $\mathcal{P}$-causal
polytopes, as established by the following theorem, proved in Appendix 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 nontrivial777If one of the two partitions is trivial, say
$\mathcal{P}^{\prime}=\\{\mathcal{N}\\}$, then the $\mathcal{P}$-causal
polytope is of course contained in the trivial $\mathcal{P}^{\prime}$-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\geq 3$. partitions $\mathcal{P}$ and $\mathcal{P}^{\prime}$
of $\mathcal{N}$ with $|\mathcal{P}|,|\mathcal{P}^{\prime}|>1$, the
$\mathcal{P}$-causal polytope is not contained in the
$\mathcal{P}^{\prime}$-causal one, nor vice versa.

One may also ask whether, for a given $\mathcal{P}$-causal correlation $P$,
there always exists a partition $\mathcal{P}^{\prime}$ with
$2\leq|\mathcal{P}^{\prime}|<|\mathcal{P}|$ such that $P$ is also
$\mathcal{P}^{\prime}$-causal (recall that the case $|\mathcal{P}^{\prime}|=1$
is trivial). The answer is negative when mixtures of different causal orders
are involved: e.g., in the tripartite case with
$\mathcal{P}=\\{\\{A_{1}\\},\\{A_{2}\\},\\{A_{3}\\}\\}$, a fully causal
correlation of the form $P=\frac{1}{6}\,(P_{A_{1}\prec A_{2}\prec
A_{3}}+P_{A_{1}\prec A_{3}\prec A_{2}}+P_{A_{2}\prec A_{1}\prec
A_{3}}+P_{A_{2}\prec A_{3}\prec A_{1}}+P_{A_{3}\prec A_{1}\prec
A_{2}}+P_{A_{3}\prec A_{2}\prec A_{1}})$, where each correlation in the sum is
compatible with the corresponding causal order, may not be
$\mathcal{P}^{\prime}$-causal for any $\mathcal{P}^{\prime}$ of the form
$\mathcal{P}^{\prime}=\\{\\{A_{i},A_{j}\\},\\{A_{k}\\}\\}_{i\neq j\neq 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_{\mathcal{P},\sigma}^{\text{det}}$
introduced in Appendix B.888To see that $P$ thus defined is indeed not
$\mathcal{P}^{\prime}$-causal for any such bipartition, first note that, by
symmetry, it suffices to show it is not $\mathcal{P}^{\prime}$-causal for
$\mathcal{P}^{\prime}=\\{\\{A_{1}\\},\\{A_{2},A_{3}\\}\\}$. One can readily
show that all such $\mathcal{P}^{\prime}$-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)\geq 0$
(which, moreover, is a facet of the $\mathcal{P}^{\prime}$-causal polytope).
It is easily verified that $P$ violates this inequality with the left-hand
side obtaining the value $-1/3$.

The above results tell us that $\mathcal{P}$-causal polytopes do not really
define useful classes to directly quantify how genuinely multipartite the
noncausality of a correlation is. One may wonder whether considering convex
hulls of $\mathcal{P}$-causal polytopes allows one to avoid these issues. For
example, is it the case that any $\mathcal{P}$-causal correlation $P$ is
contained in the convex hull of all $\mathcal{P}_{j}^{\prime}$-causal
correlations for all partitions $\mathcal{P}_{j}^{\prime}$ with a fixed value
of $|\mathcal{P}_{j}^{\prime}|=\mathfrak{m}^{\prime}<|\mathcal{P}|$?999Note
that a convex combination of $\mathcal{P}_{j}^{\prime}$-causal correlations
for various partitions $\mathcal{P}_{j}^{\prime}$ with a fixed number of
subsets $|\mathcal{P}_{j}^{\prime}|=\mathfrak{m}^{\prime}$ is not necessarily
$\mathcal{P}^{\prime}$-causal for any single partition $\mathcal{P}^{\prime}$
with the same value of $|\mathcal{P}^{\prime}|=\mathfrak{m}^{\prime}$. For
$\mathfrak{m}^{\prime}=1$ this is trivial, and this remains true for
$\mathfrak{m}^{\prime}=2$: any $\mathcal{P}$-causal correlation $P$ can be
decomposed as a convex combination of $\mathcal{P}_{j}^{\prime}$-causal
correlations for various partitions $\mathcal{P}_{j}^{\prime}$ with
$|\mathcal{P}_{j}^{\prime}|=2$. Eq. (15) is indeed such a decomposition, with
the partitions
$\mathcal{P}_{\ell}^{\prime}=\\{\mathcal{A}_{\ell},\mathcal{N}\backslash\mathcal{A}_{\ell}\\}$.
This is also true, for any value of $\mathfrak{m}^{\prime}$, for
$\mathcal{P}$-causal correlations that are compatible with a fixed causal
order between the subsets in $\mathcal{P}$ (or convex mixtures thereof):
indeed, such a correlation is also $\mathcal{P}^{\prime}$-causal for any
coarse-grained partition $\mathcal{P}^{\prime}$ of $\mathcal{P}$ where
consecutive subsets (as per the causal order in question, or per each causal
order in a convex mixture) of $\mathcal{P}$ are grouped together. However,
this is not true in general for $\mathfrak{m}^{\prime}>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
$\mathcal{P}_{j}^{\prime}$-causal correlations with all
$|\mathcal{P}_{j}^{\prime}|=3$; an explicit counterexample is presented in
Appendix C.

From these observations we conclude that, although grouping parties into
$\mathfrak{m}$ subsets seems to be a stronger constraint than grouping parties
into some $\mathfrak{m}^{\prime}<\mathfrak{m}$ subsets, the fact that a
correlation is $\mathcal{P}$-causal for some $|\mathcal{P}|=\mathfrak{m}\geq
4$ (or more generally, that it is a convex combination of various
$\mathcal{P}_{j}$-causal correlations with all
$|\mathcal{P}_{j}|=\mathfrak{m}\geq 4$) does not guarantee that it is also
$\mathcal{P}^{\prime}$-causal for some
$|\mathcal{P}^{\prime}|=\mathfrak{m}^{\prime}<\mathfrak{m}$—unless
$\mathfrak{m}^{\prime}=2$ (or $\mathfrak{m}^{\prime}=1$, trivially)—nor that
it can be decomposed as a convex combination of
$\mathcal{P}_{j}^{\prime}$-causal correlations with all
$|\mathcal{P}_{j}^{\prime}|=\mathfrak{m}^{\prime}$. In particular, fully
causal correlations may not be $\mathcal{P}^{\prime}$-causal for any
$\mathcal{P}^{\prime}$ with $2<|\mathcal{P}^{\prime}|<N$, or convex
combinations of such $\mathcal{P}^{\prime}$-causal correlations. This remark
motivates the definitions 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\leq M\leq N$) if
and only if it is a convex combination of $\mathcal{P}$-causal correlations,
for various partitions $\mathcal{P}$ of $\mathcal{N}$ into $|\mathcal{P}|\geq
M$ subsets.

More explicitly: $P$ is $M$-causal if and only if it can be decomposed as

$P(\vec{a}|\vec{x})=\sum_{\mathcal{P}:\,|\mathcal{P}|\geq
M}q_{\mathcal{P}}\,P_{\mathcal{P}}(\vec{a}|\vec{x}),$ (16)

where the sum is over all partitions $\mathcal{P}$ of $\mathcal{N}$ into $M$
subsets or more, with $q_{\mathcal{P}}\geq 0$ for each $\mathcal{P}$,
$\sum_{\mathcal{P}}q_{\mathcal{P}}=1$, and where each
$P_{\mathcal{P}}(\vec{a}|\vec{x})$ is a $\mathcal{P}$-causal correlation.

For $M=1$, any correlation is trivially 1-causal, since for
$\mathcal{P}=\\{\mathcal{N}\\}$ any correlation is $\mathcal{P}$-causal. For
$M=N$, the definition of $M$-causal correlations above is equivalent to that
of fully causal correlations, Definition 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
discussion in the previous subsection), that any $\mathcal{P}$-causal
correlation with $|\mathcal{P}|\geq 2$ can be written as a convex combination
of some $\mathcal{P}^{\prime}$-causal correlations, for various bipartitions
$\mathcal{P}^{\prime}$ with $|\mathcal{P}^{\prime}|=2$. It follows that, for
$M=2$, it would be equivalent to have the condition $|\mathcal{P}|=2$ instead
of $|\mathcal{P}|\geq 2$ in Definition 8 of $M$-causal correlations.
Definition 2 is then recovered when writing the bipartitions in the
decomposition as
$\mathcal{P}=\\{\mathcal{K},\mathcal{N}\backslash\mathcal{K}\\}$, using Eq.
(15) from the definition of $\mathcal{P}$-causal correlations, and rearranging
the terms in the decomposition. Hence, Definition 2 is in fact equivalent to
saying that 2-causal correlations are those that can be written as a convex
mixture of $\mathcal{P}$-causal correlations, for different partitions
$\mathcal{P}$ of $\mathcal{N}$ into $|\mathcal{P}|\geq 2$ subsets, thus
justifying further our definition of genuinely $N$-partite noncausal
correlations as those that cannot be written as such a convex mixture (or
equivalently, those that are not $M$-causal for any $M>1$). Note that since we
used the constraint $|\mathcal{P}|\geq M$ rather than $|\mathcal{P}|=M$ in Eq.
(16),101010Replacing the condition $|\mathcal{P}|\geq M$ by $|\mathcal{P}|=M$
in Definition 8 for arbitrary $M$, we could define “$({=}M)$-causal
correlations”, which would be distinct from $M$-causal correlations for
$2<M<N$. We would also have that “$({=}M)$-causal correlations” form a convex
polytope; however, the various “$({=}M)$-causal polytopes” would not
necessarily be included in one another for distinct values of $M$, as
discussed in the previous subsection.  our definition establishes a hierarchy
of correlations as desired, with $M$-causal $\Rightarrow$ $M^{\prime}$-causal
if $M\geq M^{\prime}$.

With the above definition of $M$-causal correlations, we have the following:

######  Theorem 9.

For any given value of $M$ (with $1\leq M\leq N$), the set of $M$-causal
correlations forms a convex polytope, whose (finitely many) extremal points
correspond to deterministic $\mathcal{P}$-causal correlations, for all
possible partitions $\mathcal{P}$ with $|\mathcal{P}|\geq M$—that is,
deterministic $M$-causal correlations.

###### Proof.

According to Eq. (16), the set of $M$-causal correlations is the convex hull
of the polytopes of $\mathcal{P}$-causal correlations with $|\mathcal{P}|\geq
M$. Since there is a finite number of such polytopes, the set of $M$-causal
correlations is itself a convex polytope; its extremal points are those of the
various $\mathcal{P}$-causal polytopes with $|\mathcal{P}|\geq M$, namely
deterministic $\mathcal{P}$-causal correlations (see Theorem 6). ∎

Figure 3: Sketch of the full hierarchy of nested $M$-causal polytopes, that
allows one to refine the characterisation represented 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^{\prime}$-causal for any $M^{\prime}\leq M$;
the largest $M$ for which a correlation $P$ is $M$-causal quantifies how
genuinely multipartite its noncausality is.

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^{\prime}$-causal
inequalities if $M^{\prime}\leq M$—or equivalently: if some
$M^{\prime}$-causal inequality is violated, then some $M$-causal inequality
must also be violated if $M\geq M^{\prime}$. Given a correlation $P$, one can
in principle 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
$\mathcal{P}$-causal correlations with all $|\mathcal{P}|\geq M$, but not with
all $|\mathcal{P}|>M$—indeed, if $M<N$ then $P$ violates some
$M^{\prime}$-causal inequality for any $M^{\prime}>M$ (with $M^{\prime}\leq
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\leq M\leq 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 partitions rather than bipartitions.
We thus obtain that

$J_{2}(N)=\sum_{\\{i,j\\}\subset\mathcal{N}}L_{N}(i,j)\ \geq\
-\binom{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 $\mathcal{P}=\\{\mathcal{A}_{1},\dots,\mathcal{A}_{M}\\}$ of
$\mathcal{N}$ with $\mathcal{A}_{1}=\\{1,\dots,N-M+1\\}$ and
$\mathcal{A}_{\ell}=\\{N-M+\ell\\}$ for $2\leq\ell\leq M$, and take the
distribution

$P(\vec{a}|\vec{x})=\delta_{\vec{a}_{\mathcal{A}_{1}},f(\vec{x}_{\mathcal{A}_{1}})}\,\delta_{\vec{a}_{\mathcal{N}\backslash\mathcal{A}_{1}},\vec{0}},$
(18)

where we use the same function $f$ as in Eq. (14). Analogous reasoning shows
that this correlation indeed 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 inclusions $N$-causal $\subset(N{-}1)$-causal $\subset\cdots\subset$
3-causal $\subset$ 2-causal in the hierarchy of $M$-causal polytopes are
strict. In fact, redas for inequalities (3.3) 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 example for
all $N$. Moreover, one can saturate it in such scenarios by trivially
extending the $M$-causal correlation (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 subsets 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 $\mathcal{P}$ needed to
reproduce a correlation, the more genuinely multipartite noncausal the
corresponding $\mathcal{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
$\mathcal{P}$-causal for some partition $\mathcal{P}$ with subsets of a
particular size. We therefore focus on classes of correlations that can be
written as mixtures of $\mathcal{P}$-causal ones whose largest subset is not
larger than some number $S$. For convenience, we introduce the notation

$\mathfrak{s}(\mathcal{P})\coloneqq\max_{\mathcal{A}\in\mathcal{P}}\left|\mathcal{A}\right|.$
(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\leq S\leq N$)
if and only if it is a convex combination of $\mathcal{P}$-causal
correlations, for various partitions $\mathcal{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(\vec{a}|\vec{x})=\sum_{\mathcal{P}:\,\mathfrak{s}(\mathcal{P})\leq
S}q_{\mathcal{P}}\,P_{\mathcal{P}}(\vec{a}|\vec{x}),$ (20)

where the sum is over all partitions $\mathcal{P}$ of $\mathcal{N}$ with no
subset of size larger than $S$, with $q_{\mathcal{P}}\geq 0$ for each
$\mathcal{P}$, $\sum_{\mathcal{P}}q_{\mathcal{P}}=1$, and where each
$P_{\mathcal{P}}(\vec{a}|\vec{x})$ is a $\mathcal{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 $\mathfrak{s}(\mathcal{P})\leq N-1$ if and only if
$|\mathcal{P}|\geq 2$, we see that the set of size-$(N{-}1)$-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 $N{-}1$ 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 vertices are deterministic size-$S$-causal correlations and whose facets
define _size- $S$-causal inequalities_. For $S\leq S^{\prime}$, all
size-$S$-causal correlations are also size-$S^{\prime}$-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 noncausal 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)\geq-\left\lfloor\frac{N}{S}\right\rfloor\binom{S}{2}-\binom{N-\left\lfloor\frac{N}{S}\right\rfloor
S}{2}$ (21)

(where $\left\lfloor x\right\rfloor$ 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
$\mathcal{P}=\\{\mathcal{A}_{1},\ldots,\mathcal{A}_{\left\lfloor\frac{N}{S}\right\rfloor}(,\mathcal{A}_{\left\lfloor\frac{N}{S}\right\rfloor+1})\\}$
of $\mathcal{N}$ into $\left\lfloor\frac{N}{S}\right\rfloor$ groups of $S$
parties, and (if $N$ is not a multiple of $S$) a last group with the remaining
$N-\left\lfloor\frac{N}{S}\right\rfloor S$ parties, and by taking the
deterministic correlation

$P(\vec{a}|\vec{x})=\prod_{\ell}\delta_{\vec{a}_{\mathcal{A}_{\ell}},f(\vec{x}_{\mathcal{A}_{\ell}})}$
(22)

(with again the same function $f$ as in Eq. (14)). Since the (reachable) lower
bounds in Eq. (21) are different for all possible values of $S$, this implies,
again, that all the inclusions size-$1$-causal $\subset$ size-$2$-causal
$\subset\cdots\subset$ size-$(N{-}1)$-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 correlations can be
established through the following, straightforwardly verifiable, inequalities:

$|\mathcal{P}|-1+\mathfrak{s}(\mathcal{P})\leq
N\leq|\mathcal{P}|\,\mathfrak{s}(\mathcal{P}).$ (23)

From these it follows that, for $N$ parties:

######  Theorem 11.

  * •

If a correlation is $M$-causal, then it is size-$S$-causal for all $S\geq
N{-}M{+}1$.

  * •

If a correlation is size-$S$-causal, then it is $M$-causal for all
$M\leq\left\lceil\frac{N}{S}\right\rceil$ (where $\left\lceil x\right\rceil$
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 polytopes implied by Theorem 11 are complete,
in the sense that no other inclusion exists that is not implied by the
theorem. We prove this in Appendix D. Together with the respective inclusion
relations of each hierarchy separately, this result thus fully characterises
the inclusion relations of all the classes of noncausal correlations that we
introduced; the situation is illustrated in Fig. 4 for the 6-partite case as
an example.

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 relations: 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
implied 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.

##  5 Discussion

The possibility that nature might allow for correlations 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 correlations in
laboratory experiments, are as yet unverified. Motivated by the fact that
noncausal resources exhibit interesting new features in multipartite scenarios
[6, 7, 8, 9], we aimed here to clarify when noncausal correlations 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$ parties is “genuinely $N$-partite
noncausal”—i.e., its noncausality is indeed a genuinely $N$-partite
resource—or not. We then refined our approach into two distinct criteria
quantifying the extent to which the noncausality of a correlation is a
genuinely multipartite resource. 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 multipartite 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\leq 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 general, they coincide on the edge cases and thus lead to
exactly the same definition of genuinely $N$-partite noncausal correlations,
adding support to the robustness 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 characterised the
2-causal polytope for the simplest nontrivial 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 inequalities; this stands in contrast to previous
studies of causal inequalities, where violations with process matrices were
always found111111At least for standard causal inequalities that bound
probabilities directly; for _entropic_ causal inequalities, which only provide
a relaxed characterisation of the set of causal correlations, 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. [4, 6, 7, 5, 9]. Although it remains to be confirmed
whether this is simply a failure of the search method we used, we provided
some intuition why such a violation would in fact be a surprise.

Our definition of genuinely $N$-partite noncausality is analogous to the
corresponding notion for nonlocality originally due to Svetlichny [19, 20,
21]. It is known, however, that that notion harbours some issues: for example,
it is not robust under local operations, a necessary requirement for an
operational resource theory of nonlocality [22, 23]. In order to overcome
these issues, additional constraints must be imposed on the correlations
shared by subsets of parties when defining correlations that are not genuinely
multipartite nonlocal. In the case of noncausality, however, there appears to
be no clear reason to impose any additional 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 resource itself, and additional
communication beyond what the resource specifies seems to fall outside the
relevant framework. More generally, however, an operational framework and
understanding of the relevant “free operations” for noncausal resources
remains to be properly developed.

Finally, in this paper we only considered correlations from a fully theory-
and device-independent perspective; it would be interesting to develop similar
notions within specific physical theories like the process matrix framework,
where quantum theory holds locally 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 nonseparability. It should, however, be noted that
different possible notions of multipartite causal (non)separability have been
proposed [14, 8], so a better understanding of their significance would be
necessary in order to extend the notions we have developed here to that
framework.

## 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 Research 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 owners of the land on which the University of
Queensland is situated, the Turrbal and Jagera people.

## References

  * Reichenbach [1956] H. Reichenbach,  _The direction of time_ (University of California Press, Berkeley, 1956).
  * Pearl [2009] J. Pearl,  _Causality_ (Cambridge University Press, Cambridge, 2009).
  * Brukner [2014] Č. Brukner, Quantum causality, \bibfield journal \bibinfo journal Nat. Phys.\ \textbf \bibinfo volume 10,\ \bibinfo pages 259–263 (\bibinfo year 2014).
  * Oreshkov  _et al._ [2012] O. Oreshkov, F. Costa, and Č. Brukner, Quantum correlations with no causal order, \bibfield journal \bibinfo journal Nat. Commun.\ \textbf \bibinfo volume 3,\ \bibinfo pages 1092 (\bibinfo year 2012).
  * Branciard  _et al._ [2016] C. Branciard, M. Araújo, A. Feix, F. Costa, and Č. Brukner, The simplest causal inequalities and their violation, \bibfield journal \bibinfo journal New J. Phys.\ \textbf \bibinfo volume 18,\ \bibinfo pages 013008 (\bibinfo year 2016).
  * Baumeler and Wolf [2014] Ä. Baumeler and S. Wolf, Perfect signaling among three parties violating predefined causal order, in \emph \bibinfo booktitle 2014 IEEE International Symposium on Information Theory (ISIT) (IEEE, Piscataway, NJ, 2014) pp. 526–530.
  * Baumeler  _et al._ [2014] Ä. Baumeler, A. Feix, and S. Wolf, Maximal incompatibility of locally classical behavior and global causal order in multi-party scenarios, \bibfield journal \bibinfo journal Phys. Rev. A\ \textbf \bibinfo volume 90,\ \bibinfo pages 042106 (\bibinfo year 2014).
  * Oreshkov and Giarmatzi [2016] O. Oreshkov and C. Giarmatzi, Causal and causally separable processes, \bibfield journal \bibinfo journal New J. Phys.\ \textbf \bibinfo volume 18,\ \bibinfo pages 093020 (\bibinfo year 2016).
  * Abbott  _et al._ [2016] A. A. Abbott, C. Giarmatzi, F. Costa, and C. Branciard, Multipartite causal correlations: Polytopes and inequalities, \bibfield journal \bibinfo journal Phys. Rev. A\ \textbf \bibinfo volume 94,\ \bibinfo pages 032131 (\bibinfo year 2016).
  * Hardy [2005] L. Hardy, Probability theories with dynamic causal structure: a new framework for quantum gravity, (2005), arXiv:gr-qc/0509120.
  * Fukuda [2012] K. Fukuda, cdd, v0.94g, (2012), NoStop
  * Araújo  _et al._ [2017] author author M. Araújo, author A. Feix, author M. Navascués, and author Č. Brukner, title title A purification postulate for quantum mechanics with indefinite causal order, 10.22331/q-2017-04-26-10 journal journal Quantum volume 1, pages 10 (year 2017)NoStop
  * Feix  _et al._ [2016] author author A. Feix, author M. Araújo, and author Č. Brukner, title title Causally nonseparable processes admitting a causal model, 10.1088/1367-2630/18/8/083040 journal journal New J. Phys. volume 18, pages 083040 (year 2016)NoStop
  * Araújo  _et al._ [2015] author author M. Araújo, author C. Branciard, author F. Costa, author A. Feix, author C. Giarmatzi, and author Č. Brukner, title title Witnessing causal nonseparability, 10.1088/1367-2630/17/10/102001 journal journal New J. Phys. volume 17, pages 102001 (year 2015)NoStop
  * Hardy [2007] author author L. Hardy, title title Towards quantum gravity: a framework for probabilistic theories with non-fixed causal structure, 10.1088/1751-8113/40/12/S12 journal journal J. Phys. A: Math. Gen. volume 40, pages 3081 (year 2007)NoStop
  * Baumeler  _et al._ [2017] author author Ä. Baumeler, author F. Costa, author T. C. Ralph, author S. Wolf, and author M. Zych, title title Reversible time travel with freedom of choice, @noop (year 2017), http://arxiv.org/abs/1703.00779arXiv:1703.00779 [gr-qc]NoStop
  * Araújo  _et al._ [2017] author author M. Araújo, author P. A. Guérin, and author Ä. Baumeler, title title Quantum computation with indefinite causal structures, 10.1103/PhysRevA.96.052315 journal journal Phys. Rev. A volume 96, pages 052315 (year 2017)NoStop
  * Miklin  _et al._ [2017] author author N. Miklin, author A. A. Abbott, author C. Branciard, author R. Chaves, and author C. Budroni, title title The entropic approach to causal correlations, 10.1088/1367-2630/aa8f9f journal journal New J. Phys. volume 19, pages 113041 (year 2017)NoStop
  * Svetlichny [1987] author author G. Svetlichny, title title Distinguishing three-body from two-body nonseparability by a Bell-type inequality, 10.1103/PhysRevD.35.3066 journal journal Phys. Rev. D volume 35, pages 3066 (year 1987)NoStop
  * Seevinck and Svetlichny [2002] author author M. Seevinck and author G. Svetlichny, title title Bell-type inequalities for partial separability in $N$-particle systems and quantum mechanical violations, 10.1103/PhysRevLett.89.060401 journal journal Phys. Rev. Lett. volume 89, pages 060401 (year 2002)NoStop
  * Collins  _et al._ [2002] author author D. Collins, author N. Gisin, author S. Popescu, author D. Roberts, and author V. Scarani, title title Bell-type inequalities to detect true $\mathit{n}$-body nonseparability, 10.1103/PhysRevLett.88.170405 journal journal Phys. Rev. Lett. volume 88, pages 170405 (year 2002)NoStop
  * Gallego  _et al._ [2012] author author R. Gallego, author L. E. Würflinger, author A. Acín, and author M. Navascués, title title Operational framework for nonlocality, 10.1103/PhysRevLett.109.070401 journal journal Phys. Rev. Lett. volume 109, pages 070401 (year 2012)NoStop
  * Bancal  _et al._ [2013] author author J.-D. Bancal, author J. Barrett, author N. Gisin, and author S. Pironio, title title Definitions of multipartite nonlocality, 10.1103/PhysRevA.88.014102 journal journal Phys. Rev. A volume 88, pages 014102 (year 2013)NoStop
  * [24] @noop howpublished See Supplementary Material in the https://arxiv.org/src/1708.07663v2/anc/Supplementary_Material.cdfarXiv ‘ancillary files’ for the full list of 2-causal inequalities in the tripartite lazy scenario and further analysis.Stop

##  Appendix A Proof of the generalised 2-causal inequalities and their bounds

###  A.1 Proof of inequality (3.3)

To prove that Eq. (3.3) is a valid 2-causal inequality for all $N$, it
suffices to show that it holds for all deterministic 2-causal correlations.
For a nonempty strict subset $\mathcal{K}$ of $\mathcal{N}$, let
$P^{\text{det}}(\vec{a}|\vec{x})=P^{\text{det}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})P^{\text{det}}_{\vec{x}_{\mathcal{K}},\vec{a}_{\mathcal{K}}}(\vec{a}_{\mathcal{N}\backslash\mathcal{K}}|\vec{x}_{\mathcal{N}\backslash\mathcal{K}})$
be an arbitrary deterministic correlation compatible with the causal order
$\mathcal{K}\prec\mathcal{N}\backslash\mathcal{K}$. Then, since
$P^{\text{det}}(\vec{a}_{\mathcal{K}}|\vec{x})=P^{\text{det}}(\vec{a}_{\mathcal{K}}|\vec{x}_{\mathcal{K}})$,
it follows that

$\displaystyle
P^{\text{det}}\big{(}\vec{a}_{\mathcal{K}}=\vec{1}\,|\,\vec{x}_{\mathcal{K}}=\vec{1},\vec{x}_{\mathcal{N}\backslash\mathcal{K}}=\vec{0}\big{)}$
$\displaystyle\quad=P^{\text{det}}\big{(}\vec{a}_{\mathcal{K}}=\vec{1}\,|\,\vec{x}=\vec{1}\big{)}\
\geq\ P^{\text{det}}\big{(}\vec{a}=\vec{1}\,|\,\vec{x}=\vec{1}\big{)}$ (24)

and hence
$P^{\text{det}}\big{(}\vec{a}_{\mathcal{K}}=\vec{1}\,|\,\vec{x}_{\mathcal{K}}=\vec{1},\vec{x}_{\mathcal{N}\backslash\mathcal{K}}=\vec{0}\big{)}-P^{\text{det}}\big{(}\vec{a}=\vec{1}\,|\,\vec{x}=\vec{1}\big{)}\geq
0$. Since $J_{1}(N)$ is then obtained by adding some more nonnegative terms
$P^{\text{det}}\big{(}\vec{a}_{\mathcal{K}^{\prime}}=\vec{1}\,|\,\cdots)\geq
0$, this proves the validity of Eq. (3.3) 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)=\sum_{\\{i,j\\}\subset\mathcal{N}}L_{N}(i,j)$, with the summands
defined in Eq. (13), while the 2-causal inequality (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 $\mathcal{P}$-causal correlations, for any partition
$\mathcal{P}$, and then use this bound to derive the corresponding $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 determining the outputs of a deterministic
$\mathcal{P}$-causal correlation can be seen as processing deterministically
one input after another and consequently defining a (dynamical) causal order
between the subsets in $\mathcal{P}$, also implies the following result (which
will be used below and in the subsequent appendices):

######  Proposition 12.

For a deterministic $\mathcal{P}$-causal correlation $P$, given two subsets
$\mathcal{A}_{\ell}$ and $\mathcal{A}_{m}$ in $\mathcal{P}$, the vector of
inputs
$\vec{x}_{\mathcal{N}\backslash(\mathcal{A}_{\ell}\cup\mathcal{A}_{m})}$ for
the parties that are neither in $\mathcal{A}_{\ell}$ nor in $\mathcal{A}_{m}$
determines a (not necessarily unique) causal order between
$\mathcal{A}_{\ell}$ and $\mathcal{A}_{m}$,
$\mathcal{A}_{\ell}\prec\mathcal{A}_{m}$ or
$\mathcal{A}_{m}\prec\mathcal{A}_{\ell}$.

More technically: for any $\vec{x}_{\backslash\ell
m}\coloneqq\vec{x}_{\mathcal{N}\backslash(\mathcal{A}_{\ell}\cup\mathcal{A}_{m})}$,
a deterministic $\mathcal{P}$-causal correlation $P$ satisfies either
$P(\vec{a}_{\mathcal{A}_{\ell}}|\vec{x}_{\backslash\ell
m},\vec{x}_{A_{\ell}},\vec{x}_{\mathcal{A}_{m}})=P(\vec{a}_{\mathcal{A}_{\ell}}|\vec{x}_{\backslash\ell
m},\vec{x}_{A_{\ell}},\vec{x}_{\mathcal{A}_{m}}^{\,\prime})$ for all
$\vec{x}_{A_{\ell}},\vec{x}_{\mathcal{A}_{m}},\vec{x}_{\mathcal{A}_{m}}^{\,\prime},\vec{a}_{\mathcal{A}_{\ell}}$,
or $P(\vec{a}_{\mathcal{A}_{m}}|\vec{x}_{\backslash\ell
m},\vec{x}_{A_{\ell}},\vec{x}_{\mathcal{A}_{m}})=P(\vec{a}_{\mathcal{A}_{m}}|\vec{x}_{\backslash\ell
m},\vec{x}_{A_{\ell}}^{\,\prime},\vec{x}_{\mathcal{A}_{m}})$ for all
$\vec{x}_{A_{m}},\vec{x}_{A_{\ell}}^{\,\prime},\vec{x}_{\mathcal{A}_{m}},\vec{a}_{\mathcal{A}_{m}}$—i.e.,
in short, either
$P(\vec{a}_{\mathcal{A}_{\ell}}|\vec{x})=P(\vec{a}_{\mathcal{A}_{\ell}}|\vec{x}_{\mathcal{N}\backslash\mathcal{A}_{m}})$
or
$P(\vec{a}_{\mathcal{A}_{m}}|\vec{x})=P(\vec{a}_{\mathcal{A}_{m}}|\vec{x}_{\mathcal{N}\backslash\mathcal{A}_{\ell}})$.

To derive a $\mathcal{P}$-causal bound for $J_{2}(N)$ for a given partition
$\mathcal{P}=\\{\mathcal{A}_{1},\dots,\mathcal{A}_{|\mathcal{P}|}\\}$, it is
sufficient to find a bound that holds for any deterministic
$\mathcal{P}$-causal correlation $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 $\mathcal{P}$, i.e. $i\in\mathcal{A}_{\ell}$, $j\in\mathcal{A}_{m}$
with $\ell\neq m$; or ii) both parties are in the same subset:
$i,j\in\mathcal{A}_{\ell}$.

  1. i)

According to Proposition 12, the inputs
$\vec{x}_{\mathcal{N}\backslash(\mathcal{A}_{\ell}\cup\mathcal{A}_{m})}=\vec{0}$
imply either the order $\mathcal{A}_{\ell}\prec\mathcal{A}_{m}$, or
$\mathcal{A}_{m}\prec\mathcal{A}_{\ell}$ for $P$. In the first case,

$\displaystyle\quad
P\big{(}a_{i}=1|x_{i}x_{j}=10,\vec{x}_{\mathcal{N}\backslash\\{i,j\\}}=\vec{0}\big{)}$
$\displaystyle\qquad=P\big{(}a_{i}=1|x_{i}x_{j}=11,\vec{x}_{\mathcal{N}\backslash\\{i,j\\}}=\vec{0}\big{)},$
(25)

which implies

$\displaystyle
P\big{(}a_{i}=1|x_{i}x_{j}=10,\vec{x}_{\mathcal{N}\backslash\\{i,j\\}}=\vec{0}\big{)}$
$\displaystyle\quad-P\big{(}a_{i}a_{j}=11|x_{i}x_{j}=11,\vec{x}_{\mathcal{N}\backslash\\{i,j\\}}=\vec{0}\big{)}\geq
0,$ (26)

and therefore (after adding a nonnegative term) $L_{N}(i,j)\geq 0$. An
analogous argument shows that $L_{N}(i,j)\geq 0$ also in the case that one has
$\mathcal{A}_{m}\prec\mathcal{A}_{\ell}$ for $P$ when
$\vec{x}_{\mathcal{N}\backslash(\mathcal{A}_{\ell}\cup\mathcal{A}_{m})}=\vec{0}$.

  2. ii)

If the parties $A_{i}$ and $A_{j}$ belong to the same subset
$\mathcal{A}_{\ell}$, they can share arbitrary correlations and thus win the
(conditional) LGYNI game perfectly. In that case we have $L_{N}(i,j)\geq-1$,
which is the minimum algebraic bound.

Combining the two cases, we thus have, for any $\mathcal{P}$-causal
correlation,

$\displaystyle J_{2}(N)$
$\displaystyle=\sum_{\\{i,j\\}\subset\mathcal{N}}L_{N}(i,j)$
$\displaystyle\geq\sum_{\begin{subarray}{c}\\{i,j\\}\in\mathcal{A}_{\ell}\\\
\textrm{for some
}\mathcal{A}_{\ell}\in\mathcal{P}\end{subarray}}\\!\\!\\!\\!\\!\\!(-1)$
$\displaystyle=\
-\sum_{\mathcal{A}_{\ell}\in\mathcal{P}}\binom{|\mathcal{A}_{\ell}|}{2}\coloneqq
L(\mathcal{P}).$ (27)

In order to prove the $M$-causal bound (17), we shall now prove that among all
partitions $\mathcal{P}$ containing a fixed number $\mathfrak{m}$ of subsets,
the quantity $L(\mathcal{P})$ defined above is minimal when $\mathcal{P}$
consists of $\mathfrak{m}-1$ singletons, and one subset containing the
remaining $N-\mathfrak{m}+1$ parties. Assume for the sake of contradiction
that this is not the case, so that the minimum is obtained for a partition
$\mathcal{P}$ that contains at least two subsets $\mathcal{A}_{\ell}$ and
$\mathcal{A}_{m}$ that are not singletons, for which we assume
$|\mathcal{A}_{\ell}|\geq|\mathcal{A}_{m}|\,(\geq 2)$. Let then
$k\in\mathcal{A}_{m}$, and define the partition $\mathcal{P}^{\prime}$
obtained from $\mathcal{P}$ by replacing $\mathcal{A}_{\ell}$ and
$\mathcal{A}_{m}$ by
$\mathcal{A}_{\ell}^{\prime}=\mathcal{A}_{\ell}\cup\\{k\\}$ and
$\mathcal{A}_{m}^{\prime}=\mathcal{A}_{m}\backslash\\{k\\}$, respectively
(note that the assumption that $|\mathcal{A}_{m}|\geq 2$ ensures that
$\mathcal{A}_{m}^{\prime}$ remains nonempty). One then has

$\displaystyle L(\mathcal{P}^{\prime})-L(\mathcal{P})$
$\displaystyle\quad=-\Big{[}\binom{|\mathcal{A}_{\ell}^{\prime}|}{2}+\binom{|\mathcal{A}_{m}^{\prime}|}{2}\Big{]}+\Big{[}\binom{|\mathcal{A}_{\ell}|}{2}+\binom{|\mathcal{A}_{m}|}{2}\Big{]}$
$\displaystyle\quad=-|\mathcal{A}_{\ell}|+|\mathcal{A}_{m}|-1\ <\ 0,$ (28)

in contradiction with the assumption that $\mathcal{P}$ minimised $L$. For a
given $N$ it then follows that

$\min_{\mathcal{P}:|\mathcal{P}|=\mathfrak{m}}L(\mathcal{P})=-\binom{N-\mathfrak{m}+1}{2},$
(29)

and therefore, from Eq. (27),

$J_{2}(N)\geq-\binom{N-|\mathcal{P}|+1}{2}.$ (30)

Finally, we note that $|\mathcal{P}|\geq M$ implies
$-\binom{N-|\mathcal{P}|+1}{2}\geq-\binom{N-M+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 $\mathcal{P}$ with $\mathfrak{s}(\mathcal{P})\leq
S$, $L(\mathcal{P})$ from Eq. (27) is minimised for the partition containing
$\left\lfloor\frac{N}{S}\right\rfloor$ groups of $S$ parties, and (if $N$ is
not a multiple of $S$) a last group with the remaining
$N-\left\lfloor\frac{N}{S}\right\rfloor S$ parties—for which $L(\mathcal{P})$
is indeed 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 $\mathcal{P}$ containing at least two subsets
$\mathcal{A}_{\ell}$ and $\mathcal{A}_{m}$ of less than $S$ parties, for which
we take $|\mathcal{A}_{m}|\leq|\mathcal{A}_{\ell}|<S$. If
$|\mathcal{A}_{m}|>1$, one can follow the same reasoning as in the proof of
the $M$-causal bound above: take $k\in\mathcal{A}_{m}$ and consider the
partition $\mathcal{P}^{\prime}$ obtained by replacing $\mathcal{A}_{\ell}$
and $\mathcal{A}_{m}$ by
$\mathcal{A}_{\ell}^{\prime}=\mathcal{A}_{\ell}\cup\\{k\\}$ and
$\mathcal{A}_{m}^{\prime}=\mathcal{A}_{m}\setminus\\{k\\}$, respectively. Note
that since we assumed $|\mathcal{A}_{\ell}|<S$, we have
$|\mathcal{A}_{\ell}^{\prime}|\leq S$ and
$\mathfrak{s}(\mathcal{P}^{\prime})\leq S$. Eq. (A.2) then holds again, in
contradiction with the assumption that $\mathcal{P}$ minimised $L$. In the
case when $|\mathcal{A}_{m}|=1$, consider instead the partition
$\mathcal{P}^{\prime}$ formed by merging $\mathcal{A}_{\ell}$ and
$\mathcal{A}_{m}$ into a new subset
$\mathcal{A}_{\ell}^{\prime}=\mathcal{A}_{\ell}\cup\mathcal{A}_{m}$ (so that
$|\mathcal{A}_{\ell}^{\prime}|=|\mathcal{A}_{\ell}|+1\leq S$ and we still have
$\mathfrak{s}(\mathcal{P}^{\prime})\leq S$). We then have

$\displaystyle L(\mathcal{P}^{\prime})-L(\mathcal{P})$
$\displaystyle=-\binom{|\mathcal{A}_{\ell}^{\prime}|}{2}+\binom{|\mathcal{A}_{\ell}|}{2}$
$\displaystyle=-|\mathcal{A}_{\ell}|\ <\ 0,$ (31)

again in contradiction with the assumption that $\mathcal{P}$ minimised $L$,
which concludes the proof that Eq. (21) holds for all size-$S$-causal
correlations.

##  Appendix B Separation of $\mathcal{P}$-causal polytopes

In this appendix we shall prove Theorem 7, which states that there are no
nontrivial inclusions among $\mathcal{P}$-causal polytopes. Before that, we
start by introducing a useful family of deterministic $\mathcal{P}$-causal
correlations.

###  B.1 A family of deterministic $\mathcal{P}$-causal correlations

The $N$-partite correlations $P_{\mathcal{P},\sigma}^{\text{det}}$ we
introduce here are defined for a given partition
$\mathcal{P}=\\{\mathcal{A}_{1},\ldots,\mathcal{A}_{|\mathcal{P}|}\\}$ of
$\mathcal{N}$ and a given permutation $\sigma$ of its $|\mathcal{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 $\mathcal{A}\in\mathcal{P}$ and a vector of
inputs $\vec{x}$, we define the bit

$z_{\mathcal{A}}\coloneqq\prod_{k\in\mathcal{A}}x_{k}.$ (32)

We then define the deterministic response function
$\vec{\alpha}_{\mathcal{P},\sigma}$ such that, for each party $A_{k}$
belonging to a subset $\mathcal{A}_{\ell}$ of $\mathcal{P}$, we have

$\big{(}\vec{\alpha}_{\mathcal{P},\sigma}(\vec{x})\big{)}_{k}\
\coloneqq\\!\\!\prod_{m:\,\sigma(m)\leq\sigma(\ell)}\\!\\!\\!\\!z_{\mathcal{A}_{m}}.$
(33)

The correlation $P_{\mathcal{P},\sigma}^{\text{det}}$ is then defined as

$P_{\mathcal{P},\sigma}^{\text{det}}(\vec{a}|\vec{x})\
\coloneqq\delta_{\vec{a},\vec{\alpha}_{\mathcal{P},\sigma}(\vec{x})}.$ (34)

In other words, each party $A_{k}$ in some subset
$\mathcal{A}_{\ell}\in\mathcal{P}$ outputs the product of the inputs of all
parties that came before itself according to the partition $\mathcal{P}$ and
the causal order
$\mathcal{A}_{\sigma(1)}\prec\mathcal{A}_{\sigma(2)}\prec\cdots\prec\mathcal{A}_{\sigma(|\mathcal{P}|)}$
defined by the permutation $\sigma$, including all parties in the same subset
$\mathcal{A}_{\ell}$. Clearly the correlation
$P_{\mathcal{P},\sigma}^{\text{det}}$ is compatible with this fixed causal
order, and is therefore $\mathcal{P}$-causal; as it is deterministic, it
corresponds to a vertex of the $\mathcal{P}$-causal polytope.

Note that each party outputs $a_{k}=0$ whenever $x_{k}=0$, as required in the
lazy scenario. The correlations $P_{\mathcal{P},\sigma}^{\text{det}}$ 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_{\mathcal{P},\sigma}^{\text{det}}$ 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 $\mathcal{P}$-causal
polytope is not contained in the $\mathcal{P}^{\prime}$-causal one by
exhibiting a $\mathcal{P}$-causal correlation (from the family introduced
above) that is not $\mathcal{P}^{\prime}$-causal. The proof that the
$\mathcal{P}^{\prime}$-causal polytope is not contained in the
$\mathcal{P}$-causal one then follows by symmetry. We distinguish two cases,
whether i) $\mathcal{P}^{\prime}$ is a coarse-graining of $\mathcal{P}$ or ii)
$\mathcal{P}^{\prime}$ is not a coarse-graining of $\mathcal{P}$.

  1. i)

If $\mathcal{P}^{\prime}$ (with $|\mathcal{P}^{\prime}|>1$) is a coarse-
graining of $\mathcal{P}$, then one can find two subsets $\mathcal{A}_{\ell}$
and $\mathcal{A}_{\ell^{\prime}}$ in $\mathcal{P}$ that are grouped together
in some subset $\mathcal{A}_{\ell\ell^{\prime}}^{\prime}$ in
$\mathcal{P}^{\prime}$, and a third subset $\mathcal{A}_{m}$ in $\mathcal{P}$
that is contained in a different subset $\mathcal{A}_{m}^{\prime}$ of
$\mathcal{P}^{\prime}$. Let $\sigma$ be a permutation of $\mathcal{P}$ which
defines a causal order between its elements such that
$\mathcal{A}_{\ell}\prec\mathcal{A}_{m}\prec\mathcal{A}_{\ell^{\prime}}$. The
correlation $P_{\mathcal{P},\sigma}^{\text{det}}$ as defined in Eq. (34) is
then $\mathcal{P}$-causal, but not $\mathcal{P}^{\prime}$-causal. Intuitively,
this is because we cannot order $\mathcal{A}_{\ell\ell^{\prime}}^{\prime}$ (in
which $\mathcal{A}_{\ell}$ and $\mathcal{A}_{\ell^{\prime}}$ are grouped
together) against $\mathcal{A}_{m}^{\prime}$ (which contains
$\mathcal{A}_{m}$). More specifically, for
$\vec{x}_{\mathcal{N}\backslash(\mathcal{A}_{\ell}\cup\mathcal{A}_{\ell^{\prime}}\cup\mathcal{A}_{m})}=\vec{1}$
(so that in particular,
$\vec{x}_{\mathcal{N}\backslash(\mathcal{A}_{\ell\ell^{\prime}}^{\prime}\cup\mathcal{A}_{m}^{\prime})}=\vec{1}$),
the response function $\vec{\alpha}_{\mathcal{P},\sigma}$ defined in Eq. (33)
gives
$a_{k}=\big{(}\vec{\alpha}_{\mathcal{P},\sigma}(\vec{x})\big{)}_{k}=z_{\mathcal{A}_{\ell}}z_{\mathcal{A}_{m}}z_{\mathcal{A}_{\ell^{\prime}}}$
if $k\in\mathcal{A}_{\ell^{\prime}}$ and
$a_{k}=\big{(}\vec{\alpha}_{\mathcal{P},\sigma}(\vec{x})\big{)}_{k}=z_{\mathcal{A}_{\ell}}z_{\mathcal{A}_{m}}$
if $k\in\mathcal{A}_{m}$. Hence,
$P(\vec{a}_{\mathcal{A}_{\ell\ell^{\prime}}^{\prime}}|\vec{x})$ depends
nontrivially on $\vec{x}_{\mathcal{A}_{m}^{\prime}}$ (via
$z_{\mathcal{A}_{m}}$) while $P(\vec{a}_{\mathcal{A}_{m}^{\prime}}|\vec{x})$
depends nontrivially on $\vec{x}_{\mathcal{A}_{\ell\ell^{\prime}}^{\prime}}$
(via $z_{\mathcal{A}_{\ell}}$). According to Proposition 12, this implies that
$P_{\mathcal{P},\sigma}^{\text{det}}$ indeed cannot be
$\mathcal{P}^{\prime}$-causal.

  2. ii)

If $\mathcal{P}^{\prime}$ is not a coarse-graining of $\mathcal{P}$, then one
can find two parties $A_{i},A_{j}$ that belong to the same subset
$\mathcal{A}_{ij}$ of $\mathcal{P}$, but belong to two distinct subsets of
$\mathcal{P}^{\prime}$, i.e. $A_{i}\in\mathcal{A}_{i}^{\prime}$,
$A_{j}\in\mathcal{A}_{j}^{\prime}$. Let now $\sigma$ be any permutation of
$\mathcal{P}$. The correlation $P_{\mathcal{P},\sigma}^{\text{det}}$ as
defined in Eq. (34) is then $\mathcal{P}$-causal, but not
$\mathcal{P}^{\prime}$-causal. Intuitively, this is because the parties
$A_{i}$ and $A_{j}$ cannot be separated in the definition of
$P_{\mathcal{P},\sigma}^{\text{det}}$. More specifically, for
$\vec{x}_{\mathcal{N}\backslash\\{i,j\\}}=\vec{1}$ (so that in particular,
$\vec{x}_{\mathcal{N}\backslash(\mathcal{A}_{i}^{\prime}\cup\mathcal{A}_{j}^{\prime})}=\vec{1}$),
the response function $\vec{\alpha}_{\mathcal{P},\sigma}$ gives
$a_{k}=\big{(}\vec{\alpha}_{\mathcal{P},\sigma}(\vec{x})\big{)}_{k}=z_{\mathcal{A}_{ij}}=x_{i}x_{j}$
for both $k=i$ and $k=j$. Hence,
$P(\vec{a}_{\mathcal{A}_{i}^{\prime}}|\vec{x})$ depends nontrivially on
$\vec{x}_{\mathcal{A}_{j}^{\prime}}$ (via $x_{j}$) while
$P(\vec{a}_{\mathcal{A}_{j}^{\prime}}|\vec{x})$ depends nontrivially on
$\vec{x}_{\mathcal{A}_{i}^{\prime}}$ (via $x_{i}$). According to Proposition
12, this implies that $P_{\mathcal{P},\sigma}^{\text{det}}$ indeed cannot be
$\mathcal{P}^{\prime}$-causal.

##  Appendix C A 4-partite fully causal correlation with dynamical order that
is not a convex mixture of $\mathcal{P}_{j}^{\prime}$-causal correlations with
$|\mathcal{P}_{j}^{\prime}|=3$.

We provide here an explicit counterexample to the question raised at the end
of Sec. 4.2, of whether a $\mathcal{P}$-causal correlation can always be
written as a convex combination of $\mathcal{P}_{j}^{\prime}$-causal
correlations for various partitions $\mathcal{P}_{j}^{\prime}$ with a fixed
number of subsets
$|\mathcal{P}_{j}^{\prime}|=\mathfrak{m}^{\prime}<|\mathcal{P}|$.

Figure 5: The causal structure sketched above provides an example of a
4-partite fully causal correlation that is not a convex mixture of
$\mathcal{P}_{j}^{\prime}$-causal correlations with
$|\mathcal{P}_{j}^{\prime}|=3$ (see text for details).

As we noted, such a counterexample requires $\mathfrak{m}^{\prime}\geq 3$ (and
hence $|\mathcal{P}|\geq 4$), as well as a dynamical causal order. Consider
thus a 4-partite scenario, with parties $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 parties $B_{k}$ (see
Fig. 5), with each possible value of $x$ corresponding to one of the six
possible permutations, denoted by $\sigma_{x}$. For parties $B_{k}$ we
consider the lazy scenario, with inputs $y_{k}\in\\{0,1\\}$ and outputs
$b_{k}=0$ if $y_{k}=0$, $b_{k}\in\\{0,1\\}$ if $y_{k}=1$. We then define the
deterministic correlation $P^{\textrm{det}}$ by the response functions

$b_{\sigma_{x}(1)}\\!=\\!0,\
b_{\sigma_{x}(2)}\\!=\\!y_{\sigma_{x}(1)}y_{\sigma_{x}(2)},\
b_{\sigma_{x}(3)}\\!=\\!y_{\sigma_{x}(2)}y_{\sigma_{x}(3)}.$ (35)

While the correlation $P^{\textrm{det}}$ thus obtained is fully causal (i.e.,
it is $\mathcal{P}$-causal for the “full partition” $\mathcal{P}$ such that
$|\mathcal{P}|=N=4$), it is not $\mathcal{P}^{\prime}$-causal for any 3-subset
partition $\mathcal{P}^{\prime}$ of $\\{A,B_{1},B_{2},B_{3}\\}$—which also
implies, since $P^{\textrm{det}}$ is deterministic, that it is not
decomposable as a convex combination of $\mathcal{P}^{\prime}$-causal
correlations for various 3-subset partitions $\mathcal{P}^{\prime}$ either.
Indeed, such a $\mathcal{P}^{\prime}$ 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^{\textrm{det}}$ is deterministic, and the outputs
of all parties $B_{k}$ depend on $x$, any $\mathcal{P}^{\prime}$-causal
correlation should be compatible with the subset $\\{A,B_{i}\\}$ being first,
with therefore $b_{i}$ independent of $y_{k}$ for $k\neq i$; this, however,
cannot be because, for every $i=1,2,3$, we can find $x$ such that
$i=\sigma_{x}(2)$, so that $b_{i}=y_{\sigma_{x}(1)}y_{i}$, which depends on
$y_{k}$ with $k={\sigma_{x}(1)}\neq i$. In the second case where
$\mathcal{P}^{\prime}=\\{\\{A\\},\\{B_{i},B_{j}\\},\\{B_{k}\\}\\}$, according
to Proposition 12, a deterministic $\mathcal{P}^{\prime}$-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 $\sigma_{x}(1)=i$, $\sigma_{x}(2)=k$,
$\sigma_{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 (singletons of) parties.
This shows that the correlation $P^{\textrm{det}}$ defined above is indeed not
$\mathcal{P}^{\prime}$-causal for any 3-subset partition
$\mathcal{P}^{\prime}$—and as said above, being deterministic, it is not a
convex mixture of $\mathcal{P}^{\prime}$-causal partitions for various such
partitions $\mathcal{P}^{\prime}$ either.

##  Appendix D Proof of completeness of Theorem 11

In order to prove that Theorem 11 completely characterises the possible
inclusions between $M$-causal and size-$S$-causal polytopes, we first prove
the following lemma regarding non-inclusions between $\mathcal{P}$-causal
polytopes (which is perhaps of interest in and of itself).

######  Lemma 13.

Given a partition $\mathcal{P}$ and a set of partitions
$\left\\{\mathcal{P}_{1}^{\prime},\dots,\mathcal{P}_{r}^{\prime}\right\\}$,
none of which is a coarse-graining of $\mathcal{P}$, the convex hull of the
$\mathcal{P}_{j}^{\prime}$-causal polytopes, $j=1,\dots,r$, does not contain
the $\mathcal{P}$-causal polytope.

###### Proof.

It suffices here to show that, if no partition among
$\mathcal{P}_{1}^{\prime},\dots,\mathcal{P}_{r}^{\prime}$ is a coarse-graining
of a partition $\mathcal{P}$, it is possible to find a deterministic
$\mathcal{P}$-causal correlation that is not $\mathcal{P}_{j}^{\prime}$-causal
for any $j=1,\dots,r$. The given correlation being deterministic, this will
indeed imply that it is also not a convex mixture of
$\mathcal{P}_{j}^{\prime}$-causal correlations.

We can again take the correlation $P_{\mathcal{P},\sigma}^{\text{det}}$
defined in Eq. (34), for any choice of the permutation $\sigma$. Recall that
for this correlation the output of each party depends nontrivially on the
inputs of all parties in the same subset. As already established for case
_ii)_ in Appendix B.2, no such correlation is
$\mathcal{P}_{j}^{\prime}$-causal for any partition $\mathcal{P}_{j}^{\prime}$
that is not a coarse-graining of $\mathcal{P}$, which proves the result. ∎

Note that the assumption that none of the partitions
$\mathcal{P}_{j}^{\prime}$ is a coarse-graining of $\mathcal{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
$\mathcal{P}$-causal correlation, with
$\mathcal{P}=\\{\mathcal{A}_{\ell}\\}_{\ell}$, can be written as a convex
combination of $\mathcal{P}_{\ell}^{\prime}$-causal correlations, with the
partitions
$\mathcal{P}_{\ell}^{\prime}=\\{\mathcal{A}_{\ell},\mathcal{N}\backslash\mathcal{A}_{\ell}\\}$
being coarse-grainings of $\mathcal{P}$.

Let us now prove the completeness of Theorem 11. To this end, let us consider
first a partition $\mathcal{P}$ with $|\mathcal{P}|=M$ that consists of $M-1$
singletons and an $(N{-}M{+}1)$-partite subset. Such a partition saturates the
first inequality in Eq. (23), i.e., it satisfies
$\mathfrak{s}(\mathcal{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
$\mathcal{P}_{j}^{\prime}$-causal polytopes for all partitions
$\mathcal{P}_{j}^{\prime}$ with $\mathfrak{s}(\mathcal{P}_{j}^{\prime})\leq
S$. None of these partitions can be a coarse-graining of $\mathcal{P}$, as
this would imply (since coarse-graining can only increase the size of the
largest subset in a partition)
$\mathfrak{s}(\mathcal{P}_{j}^{\prime})\geq\mathfrak{s}(\mathcal{P})=N-M+1>S$,
in contradiction with $\mathfrak{s}(\mathcal{P}_{j}^{\prime})\leq S$. But then
Lemma 13 shows that the $\mathcal{P}$-causal polytope is not contained in the
size-$S$-causal polytope, and (since $|\mathcal{P}|=M$) this thus implies that
the $M$-causal polytope is not contained in the size-$S$-causal polytope.

Similarly, consider a partition $\mathcal{P}$ with
$\mathfrak{s}(\mathcal{P})=S$, that consists of
$\left\lfloor\frac{N}{S}\right\rfloor$ groups of $S$ parties and, if $N$ is
not a multiple of $S$, a final group containing the remaining
$N{-}\left\lfloor\frac{N}{S}\right\rfloor S$ parties. Such a partition thus
contains $|\mathcal{P}|=\left\lceil\frac{N}{S}\right\rceil$ subsets. Let us
now take $M>\left\lceil\frac{N}{S}\right\rceil$. The $M$-causal polytope is,
again by definition, the convex hull of all $\mathcal{P}_{j}^{\prime}$-causal
polytopes for all partitions $\mathcal{P}_{j}^{\prime}$ with
$|\mathcal{P}_{j}^{\prime}|\geq M$. None of these partitions can be a coarse-
graining of $\mathcal{P}$, as this would imply (since coarse-graining can only
decrease the number of subsets in a partition)
$|\mathcal{P}_{j}^{\prime}|\leq|\mathcal{P}|=\left\lceil\frac{N}{S}\right\rceil<M$,
in contradiction with $|\mathcal{P}_{j}^{\prime}|\geq M$. Lemma 13 then again
shows that the $\mathcal{P}$-causal polytope is not contained in the
$M$-causal polytope, and (since $\mathfrak{s}(\mathcal{P})=S$) this then
implies that the size-$S$-causal polytope is not contained in the $M$-causal
polytope, which completes the proof.

Finally, let us also note that since no partition $\mathcal{P}^{\prime}$ with
$\left|\mathcal{P}^{\prime}\right|\geq M^{\prime}>M$ is a coarse-graining of
any partition $\mathcal{P}$ with $|\mathcal{P}|=M$, and since no partition
$\mathcal{P}^{\prime}$ with $\mathfrak{s}(\mathcal{P}^{\prime})\leq
S^{\prime}<S$ is a coarse-graining of any partition $\mathcal{P}$ with
$\mathfrak{s}(\mathcal{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) before) that all inclusions among $M$-causal and
among size-$S$-causal polytopes are strict.