# Correlations and quantum circuits with dynamical causal order

Raphaël Mothe, Alastair A. Abbott, Cyril Branciard

► To cite this version:

Raphaël Mothe, Alastair A. Abbott, Cyril Branciard. Correlations and quantum circuits with dynamical causal order. 2025. hal-05266743

HAL Id: hal-05266743

https://inria.hal.science/hal-05266743v1

Preprint submitted on 18 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Correlations and quantum circuits with dynamical causal order

Raphaël Mothe,¹,²,³ Alastair A. Abbott,² and Cyril Branciard¹

¹Univ. Grenoble Alpes, CNRS, Grenoble INP, Institut Néel, 38000 Grenoble, France

²Univ. Grenoble Alpes, Inria, 38000 Grenoble, France

³Naturwissenschaftlich-Technische Fakultät, Universität Siegen, Walter-Flex-Straße 3, 57068 Siegen, Germany

(Dated: July 14, 2025)

Requiring that the causal structure between different parties is well-defined imposes constraints on the correlations they can establish, which define so-called causal correlations. Some of these are known to have a “dynamical” causal order in the sense that their causal structure is not fixed *a priori* but is instead established on the fly, with for instance the causal order between future parties depending on some choice of action of parties in the past. Here we identify a new way that the causal order between the parties can be dynamical: with at least four parties, there can be some dynamical order which can nevertheless not be influenced by the actions of past parties. This leads us to introduce an intermediate class of correlations with what we call non-influenceable causal order, in between the set of correlations with static (non-dynamical) causal order and the set of general causal correlations. We then define analogous classes of quantum processes, considering recently introduced classes of quantum circuits with classical or quantum control of causal order—the latter being the largest class within the process matrix formalism known to have a clear interpretation in terms of coherent superpositions of causal orders. This allows us to formalise precisely in which sense certain quantum processes can have both indefinite and dynamical causal order.

## I. INTRODUCTION

The study of the causal structure of the physical world has led to many rich and fascinating research directions. On the one hand, the assumption of particular causal structures places constraints on observations that may be challenged, for example, by quantum mechanics [1] or gravity [2], while on the other hand, the possibility of causally indefinite processes opens intriguing possibilities, both foundational [3] and practical [4–6] in nature.

One approach has been to investigate how the assumption of a well-defined causal structure between different events constrains the correlations that can be established between them [3, 7–12]. Formally, such correlations can be studied through the notion of *causal correlations* obtainable by *N* parties receiving classical inputs and producing classical outputs within a well-defined causal structure. In the simplest nontrivial case with *N* = 2 parties *A* and *B*, the correlations are said to be causal if they can be established with the two parties acting one after the other in a fixed causal order (that may be chosen probabilistically for each run of the experiment), either “*A* before *B*” or “*B* before *A*” [3]. However, it was quickly realised that, as soon as one considers a third party, the assumption of a well-defined causal structure between the parties no longer imposes that the correlations established are necessarily compatible with a probabilistic fixed causal order: the correlations may follow a *dynamical* causal order that is not predetermined, or fixed *a priori*, but instead established on the fly as the parties act one after another [2, 10, 13, 14]. Causal correlations with dynamical causal order can be found in situations where the order between “future” parties depends on the actions of some “past” parties. While some recent works have studied correlations with dynamical, or “non-static”, causal order in specific scenarios [15–17],

little effort has so far been made to characterise more directly the notion of correlations with dynamical causal order as opposed to ones with non-dynamical causal order, or to understand their properties.

At the same time, the causal structure of quantum processes has been explored, in particular within the process matrix formalism [3]. By describing how different parties’ actions, which are locally causal and consistent with quantum mechanics, can be related without assuming any *a priori* well-defined global causal structure, this formalism distinguishes between processes that are compatible with a definite causal order from those that are not, the latter having an *indefinite causal order*. Indeed, the set of quantum processes compatible with a well-defined causal structure, the so-called *causally separable processes*, has been well studied [3, 8, 18] and, just as for causal correlations, it was observed that one must take into account processes with dynamical causal order in the definition of causally separable processes for $N \ge 3$ parties [14, 18]. For instance, one can create quantum processes in which the operation implemented by a party *A* can influence, or even determine, the order between two later parties, *B* and *C*, in the causal future of *A*; in any given run, however, a well-defined causal order can nonetheless be identified, albeit dynamically chosen. The notion of causal separability also, in particular, allows one to precisely argue that certain processes are causally indefinite, or *causally nonseparable* [3]. The *quantum switch* [19] is a notable example of such a process, in which the two possible causal orders between two parties *A* and *B*, namely “*A* before *B*” and “*B* before *A*”, are superposed in a coherent manner with the help of a control qubit, leading to a so-called *causal superposition*. In the quantum switch and its natural generalisations [5, 20], the parties never intervene on the causal order itself, and thus, despite being causally nonseparable, the quantum
switch does not intuitively exhibit a dynamical causal order. More recently, examples of processes that intuitively combine dynamical and indefinite causal order have been presented within the larger class of *quantum circuits with quantum control of causal order* (QC-QCs) [21]. These examples have highlighted, however, that the concept of dynamical causal orders has largely been overlooked, except for its consideration in the definition of causally separable processes. Until now, no precise definition of what it means for a process to have (or not) a dynamical causal order has been proposed, hindering attempts to argue precisely, for example, that the quantum switch does not feature any dynamical causal order while other QC-QCs may do. Moreover, the idea of combining dynamical and indefinite causal order finds motivations in a wide range of research lines, from foundational problems [2]—as a theory of quantum gravity is likely to involve a dynamical causal structure because of general relativity theory, with an indefinite causal structure because of quantum theory—to more applied problems—as it could offer new forms of advantages for quantum information processing over standard quantum circuits.

In this work, we propose precise definitions of (non)-dynamical causal structures, both at the level of causal correlations and quantum processes, and study in detail these notions of dynamical causal orders. Exploiting a characterisation of causal correlations in which the causal order appears explicitly as an additional (unobserved) random variable, we identify a novel way in which the causal order between different parties that establish causal correlations can be dynamical: for $N \ge 4$ parties, there can be some dynamical order which can nevertheless not be influenced by the actions of past parties. We thereby observe that the standard understanding of dynamical causal orders—as parties in the past influencing the order of those in the future [10, 13–17]—is incomplete. In addition to the already known classes of causal correlations, namely mixtures of fixed causal order correlations (which have non-dynamical causal order), and general causal correlations (which allow for any kind of dynamicality), this allows us to define the class of causal correlations with “non-influenceable orders”, and a weaker form of it, the class of causal correlations with “non-influenceable coarse-grained orders”. Using a four-partite causal game, we show that (for $N \ge 4$) these classes form a strict hierarchy of correlations.

Inspired by these classes of causal correlations, we next look to define analogous classes at the level of quantum processes. To this end, we restrict ourselves to subclasses of quantum circuits with classical or quantum control of causal order (QC-CCs or QC-QCs), as these have clear physical interpretations as generalised circuits in which a classical or quantum system is used to control, at each step, which party should act [21]. QC-QCs in particular include causally indefinite processes such as the quantum switch, but nevertheless can only produce causal correlations (potentially with dynamical causal order). We first study the class of QC-CCs, which are causally separable processes,

allowing us to study dynamicality independently from causal indefiniteness. We formalise QC-CCs with non-dynamical causal order as those that are convex mixtures of quantum circuits with fixed causal order (i.e., standard quantum circuits), a class that we denote QC-convFO. Just as for causal correlations, we find that a more subtle type of “non-influenceable” dynamical causal order also exists for QC-CCs. We formalise this as a condition for the internal control system of the QC-CC to be independent of the quantum operations chosen by previous parties, and we show how the corresponding class, QC-NICC, can be explicitly characterised. Turning our attention to QC-QCs, we then describe the class of QC-QCs with non-dynamical causal order, which allow for the quantum control system to create superpositions of causal orders, but with the weight of each order being fixed from the start, and not altered dynamically—a class that we call QC-supFO. The quantum switch (with a fixed control system) and its generalisations are shown to be contained in this class. By contrast, the existence of causally nonseparable quantum circuits beyond this class, in QC-QC\QC-supFO, allows us to formalise precisely in which sense certain quantum processes can have both indefinite and dynamical causal order. Finally, we formulate an analogous condition for QC-QCs to have non-influenceable quantum control of causal order, defining the class QC-NIQC, and providing nontrivial examples of QC-QCs with dynamical but non-influenceable causal order.

The rest of this paper is organised as follows. In Sec. II we introduce four classes of causal correlations: the class of mixtures of correlations with fixed causal orders, two classes of correlations with possibly dynamical but non-influenceable order, and the class of general causal correlations. We present a causal game that allows us to show a strict separation between these different classes. In Sec. III we introduce the corresponding classes of quantum circuits with classical and quantum control of causal order, and present examples of processes in each class. In Sec. IV we investigate the ability for processes in the different classes just introduced to saturate or violate inequalities that bound the different sets of causal correlations. Then, in Sec. V, we conclude with a discussion of our results and some related open questions.

## II. CORRELATIONS WITH DYNAMICAL CAUSAL ORDER

We will be interested throughout this paper in different scenarios, given by a finite number $N \ge 1$ of parties $A_k$ ($k \in \mathcal{N} := \{1, \dots, N\}$) that each chooses, or receives from an external referee, a classical input $x_k$ and produces a classical output $a_k$. Both the input and output belong to finite sets (not necessarily identical), which may differ for each party. When convenient (for a small enough, fixed value of $N$), we will sometimes equivalently refer to the parties by $A_1, A_2, A_3, \dots$ or $A, B, C, \dots$, and anal-
ogously denote their inputs and outputs $x_1, x_2, x_3, \dots$ and $a_1, a_2, a_3, \dots$, or $x, y, z, \dots$ and $a, b, c, \dots$. An ordered set of $n$ parties, where $A_{k_1}$ is first and $A_{k_n}$ is last, will be denoted as $(k_1, \dots, k_n)$, while the unordered set composed of the same $n$ parties will be denoted as $\mathcal{K}_n = \{k_1, \dots, k_n\}$. Both notations implicitly assume that all $k_i$'s are different (with the notation $\mathcal{K}_n$ implying it contains $n$ elements); furthermore, we simply identify the parties $A_k$ with their label $k$.

Due to a common cause prior to the parties' actions, or because of signalling between the parties, their outputs might be correlated, conditioned on their inputs. We are thus interested in the correlations established by the different parties that are described using the conditional probability distribution $p(\vec{a}|\vec{x})$, where $\vec{x} = (x_1, \dots, x_N)$ and $\vec{a} = (a_1, \dots, a_N)$ are the vectors of inputs and outputs. For the sake of conciseness, we will denote the vector of inputs and outputs of the set of parties $\mathcal{K}_n = \{k_1, \dots, k_n\}$ by $\vec{x}_{\mathcal{K}_n}$ or $\vec{x}_{k_1, \dots, k_n} = (x_{k_1}, \dots, x_{k_n})$ and $\vec{a}_{\mathcal{K}_n}$ or $\vec{a}_{k_1, \dots, k_n} = (a_{k_1}, \dots, a_{k_n})$. We will study here the correlations obtained when imposing that the causal structure between the parties is well-defined.

## A. Multipartite causal correlations

The causal structure between parties constrains the correlations they can establish; indeed, a party cannot signal to any party in its causal past. This observation forms the basis of the definition of causal correlations, which are those compatible with a well-defined causal structure.

To start with, let us consider the case of $N = 2$ parties, the $N = 1$ case being rather trivial. Assuming a well-defined causal order between $A$ and $B$ implies that either $A$ causally precedes $B$ (which we will denote $A \prec B$), $B$ causally precedes $A$ (which we will denote $B \prec A$), or one may be in a probabilistic mixture of the two possibilities. The case that $A$ and $B$ are causally independent can be included in either of the above cases, as the observed correlations will be non-signalling in both directions and thus compatible with both $A \prec B$ and $B \prec A$. Thus, we say that the causal structure between the two parties is well-defined, or equivalently, that the probability distribution $p(a, b|x, y)$ is a bipartite causal correlation, if and only if

$$p(a, b|x, y) = q p_{A\prec B}(a, b|x, y) + (1-q) p_{B\prec A}(a, b|x, y), \quad (1)$$

where $q \in [0, 1]$, and $p_{A\prec B}, p_{B\prec A}$ are probability distributions whose marginal distributions satisfy the one-way-signalling constraints $p_{A\prec B}(a|x, y) = p_{A\prec B}(a|x)$ and $p_{B\prec A}(b|x, y) = p_{B\prec A}(b|y)$ [3].

In the general multipartite scenario with $N$ parties, we say that a correlation $p_{\pi}(\vec{a}|\vec{x})$ is compatible with a fixed causal order (encoded as a permutation of the parties)

$$\pi = (k_1, \dots, k_N) \text{ if and only if}^1$$

$$\begin{gathered} \forall n = 1, \dots, N-1, \\ p_{\pi}(\vec{a}_{k_1, \dots, k_n} | \vec{x}) \text{ does not depend on } \vec{x}_{\mathcal{N}\setminus\{k_1, \dots, k_n\}}, \quad (2) \end{gathered}$$

where $p_{\pi}(\vec{a}_{k_1, \dots, k_n} | \vec{x}) := \sum_{\vec{a}_{\mathcal{N}\setminus\{k_1, \dots, k_n\}}} p_{\pi}(\vec{a}|\vec{x})$. As (for any fixed number of parties, and of inputs and outputs for each party) the set of correlations compatible with a fixed causal order $\pi$ is defined by a finite number of linear constraints on a bounded probability space, it defines a convex polytope [22]. The convex hull of all the polytopes of correlations compatible with a given fixed causal order $\pi$ is therefore also a convex polytope, that we call $\mathcal{P}_{\text{convFO}}$. It comprises any probabilistic mixture of correlations, each of which is compatible with a fixed causal order $\pi$. Note that in the bipartite scenario, $\mathcal{P}_{\text{convFO}}$ corresponds precisely to the set of causal correlations.

As soon as one considers scenarios with more than two parties, however, there are correlations that can be understood as being compatible with a well-defined causal structure between the parties, and yet do not correspond to probabilistic mixtures of correlations with fixed causal order. As proposed in [2] and formalised in [10, 13, 14], fundamentally new, dynamical properties appear from the tripartite case onwards. These are usually referred to as dynamical causal orders, in the sense that the causal order of future parties is not fixed from the start, but is established on the fly ("dynamically") as the correlations are constructed, i.e., as the inputs of the parties are chosen and their outputs are obtained. For instance, the input choice of a first party, say $A$, may determine the causal order between two subsequent parties, $B$ and $C$. Intuitively, we say that a causal structure is well-defined if, after the parties have acted, one can interpret them as having acted in a strict order, where a given party can only affect the order between the parties that have not already acted, as well as their outputs (together with the given party's own output). More precisely, we say that a correlation $p(\vec{a}|\vec{x})$ between $N$ parties has a well-defined causal structure if one can identify a hidden variable $\pi$ encoding the causal order, and a joint distribution $p(\pi, \vec{a}|\vec{x})$, such that the probability to observe $n$ parties following the order $(k_1, \dots, k_n)$ with given outputs $\vec{a}_{k_1, \dots, k_n}$, and the choice of the next party $A_{k_{n+1}}$ to act, cannot be influenced by the choice of inputs made by the $N-n$ parties that remain to act. Formally, a distribution $p(\vec{a}|\vec{x})$ is thus a causal correlation if and only

<footnote n="1">¹ More formally, that the specified probability does not depend on $\vec{x}_{\mathcal{N}\setminus\{k_1, \dots, k_n\}}$ means here that $\forall \vec{a}_{k_1, \dots, k_n}, \forall \vec{x}_{k_1, \dots, k_n}, \forall \vec{x}_{\mathcal{N}\setminus\{k_1, \dots, k_n\}}, \forall \vec{x}'_{\mathcal{N}\setminus\{k_1, \dots, k_n\}}, p_{\pi}(\vec{a}_{k_1, \dots, k_n} | \vec{x}_{k_1, \dots, k_n}, \vec{x}_{\mathcal{N}\setminus\{k_1, \dots, k_n\}}) = p_{\pi}(\vec{a}_{k_1, \dots, k_n} | \vec{x}_{k_1, \dots, k_n}, \vec{x}'_{\mathcal{N}\setminus\{k_1, \dots, k_n\}})$.</footnote>
if

$$ \exists p(\pi, \vec{a}|\vec{x}) \text{ s.t. } p(\vec{a}|\vec{x}) = \sum_{\pi} p(\pi, \vec{a}|\vec{x}) \\ \text{and } \forall n = 0, \dots, N-1, \forall (k_1, \dots, k_n, k_{n+1}), \\ \qquad p((k_1, \dots, k_n, k_{n+1}), \vec{a}_{k_1, \dots, k_n} | \vec{x}) \\ \qquad \text{does not depend on } \vec{x}_{N \setminus \{k_1, \dots, k_n\}}, \quad (3) $$

where the marginal distributions are defined according to

$$ \begin{aligned} p((k_1, \dots, k_{n+1}), |\cdot) &:= \sum_{\substack{\pi \text{ s.t. } \pi(1)=k_1, \dots \\ \dots, \pi(n+1)=k_{n+1}}} p(\pi, |\cdot) \\ &= \sum_{(k_{n+2}, \dots, k_N)} p(\pi = (k_1, \dots, k_{n+1}, k_{n+2}, \dots, k_N), |\cdot), \end{aligned} \quad (4) $$

$$ \text{and } p(\cdot, \vec{a}_{k_1, \dots, k_n} | \cdot) := \sum_{\vec{a}_{N \setminus \{k_1, \dots, k_n\}}} p(\cdot, \vec{a} | \cdot). $$

From the general requirement that the causal structure between the parties should be well defined, Refs. [10, 14] proposed two equivalent definitions of causal correlations $p(\vec{a}|\vec{x})$. The definition of [14] proposes a decomposition of a causal correlation in terms of components compatible with a strict partial order, while the one of [10] proposes a recursive characterisation of causal correlations. Our definition in Eq. (3) turns out to also be equivalent to the ones proposed in [10, 14], as we prove in Appendix A (where we also provide two more possible characterisations of causal correlations). Our approach based on the compatibility with a total ordering of the parties will prove useful to investigate the notion of causal correlations with dynamical causal order, and somewhat simpler to deal with than with strict partial orders (as considered in [14]).

As any convex combination of causal correlations is a causal correlation, the set of causal correlations is convex. As noted in [9, 14], this set (for any given scenario, i.e. for any given number of parties, and of inputs and outputs for each party) forms a convex polytope $P_{causal}$, called the causal polytope, that clearly contains $P_{convFO}$. Its vertices correspond to deterministic strategies, i.e., correlations for which the probabilities $p(\vec{a}|\vec{x})$ (as well as $p(\pi, \vec{a}|\vec{x})$ in their causal decomposition) only take the values 0 and 1. In principle one can list all such vertices, and use standard techniques to then enumerate the facets of the causal polytope [9, 10, 22], which define so-called causal inequalities—although this becomes computationally quite demanding when the numbers of parties, of inputs and outputs go beyond the simplest cases.

An especially simple scenario of particular interest, which we will focus on in this paper, is the so-called “lazy” scenario, in which each party $A_k$ has a binary input $x_k$ (we will take $x_k = 0, 1$), a binary output for one of the two inputs ($a_k = 0, 1$ if $x_k = 1$), and a single fixed output for the other input ($a_k = 0$ if $x_k = 0$). The bipartite and tripartite causal polytopes were fully characterised in the lazy scenario in Refs. [9, 10] (while for the more usual scenario with binary inputs and outputs, this could

only be done for $N = 2$ [9]). It was found in particular that in the bipartite lazy scenario, the causal polytope has only one type of nontrivial facet inequality,<fnref n="2" /> which can be interpreted as a bound on the maximal probability of success in a causal game, the *Lazy Guess Your Neighbour’s Input* (LGYNI) game [9]. The goal of this game is for A and B to output the input bit of the other party, but only when their input is 1; otherwise, the lazy scenario imposes that they must output 0. In short, A and B win the game if they both output $a = b = xy$. If one assumes the input bits to be uniformly distributed, the causal bound on the success probability for the LGYNI game is<fnref n="3" />

$$ p_{\text{LGYNI}} := p(a = b = xy) \le \frac{3}{4}. \quad (5) $$

This bound captures the intuition that if the causal structure between A and B is well-defined, then the party that acts last can guess the input of the first party with certainty, while the party that comes first cannot do better than output a random guess for the input of the second party. Given that the latter is asked to guess correctly that input in half of the cases (when receiving input 1), then overall they have at least a $\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$ probability of losing at the LGYNI game.

## B. Static vs. dynamical order

As introduced above, for $N \ge 3$ parties, some causal correlations are not just convex mixtures of fixed causal orders. The correlations with “static”, or “non-dynamical” causal order, are those that are convex mixtures of fixed causal orders, and that define $P_{convFO}$.

To illustrate the difference between static and dynamical causal order, we consider the following tripartite scenario. One of the three parties (here party A) has a binary input but no output (or fixed output taking a single value), and the two other parties are in the lazy scenario. Assuming uniform inputs, i.e. $p(x, y, z) = \frac{1}{8}$, we introduce the expression

$$ I_3 := p(x = 0, c = yz) + p(x = 1, b = yz). \quad (6) $$

This equation can be interpreted as the success probability of a causal game where, depending on the input $x = 0$ or 1 of A, either C should guess the input of B (when they get the input $z = 1$), or vice-versa (when $y = 1$).

<footnote n="2">² More specifically, in that scenario $P_{causal}$ has 4 nontrivial facets: the other ones are obtained by flipping the outputs a and/or b when x and/or y = 1. Additionally, it has 8 trivial facets of the form $p(a, b|x, y) \ge 0$.</footnote>

<footnote n="3">³ Here, and throughout this work, we use the short-hand notation that implicitly assumes uniform inputs, so that $p(a = b = xy) = \sum_{x,y,a,b=0,1} p(x, y)\delta_{a,xy}\delta_{b,xy}p(a, b|x, y) = \frac{1}{4} \sum_{x,y,a,b=0,1} \delta_{a,xy}\delta_{b,xy}p(a, b|x, y)$, where $\delta$ denotes the Kronecker delta.</footnote>
As it turns out, one obtains the following bound on $I_3$, assuming that $p(b, c|x, y, z)$ should be a convex mixture of fixed causal order correlations:

$$I_3 \le \frac{7}{8}. \qquad (7)$$

This bound can be understood intuitively in a similar way to that of Eq. (5) above. A formal proof is given in Appendix B 1, where we also note that Eq. (7) is actually a facet inequality of the polytope $P_{convFO}$. The inequality (7) is thus tight, and it is saturated, e.g., by $p(b, c|x, y, z) = \delta_{b,0} \delta_{c,yz}$, which is compatible with the causal order $A \prec B \prec C$.

For general causal correlations however, we have the larger (trivial) bound

$$I_3 \le 1, \qquad (8)$$

which can be reached, e.g., by

$$p(b, c|x, y, z) = \begin{cases} \delta_{b,0} \delta_{c,yz} & \text{if } x = 0 \\ \delta_{c,0} \delta_{b,yz} & \text{if } x = 1 \end{cases}. \qquad (9)$$

This correlation is indeed causal, as it satisfies the characterisation of Eq. (3), with a decomposition given by

$$p(\pi, b, c|x, y, z) = \begin{cases} \delta_{\pi,(A,B,C)} \delta_{b,0} \delta_{c,yz} & \text{if } x = 0 \\ \delta_{\pi,(A,C,B)} \delta_{c,0} \delta_{b,yz} & \text{if } x = 1 \end{cases}. \qquad (10)$$

Hence, there is clearly a gap between convex mixtures of causal orders and general causal correlations. Causal correlations that are not convex mixtures of fixed orders are said to have dynamical causal order.

Note that in the specific example above,

$$p(\pi|x, y, z) = \begin{cases} \delta_{\pi,(A,B,C)} & \text{if } x = 0 \\ \delta_{\pi,(A,C,B)} & \text{if } x = 1 \end{cases}. \qquad (11)$$

Hence, here the causal order is determined, or “influenced” by the input $x$. As we shall see, for $N \ge 4$ parties there can also be dynamical causal order with no such influence.

### C. Dynamical but non-influenceable orders

We now study in more detail causal correlations with dynamical causal order. Inspired by the last comment above, we formalise the notion of causal correlations with (non-)influenceable causal order in order to compare it to the notion of causal correlations with (non-)dynamical causal order.

Intuitively, we say that a causal correlation has a non-influenceable causal order between the parties if none of the choices of inputs for the parties can influence the causal order between them. This can be understood as requiring that the hidden variable $\pi$ describing the causal order that unfolds in causal correlations (cf. Eq. (3)) is independent of the inputs $\vec{x}$. Formally, we thus define

causal correlations with non-influenceable orders as those that admit a causal decomposition in terms of $p(\pi, \vec{a}|\vec{x})$ as in Eq. (3), which further satisfies

$$\forall \pi, p(\pi|\vec{x}) \text{ does not depend on } \vec{x}, \qquad (12)$$

where $p(\pi|\vec{x}) := \sum_{\vec{a}} p(\pi, \vec{a}|\vec{x})$. We emphasise that this definition does not forbid, in general, the existence of another causal decomposition with $p'(\pi|\vec{x}) \ne p'(\pi|\vec{x}')$ for some $\vec{x}, \vec{x}', \pi$. We note also that one could equivalently impose a similar condition starting from a causal decomposition as defined in the language of [14] (in terms of strict partial orders rather than total orderings), see Appendix A 4.

The set of correlations $p(\pi, \vec{a}|\vec{x})$ that satisfy Eq. (3) is a bounded probability space that is linearly constrained, and thus defines a convex polytope. The set of causal correlations with non-influencable orders can then be obtained as a projection of the latter polytope (projecting out the unobserved variable $\pi$), and hence also defines a convex polytope. This polytope, which we call $P_{NIO}$, is included in the causal polytope $P_{causal}$ and moreover clearly contains the polytope $P_{convFO}$. The relation between these sets is shown in Fig. 1; we will see in the following section that the inclusions are indeed generally strict. Characterising explicitly the vertices and facet inequalities of the polytope $P_{NIO}$ is somewhat more complicated than for $P_{convFO}$ or $P_{causal}$. While for these latter polytopes the vertices are deterministic and can be enumerated relatively directly, this is not the case for the vertices of $P_{NIO}$. Instead, the polytope of correlations $p(\pi, \vec{a}|\vec{x})$ involving also $\pi$ is defined by Eqs. (3) and (12) along with nonnegativity and normalisation. Obtaining an explicit characterisation of $P_{NIO}$ is thus computationally costly. One can either first transform this higher-dimensional polytope into its vertex representation before projecting out $\pi$ to obtain the vertices of $P_{NIO}$, which are in general not deterministic, or adopt variable elimination methods in order to compute directly facet inequalities bounding $P_{NIO}$ [23]. Nonetheless, one can still test whether a given correlation is inside the polytope or not by using linear programming to search explicitly for a causal decomposition satisfying Eq. (12).

Before moving on to comparing the different sets of correlations introduced so far, let us introduce one more, which will prove relevant when analysing the correlations produced by certain quantum circuits with quantum control of causal order, see Sec. III C. As we will recall, QC-QCs involve a control system which, at any given time, only encodes the unordered set $K_{n-1}$ of parties that have already acted, together with the label $k_n$ of the party that acts at that given time. Looking back at causal correlations and at their decomposition in terms of $p(\pi, \vec{a}|\vec{x})$, this suggests it may be relevant in that context to consider the probabilities that the first $n-1$ parties are those in $K_{n-1}$, and that the $n^{th}$ party is $k_n$, i.e. the “coarse-grained” probabilities $p((K_{n-1}, k_n)|\vec{x}) := \sum_{(k_1, \dots, k_{n-1}) \in K_{n-1}} p((k_1, \dots, k_{n-1}, k_n)|\vec{x})$. In a similar way to how we introduced correlations with non-
<figure><img src="image_2.png" /><figcaption>Figure 1. Illustration of the inclusion relations between the polytopes: $P_{\text{convFO}} \subset P_{\text{NIO}} \subset P_{\text{NIO}'} \subset P_{\text{causal}}$. In general (for $N \ge 4$) the inclusions are strict; for $N \le 3$ however, $P_{\text{NIO}}$ and $P_{\text{NIO}'}$ reduce to $P_{\text{convFO}}$; and for $N \le 2$, they all coincide. The polytopes are also all (in general strictly) included in the polytope of all correlations (all valid probability distributions), illustrated by the dashed lines.</figcaption></figure>

influenceable order, let us then define causal correlations with non-influenceable coarse-grained orders as those that admit a causal decomposition in terms of $p(\pi, \vec{a}|\vec{x})$ as in Eq. (3), which further satisfies<fnref n="4" />

$$ \forall \mathcal{K}_{n-1} \subsetneq \mathcal{N}, \forall k_n \in \mathcal{N} \setminus \mathcal{K}_{n-1}, \\ p(\mathcal{K}_{n-1}, k_n|\vec{x}) \text{ does not depend on } \vec{x}. \quad (13) $$

As for the set of correlations with non-influenceable orders, the set of causal correlations with non-influenceable coarse-grained orders forms a convex polytope, which we denote $P_{\text{NIO}'}$, that includes $P_{\text{NIO}}$ and is included in $P_{\text{causal}}$. Characterising this polytope in terms of vertices (which, in general, are not deterministic) and facets is of a similar difficulty as for $P_{\text{NIO}}$.

It turns out that for $N \le 3$, correlations with non-influenceable orders, as well as correlations with non-influenceable coarse-grained orders, are nothing but convex mixtures of fixed orders, i.e. $P_{\text{NIO}}$ and $P_{\text{NIO}'}$ reduce to $P_{\text{convFO}}$ (see the proof in Appendix B 2). Thus, the notions of dynamicality and influenceability coincide in that case. However, we will see that as soon as $N \ge 4$, these form genuinely distinct classes of correlations.

### D. Separation between the four polytopes of correlations

To show that the classes of correlations introduced above indeed form a strict hierarchy, let us consider the fourpartite case with all parties in the lazy scenario, and let us introduce

$$ I_4 := p(a=b=xy, d=zt) \\ + p(\neg(a=b=xy), c=zt). \quad (14) $$

This expression can be understood as the success probability of a new causal game involving all four parties, defined as follows: A and B play the LGYNI game, as presented before Eq. (5); depending on whether they win or lose the LGYNI game, either D must guess (when receiving the input 1) the input of C, or vice-versa.

One can readily see the connection with the expression of $I_3$, Eq. (6): instead of looking at how the direction of signalling between the last two parties correlates with the input of the first party, as in $I_3$, here we look at how that direction of signalling correlates with the success or failure in the LGYNI game between the first two parties—which, if these are causally connected, cannot be predetermined since the LGYNI cannot be won, nor lost,<fnref n="5" /> with certainty.

As we show in Appendix C, the bounds on $I_4$ are different for the different sets of correlations introduced above, namely:<fnref n="6" />

* For convex mixtures of fixed orders:

$$ I_4 \le \frac{15}{16}. \quad (15) $$

This bound is reached for instance by the correlation (compatible with any fixed order where $C \prec D$) $p(a, b, c, d|x, y, z, t) = \delta_{a,0} \delta_{b,0} \delta_{c,0} \delta_{d,zt}$.

* For non-influenceable orders:

$$ I_4 \le \frac{31}{32}. \quad (16) $$

This bound is reached for instance by the correlation presented in Eq. (C20) of Appendix C 2.

<footnote n="4">⁴ Notice that one could have equivalently defined correlations with non-influenceable order by imposing that for any $n = 1, \dots, N$, $p((k_1, \dots, k_n)|\vec{x})$ does not depend on $\vec{x}$—which would be slightly closer to Eq. (13). In that case however, considering $n = N$ was enough; for correlations with non-influenceable coarse-grained orders on the other hand, imposing the corresponding constraint only for $n = N$ would in general define a larger set of correlations.</footnote>

<footnote n="5">⁵ Notice that the LGYNI game is always won when the inputs are $x = y = 0$, so $p_{\text{LGYNI}} \ge \frac{1}{4}$ always holds.</footnote>

<footnote n="6">⁶ We note that neither Eq. (15), nor Eq. (18), are facets of the corresponding polytopes: we find that the vertices that saturate them span affine subspaces of dimensions 55 and 33, respectively, while the dimension of the total correlation space in the 4-partite lazy scenario, and of the four polytopes under consideration here, is 65. We also do not expect Eqs. (16) and (17) to define facet inequalities, although we could not check this because of the difficulty of enumerating the vertices of $P_{\text{NIO}}$ and $P_{\text{NIO}'}$. In Appendix E 4 we present an inequality that defines a facet of $P_{\text{convFO}}$. Obtaining more facet inequalities for the various polytopes—possibly inequalities that can be given nice interpretations in terms of causal games—is left for future work.</footnote>
• For non-influenceable coarse-grained orders:

$$I_4 \le \frac{47}{48}. \qquad (17)$$

This bound is reached for instance by the correlation presented in Eq. (C24) of Appendix C 3.

• For general causal correlations, one has the trivial bound:

$$I_4 \le 1. \qquad (18)$$

This bound is reached for instance by

$$p(a, b, c, d|x, y, z, t) = \delta_{a,0} \delta_{b,0} \begin{cases} \delta_{c,0} \delta_{d,zt} & \text{if } xy = 0 \\ \delta_{d,0} \delta_{c,zt} & \text{if } xy = 1 \end{cases}, \quad (19)$$

where the order between C and D depends on the product of inputs xy.

The fact that the bounds above are different implies that there is a clear separation between the different types of correlations and the corresponding polytopes, as depicted in Fig. 1:

$$\mathcal{P}_{\text{convFO}} \subset \mathcal{P}_{\text{NIO}} \subset \mathcal{P}_{\text{NIO}'} \subset \mathcal{P}_{\text{causal}}, \quad (20)$$

where the inclusions are in general all strict for $N \ge 4$. In particular, we see that correlations with static causal order (in $\mathcal{P}_{\text{convFO}}$) are only a restricted case of correlations with non-influenceable order: one can find correlations with non-influenceable order that are not just convex mixtures of correlations with fixed orders. In other words, there exist correlations with dynamical but non-influenceable order, i.e. dynamicality and influenceability are inequivalent notions in general, despite the fact that these notions have largely been equated in the literature [10, 14–17].

### III. QUANTUM CIRCUITS WITH DYNAMICAL CAUSAL ORDER

Now that we have clarified the definition of correlations with dynamical causal order and explored some of their features, let us turn to the quantum processes that may generate such correlations, and see how one may characterise the dynamicality of these processes directly. More specifically, we will focus on quantum circuits, although with a less constrained definition than the usual one: we allow for quantum circuits that do not necessarily have a fixed, or even well-defined causal order. Two important, physically relevant classes of such circuits were introduced in Ref. [21]: quantum circuits with classical or with quantum control of causal order (QC-CCs or QC-QCs). The latter includes in particular processes that intuitively feature both indefinite and dynamical causal order, although no clear definition of dynamicality was given so far, that would formalise this intuition. Below

we will remedy this by looking at whether the classical or quantum systems used to control the causal order can be fixed from the start, or can be influenced by the choice of the parties’ operations.

QC-CCs and QC-QCs are conveniently described within the framework of process matrices [3]; let us start by recalling this formalism.

#### A. The process matrix formalism

The process matrix formalism was introduced in Ref. [3] in order to characterise correlations that could be obtained from quantum processes, without imposing a priori that the operations giving rise to these correlations are applied according to any specific, well-defined causal structure. By relaxing the assumption of a well-defined global causal order between the different operations, this formalism allows one to go beyond standard, causally ordered quantum circuits, and describe processes with potentially indefinite causal order.

More formally, one considers a situation with $N$ parties $A_k$ applying some quantum operations, described as quantum instruments [24], i.e. as collections $\{M_{a_k|x_k}^{A_k}\}_{a_k}$ of completely positive (CP) maps $M_{a_k|x_k}^{A_k}: \mathcal{L}(\mathcal{H}^{A_k}) \to \mathcal{L}(\mathcal{H}^{A_k^O})$ from party $A_k$’s input Hilbert space $\mathcal{H}^{A_k^I}$ to their output Hilbert space $\mathcal{H}^{A_k^O}$, with $\mathcal{L}(\mathcal{H}^X)$ denoting the space of linear operators acting on $\mathcal{H}^X$ (and restricting ourselves, throughout this paper, to finite-dimensional Hilbert spaces). Here $x_k$ labels the instrument, and thus describes the choice of a “setting” for $A_k$’s operation. Each map $M_{a_k|x_k}^{A_k}$ in the instrument is associated with a classical output $a_k$, so that for any given (trace 1) input state $\rho \in \mathcal{L}(\mathcal{H}^{A_k^I})$, the probability for that map to be applied and for that output to be produced is $\text{Tr}[M_{a_k|x_k}^{A_k}(\rho)]$. To ensure that these probabilities sum up to 1, the sum over $a_k$ of all CP maps $M_{a_k|x_k}^{A_k}$ in a given instrument must be trace-preserving (TP).

A convenient way to represent such quantum operations, that the process matrix formalism relies on, is through the Choi–Jamiołkowski isomorphism [25, 26]. For any given map $\mathcal{M}: \mathcal{L}(\mathcal{H}^{A^I}) \to \mathcal{L}(\mathcal{H}^{A^O})$, one can define its Choi matrix $\mathcal{M}$ as<fnref n="7" />

$$\mathcal{M}^{A^O} := \sum_{i,j} |i\rangle\langle j|^{A^I} \otimes \mathcal{M}(|i\rangle\langle j|^{A^I}) \in \mathcal{L}(\mathcal{H}^{A^O}), \quad (21)$$

where $\{|i\rangle^X\}_i$ generically denotes a fixed orthonormal basis—the “computational basis”—of $\mathcal{H}^X$, and where we use the short-hand notations $|i\rangle\langle j|^{X} := |i\rangle^X\langle j|^{X}$,

<footnote n="7">⁷ We often use superscripts on operators and vectors to indicate the spaces they belong to. These may be dropped when the situation is clear enough.</footnote>
$\mathcal{H}^{XY} := \mathcal{H}^X \otimes \mathcal{H}^Y$ and $\mathcal{H}^{A^IO} := \mathcal{H}^{A^IA^O}$. With this, a quantum instrument $\{\mathcal{M}_{a_k|x_k}^{A_k}\}_{a_k}$ can equivalently be described by the set of Choi matrices $\{M_{a_k|x_k}^{A_k}\}_{a_k}$, with each $M_{a_k|x_k}^{A_k} \in \mathcal{L}(\mathcal{H}^{A^IO})$. The complete positivity of each $\mathcal{M}_{a_k|x_k}^{A_k}$ translates to the positive semidefiniteness of their Choi matrices, $M_{a_k|x_k}^{A_k} \ge 0$, while the trace-preserving property of their sum (for each $x_k$) translates to the property that $\sum_{a_k} \text{Tr}_{A^O_k} M_{a_k|x_k}^{A_k} = 1^{A_k^I}$ (where $\text{Tr}_X$ denotes the partial trace over $\mathcal{H}^X$, and $1^Y$ denotes the identity operator on $\mathcal{H}^Y$).

Ref. [3] then considered the question of what are the most general correlations—i.e., the most general conditional probability distributions $p(\vec{a}|\vec{x})$ of obtaining the outputs $\vec{a} = (a_1, \dots, a_N)$ for a choice of settings (of instruments) $\vec{x} = (x_1, \dots, x_N)$—that would be consistent with the quantum description of the $N$ parties’ local operations, but would not require a priori that these operations are applied in any well-defined order. Imposing that the probabilities $p(\vec{a}|\vec{x})$ only depend on the local maps $\mathcal{M}_{a_k|x_k}^{A_k}$ (rather than on the full instruments $\{\mathcal{M}_{a_k|x_k}^{A_k}\}_{a_k}$) and that these probabilities are linear in the local maps (for consistency with probabilistic mixtures and coarse-graining of operations, assuming that each of them is applied once and only once), it was shown that they can most generally be written in the following form—via the “generalised Born rule”:

$$p(\vec{a}|\vec{x}) = \text{Tr} \left[ \left( \bigotimes_k M_{a_k|x_k}^{A_k} \right)^T W \right], \quad (22)$$

where $W \in \mathcal{L}(\mathcal{H}^{A^IO})$ (with $\mathcal{H}^{A^IO} := \bigotimes_{k \in \mathcal{N}} \mathcal{H}^{A^IO}$) is the so-called “process matrix”. In order to only generate non-negative and normalised probabilities through Eq. (22), for any actions of the parties (even when the latter share auxiliary, possibly entangled systems and their local operations are allowed to also act on these), the process matrix must be positive semidefinite (PSD) and must satisfy certain linear constraints [3, 8], which we recall in Appendix D 1. If that is the case, we say that the process matrix is “valid”.

The process matrix framework has also been extended to describe how $N$ quantum operations may be combined so as to generate a new “global” quantum map (rather than probabilities, i.e. scalar values), from some “past” Hilbert space $\mathcal{H}^P$ to some “future” Hilbert space $\mathcal{H}^F$— again without assuming a priori that the operations are composed in any well-defined order [27]. In that case the process matrix lives in $\mathcal{L}(\mathcal{H}^{PA^IO}) = \mathcal{L}(\mathcal{H}^P \otimes \mathcal{H}^{A^IO} \otimes \mathcal{H}^F)$ and acts as a “supermap”: a map that transforms quantum maps to a new quantum map [28]. Specifically, the Choi matrix of the resulting global map is given

through a further generalisation of the Born rule above:

$$M_{\vec{a}|\vec{x}}^{PF} = \text{Tr}_{A^O_N} \left[ \left[ 1^P \otimes \left( \bigotimes_k M_{a_k|x_k}^{A_k} \right)^T \otimes 1^F \right] W \right] \in \mathcal{L}(\mathcal{H}^{PF}) \quad (23)$$

(which indeed recovers Eq. (22) when $\mathcal{H}^P, \mathcal{H}^F$ are “trivial”, i.e. 1-dimensional spaces). When the local input maps (possibly extended to auxiliary systems) are CP, then the resulting global map is required to also be CP. When the local input maps are TP (e.g. considering the sum of the parties’ instrument elements), then the resulting global map is required to also be TP. This implies that the process matrix must still be PSD and satisfy certain linear constraints (also recalled in Appendix D 1), for it to be valid.<fnref n="8" />

By just requiring that only valid probabilities, or only valid CP(TP) maps are obtained through Eq. (22) or (23), the “top-down” approach of the framework allows for quite general forms of process matrices, including some for which no clear physical interpretation is known [3, 11]. A more constructive, bottom-up approach was taken in Ref. [21] to describe (using the same formalism) certain processes with a clearer physical understanding. This led to the introduction of the subclasses of quantum circuits with classical or quantum control of causal order. Interestingly these subclasses can be characterised in terms of linear constraints on PSD matrices, as we will recall below.

## B. Quantum Circuits with Classical Control of causal order

Let us start with the case of quantum circuits with classical control of causal order (QC-CCs). We will first recall their general form and then introduce two subclasses so as to characterise the dynamicality of their causal order.

### 1. The general QC-CC class

QC-CCs were introduced in [21], in an attempt to construct the most general class of processes with a well-defined causal order. The causal order of a QC-CC is not necessarily predetermined: it is in general established on the fly, and can hence be dynamical. More precisely, the action of a QC-CC can be understood as a protocol that alternatively applies “internal” and “external” operations,

<footnote n="8">⁸ We recall however that the two versions of the process matrix formalism, with “close” or “open” past and future spaces $\mathcal{H}^P, \mathcal{H}^F$, are in fact equivalent [21, 27]. Indeed, the past Hilbert space $\mathcal{H}^P$ (the future Hilbert space $\mathcal{H}^F$, respectively) can be considered as the output space (the input space, resp.) of an additional party with no input space (no output space, resp.).</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 2. Graphical representation of a quantum circuit with classical control (QC-CC) of causal order (a simplified version of Fig. 9 from Ref. [21], also reproduced with more details as Fig. 9 in Appendix D 2). The QC-CC is defined as the composition of the “internal” operations $\tilde{\mathcal{M}}_1, \dots, \tilde{\mathcal{M}}_{N+1}$ (shown in the red shaded area), leaving “open slots” for the parties’ “external” operations $\mathcal{A}_k$ (or the CP maps $\mathcal{M}_{a_k|x_k}^{A_k}$, as we denote them in the main text.) Each internal operation $\tilde{\mathcal{M}}_n$ (for $n \le N$) determines which party $A_{k_n}$ should act next; it transmits a target system from the previous party $A_{k_{n-1}}$ to the next party $A_{k_n}$ (or from the global past space $\mathcal{H}^P$ to $A_{k_1}$ for $\tilde{\mathcal{M}}_1$), potentially along with an auxiliary system (mid-height line on the figure), and updates the state of the classical control system (bottom double-stroke line) into the state $\llbracket (k_1, \dots, k_{n-1}, k_n) \rrbracket := |(k_1, \dots, k_{n-1}, k_n)\rangle\langle(k_1, \dots, k_{n-1}, k_n)|$, which keeps track of the ordered list of all external operations used so far. The last internal operation $\tilde{\mathcal{M}}_{N+1}$ just outputs a state in the global future space $\mathcal{H}^F$ (when the latter is nontrivial). According to this description, the causal order between the external operations is thus established on the fly or dynamically, as each internal operation is applied.</figcaption></figure>

the latter corresponding to the quantum operations chosen by the different parties $A_k$. As depicted in Fig. 2, a first internal operation $\tilde{\mathcal{M}}_1$ acts on the system entering the circuit in the “past” Hilbert space $\mathcal{H}^P$ (if any: the past system could also be trivial) and determines which party $A_{k_1}$ will apply its external operation first. Then each subsequent internal operation $\tilde{\mathcal{M}}_n$ determines (potentially, probabilistically) which party $A_{k_n}$ will be the next to apply its external operation, conditioned on which previous external operations have already been applied (to ensure that each of them is applied once and only once), and in which order. This conditioning can be physically encoded in a control system that acts classically, with its state of the form $\llbracket (k_1, \dots, k_n) \rrbracket := |(k_1, \dots, k_n)\rangle\langle(k_1, \dots, k_n)|$ being updated to $\llbracket (k_1, \dots, k_n, k_{n+1}) \rrbracket$ as the next party $A_{k_{n+1}}$ is chosen—thereby dynamically storing the causal order of the parties as it gets established. The QC-CC under consideration is then defined as the composition of the internal maps $\tilde{\mathcal{M}}_1, \dots, \tilde{\mathcal{M}}_{N+1}$, leaving “open slots” for the parties’ external operations; see Appendix D 2 a and Ref. [21] for more details on this construction. Notice that different internal maps may define the same QC-CC (the same “supermap”) after being composed; different choices of internal maps can be thought of as defining different “implementations” of a given QC-CC.

We denote by QC-CC the set of process matrices that describe QC-CCs. As shown in [21], this set can be characterised as follows: $W \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{N}}^{IO}F})$ is in QC-CC iff $W \ge 0$, and for all $n = 1, \dots, N$ and all $(k_1, \dots, k_n)$, there exist PSD matrices $W_{(k_1, \dots, k_N, F)} \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{N}}^{IO}F})$ and

$$ W_{(k_1, \dots, k_n)} \in \mathcal{L}(\mathcal{H}^{PA_{\{k_1, \dots, k_{n-1}\}}^{IO} A_{k_n}^{I}}) \text{ such that} \\ \left\{ \begin{array}{l} W = \sum_{(k_1, \dots, k_N)} W_{(k_1, \dots, k_N, F)}, \\ \forall (k_1, \dots, k_N), \text{Tr}_F W_{(k_1, \dots, k_N, F)} = W_{(k_1, \dots, k_N)} \otimes 1^{A_{k_N}^{O}}, \\ \forall n = 1, \dots, N-1, \forall (k_1, \dots, k_n), \\ \sum_{k_{n+1}} \text{Tr}_{A_{k_{n+1}}^I} W_{(k_1, \dots, k_n, k_{n+1})} = W_{(k_1, \dots, k_n)} \otimes 1^{A_{k_n}^{O}}, \\ \sum_{k_1 \in \mathcal{N}} \text{Tr}_{A_{k_1}^I} W_{(k_1)} = 1^P. \end{array} \right. \tag{24} $$

As these are linear and affine constraints on PSD matrices, the existence of such a decomposition for a matrix $W$ can be (for small enough dimensions) efficiently and reliably tested via semidefinite programming (SDP) [29]. Furthermore, given the various matrices $W_{(k_1, \dots, k_N, F)}$ and $W_{(k_1, \dots, k_n)}$ that appear in the decomposition above, one can explicitly reconstruct (in a non-unique manner) the internal operations that, composed together, give the QC-CC. These same two remarks apply to all the classes that will be defined below; see Appendix D and [21] for more details.

Since QC-CCs are processes with a well-defined causal order, they clearly only produce causal correlations in $\mathcal{P}_{\text{causal}}$ through the generalised Born rule of Eq. (22) [21], as we illustrate in Fig. 3. In Appendix E 1 a we provide an explicit proof of this, which uses the definition of causal correlations given in Eq. (3), and uses the fact that each $W_{(k_1, \dots, k_N, F)}$ and $W_{(k_1, \dots, k_n)}$ in the decomposition of Eq. (24) relates to the causal order $\pi = (k_1, \dots, k_N)$ or to the order $(k_1, \dots, k_n)$ of the first $n$ parties, respectively.

The connection between the structure of the control system of a QC-CC, which in general is in the intermediate
<figure><img src="image_4.png" /><figcaption>Figure 3. The upper part of the figure depicts the inclusion relations between the different (sub)classes of QC-CCs considered in this paper. For $N \ge 4$ (and nontrivial input and output spaces for the different parties) the inclusions are strict; for $N \le 3$, QC-NICC reduces to QC-convFO. The arrows directed to the lower part of the figure indicate the kind of causal correlations (defined through the generalised Born rule, Eq. (22)) that process matrices in each class can produce: process matrices in QC-convFO only give correlations in $P_{\text{convFO}}$; those in QC-NICC only give correlations in $P_{\text{NIO}}$; those in QC-CC give causal correlations in $P_{\text{causal}}$.</figcaption></figure>

diate state $\langle(k_1, \dots, k_n)\rangle := |(k_1, \dots, k_n)\rangle\langle(k_1, \dots, k_n)|$, and the definition of causal correlations given in Eq. (3), which involves the corresponding intermediate probability to obtain the order $(k_1, \dots, k_{n+1})$, suggests that one could define subclasses of QC-CC inspired by the classes of correlations introduced above. Indeed, we are going to consider particular QC-CCs by constraining their control systems, first to be fixed from the beginning of the process, analogously to correlations with fixed causal order, and then by requiring their evolution to be unaffected by the choice of the parties' operations, analogously to correlations with non-influenceable causal order.

## 2. The QC-convFO subclass

We thus move on to consider the simplest class of quantum circuits, also called “quantum channels with memory” [30], “quantum strategies” [31] or “quantum combs” [32, 33], for which the causal order between the external operations is fixed. A quantum circuit with fixed causal order can be seen as a particular QC-CC, where the control system is determined from the beginning,

and therefore not dynamical. Furthermore, as in the case of correlations, we consider statistical mixtures of quantum circuits with fixed order as having a static, non-dynamical order.

We thus define QC-CCs with non-dynamical causal order to be those that can be written as convex mixtures of quantum circuits with fixed causal order (QC-convFOs), and we denote by QC-convFO the set of process matrices describing them. Extending in a rather straightforward way the characterisation of quantum channels with memory, quantum strategies or quantum combs [31–33] to convex mixtures thereof, one easily obtains the following process matrix characterisation (see Appendix D 2 b): $W \in \mathcal{L}(\mathcal{H}^{PA_{N}^{IO}F})$ is in QC-convFO iff $W \ge 0$, and for all $(k_1, \dots, k_N)$ and all $n = 1, \dots, N$, there exist PSD matrices $W_{(k_1, \dots, k_N, F)} \in \mathcal{L}(\mathcal{H}^{PA_{N}^{IO}F})$ and $W_{(k_1, \dots, k_n)}^{(k_{n+1}, \dots, k_N)} \in \mathcal{L}(\mathcal{H}^{PA_{\{k_1, \dots, k_{n-1}\}^{I}}^{IO}A_{k_n}^{I}})$ such that

$$ 
\left\{ 
\begin{array}{l}
W = \sum_{(k_1, \dots, k_N)} W_{(k_1, \dots, k_N, F)}, \\
\forall (k_1, \dots, k_N), \text{Tr}_F W_{(k_1, \dots, k_N, F)} = W_{(k_1, \dots, k_N)}^{\emptyset} \otimes 1^{A_{k_N}^{IO}}, \\
\forall n = 1, \dots, N-1, \forall (k_1, \dots, k_n, k_{n+1}, k_{n+2}, \dots, k_N), \\
\text{Tr}_{A_{k_{n+1}}^{I}} W_{(k_1, \dots, k_{n+1})}^{(k_{n+2}, \dots, k_N)} = W_{(k_1, \dots, k_n)}^{(k_{n+1}, \dots, k_N)} \otimes 1^{A_{k_n}^{IO}}, \\
\forall \pi = (k_1, k_2, \dots, k_N), \text{Tr}_{A_{k_1}^{I}} W_{(k_1)}^{(k_2, \dots, k_N)} = q_{\pi} 1^P, \\
q_{\pi} \ge 0, \sum_{\pi} q_{\pi} = 1.
\end{array}
\right. 
\tag{25}
$$

Note that each matrix $W_{(k_1, \dots, k_N, F)}$ and $W_{(k_1, \dots, k_N)}^{(k_{n+1}, \dots, k_N)}$ relates to a specific fixed order $(k_1, \dots, k_n, k_{n+1}, \dots, k_N)$ in the convex mixture. Each $W_{(k_1, \dots, k_n)}^{(k_{n+1}, \dots, k_N)}$ describes the reduced (valid, up to normalisation) process matrix for the first $n$ parties, for that specific order. The notation we use keeps track explicitly of the full order, by displaying those first $n$ parties in the subscript, and the (ordered) list of remaining parties in the superscript.

It can be seen that as soon as $N \ge 2$ with a nontrivial $\mathcal{H}^P$, or as $N \ge 3$ if $\mathcal{H}^P$ is trivial (see Appendix D 2 d), QC-convFO is in general (at least, when the different parties have nontrivial input/output spaces) a strict subclass of QC-CC. Furthermore, as QC-convFOs are convex mixtures of processes compatible with a fixed causal order, it is rather straightforward to see that the correlations they create are convex mixtures of correlations compatible with a fixed causal order, in $P_{\text{convFO}}$. See Fig. 3 for an illustration.

## 3. The QC-NICC subclass

In analogy to the notion of causal correlations with non-influenceable orders introduced in the previous section, we now define quantum circuits with non-influenceable classical control of causal order (QC-NICCs).
Recall that in the case of correlations, we imposed that the probability distribution of the underlying variable $\pi$ describing the causal order should not depend on the choice of the parties' settings, see Eq. (12). Given how, in a QC-CC, the causal order is encoded in the classical control system, then we similarly impose here that the state of the control should not depend on what TP operations the parties implement—nor on the initial state that may be fed into the circuit, as one may consider it to be influenced by some other party in the global past. More formally:

QC-NICCs are the QC-CCs for which at any intermediate time step, the state of the control system is independent of the choice of previously applied external operations and of the potential initial state preparation in the global past.

We denote by QC-NICC the set of process matrices that describe QC-NICCs. We show in Appendix D2c that the above constraint implies the following characterisation: $W \in \mathcal{L}(\mathcal{H}^{PA_N^{\text{OF}}})$ is in QC-NICC if and only if it has a QC-CC decomposition in terms of PSD matrices $W_{(k_1, \dots, k_N, F)}$ and $W_{(k_1, \dots, k_n)}$ as in Eq. (24), with the additional constraint that

$$ \text{all } W_{(k_1, \dots, k_n)} \text{ 's are valid process matrices} \\ \text{(up to normalisation).} \qquad (26) $$

We note that it suffices to impose that all $W_{(k_1, \dots, k_N)}$'s are valid process matrices (up to normalisation), or that all $W_{(k_1, \dots, k_N, F)}$'s are valid process matrices (up to normalisation), to imply (through Eq. (24)) the validity of all $W_{(k_1, \dots, k_n)}$'s. We also emphasise that Eq. (26) does not imply that the $W_{(k_1, \dots, k_n)}$'s must be compatible with the causal order $(k_1, \dots, k_n)$, otherwise QC-NICC would reduce to QC-convFO; see the example below for an illustration.

As we show in Appendix D2d, for $N \le 3$ QC-NICC reduces to QC-convFO. For $N \ge 4$ however, we obtain a new class in between QC-convFO and QC-NICC, as depicted in Fig. 3:

$$ \text{QC-convFO} \subset \text{QC-NICC} \subset \text{QC-CC}. \qquad (27) $$

The situation here is somewhat similar to the case of correlations, where we observed that $P_{\text{NIO}}$ reduces to $P_{\text{convFO}}$ for $N \le 3$, and $P_{\text{NIO}}$ becomes a strictly larger polytope than $P_{\text{convFO}}$ for $N \ge 4$.

As the analogy between correlations with non-influenceable orders and QC-NICC may have suggested, we also find that correlations generated by process matrices in QC-NICC are in $P_{\text{NIO}}$, as illustrated in Fig. 3. See Appendix E1c for the proof.

## 4. Examples

We will now provide examples of process matrices that belong to each of the three classes with classical control

of causal order introduced above.<fnref n="9" /> Before that, let us introduce an important building block that will be used in all our examples: for any two isomorphic spaces $\mathcal{H}^X$ and $\mathcal{H}^Y$ whose computational bases $\{|i\rangle^X\}_i$ and $\{|i\rangle^Y\}_i$ are in one-to-one correspondence, we define the unnormalised maximally entangled state $|1\rangle\rangle^{XY} := \sum_i |i\rangle^X \otimes |i\rangle^Y$, such that $|1\rangle\rangle\langle 1|^{XY}$ is the Choi matrix of an identity channel between the two spaces.

With this,

$$ W_{\text{convFO}} = \frac{1}{2} |\psi\rangle\langle\psi|^{A^I} \otimes |1\rangle\rangle\langle 1|^{A^O B^I} \otimes 1^{B^O} \\ + \frac{1}{2} |\psi\rangle\langle\psi|^{B^I} \otimes |1\rangle\rangle\langle 1|^{B^O A^I} \otimes 1^{A^O}, \qquad (28) $$

where (here and in all our examples below) $|\psi\rangle$ denotes any fixed state received by one of the parties, is clearly an example of a process matrix in QC-convFO (for $N = 2$, with trivial spaces $\mathcal{H}^P, \mathcal{H}^F$). It corresponds indeed to a convex mixture of two identity channels, one from A to B and one from B to A (and with the first party receiving the initial state $|\psi\rangle$).

An example of a process with dynamical but non-influenceable classical control of causal order in QC-NICC \ QC-convFO (for $N = 4$, still with trivial $\mathcal{H}^P, \mathcal{H}^F$) is given by the process matrix

$$ W_{\text{NICC}} = \frac{1}{2} W_{+\alpha} \otimes |\psi\rangle\langle\psi|^{C^I} \otimes |1\rangle\rangle\langle 1|^{C^O D^I} \otimes 1^{D^O} \\ + \frac{1}{2} W_{-\alpha} \otimes |\psi\rangle\langle\psi|^{D^I} \otimes |1\rangle\rangle\langle 1|^{D^O C^I} \otimes 1^{C^O}, \qquad (29) $$

where $W_{\pm\alpha} := \frac{1}{4}(1^{\otimes 4} \pm \alpha(ZZZ1 + Z1XX)) \in \mathcal{L}(\mathcal{H}^{A^I B^I})$, with $\alpha = \frac{1}{\sqrt{2}}$ here, X and Z (together with Y, which will be used later on) being the Pauli matrices, and with implicit tensor products. The matrix $W_{\pm\alpha}$ is a bipartite causally nonseparable process matrix (with qubit input/output systems for both parties), and it was shown in [9] that $W_{+\alpha}$ can produce correlations that violate the LGYNI causal inequality, Eq. (5) (so can $W_{-\alpha}$, with different instruments).

From an explicit decomposition of $W_{\text{NICC}}$ as in Eq. (24), in terms of matrices $W_{(k_1, \dots, k_n)}$ (see Eq. (D33) of Appendix D2e), one can construct internal operations $\hat{M}_n$ which, composed together, give the process matrix $W_{\text{NICC}}$ (as in the general description of QC-CCs above). This allows us to give the circuit-like representation of $W_{\text{NICC}}$ depicted in Fig. 4. This implementation is compatible with the “coarse-grained” causal order $\{A, B\} \prec \{C, D\}$, i.e. with both A and B acting

<footnote n="9">⁹ For each of the three examples below, we provide in Appendix D2e an explicit decomposition, which matches the characterisation of the class that we claim they belong to. On the other hand, our claims that a given process matrix does not belong to a given class, i.e. that it does not admit a given decomposition, can be verified using SDP (for some choice of the arbitrary states $|\psi\rangle$ appearing below, and of the dimension of the unspecified spaces—we typically consider qubits). One may also construct explicit “witnesses” to prove that a process is not in a given class, using the technique of causal witnesses [8, 34].</footnote>
<figure><img src="image_5.png" /><figcaption>Figure 4. A circuit-like representation of $W_{NICC}$. A and B are each initially given half of a maximally entangled pair of qubits in the state $|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|0, 0\rangle + |1, 1\rangle)$. The global output state is then measured by the projective measurement $\{2W_{+\alpha}, 2W_{-\alpha}\}$. A new system initialised in the state $|\psi\rangle$ is then sent to C and subsequently forwarded to D, or sent to D and forwarded to C, with the order depending on the outcome of the previous measurement. The two branches of the circuit containing C and D are exclusive: on each run only one “happens”, so that C and D (like A and B) are each applied once and only once.</figcaption></figure>

before C and before D, without assuming a priori any particular causal relation between respectively A and B, and between C and D.<fnref n="10" /> Here, the parties A and B are both given half of a maximally entangled pair of qubits and can in fact act in parallel. Then, $\{2W_{+\alpha}, 2W_{-\alpha}\}$ defines a projective measurement performed on the output spaces of A and B, along with the auxiliary spaces containing the other halves of the maximally entangled states, whose outcome controls classically the causal order between C and D: $C \prec D$ for outcome +, and $D \prec C$ for outcome -. The probability to obtain + or - is always 1/2 for each measurement outcome, independently of the CPTP maps performed by A and B; hence, the latter cannot influence the causal order between C and D and the process has non-influenceable control of causal order. Yet, the process has dynamical causal order in the sense that the causal order is not and cannot be fixed from the start: A and B have to first perform their operations before the measurement is performed and its outcome controls the causal order between C and D. This is fundamentally related to the fact that $W_{\pm\alpha}$ are causally nonseparable process matrices. Indeed, if we were to define a similar process with $W_{\pm\alpha}$ being causally separable processes, then one would be able to find decompositions of the resulting process matrix of the QC-convFO form of Eq. (25). This is not the case here. Note that while the terms $W_{(A,B,C,(D))}$ and $W_{(A,B,D,(C))}$ appearing in the QC-NICC decomposition of $W_{NICC}$ (e.g., $W_{(A,B,C)} = \frac{1}{2}W_{+\alpha} \otimes |\psi\rangle\langle\psi|^{C'}$; see Eq. (D33) of Appendix D 2e) are valid process matrices

(up to normalisation), these are not compatible with the corresponding orders $(A, B, C, (D))$ and $(A, B, D, (C))$— see our comment below Eq. (26).

Finally, the “classical switch” [19], where a (2-dimensional) state prepared in the past Hilbert space $\mathcal{H}^P$ classically controls the causal order between two parties A and B acting on a target system, is an example of a process with dynamical and influenceable classical control of causal order in QC-CC \ QC-NICC (for $N = 2$, with a trivial $\mathcal{H}^F$). Its process matrix is defined as

$$W_{\text{CS}} = |0\rangle\langle 0|^P \otimes |\psi\rangle\langle\psi|^A \otimes |1\rangle\langle 1|^B \langle 1|^A \otimes |1\rangle\langle 1|^B + |1\rangle\langle 1|^P \otimes |\psi\rangle\langle\psi|^B \otimes |1\rangle\langle 1|^B \langle 1|^B \otimes |1\rangle\langle 1|^A. \quad (30)$$

The first term relates to the order $A \prec B$, while the second term relates to the order $B \prec A$. These two terms individually are not valid process matrices; rather than being in a convex mixture (as were the two terms in $W_{\text{convFO}}$, Eq. (28)), here their contribution is controlled by the state prepared in $\mathcal{H}^P$. The first term indeed contributes when that state is $|0\rangle^P$, while the second term contributes when it is $|1\rangle^P$—hence the influenceability of the control by the initial state preparation in $\mathcal{H}^P$.<fnref n="11" />

### C. Quantum Circuits with Quantum Control of causal order

Let us now turn our attention to the second main class of quantum circuits introduced in Ref. [21]: circuits with quantum, rather than classical, control of causal order. QC-QCs allow for indefinite causal orders; nevertheless, we will see that one can still characterise some form of dynamicality for the quantum control.

#### 1. The general QC-QC class

QC-QCs are built in analogy to QC-CCs, with now a quantum (coherent) control of causal order. As for a QC-CC, the action of a QC-QC (depicted in Fig. 5) can be understood as a protocol that alternatively applies “internal” and “external” operations, the latter corresponding to the quantum operations realised by the different parties $A_k$. Each internal operation $\tilde{V}_n$ produces the system that coherently controls which party $A_{k_n}$ will be the next to apply its external operation, and which keeps track of which previous external operations have already been applied (to ensure that each is applied once and only once). The state of the control system is now of the form

<footnote n="10">¹⁰ As it turns out, $W_{NICC}$ can also be interpreted as a QC-CC compatible with $\{C, D\} \prec \{A, B\}$, however at the cost of losing the non-influenceable property, as it cannot be interpreted as a QC-NICC compatible with $\{C, D\} \prec \{A, B\}$.</footnote>

<footnote n="11">¹¹ By considering $\mathcal{H}^P$ to be the output space of an additional party (that has no input space, see Footnote 8), then one would equivalently say that it is the choice of operation (the state preparation) of that new party that influences the order between A and B.</footnote>
<figure><img src="image_6.png" /><figcaption>Figure 5. Graphical representation of a quantum circuit with quantum control (QC-QC) of causal order (a simplified version of Fig. 10 from Ref. [21], also reproduced with more details as Fig. 10 in Appendix D 3). The QC-QC is defined as the composition of the “internal” operations $\tilde{V}_1, \dots, \tilde{V}_{N+1}$ (in the red shaded area), leaving “open slots” for the parties’ “external” operations $A_k$. The construction is similar to that of QC-CCs (see Fig. 2), except that here the control system (the now single-stroke bottom line) acts in a quantum manner, and can coherently control different causal orders, in a superposition. Furthermore, the state of the control system, in the form $|K_{n-1}, k_n\rangle$, only keeps track of the unordered set $K_{n-1}$ of parties that have already acted, together with the next party $A_{k_n}$ to come. The causal order between the external operations can again be seen as being established on the fly or dynamically, as each internal operation is applied.</figcaption></figure>

$|K_{n-1}, k_n\rangle$, where $K_{n-1}$ describes the set of $n-1$ parties that already applied their external operation, while $k_n$ describes the choice of the next party that applies its external operation. Contrarily to QC-CCs, only the unordered set of past operations is encoded in the control system: for the branch in which the next party to act is chosen to be $A_{k_{n+1}}$, the control state is updated from $|K_{n-1}, k_n\rangle$ to $|K_{n-1} \cup \{k_n\}, k_{n+1}\rangle$, thereby forgetting which was the previous party $A_{k_n}$. This eventually makes it possible for different causal orders corresponding to the same unordered set to interfere, once the information about the causal order is erased. The QC-QC under consideration is then defined as the composition of the internal operations $\tilde{V}_1, \dots, \tilde{V}_{N+1}$ (possibly tracing out some system at the end), leaving “open slots” for the parties’ external operations; see Appendix D 3 a and Ref. [21] for more details on this construction. Again, different internal operations may define the same QC-QC after being composed.

We denote by QC-QC the set of process matrices that describe QC-QCs. As shown in [21], this set admits the following characterisation: $W \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{N}}^{IO}F})$ is in QC-QC iff $W \ge 0$, and for all $n = 1, \dots, N$, for all strict subsets $K_{n-1}$ of $\mathcal{N}$ (with $|K_{n-1}| = n-1$), and all $k_n \in \mathcal{N} \setminus K_{n-1}$, there exist PSD matrices $W_{(K_{n-1}, k_n)} \in \mathcal{L}(\mathcal{H}^{PA_{K_{n-1}}^{IO}A_{k_n}^I})$ such that

$$ \left\{ \begin{array}{l} \mathrm{Tr}_F W = \sum_{k_N \in \mathcal{N}} W_{(\mathcal{N} \setminus \{k_N\}, k_N)} \otimes 1^{A_{k_N}^O}, \\ \forall \emptyset \subset \mathcal{K}_n \subset \mathcal{N}, \quad \sum_{k_{n+1} \in \mathcal{N} \setminus \mathcal{K}_n} \mathrm{Tr}_{A_{k_{n+1}}^I} W_{(\mathcal{K}_n, k_{n+1})} \\ \qquad = \sum_{k_n \in \mathcal{K}_n} W_{(\mathcal{K}_n \setminus \{k_n\}, k_n)} \otimes 1^{A_{k_n}^O}, \\ \sum_{k_1 \in \mathcal{N}} \mathrm{Tr}_{A_{k_1}^I} W_{(\emptyset, k_1)} = 1^P. \end{array} \right. \qquad (31) $$

The QC-QC set contains QC-CC as a generally strict subset (for $N \ge 2$ if $\mathcal{H}^F$ is nontrivial, or for $N \ge 3$

if $\mathcal{H}^F$ is trivial). Beyond this, it also contains circuits with genuinely quantum control of causal order, which may feature indefinite causal order. Despite this, QC-QCs are known to create only causal correlations, in $\mathcal{P}_{\mathrm{causal}}$ [21, 35]; see Fig. 6 for an illustration. We provide in Appendix E 2 a new formulation of this proof that is more directly related to the definition of causal correlations given in Eq. (3), and to an alternative form given in Appendix A 3.

We will now see how to characterise the dynamicality of causal orders within QC-QCs, in analogy with what we did for QC-CCs, by referring to the state of the control system.

## 2. The QC-supFO subclass

One may first wonder what is the most general way to coherently control the causal order within QC-QCs, without any sort of dynamicality. In some sense, one wishes to look for the largest class that generalises the quantum switch with a fixed initial control state, keeping this “static” form.

To define such QC-QCs with non-dynamical orders, we propose a similar construction to that of general QC-QCs, except that we now impose that the total causal order should be encoded in the control system from the very beginning, and that the “weight” of each order should not be affected by the internal operations. More specifically, referring to Fig. 5: we take the basis states of the control system between the internal operations $\tilde{V}_1$ and $\tilde{V}_2$ to be of the form $|\emptyset, k_1; (k_2, \dots, k_N)\rangle$ (instead of just $|\emptyset, k_1\rangle$), each of them coming with a weight that has a fixed value $q_{\pi=(k_1, k_2, \dots, k_N)}$ (which does not depend, in particular, on the initial state fed into the circuit in the global past space $\mathcal{H}^P$). Subsequent internal operations then update the control system from
<figure><img src="image_7.png" /><figcaption>Figure 6. The upper part of the figure depicts the inclusion relations between the different subclasses of QC-QCs considered in this paper (including the subclasses of QC-CCs, already presented in Fig. 3). For $N \ge 4$ (and nontrivial input and output spaces for the different parties) the inclusions between QC-supFO, QC-NIQC and QC-QC are strict; for $N \le 3$, QC-NIQC reduces to QC-supFO. It remains an open question whether the intersections with question marks are empty or not.</figcaption></figure>

The arrows directed to the lower part of the figure indicate the kind of causal correlations that process matrices in each (sub)class of QC-QCs can produce: process matrices in QC-supFO only give correlations in $P_{\text{convFO}}$; those in QC-NIQC only give correlations in $P_{\text{NIO}'}$; those in QC-QC give causal correlations in $P_{\text{causal}}$.

states of the form $|K_{n-1}, k_n; (k_{n+1}, \dots, k_N)\rangle$ to states of the form $|K_{n-1} \cup \{k_n\}, k_{n+1}; (k_{n+2}, \dots, k_N)\rangle$ (instead of $|K_{n-1}, k_n\rangle$ to $|K_{n-1} \cup \{k_n\}, k_{n+1}\rangle$). We keep here the feature that the “past” order is erased: the control system only keeps track of the unordered set of past parties. On the other hand, the order of remaining parties is left unchanged, and we impose that the internal operations cannot change it, nor can they change the weight of each of the “future” orders $(k_{n+2}, \dots, k_N)$: see Appendix D 3 b for more details on this construction.

We call circuits that abide by this description quan-

tum circuits with superposition of fixed causal orders (QC-supFO), and we denote by QC-supFO the set of process matrices that describe them. As we show in Appendix D 3 b, one obtains the following characterisation: $W \in \mathcal{L}(\mathcal{H}^{PA_{N}^{IO}F})$ is in QC-supFO iff $W \ge 0$, and for all $n = 1, \dots, N$, all $K_{n-1} \subsetneq \mathcal{N}$ and all $(k_n, k_{n+1}, \dots, k_N) \notin K_{n-1}$, there exist PSD matrices $W_{(K_{n-1}, k_n)}^{(k_{n+1}, \dots, k_N)} \in \mathcal{L}(\mathcal{H}^{PA_{K_{n-1}}^{IO}A_{k_n}^I})$ such that

$$ \left\{ \begin{array}{l} \text{Tr}_F W = \sum_{k_N \in \mathcal{N}} W_{(\mathcal{N}\setminus\{k_N\}, k_N)}^{\emptyset} \otimes 1^{A_{k_N}^O}, \\ \forall \emptyset \subsetneq \mathcal{K}_n \subsetneq \mathcal{N}, \forall (k_{n+1}, \dots, k_N) \in \mathcal{N}\setminus\mathcal{K}_n, \\ \text{Tr}_{A_{k_{n+1}}^I} W_{(\mathcal{K}_n, k_{n+1})}^{(k_{n+2}, \dots, k_N)} = \sum_{k_n \in \mathcal{K}_n} W_{(\mathcal{K}_n\setminus\{k_n\}, k_n)}^{(k_{n+1}, \dots, k_N)} \otimes 1^{A_{k_n}^O}, \\ \forall \pi = (k_1, \dots, k_N) \in \mathcal{N}, \text{Tr}_{A_{k_1}^I} W_{(\emptyset, k_1)}^{(k_2, \dots, k_N)} = q_{\pi} \otimes 1^P, \\ q_{\pi} \ge 0, \quad \sum_{\pi} q_{\pi} = 1. \end{array} \right. \qquad (32) $$

This QC-supFO class is the quantum-controlled analogue of the classically and non-dynamically-controlled QC-convFO, in the same way as QC-QCs are the quantum-controlled analogue of QC-CCs. The characterisations and the notations we use reflect this: Eq. (32) above involves matrices $W_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_N)}$, while the characterisation of QC-convFO in Eq. (25) involved matrices $W_{(k_1, \dots, k_n)}^{(k_{n+1}, \dots, k_N)}$; in both cases, the subscripts include the first $n$ parties of a given order (forgetting about the order of the first $n-1$ parties, in the QC-QC or QC-supFO case), while the superscript (not present in the general QC-CC and QC-QC decompositions) display the ordered list of remaining parties. We note also that just like the $W_{(k_1, \dots, k_n)}^{(k_{n+1}, \dots, k_N)}$'s, the matrices $W_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_N)}$ here can be seen to be valid process matrices (up to normalisation). Comparing the two classes, one has QC-convFO $\subset$ QC-supFO, the inclusion being strict (in general) for $N \ge 2$ if $\mathcal{H}^F$ is nontrivial, or for $N \ge 3$ if $\mathcal{H}^F$ is trivial.

It is interesting to observe, also, that the characterisation of QC-supFOs above displays some form of symmetry with that of general QC-CCs, Eq. (24): for QC-CCs the total causal order is not encoded in the decomposition at the “lower levels” (for small $n$), but it appears in the matrices involved in the decomposition as we go “up” (to larger $n$) in the decomposition. For QC-supFOs it is the opposite: the causal order is encoded in the decomposition at the lower levels, but gets erased as we go up in the decomposition. This symmetry can also be seen in the equations: the sums appear on the left-hand side of the constraints in Eq. (24), and on the right-hand side of the constraints in Eq. (32) (notice that for QC-QCs they appear on both sides). In Appendix D 4 we propose a graphical representation of the SDP constraints for our different classes, which allows one, in particular, to clearly visualise the symmetry between the decompositions of QC-CCs and of QC-supFOs.

Comparing it to the full set of QC-QCs, it can
clearly be seen that QC-supFO is a subclass of QC-QC: QC-supFO ⊂ QC-QC, the inclusion being in general strict for $N \ge 2$ with a nontrivial $\mathcal{H}^P$, or for $N \ge 3$ with a trivial $\mathcal{H}^P$ (see Appendix D 3 d; the situation is thus similar to that of QC-convFO vs QC-CC). It contains on the other hand the subclass of QC-convFOs: QC-convFO ⊂ QC-supFO, the inclusion being in general strict for $N \ge 2$ with a nontrivial $\mathcal{H}^F$, or for $N \ge 3$ with a trivial $\mathcal{H}^F$ (see also Appendix D 3 d; here the situation is similar to that of QC-CC vs QC-QC). Furthermore, building on the proof that QC-QCs produce causal correlations, we show in Appendix E 2 b that QC-supFOs produce correlations in $\mathcal{P}_{\text{convFO}}$, which is consistent with the claim that these processes feature no dynamical causal order; see Fig. 6.

The definition and characterisation of QC-supFOs allows us to now properly formalise the claim that some processes can have both indefinite and dynamical causal order. Indeed, this can be said of any QC-QC that is not a QC-CC,<fnref n="12" /> but also not a QC-supFO—i.e., whose process matrix is in QC-QC \ (QC-CC ∪ QC-supFO). Explicit examples will be given below.

To finish with the presentation of QC-supFOs, let us mention that another somewhat related class was introduced in Ref. [36] (just called Sup there), which may have also looked like a natural candidate to characterise processes with non-dynamical superpositions of causal orders. The idea was to impose that if one traces out the global future system in $\mathcal{H}^F$, the reduced circuit should end up in just a convex mixture of fixed-order processes (in QC-convFO)—as is indeed the case for the “static” quantum switch. However, we argue that such a constraint is too restrictive. It also has some undesirable features, e.g. that if several parties have no output Hilbert space and could be considered to be in the global future, then the definition crucially depends on whose Hilbert space is called $\mathcal{H}^F$. We discuss this in more details in Appendix D 3 b. In fact, we show that by generalising the Sup class in an adequate way, so as precisely to avoid the unwanted features, one naturally obtains the same characterisation as in Eq. (32). This alternative perspective lends further support to the claim that our QC-supFO class appropriately characterises quantum circuits with non-dynamical quantum control of causal order.

### 3. The QC-NIQC subclass

Let us finally introduce one last class: the quantum-controlled counterpart of QC-NICCs, namely quantum

circuits with non-influenceable quantum control of causal order (QC-NIQCs).

Recall that for QC-NICCs, although the (classical) state of the control could be dynamical (if it cannot be fixed in advance), we imposed that it should not depend on the choice of parties' TP operations (it must be non-influenceable). One may be tempted to impose the same condition, now for the quantum control system. However, this would not quite correspond to what we want. To see this, consider the “static” quantum switch, where a control qubit, initialised in the fixed state $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$, coherently controls the order between two operations applied on a target system [19] (see also Eq. (35) below for its process matrix description). This example is clearly a QC-supFO, so we do not want to say that its quantum control features any form of dynamicality. However, the reduced state of the control system does depend on the two external operations: e.g. the output state of the control qubit is $|+\rangle$ if (the Kraus operators of) the two external operations commute, or $|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ if these anti-commute—this is in fact at the very heart of the best-known application of the quantum switch [4]. What does not depend on the external operations in this example are the classical weights corresponding to each fixed order in the quantum-controlled superposition of orders—that is, the diagonal elements of the state of the control system, when written in the basis that defines the controllisation (the $\{|0\rangle, |1\rangle\}$ basis here).

This is precisely what we shall impose here to define QC-NIQCs, extending it to the general form of the control system as defined in QC-QCs:

> QC-NIQCs are the QC-QCs for which at any intermediate time step, the classical weights of each term in the basis $\{|K_{n-1}, k_n\rangle^{C_n}\}_{K_{n-1}, k_n}$ that defines the controllisation—i.e. the diagonal elements of the state of the control system in that basis—are independent of the choice of previously applied external operations and of the potential initial state preparation in the global past.

We denote by QC-NIQC the set of process matrices that describe QC-NIQCs. We show in Appendix D 3 c that the above constraint implies the following characterisation: $W \in \mathcal{L}(\mathcal{H}^{PA^{\text{I}}F})$ is in QC-NIQC if and only if $W \ge 0$ and it has a QC-QC decomposition in terms of PSD matrices $W_{(\mathcal{K}_{n-1}, k_n)}$ as in Eq. (31), with the additional constraint that

$$ \text{all } W_{(\mathcal{K}_{n-1}, k_n)}\text{'s are valid process matrices} \tag{33} \\ \text{(up to normalisation).} $$

This additional constraint is thus quite analogous to the one we obtained for QC-NICCs, Eq. (26). Note however that, contrary to QC-NICCs, it is not sufficient here to verify the validity for only the “highest” terms $W_{(\mathcal{K}_{N-1}, k_N)}$ to ensure that Eq. (33) is satisfied.

We show in Appendix D 3 d that for $N \le 3$, QC-NIQC coincides with QC-supFO, but for $N \ge 4$ it defines a

<footnote n="12">¹² We recall that it remains an open question, whether for $N \ge 4$, all causally separable processes are QC-CCs [18, 21]. Here we overlook this subtlety for the case of quantum circuits, and consider all those that are not QC-CCs to have indefinite causal order.</footnote>
class in between QC-supFO and QC-NIQC, as depicted in Fig. 6:

$$QC-supFO \subset QC-NIQC \subset QC-QC. \quad (34)$$

It can also easily be seen that QC-NICC ⊂ QC-NIQC (the inclusion being again generally strict for $N \ge 2$ if $\mathcal{H}^F$ is nontrivial, or for $N \ge 3$ if $\mathcal{H}^F$ is trivial, as in the previous cases of QC-CC vs QC-QC, and of QC-convFO vs QC-supFO).

Considering now the correlations generated by QC-NIQCs, one can show (see Appendix E 2 c) that these are necessarily in the polytope $\mathcal{P}_{\text{NIO}}'$ of causal correlations with “non-influenceable coarse-grained order”, which we pre-emptively introduced in Sec. II C. This can be understood by recalling that the control state in a QC-QC only encodes, at any given time step, the “coarse-grained” order ($\mathcal{K}_{n-1}, k_n$) (with $\mathcal{K}_{n-1}$ containing all “past” parties, grouped together). When imposing the non-influenceability of (the diagonal elements of) the control state, it is then natural to expect that the distribution of $p((\mathcal{K}_{n-1}, k_n)|\vec{x})$ obtained from a causal decomposition of some induced correlation would not depend on the choice of external operations.

One may then wonder whether the stronger statement holds, that the non-coarse-grained probabilities $p((k_1, \dots, k_n)|\vec{x})$ also do not depend on the external operations, i.e. that the correlations created by QC-NIQCs are in the smaller polytope $\mathcal{P}_{\text{NIO}}$. We leave this as an open question: we could not show this in general, but neither did we find any QC-NIQC correlation in $\mathcal{P}_{\text{NIO}}' \setminus \mathcal{P}_{\text{NIO}}$ (see Sec. IV).

## 4. Examples

We now provide examples of process matrices that belong to each of the three classes with quantum control of causal order introduced above.<fnref n="13" />

First, the quantum switch with a fixed initial state of the control system [19]—the “static”, or “non-dynamical” quantum switch (already referred to at the beginning of Sec. III C 3)—is an example of a process in QC-supFO \ QC-convFO for $N = 2$ parties (with a trivial global past space $\mathcal{H}^P$ but a nontrivial future space $\mathcal{H}^F$). Considering that the future Hilbert space $\mathcal{H}^F = \mathcal{H}^{F_t} \otimes \mathcal{H}^{F_c}$ receives the target (in $\mathcal{H}^{F_t}$) and control (in $\mathcal{H}^{F_c}$) systems, its

process matrix is defined as

$$ 
\begin{gathered}
W_{\text{supFO}} = |w_{\text{supFO}}\rangle\langle w_{\text{supFO}}| \quad \text{with} \\
|w_{\text{supFO}}\rangle = \frac{1}{\sqrt{2}}|\psi\rangle^{A^I} \otimes |1\rangle^{A^O B^I} \otimes |1\rangle^{B^O F_t} \otimes |0\rangle^{F_c} \\
+ \frac{1}{\sqrt{2}}|\psi\rangle^{B^I} \otimes |1\rangle^{B^O A^I} \otimes |1\rangle^{A^O F_t} \otimes |1\rangle^{F_c}.
\end{gathered}
\quad (35) $$

This process corresponds to a coherent superposition of two branches where $A \prec B$ or $B \prec A$, with the target system being sent in each branch to the first party and forwarded through identity channels to the second party and then to $\mathcal{H}^{F_t}$, and with a control qubit initially in the fixed state $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ and finally sent to $\mathcal{H}^{F_c}$.

Our second example here is of a process with dynamical but non-influenceable quantum control of causal order, i.e. in QC-NIQC \ (QC-supFO ∪ QC-NICC), for the $N = 4$ case with trivial spaces $\mathcal{H}^P, \mathcal{H}^F$. Let us first define the ket vectors

$$ 
\begin{aligned}
|\Phi_{00}\rangle &= \frac{1}{\sqrt{2}}(|0, 0\rangle + |1, 1\rangle), & |\Phi_{11}\rangle &= \frac{1}{\sqrt{2}}(|0, 0\rangle - |1, 1\rangle), \\
|\Phi_{01}\rangle &= \frac{1}{\sqrt{2}}(|0, 0\rangle + i|1, 1\rangle), & |\Phi_{10}\rangle &= \frac{1}{\sqrt{2}}(|0, 0\rangle - i|1, 1\rangle),
\end{aligned}
\quad (36) $$

and the matrices

$$ 
\begin{aligned}
W_0 &= \sum_{a,b} |\Phi_{ab}\rangle\langle\Phi_{ab}|^{A^I B^I} \otimes |a, b\rangle\langle a, b|^{A^O B^O}, \\
W_1 &= \sum_{a,b} |\Phi_{ba}\rangle\langle\Phi_{ba}|^{A^I B^I} \otimes |a, b\rangle\langle a, b|^{A^O B^O},
\end{aligned}
\quad (37) $$

which can both be shown to be bipartite causally nonseparable process matrices in $\mathcal{L}(\mathcal{H}^{A^I B^I})$. We then define $W_{\text{NIQC}}$ as:

$$ W_{\text{NIQC}} = \frac{1}{2}W_0 \otimes |\psi\rangle\langle\psi|^{C^I} \otimes |1\rangle\langle 1|^{C^O D^I} \otimes |1\rangle^{D^O} \\ + \frac{1}{2}W_1 \otimes |\psi\rangle\langle\psi|^{D^I} \otimes |1\rangle\langle 1|^{D^O C^I} \otimes |1\rangle^{C^O}. \quad (38) $$

As for any QC-QC, one can find an implementation of this process by constructing internal operations from its QC-QC decomposition, through a procedure detailed in Appendix D 3 c [21]. The process matrix $W_{\text{NIQC}}$ has a similar structure to $W_{\text{NICC}}$, and one can also find an implementation compatible with the coarse-grained causal order $\{A, B\} \prec \{C, D\}$, which is graphically represented in Fig. 7. However, in contrast to $W_{\text{NICC}}$, the order between A and B is now coherently controlled using a control qubit initialised in the state $|+\rangle$. Then, $\{E_+, E_-\}$, with $E_\pm = \frac{1}{2}[1^{\otimes 3} \pm \frac{1}{2}(XX + YY)Y]$ and implicit tensor products, defines a POVM (no longer a projective measurement) performed on the output spaces of A and B, along with the auxiliary and control spaces, whose outcome controls classically the causal order between C and D ($C \prec D$ for outcome + and $D \prec C$ for outcome −). One can explain why $W_{\text{NIQC}}$ has dynamical but non-influenceable causal order with the same reasoning as for

<footnote n="13">¹³ For each of the three examples detailed below, we provide in Appendix D 3 e an explicit decomposition, which matches the characterisation of the corresponding class. Again, our claims that a given process matrix does not belong to a given class can be verified through SDP (see Footnote 9).</footnote>
<figure><img src="image_8.png" /><figcaption>Figure 7. Circuit-like representation of $W_{\text{NIQC}}$. The causal order between A and B is coherently controlled (illustrated by the overlap between gates A and B) by a control qubit prepared in the state $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$. The first party to act (be it A or B) is given half of the state $|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|0, 0\rangle + |1, 1\rangle)$. An internal unitary, composed of a Swap and a Controlled-Z gate, is applied between the first and the second operations in both branches of the causal superposition between A and B. The output state coming from the output Hilbert space of the second operation, the auxiliary space and the control Hilbert spaces are then measured by the POVM defined by $\{E_+, E_-\}$ (see main text). As in the implementation of $W_{\text{NICC}}$ shown on Fig. 4, a new system in the state $|\psi\rangle$ is then, according to the measurement result, either sent to C then forwarded to D, or sent to D then forwarded to C—the two corresponding branches of the circuit being exclusive.</figcaption></figure>

$W_{\text{NICC}}$: dynamicality relates to the fact that $W_{0/1}$ are causally nonseparable, while non-influenceability is due to the fact that the probabilities for the outcomes ± of the POVM $\{E_+, E_-\}$ are independent of the operations performed by A and B (these probabilities are $\frac{1}{2}$ for both outcomes). The only different qualitative feature between these two processes is the coherent control of causal order between A and B in $W_{\text{NIQC}}$. This raises questions concerning other potential features that would differentiate QC-NICC from QC-NIQC; we will comment on this in the outlook below.

Next, the “dynamical quantum switch” (as opposed to the static one), where the qubit that coherently controls the causal order between two parties A and B is not fixed a priori, but is left to be prepared (in any possible state) in the past Hilbert space $\mathcal{H}^P$, is an example of a process with influenceable quantum control of causal order in QC-QC \ (QC-NIQC ∪ QC-CC) (for $N = 2$, with now both $\mathcal{H}^P$ and $\mathcal{H}^F$ being nontrivial). Considering again that the target and control systems are ultimately sent to the future Hilbert space $\mathcal{H}^F = \mathcal{H}^{F_t} \otimes \mathcal{H}^{F_c}$, its process matrix is defined here as

$$ W_{\text{QS}} = |w_{\text{QS}}\rangle\langle w_{\text{QS}}| \text{ with} \\ |w_{\text{QS}}\rangle = |0\rangle^P \otimes |\psi\rangle^{A^I} \otimes |1\rangle^{A^O B^I} \otimes |1\rangle^{B^O F_t} \otimes |0\rangle^{F_c} \\ + |1\rangle^P \otimes |\psi\rangle^{B^I} \otimes |1\rangle^{B^O A^I} \otimes |1\rangle^{A^O F_t} \otimes |1\rangle^{F_c}. \qquad (39) $$

Compared to $|w_{\text{supFO}}\rangle$ in Eq. (35), here the past is “open”, so that the input state of the control system in $\mathcal{H}^P$ can influence the weight of the two branches, corresponding to $A \prec B$ and $B \prec A$.

The other new explicit example of a QC-QC presented in [21] (dubbed the “Grenoble process” in Ref. [37]) is also an example of a process in QC-QC \ (QC-NIQC ∪ QC-CC), for $N = 3$. The “double quantum switch” from Ref. [38] is yet another example in the same class, now for $N = 4$. This process is obtained by composing two quantum switches, where the control qubit of the first quantum switch (between A and B, controlled in the $\{|0\rangle, |1\rangle\}$ basis) is transmitted in order to control the second quantum switch (between C and D), in the complementary $\{|+\rangle, |-\rangle\}$ basis. Since the projection onto the $\{|\pm\rangle\}$ basis of the control qubit after the first quantum switch depends on the operations performed by A and B (e.g., it is $|+\rangle$ if those operations commute, or $|-\rangle$ if they anti-commute, as already discussed [4]), then A and B can indeed influence the causal order between C and D.

## IV. CORRELATIONS WITH DYNAMICAL CAUSAL ORDER FROM QUANTUM CIRCUITS

We have already clarified, for each class of quantum circuits introduced in the previous section, the type of correlations they may generate—i.e., in which of the polytopes introduced in Sec. II their correlations can be found (see Figs. 3 and 6). One may now wonder whether the circuits from a given class can reach all correlations in the corresponding polytopes (and if not, whether some further restrictions can be evidenced) and whether one can exhibit correlations that are outside of a smaller polytope. This can be done, in particular, by considering the quantity $I_4$ from Eq. (14)—which we introduced precisely to separate our four polytopes of correlations—and by looking at the maximal value that processes in a given class, with appropriate quantum instruments for the different parties, can reach.

As one may have expected, it can be shown that any correlation in $P_{\text{convFO}}$ can be obtained from a quantum (and even a classical) circuit in QC-convFO—hence also from circuits in larger classes, in particular in QC-supFO—and that any correlation in $P_{\text{causal}}$ can be obtained from a quantum (and even a classical) circuit in QC-CC—hence also from circuits in QC-QC; see Appendix E 3. Thus, quantum circuits in QC-convFO and QC-supFO (which both only generate correlations in $P_{\text{convFO}}$) saturate the convFO bound of $I_4 \le_{\text{convFO}} \frac{15}{16}$; while quantum circuits in QC-CC and QC-QC can reach the trivial upper bound of $I_4 \le_{\text{causal}} 1$, thereby violating the bounds of Eqs. (15)–(17) for $P_{\text{convFO}}$, $P_{\text{NIO}}$ and $P_{\text{NIO}'}$. In Appendix E 3 we present explicit process matrices, together with choices of instruments, that can be used to reach these different bounds.

The situation is more subtle for the circuits with non-influenceable classical or quantum control of causal order. Recall that we showed that circuits in QC-NICC and QC-NIQC only generate correlations in $P_{\text{NIO}}$ and $P_{\text{NIO}'}$, respectively. It is however less clear a priori whether the whole polytopes can be obtained. Indeed while the
<figure><img src="image_9.png" /></figure>

Figure 8. Different bounds on the quantity $I_4$ defined in Eq. (14), attainable by circuits in the different classes under considerations. QC-convFOs and QC-supFOs can only generate correlations in $\mathcal{P}_{\text{convFO}}$ and saturate the corresponding bound $I_4 \le_{\text{convFO}} \frac{15}{16}$ from Eq. (15). Similarly, general QC-CCs and QC-QCs can only generate correlations in $\mathcal{P}_{\text{causal}}$ and saturate the corresponding (trivial) bound $I_4 \le_{\text{causal}} 1$ from Eq. (18). On the other hand, the largest values we found for QC-NICCs and QC-NIQCs—obtained numerically with a see-saw algorithm—do not reach the corresponding bounds for $\mathcal{P}_{\text{NIO}}$ and $\mathcal{P}_{\text{NIO}'}$, $I_4 \le_{\text{NIO}} \frac{31}{32}$ and $I_4 \le_{\text{NIO}'} \frac{47}{48}$ from Eqs. (16)–(17).

correlation with non-influenceable order that reaches the bound $I_4 \le_{\text{NIO}} \frac{31}{32}$ (Eq. (C20) in Appendix C 2), for instance, can be obtained by a QC-CC and appropriate instruments, that QC-CC is not a QC-NICC: other choices of instruments give correlations with influenceable order (see again Appendix E 3).

To investigate this question further, we tried to optimise numerically the value of $I_4$ over the classes QC-NICC and QC-NIQC using a see-saw approach [9, 39]—i.e., iteratively optimising (via SDP) over the class of quantum circuits in question and the instruments of the parties, one at a time. The highest value of $I_4$ we found was 0.9455 for QC-NICC and 0.9534 for QC-NIQC.<fnref n="14" /> Both of these values violate the convFO bound $I_4 \le_{\text{convFO}} \frac{15}{16} = 0.9375$. However, they are far from saturating the NIO and NIO' bounds $I_4 \le_{\text{NIO}} \frac{31}{32} = 0.96875$ and $I_4 \le_{\text{NIO}'} \frac{47}{48} \approx 0.9792$; see Fig. 8. Although the see-saw approach only gives lower bounds on the possible values attainable for QC-NICC and QC-NIQC, it thus seems plausible that these classes cannot cover the whole polytopes $\mathcal{P}_{\text{NIO}}$ and $\mathcal{P}_{\text{NIO}}'$. Understanding how exactly these correlations are further restricted remains an open problem.

A related question is whether QC-NIQCs can give correlations outside of $\mathcal{P}_{\text{NIO}}$, or if for some reason their correlations are also constrained to be in that polytope. Despite the fact that we did not find any violation of the NIO bound on $I_4$ with a QC-NIQC, this question remains open.

First, as already noted, the see-saw approach does not necessarily find a global maximum, and it could be in principle that a larger value of $I_4$ can be obtained with a QC-NIQC. It could also be that the violation of an NIO bound can only be witnessed by a different quantity

than $I_4$. Since we were unable to characterise the polytope $\mathcal{P}_{\text{NIO}}$ in terms of its vertices or facets due to its high-dimensionality (even in the simplest nontrivial scenario), we have no easy method to obtain other inequalities that bound these correlations, and hence study their potential violation. Finally, numerically we only looked for violations using processes where the quantum systems exchanged between the parties are qubits (i.e., the dimension of input and output Hilbert spaces for each party is 2). It could be that larger violations can be obtained with higher-dimensional systems, potentially violating the NIO bound using QC-NIQCs. In this respect, one may also wonder whether the techniques of [40] could be adapted to obtain upper bounds on the possible violation of the inequalities we considered. We leave the exploration of these various directions for future work.

Adopting a complementary perspective, one may also wonder whether one could define any other subclass of QC-NIQC, larger than QC-NICC, for which one can prove that the correlations produced are in $\mathcal{P}_{\text{NIO}}$. We formally define such a class in Appendix E 2 d, even if its definition is somewhat ad hoc and lacking—for now, at least—a clear physical motivation.

Finally, we considered whether our explicit examples of circuits with dynamical but non-influenceable control of causal order, $W_{\text{NICC}} \in \text{QC-NICC} \setminus \text{QC-convFO}$ and $W_{\text{NIQC}} \in \text{QC-NIQC} \setminus (\text{QC-supFO} \cup \text{QC-NICC})$ from Eqs. (29) and (38), could provide violations of some inequality for non-dynamical causal orders. Although we did not find violations of Eq. (15), we were able to find another inequality that bounds $\mathcal{P}_{\text{convFO}}$ and can be violated by $W_{\text{NICC}}$. We did not find such a violation with $W_{\text{NIQC}}$, but we found another similar process in QC-NIQC $\setminus (\text{QC-supFO} \cup \text{QC-NICC})$ that also provides an analytical violation of the same inequality as for $W_{\text{NICC}}$; see Appendix E 4.

V. OUTLOOK

As soon as $N \ge 3$ parties establish correlations in a well-defined causal structure, there may be some dynamical causal order, which cannot be explained in terms of a (probabilistic) fixed causal order between the parties. Previously, all the examples of causal structures with dynamical causal order have been understood as the influence of past parties on the causal order of future parties. In this work, we have critically reassessed this assertion and shown it to be incomplete. We identified a new way for the causal order to be dynamical without any influence of the past parties on the causal order of the future parties, and which arises as soon as $N \ge 4$. We termed this dynamical but non-influenceable causal order, and we showed that the set of causal correlations with non-influenceable order forms a subpolytope $\mathcal{P}_{\text{NIO}}$ of the causal polytope $\mathcal{P}_{\text{causal}}$, that reduces to the convex mixture of fixed orders polytope $\mathcal{P}_{\text{convFO}}$ for $N \le 3$. Yet, for $N \ge 4$, $\mathcal{P}_{\text{NIO}}$ is strictly larger than $\mathcal{P}_{\text{convFO}}$, and

<footnote n="14">¹⁴ As none of the corresponding process matrices and quantum instruments thus obtained could be easily interpreted, we do not present them explicitly here.</footnote>
there exist causal correlations with dynamical but non-influenceable order. We also proposed a relaxed form of non-influenceable causal order, namely causal correlations with non-influenceable coarse-grained orders.

We then built on the formalism of quantum circuits with classical and quantum control of causal order [21] to define various classes of processes inspired by the different classes of causal correlations presented. We are thus able to clearly distinguish between the classes of quantum circuits with non-dynamical, dynamical but non-influenceable and dynamical and influenceable classical control of causal order (QC-convFO, QC-NICC and QC-CC), and analogously in the case of quantum circuits with quantum control of causal order (with the classes QC-supFO, QC-NIQC and QC-QC respectively). We summarise the inclusion relations between these classes as follows (see also Fig. 6):

$$ \begin{array}{c} \text{QC-convFO} \subset \text{QC-NICC} \subset \text{QC-CC} \\ \cap \quad \cap \quad \cap . \quad (40) \\ \text{QC-supFO} \subset \text{QC-NIQC} \subset \text{QC-QC} \end{array} $$

In general, for $N \ge 4$, the inclusions are all strict, while for $N \le 3$, QC-NICC coincides with QC-convFO and QC-NIQC coincides with QC-supFO. From the inclusion relations defined in Eq. (40), one may wonder whether there remain nontrivial and interesting intersections between the classes, as denoted by the question marks in Fig. 6, or whether it is the case that (some of) these intersections are empty, so that QC-supFO $\cap$ QC-NICC = QC-convFO, QC-supFO $\cap$ QC-CC = QC-convFO, and/or that QC-NIQC $\cap$ QC-CC = QC-NICC? We leave these as open questions.

All the classes of quantum circuits considered in this work were characterised in terms of SDP constraints on positive semidefinite matrices. We propose in Appendix D4 a graphical representation of these constraints which highlights the structural differences between the considered classes. Considering new graphical structures could inspire the definition of new classes of circuits. It would also be interesting to explore the connection between this graphical representation with other graphical understandings of the causal structure that underlies process matrices. One can for instance find similar structures in the graph that represents the SDP constraints for the QC-QC class (see Fig. 13 in Appendix D4) as in the so-called “branch graph” [37] that one can build from a possible generic routed quantum circuit representation of QC-QCs [41]. We leave all this for future work.

We exhibited in particular two examples of quantum circuits with dynamical but non-influenceable classical or quantum control of causal order, characterised by their process matrices $W_{NICC}$ and $W_{NIQC}$ (Eqs. (29) and (38)). Admittedly, for these two examples the dynamical behaviour has a strong classical flavour: a measurement is performed after the action of A and B, whose classical outcome controls the order between C and D. One may wonder whether there exist other examples of quantum circuits with non-influenceable causal order, where

the dynamical behaviour has a “more quantum” flavour. How this question could be formalised, and whether a scenario with more parties involved would be required— so that for instance a quantum system that coherently controls the causal order between C and D is sent to a future party—is left for further work.

A corollary of the existence of dynamical but non-influenceable causal structures is that the two notions of dynamicality and influenceability are in general (for $N \ge 4$) inequivalent, both at the level of causal correlations and of quantum circuits with classical or quantum control of causal order. An interesting follow-up question would be to clarify under which conditions dynamicality and influenceability are found to be equivalent notions. For example, one may wonder whether dynamicality without influenceability may still be found in “pure” QC-QCs [27], that is, QC-QCs that transform unitary maps into a unitary map from a global past Hilbert space to a global future Hilbert space. Indeed, we note that the property of dynamicality without influenceability of the processes $W_{NICC}$ and $W_{NIQC}$ presented above crucially relies on the maximally entangled pair of qubits initially prepared. If one purifies these processes (in the sense of [27]), the system initially prepared will then depend on the action of the global past, in turn allowing the parties’ actions to—in general—influence the causal order. Along this line, an alternative path worth exploring further is to study whether the possibility of causal structures with dynamical but non-influenceable causal order can be understood as some sort of fine-tuning that prevents the parties from influencing the causal order at the statistical level, even if such an influence is in principle possible at the level of the underlying causal structure.

More generally, this work also opens several follow-up questions to better understand causal structures between N parties. One first idea could be to refine the analysis performed in this work in order to define “partially dynamical” causal structures, so that one has a clear understanding of which parties contribute to the dynamical behaviour of a process and which do not, allowing one to quantify some notion of “depth” of dynamicality. Another interesting perspective is to look whether any fundamentally new feature could occur if one studies scenarios with $N \ge 5$ parties, in the same way that the tripartite scenario gives rise to dynamical properties, and the fourpartite scenario gives rise to dynamical but non-influenceable causal order.

An important question that remains open is whether one could formalise a notion of dynamical causal order beyond the class of QC-QCs, as there are processes—such as the Lugano (or “AF/BW”) process [7, 11]—which cannot be expressed as a QC-QC and whose dynamicality remains ambiguous. This would be rather challenging as the formalisation of the notion of dynamical causal order presented in this present work crucially relies on the notion of a quantum control system that dictates the causal order between the parties. Yet, no clear physical interpretation of process matrices that go beyond QC-
QC has been proposed so far, which makes it unclear what the notion of dynamical causal order could mean in general. Nevertheless, a potential track to tackle this problem could be to consider the framework of routed quantum circuits [37, 42], that can model process matrices beyond QC-QCs, and in which a graphical criterion to detect the dynamical causal order in the “Grenoble process” was hinted at, in terms of “bifurcation choices” of the parties [37]. One could first try to see whether this graphical criterion captures the same notion of dynamical causal order for QC-QCs as ours (or perhaps of influenceable order) and then generalise it to processes beyond QC-QCs.

From a more practical point of view, the study of indefinite causal order has aroused some particular interest for the potential information processing advantages that they offer (see [6] for an extensive review of these). Whether dynamical causal order, both classically or coherently controlled, can provide such kind of advantages thus arises as a natural question. A positive answer to this question for classically controlled dynamical causal order was recently obtained in Ref. [43]. The authors showcased an advantage of QC-CCs over QC-convFOs in a tripartite task, where the goal is to simulate the quantum switch with two queries to A's operation and one to B's operation. However, as the notion of coherent control of non-dynamical causal order was not yet formalised, an analogous advantage in the case of coherently controlled dynamical causal order, that is, an advantage of QC-QCs over QC-supFOs, has not yet been exhibited. In a recent work [44], we presented an advantage of QC-QCs over a particular class of quantum circuits with non-dynamical control of causal order (the Sup class from Ref. [36], which turns out to be strictly included in

QC-supFO) for a tripartite task in quantum metrology. However, the present work, and in particular the formalisation of QC-supFO, helps to prove that the origin of the advantage observed in [44] cannot be attributed to dynamical causal order, since the optimal QC-QC strategy in fact belongs to QC-supFO and thus does not have dynamical causal order. Further work thus remains to be done to show whether dynamical causal order combined with indefinite causal order is indeed a useful resource in quantum information. In this context, we note that the characterisations of the various classes of processes proposed in this work, in terms of linear constraints on positive semidefinite matrices, provide a readily usable way to compare the performances of quantum circuits with dynamical control of causal order with those of quantum circuits with non-dynamical causal order, for any task that could be solved or optimised through semidefinite programming techniques.

## ACKNOWLEDGMENTS

We thank Maarten Grothus, Augustin Vanrietvelde and V. Vilasini for helpful discussions and comments on this work.

This research was funded in part by l'Agence Nationale de la Recherche (ANR) projects ANR-15-IDEX-02 and ANR-22-CE47-0012, and the PEPR integrated project EPiQ ANR-22-PETQ-0007 as part of Plan France 2030. RM acknowledges the support from the Alexander von Humboldt Foundation. For the purpose of open access, the authors have applied a CC-BY public copyright license to any Author Accepted Manuscript (AAM) version arising from this submission.

[1] C. J. Wood and R. W. Spekkens, The lesson of causal discovery algorithms for quantum correlations: causal explanations of Bell-inequality violations require fine-tuning, New Journal of Physics 17, 033002 (2015), arXiv:1208.4119 [quant-ph].

[2] L. Hardy, Probability theories with dynamic causal structure: A new framework for quantum gravity, arXiv:gr-qc/0509120 (2005).

[3] O. Oreshkov, F. Costa, and Č. Brukner, Quantum correlations with no causal order, Nat. Commun. 3, 1092 (2012), arXiv:1105.4464 [quant-ph].

[4] G. Chiribella, Perfect discrimination of no-signalling channels via quantum superposition of causal structures, Phys. Rev. A 86, 040301(R) (2012), arXiv:1109.5154 [quant-ph].

[5] M. Araújo, F. Costa, and Č. Brukner, Computational advantage from quantum-controlled ordering of gates, Phys. Rev. Lett. 113, 250402 (2014), arXiv:1401.8127 [quant-ph].

[6] L. A. Rozema, T. Strömberg, H. Cao, Y. Guo, B.-H. Liu, and P. Walther, Experimental aspects of indefinite causal order in quantum mechanics, Nature Reviews Physics 6,

483 (2024), arXiv:2405.00767 [quant-ph].

[7] Ä. Baumeler, A. Feix, and S. Wolf, Maximal incompatibility of locally classical behavior and global causal order in multiparty scenarios, Phys. Rev. A 90, 042106 (2014), arXiv:1403.7333 [quant-ph].

[8] M. Araújo, C. Branciard, F. Costa, A. Feix, C. Giarmatzi, and Č. Brukner, Witnessing causal nonseparability, New J. Phys. 17, 102001 (2015), arXiv:1506.03776 [quant-ph].

[9] C. Branciard, M. Araújo, A. Feix, F. Costa, and Č. Brukner, The simplest causal inequalities and their violation, New J. Phys. 18, 013008 (2015), arXiv:1508.01704 [quant-ph].

[10] A. A. Abbott, C. Giarmatzi, F. Costa, and C. Branciard, Multipartite causal correlations: Polytopes and inequalities, Phys. Rev. A 94, 032131 (2016), arXiv:1608.01528 [quant-ph].

[11] Ä. Baumeler and S. Wolf, The space of logically consistent classical processes without causal order, New Journal of Physics 18, 013036 (2016), arXiv:1507.01714 [quant-ph].

[12] E.-E. Tselentis and Ä. Baumeler, Admissible causal struc-
tures and correlations, PRX Quantum 4, 040307 (2023), arXiv:2210.12796 [quant-ph].

[13] Ä. Baumeler and S. Wolf, Perfect signaling among three parties violating predefined causal order, in *2014 IEEE International Symposium on Information Theory* (2014) pp. 526–530, arXiv:1312.5916 [quant-ph].

[14] O. Oreshkov and C. Giarmatzi, Causal and causally separable processes, New J. Phys. 18, 093020 (2016), arXiv:1506.05449 [quant-ph].

[15] E.-E. Tselentis and Ä. Baumeler, Möbius game and other Bell tests for relativity, Phys. Rev. A 111, 052211 (2025), arXiv:2309.15752 [gr-qc].

[16] E.-E. Tselentis and Ä. Baumeler, The Möbius game: A quantum-inspired test of general relativity, arXiv:2407.17203 [gr-qc] (2024).

[17] V. Baumann, Ä. Baumeler, and E.-E. Tselentis, No quantum advantage for violating fixed-order inequalities?, arXiv:2412.17551 [quant-ph] (2024).

[18] J. Wechs, A. A. Abbott, and C. Branciard, On the definition and characterisation of multipartite causal (non)separability, New J. Phys. 21, 013027 (2019), arXiv:1807.10557 [quant-ph].

[19] G. Chiribella, G. M. D'Ariano, P. Perinotti, and B. Valiron, Quantum computations without definite causal structure, Phys. Rev. A 88, 022318 (2013), arXiv:0912.0195 [quant-ph].

[20] T. Colnaghi, G. M. D'Ariano, P. Perinotti, and S. Facchini, Quantum computation with programmable connections between gates, Phys. Lett. A 376, 2940 (2012), arXiv:1109.5987 [quant-ph].

[21] J. Wechs, H. Dourdent, A. A. Abbott, and C. Branciard, Quantum circuits with classical versus quantum control of causal order, PRX Quantum 2, 030335 (2021), arXiv:2101.08796 [quant-ph].

[22] G. M. Ziegler, *Lectures on Polytopes*, Graduate Texts in Mathematics, Vol. 152 (Springer, New York, NY, 1995).

[23] H. P. Williams, Fourier’s method of linear programming and its dual, Am. Math. Mon. 93, 681 (1986).

[24] E. B. Davies and J. T. Lewis, An operational approach to quantum probability, Commun. Math. Phys. 17, 239 (1970).

[25] A. Jamiołkowski, Linear transformations which preserve trace and positive semidefiniteness of operators, Rep. Math. Phys. 3, 275 (1972).

[26] M.-D. Choi, Completely positive linear maps on complex matrices, Linear Algebra Appl. 10, 285 (1975).

[27] M. Araújo, A. Feix, M. Navascués, and C. Brukner, A purification postulate for quantum mechanics with indefinite causal order, Quantum 1, 10 (2017), arXiv:1611.08535 [quant-ph].

[28] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Transforming quantum operations: Quantum supermaps, EPL 83, 30004 (2008), arXiv:0804.0180 [quant-ph].

[29] P. Skrzypczyk and D. Cavalcanti, *Semidefinite Programming in Quantum Information Science*, IOP Series in Quantum Technology (IOP Publishing, 2023).

[30] D. Kretschmann and R. F. Werner, Quantum channels with memory, Phys. Rev. A 72, 062323 (2005), arXiv:quant-ph/0502106 [quant-ph].

[31] G. Gutoski and J. Watrous, Toward a general theory of quantum games, in *Proceedings of the 39th Annual ACM Symposium on Theory of Computing*, STOC '07 (2007) pp. 565–574, arXiv:quant-ph/0611234.

[32] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Quantum circuit architecture, Phys. Rev. Lett. 101, 060401 (2008), arXiv:0712.1325 [quant-ph].

[33] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Theoretical framework for quantum networks, Phys. Rev. A 80, 022339 (2009), arXiv:0904.4483 [quant-ph].

[34] C. Branciard, Witnesses of causal nonseparability: an introduction and a few case studies, Sci. Rep. 6, 26018 (2016), arXiv:1603.00043 [quant-ph].

[35] T. Purves and A. J. Short, Quantum theory cannot violate a causal inequality, Phys. Rev. Lett. 127, 110402 (2021), arXiv:2101.09107 [quant-ph].

[36] Q. Liu, Z. Hu, H. Yuan, and Y. Yang, Optimal strategies of quantum metrology with a strict hierarchy, Phys. Rev. Lett. 130, 070803 (2023), arXiv:2203.09758 [quant-ph].

[37] A. Vanrietvelde, N. Ormrod, H. Kristjánsson, and J. Barrett, Consistent circuits for indefinite causal order, arXiv:2206.10042 [quant-ph] (2022).

[38] M. Salzger, Connecting indefinite causal order processes to composable quantum protocols in a spacetime, arXiv:2304.06735 [quant-ph] (2023).

[39] R. F. Werner and M. M. Wolf, Bell inequalities and entanglement, arXiv:quant-ph/0107093 (2001).

[40] Z. Liu and G. Chiribella, Tsirelson bounds for quantum correlations with indefinite causal order, Nat. Commun. 16, 3314 (2025), arXiv:2403.02749 [quant-ph].

[41] M. Grothus, A. A. Abbott, A. Vanrietvelde, and C. Branciard, Routing quantum control of causal order (2025), in preparation.

[42] A. Vanrietvelde, H. Kristjánsson, and J. Barrett, Routed quantum circuits, Quantum 5, 503 (2021), arXiv:2011.08120 [quant-ph].

[43] J. Bavaresco, S. Yoshida, T. Odake, H. Kristjánsson, P. Taranto, M. Murao, and M. T. Quintino, Can the quantum switch be deterministically simulated?, arXiv:2409.18202 [quant-ph] (2024).

[44] R. Mothe, C. Branciard, and A. A. Abbott, Reassessing the advantage of indefinite causal orders for quantum metrology, Phys. Rev. A 109, 062435 (2024), arXiv:2312.12172 [quant-ph].

[45] J. S. Bell, On the Einstein Podolsky Rosen paradox, Physics 1, 195 (1964).
# APPENDICES

## CONTENTS

A. Multipartite causal correlations: equivalence between the different definitions 23

1. Abbott et al.'s definition 23

2. Oreshkov and Giarmatzi's definition 24

3. Two more equivalent characterisations of causal correlations 28

4. Equivalent definitions for correlations with non-influenceable causal orders 29

B. Tripartite causal correlations 29

1. The "simplest" tripartite scenario with dynamical causal order 29

2. $P_{\text{NIO}}$ and $P_{\text{NIO}'}$ reduce to $P_{\text{convFO}}$ for $N=3$ 30

C. Proofs of the different causal bounds on $I_4 := p(a=b=xy, d=zt) + p(\neg(a=b=xy), c=zt)$ 31

1. For (convex mixtures of) fixed orders: $I_4 \le_{\text{convFO}} \frac{15}{16}$ 31

2. For correlations with non-influenceable causal orders: $I_4 \le_{\text{NIO}} \frac{31}{32}$ 33

3. For correlations with non-influenceable coarse-grained causal orders: $I_4 \le_{\text{NIO}'} \frac{47}{48}$ 36

4. For general causal correlations: $I_4 \le_{\text{causal}} 1$ 38

D. Description and characterisation of our different classes of quantum circuits 38

1. Validity constraints for general process matrices 38

2. Quantum circuits with classical control of causal order (QC-CCs) 39

a. General QC-CCs 40

b. Convex mixtures of quantum circuits with fixed causal order (QC-convFOs) 43

c. Quantum circuits with non-influenceable classical control of causal order (QC-NICCs) 44

d. Inclusion relations 45

e. Explicit decompositions of our specific examples of QC-CCs 46

3. Quantum circuits with quantum control of causal order (QC-QCs) 46

a. General QC-QCs 47

b. Quantum circuits with superposition of fixed causal orders (QC-supFO) 49

c. Quantum circuits with non-influenceable quantum control of causal order (QC-NIQCs) 54

d. Inclusion relations 55

e. Explicit decompositions of our specific examples of QC-QCs 55

4. A graphical representation of the SDP constraints for our various classes of circuits 56

E. Correlations induced by quantum circuits with classical or quantum control of causal order 60

1. Correlations induced by QC-CCs 60

a. Correlations induced by QC-CCs are in $P_{\text{causal}}$ 60

b. Correlations induced by QC-convFOs are in $P_{\text{convFO}}$ 61

c. Correlations induced by QC-NICCs are in $P_{\text{NIO}}$ 61

2. Correlations induced by QC-QCs 61

a. Correlations induced by QC-QCs are in $P_{\text{causal}}$ 62

b. Correlations induced by QC-supFOs are in $P_{\text{convFO}}$ 63

c. Correlations induced by QC-NIQCs are in $P_{\text{NIO}'}$ 64

d. Defining a new class whose correlations are in $P_{\text{NIO}}$ 65

3. Obtaining any correlation in $P_{\text{convFO}}$ or $P_{\text{causal}}$ with a QC-convFO or a QC-CC 68

a. Any correlation in $P_{\text{convFO}}$ can be obtained from a QC-convFO 69

b. Any correlation in $P_{\text{causal}}$ can be obtained from a QC-CC 70

c. Saturating the bounds (15)–(18) on $I_4$ with quantum circuits 70

4. Dynamical correlations from quantum circuits with non-influenceable control of causal order 71
# Appendix A: Multipartite causal correlations: equivalence between the different definitions

## 1. Abbott et al.'s definition

In Ref. [10] Abbott et al. proposed the following recursive definition for causal correlations: an N-partite probability distribution $p(\vec{a}|\vec{x})$ is causal if and only if $N = 1$, or it has a decomposition as

$$p(\vec{a}|\vec{x}) = \sum_{k_1} q_{k_1} p_{k_1}(a_{k_1}|x_{k_1}) p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1}), \quad (A1)$$

with $q_{k_1} \ge 0$, $\sum_{k_1} q_{k_1} = 1$, where for each $k_1 \in \mathcal{N}$, $p_{k_1}(a_{k_1}|x_{k_1})$ is a probability distribution for the single party $A_{k_1}$, and where for each $k_1, x_{k_1}, a_{k_1}, p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1})$ is a conditional probability distribution for the remaining $N-1$ parties in $\mathcal{N}\setminus k_1$, which is itself causal (according to the present definition).

Our definition in Eq. (3) can be seen as an “unravelling” of this definition. Let us indeed prove by induction that the two are equivalent. This is clearly the case for $N = 1$ (they are both trivial); let us then assume they are equivalent for $N-1$ ($\ge 1$):

* Proof that (A1) ⇒ (3): Assume Eq. (A1). Since $p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1})$ is required to be an $(N-1)$-partite causal distribution according to Abbott et al.'s definition, then by the induction hypothesis, it is also causal according to our definition in the main text, i.e., it has a decomposition of the form of Eq. (3), with permutations $\pi' = (k_2, \dots, k_N)$ of $\mathcal{N}\setminus k_1$:

$$\begin{align}
p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1}) &= \sum_{\pi'=(k_2, \dots, k_N)} p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\pi' = (k_2, \dots, k_N), \vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1}) \nonumber \\
\text{s.t. } \forall n = 1, \dots, N-1, \forall (k_2, \dots, k_n, k_{n+1}), & \nonumber \\
& p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}((k_2, \dots, k_n, k_{n+1}), \vec{a}_{k_2, \dots, k_n}|\vec{x}_{\mathcal{N}\setminus k_1}) \text{ does not depend on } \vec{x}_{\mathcal{N}\setminus k_1}\setminus\{k_2, \dots, k_n\}. \tag{A2}
\end{align}$$

Defining $p((k_1, \dots, k_N), \vec{a}|\vec{x}) := q_{k_1} p_{k_1}(a_{k_1}|x_{k_1}) p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}((k_2, \dots, k_N), \vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1})$, the combination of Eq. (A1) with Eq. (A2) then readily provides the decomposition

$$\begin{align}
p(\vec{a}|\vec{x}) &= \sum_{k_1} q_{k_1} p_{k_1}(a_{k_1}|x_{k_1}) \sum_{\pi'=(k_2, \dots, k_N)} p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\pi' = (k_2, \dots, k_N), \vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1}), \nonumber \\
&= \sum_{\pi=(k_1, \dots, k_N)} p(\pi = (k_1, \dots, k_N), \vec{a}|\vec{x}), \tag{A3}
\end{align}$$

in terms of a valid probability distribution $p(\pi, \vec{a}|\vec{x})$ which can be shown to satisfy Eq. (3): indeed, for any $n = 1, \dots, N-1$ and any $(k_1, \dots, k_n, k_{n+1})$,

$$p((k_1, \dots, k_n, k_{n+1}), \vec{a}_{k_1, \dots, k_n}|\vec{x}) = q_{k_1} p_{k_1}(a_{k_1}|x_{k_1}) p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}((k_2, \dots, k_n, k_{n+1}), \vec{a}_{k_2, \dots, k_n}|\vec{x}_{\mathcal{N}\setminus k_1}) \quad (A4)$$

does not, according to Eq. (A2) above, depend on $\vec{x}_{\mathcal{N}\setminus\{k_1, \dots, k_n\}}$; while for $n = 0$ and any $k_1$, $p((k_1)|\vec{x}) = q_{k_1}$ does not depend on $\vec{x}$.

* Proof that (3) ⇒ (A1): Assume Eq. (3). The probability distribution $p(\pi, \vec{a}|\vec{x})$ in the decomposition of $p(\vec{a}|\vec{x})$ satisfies in particular, for $n = 0$ and $n = 1$, that for any $k_1$, $p((k_1)|\vec{x}) = p((k_1))$ is independent of $\vec{x}$, and $p((k_1), a_{k_1}|\vec{x}) = p((k_1), a_{k_1}|x_{k_1})$ only depends on $x_{k_1}$, and not on all the other inputs. Defining<fnref n="15" />

$$\begin{align}
q_{k_1} &:= p((k_1)), \quad p_{k_1}(a_{k_1}|x_{k_1}) := p((k_1), a_{k_1}|x_{k_1})/q_{k_1}, \nonumber \\
p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}((k_2, \dots, k_N), \vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1}) &:= p((k_1, k_2, \dots, k_N), \vec{a}|\vec{x})/p((k_1), a_{k_1}|x_{k_1}) \nonumber \\
\text{and } p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1}) &:= \sum_{(k_2, \dots, k_N)} p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}((k_2, \dots, k_N), \vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1}), \tag{A5}
\end{align}$$

<footnote n="15">¹⁵ We assume for simplicity, in these definitions, that the denominators $q_{k_1}$ and $p((k_1), a_{k_1}|x_{k_1})$ are nonzero. The terms for which these are zero do not contribute to the argument; some (irrelevant) values can always be given to $p_{k_1}(a_{k_1}|x_{k_1})$ and $p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1})$ in those cases, to make these valid and causal distributions.</footnote>
the decomposition of Eq. (3) can then be written in exactly the same form as in Eq. (A1).

Clearly $q_{k_1} \ge 0$, $\sum_{k_1} q_{k_1} = 1$, and $p_{k_1}(a_{k_1} | x_{k_1})$ is a valid (nonnegative and normalised) probability distribution. It remains to verify that $p_{\mathcal{N}\setminus\{k_1, x_{k_1}, a_{k_1}\}}(\vec{a}_{\mathcal{N}\setminus\{k_1\}} | \vec{x}_{\mathcal{N}\setminus\{k_1\}})$ is a causal $(N-1)$-partite probability distribution (according to Abbott et al.'s definition).

To see this, notice that the last line in Eq. (A5) above gives precisely a decomposition of $p_{\mathcal{N}\setminus\{k_1, x_{k_1}, a_{k_1}\}}(\vec{a}_{\mathcal{N}\setminus\{k_1\}} | \vec{x}_{\mathcal{N}\setminus\{k_1\}})$ of the form of Eq. (3) for $(N-1)$-partite distributions, with a sum over all permutations $\pi' = (k_2, \dots, k_n)$ of $\mathcal{N}' := \mathcal{N}\setminus\{k_1\}$. Consider some $n \in \{1, \dots, N-1\}$ and some subsequence $(k_2, \dots, k_{n+1})$ of $\mathcal{N}'$. One then has

$$p_{\mathcal{N}\setminus\{k_1, x_{k_1}, a_{k_1}\}}((k_2, \dots, k_n, k_{n+1}), \vec{a}_{k_2, \dots, k_n} | \vec{x}_{\mathcal{N}'}) = p((k_1, k_2, \dots, k_n, k_{n+1}), \vec{a}_{k_1, k_2, \dots, k_n} | \vec{x})/p((k_1), a_{k_1} | x_{k_1}). \quad (A6)$$

According to Eq. (3), which we assumed for $p(\vec{a}|\vec{x})$, the numerator in the right-hand-side above does not depend on $\vec{x}_{\mathcal{N}\setminus\{k_1, k_2, \dots, k_n\}}$ (and neither does the denominator). Hence, the left-hand-side does not depend on $\vec{x}_{\mathcal{N}'\setminus\{k_1, k_2, \dots, k_n\}} = \vec{x}_{\mathcal{N}'\setminus\{k_2, \dots, k_n\}}$, so that $p_{\mathcal{N}\setminus\{k_1, x_{k_1}, a_{k_1}\}}(\vec{a}_{\mathcal{N}\setminus\{k_1\}} | \vec{x}_{\mathcal{N}\setminus\{k_1\}})$ satisfies the constraint of Eq. (3) for $(N-1)$-partite distributions. It is thus causal according to that definition, and therefore, by our induction hypothesis, it is causal according to Abbott et al.'s definition, as required.

## 2. Oreshkov and Giarmatzi's definition

The first general definition for multipartite causal correlations that appeared in the literature was in fact proposed earlier by Oreshkov and Giarmatzi [14]. It says that causal correlations are those compatible with a causal structure described as a Strict Partial Order (SPO), rather than a full permutation as in our definition of Eq. (3).

More specifically: an SPO between $N$ parties $A_i$ ($i \in \mathcal{N} := \{1, \dots, N\}$) is a binary relation $\prec$ which is irreflexive, transitive and antisymmetric. An SPO can in general be defined by the (consistent$^{16}$) list of all pairwise relations for all $i \neq j$:<fnref n="17" /> either $A_i \prec A_j$ (understood as $A_i$ being in the causal past of $A_j$), $A_j \prec A_i$ ($A_j$ being in the causal past of $A_i$), or $A_i \nsim A_j$ (neither party being in the causal past of the other one). We shall generically denote by $\kappa = \kappa(\mathcal{N})$ an SPO for the parties in $\mathcal{N}$. Note that any such SPO $\kappa(\mathcal{N})$ induces an SPO $\kappa(\mathcal{K})$ on any subset $\mathcal{K}$ of $\mathcal{N}$.

Rephrasing it slightly, Oreshkov and Giarmatzi's definition (Definition 2.3 in [14]) states that a correlation $p(\vec{a}|\vec{x})$ is causal if and only if

$$\exists p(\kappa, \vec{a}|\vec{x}) \text{ s.t. } p(\vec{a}|\vec{x}) = \sum_{\kappa} p(\kappa, \vec{a}|\vec{x}) \\ \text{ and } \forall \mathcal{K} \subset \mathcal{N}, \forall \ell \in \mathcal{N}\setminus\mathcal{K}, \forall \vec{\kappa} = \vec{\kappa}(\mathcal{K} \cup \{\ell\}) \text{ for which } A_{\ell} \nsim^{\forall} \mathcal{K}, \\ p(\vec{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x}) \text{ does not depend on } x_{\ell}, \quad (A7)$$

where $p(\kappa, \vec{a}|\vec{x})$ is a probability distribution (so that $p(\kappa, \vec{a}|\vec{x}) \ge 0$, $\sum_{\kappa, \vec{a}} p(\kappa, \vec{a}|\vec{x}) = 1$) in which the random variable $\kappa = \kappa(\mathcal{N})$ takes values in all possible SPOs on $\mathcal{N}$, where the shorthand notation $A_{\ell} \nsim^{\forall} \mathcal{K}$ means $A_{\ell} \nsim A_k$ (i.e., $A_k \prec A_{\ell}$ or $A_k \nsim A_{\ell}$) for all $k \in \mathcal{K}$, and where the last line involves the marginal distributions $p(\vec{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x})$ obtained from $p(\kappa, \vec{a}_{\mathcal{K}}|\vec{x})$ ($= \sum_{\vec{a}_{\mathcal{N}\setminus\mathcal{K}}} p(\kappa, \vec{a}_{\mathcal{K}}, \vec{a}_{\mathcal{N}\setminus\mathcal{K}}|\vec{x})$) by summing over all SPOs $\kappa = \kappa(\mathcal{N})$ which induce the SPO $\vec{\kappa}(\mathcal{K} \cup \{\ell\})$ on the subset $\mathcal{K} \cup \{\ell\}$: that is, $p(\vec{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x}) := \sum_{\kappa(\mathcal{N}) \text{ s.t. } \kappa(\mathcal{K} \cup \{\ell\}) = \vec{\kappa}(\mathcal{K} \cup \{\ell\})} p(\kappa(\mathcal{N}), \vec{a}_{\mathcal{K}}|\vec{x})$.

That this definition is equivalent to that of Abbott et al., Eq. (A1) above, was in fact already proven by Oreshkov and Giarmatzi in [14]. Let us for convenience propose here a new version of this proof.

* Proof that (A1) ⇒ (A7) [or (3) ⇒ (A7)]: Assume Eq. (A1). We have just shown in the previous subsection that this is equivalent to assuming that $p(\vec{a}|\vec{x})$ has a decomposition as in Eq. (3). Now, clearly a total order defined by some permutation $\pi$ is a particular case of an SPO $\kappa$, defined by the pairwise relations $A_i \prec A_j$ iff $i$ comes before $j$ in $\pi$ (for all $i \neq j$). Hence, the decomposition $p(\vec{a}|\vec{x}) = \sum_{\pi} p(\pi, \vec{a}|\vec{x})$ is of the form $p(\vec{a}|\vec{x}) = \sum_{\kappa} p(\kappa, \vec{a}|\vec{x})$, with $p(\kappa, \vec{a}|\vec{x}) = 0$ as soon as $\kappa$ contains a pairwise relation of the form $A_i \nsim A_j$. It then remains to prove that the second and third lines of Eq. (A7) are indeed satisfied.

<footnote n="16">¹⁶ Some consistency constraints are implied by the irreflexivity, transitivity and antisymmetry of the SPO. E.g., the pairwise relations $A_1 \prec A_2$, $A_2 \prec A_3$, $A_3 \prec A_1$ would be inconsistent.</footnote>

<footnote n="17">¹⁷ When writing such pairwise relations between $A_i$ and $A_j$, we will always assume $i \neq j$, without necessarily specifying it explicitly.</footnote>
Consider $\mathcal{K} \subsetneq \mathcal{N}$, $\ell \in \mathcal{N}\setminus\mathcal{K}$, and some SPO $\bar{\kappa} = \bar{\kappa}(\mathcal{K} \cup \{\ell\})$ for which $A_\ell \not\supsetneq \mathcal{K}$. If $\bar{\kappa}$ contains any relation of the form $A_i \not\supsetneq A_j$, then so does any SPO $\kappa(\mathcal{N})$ that induces $\bar{\kappa}(\mathcal{K} \cup \{\ell\})$ on the subset $\mathcal{K} \cup \{\ell\}$, and hence $p(\bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x}) = 0$, so that the last line of Eq. (A7) is trivially satisfied. Otherwise, if $\bar{\kappa}$ contains no relation of the form $A_i \not\supsetneq A_j$, then it can be equivalently described as a permutation $(k_1, \dots, k_n, \ell)$ of $\mathcal{K} \cup \{\ell\}$

(where $n$ is the cardinality of $\mathcal{K}$, and noting that $A_\ell \not\supsetneq \mathcal{K}$ implies that $\ell$ must necessarily come last). The SPOs $\kappa = \kappa(\mathcal{N})$ that contribute to the decomposition $p(\vec{a}|\vec{x}) = \sum_\kappa p(\kappa, \vec{a}|\vec{x})$ and that induce $\bar{\kappa} \equiv (k_1, \dots, k_n, \ell)$ on the subset $\mathcal{K} \cup \{\ell\}$ are then the permutations $\pi$ of $\mathcal{N}$ that contain $(k_1, \dots, k_n, \ell)$ as a subsequence—which we write $\pi \supset (k_1, \dots, k_n, \ell)$—so that

$$ 
\begin{aligned}
p(\bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x}) &= \sum_{\pi \supset (k_1, \dots, k_n, \ell)} p(\pi, \vec{a}_{\mathcal{K}}|\vec{x}) \\
&= \sum_{(i_1, \dots, i_m, \ell) \supset (k_1, \dots, k_n, \ell)} p((i_1, \dots, i_m, \ell), \vec{a}_{\mathcal{K}}|\vec{x}) = \sum_{(i_1, \dots, i_m, \ell) \supset (k_1, \dots, k_n, \ell)} \sum_{\forall i \in \{i_1, \dots, i_m\} \setminus \mathcal{K}} p((i_1, \dots, i_m, \ell), \vec{a}_{i_1, \dots, i_m}|\vec{x}),
\end{aligned} 
\quad (A8) $$

where the second sum above is over all supersequences $(i_1, \dots, i_m, \ell)$ of $(k_1, \dots, k_n, \ell)$ (with $n \le m < N$), and the last sum is over the outcomes $a_i$ of all parties with indices $i \in \{i_1, \dots, i_m\}$ that were not already in $\mathcal{K}$. The assumption of Eq. (3) implies that each probability in the last sums above do not depend on $x_\ell$, which implies that $p(\bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x})$ itself does not depend on $x_\ell$—which indeed means that the last line of Eq. (A7) is satisfied.

* Proof that (A7) ⇒ (A1): We prove this by induction on $N$. This clearly holds for $N=1$ (both conditions are trivial); let us then assume that Eq. (A7) implies Eq. (A1) for $(N-1)$-partite distributions (with $N-1 \ge 1$), and consider an $N$-partite distribution $p(\vec{a}|\vec{x})$ that admits a decomposition $p(\vec{a}|\vec{x}) = \sum_\kappa p(\kappa, \vec{a}|\vec{x})$ satisfying Eq. (A7).

The first task, for each SPO $\kappa$ that appears in the decomposition, is to identify which party $A_{k_1}$ can be “taken to come first”, so as to provide a decomposition as in Eq. (A1). For this let us denote, for any given $\kappa = \kappa(\mathcal{N})$, by $S_\kappa^I$ the (nonempty) set of parties that have no other party in their causal past—the “first consecutive set” according to the terminology of Ref. [14]. We will first show that the independence condition of Eq. (A7) also holds when one further restricts the probabilities to SPOs with a given first consecutive set $\mathcal{S}$, i.e.:<fnref n="18" />

$$ 
\begin{gathered}
\forall \mathcal{S} \subseteq \mathcal{N}, \forall \mathcal{K} \subsetneq \mathcal{N}, \forall \ell \in \mathcal{N}\setminus\mathcal{K}, \forall \bar{\kappa} = \bar{\kappa}(\mathcal{K} \cup \{\ell\}) \text{ for which } A_\ell \not\supsetneq \mathcal{K}, \\
p(S_\kappa^I = \mathcal{S}, \bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_\mathcal{K}|\vec{x}) \text{ does not depend on } x_\ell. \quad (A9)
\end{gathered} $$

Proof of Eq. (A9):

If $\ell \in \mathcal{S}$, then using the inclusion-exclusion principle one can write:<fnref n="19" />

$$ 
\begin{aligned}
p(S_\kappa^I &= \mathcal{S}, \bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_\mathcal{K}|\vec{x}) = p\left(\bigwedge_{i,i' \in \mathcal{S}} (A_i \not\supsetneq A_{i'}), \bigwedge_{j \in \mathcal{N}\setminus\mathcal{S}} (S \not\supseteq A_j), \bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_\mathcal{K}|\vec{x}\right) \\
&= \sum_{\mathcal{J} \subseteq \mathcal{N}\setminus\mathcal{S}} (-1)^{|\mathcal{J}|} p\left(\bigwedge_{i,i' \in \mathcal{S}} (A_i \not\supsetneq A_{i'}), \bigwedge_{j \in \mathcal{J}} (S \not\supseteq A_j), \bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_\mathcal{K}|\vec{x}\right) \\
&= \sum_{\mathcal{J} \subseteq \mathcal{N}\setminus\mathcal{S}} (-1)^{|\mathcal{J}|} \sum_{\substack{\bar{\kappa}(\mathcal{S} \cup \mathcal{J} \cup \mathcal{K}) \text{ s.t.} \\ \bigwedge_{i,i' \in \mathcal{S}} (A_i \not\supseteq A_{i'}), \bigwedge_{j \in \mathcal{J}} (S \not\supseteq A_j), \\ \bar{\kappa}(\mathcal{K} \cup \{\ell\}) = \bar{\kappa}(\mathcal{K} \cup \{\ell\})}} p(\bar{\kappa}(\mathcal{S} \cup \mathcal{J} \cup \mathcal{K}), \vec{a}_\mathcal{K}|\vec{x}). \quad (A10)
\end{aligned} $$

$$ 
\begin{aligned}
p(E, \bigwedge_{j \in \mathcal{I}} F_j) &= p(E) - p(E, \bigvee_{j \in \mathcal{I}} (\neg F_j)) = p(E) - p(\bigvee_{j \in \mathcal{I}} (E \wedge \neg F_j)) \\
&= p(E) - \sum_{\emptyset \neq \mathcal{J} \subseteq \mathcal{I}} (-1)^{|\mathcal{J}|-1} p(\bigwedge_{j \in \mathcal{J}} (E \wedge \neg F_j)) = \sum_{\mathcal{J} \subseteq \mathcal{I}} (-1)^{|\mathcal{J}|} p(E, \bigwedge_{j \in \mathcal{J}} (\neg F_j)),
\end{aligned} $$

where the first equality on the second line is a direct application of the inclusion-exclusion principle.

<footnote n="18">¹⁸ Here we adopt the notation that, for a given property $[\cdot]$ that a SPO may or may not satisfy, we write $p([\cdot], \vec{a}|\vec{x}) = \sum_\kappa p(\kappa, \vec{a}|\vec{x})$. E.g. in Eq. (A9), $p(S_\kappa^I = \mathcal{S}, \bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_\mathcal{K}|\vec{x}) = \sum_\kappa p(\kappa, \bar{\kappa}(\mathcal{K} \cup \{\ell\}) = \bar{\kappa}(\mathcal{K} \cup \{\ell\}) p(\kappa, \vec{a}_\mathcal{K}|\vec{x})$.</footnote>

<footnote>In the proof that follows, the notation $S \not\supseteq A_j$ means that $\exists i \in \mathcal{S}, A_i \not\supseteq A_j$; the notation $S \not\supseteq A_j$ means that $\forall i \in \mathcal{S}, A_i \not\supseteq A_j$.</footnote>

<footnote n="19">¹⁹ More specifically, we use the fact that for some events $E$ and $\{F_j\}_{j \in \mathcal{I}}$ (for some finite set of indices $\mathcal{I}$), one has</footnote>
Now, recalling that $\ell \in S$ here, one can see that $\bigwedge_{i,i' \in S} (A_i \not\asymp A_{i'})$ and $\bigwedge_{j \in \mathcal{J}} (S \not\asymp A_j)$ imply that $A_\ell \not\asymp (S \setminus \ell)$ and $A_\ell \not\asymp \mathcal{J}$, respectively. The constraint that $\bar{\kappa}(\mathcal{K} \cup \{\ell\}) = \bar{\kappa}(\mathcal{K} \cup \{\ell\})$ implies that the condition $A_\ell \not\asymp \mathcal{K}$, which was imposed on $\bar{\kappa}$, also holds for $\bar{\bar{\kappa}}$. Hence all the $\bar{\bar{\kappa}}$'s considered in the sum above satisfy $A_\ell \not\asymp (S \cup \mathcal{J} \cup \mathcal{K} \setminus \ell)$. From Eq. (A7) (with $\mathcal{K} \to S \cup \mathcal{J} \cup \mathcal{K} \setminus \ell$, after marginalising over some of the outputs $a_k$) it then follows that the terms $p(\bar{\bar{\kappa}}(S \cup \mathcal{J} \cup \mathcal{K}), \vec{a}_\mathcal{K}|\vec{x})$ that appear in the sum, and therefore $p(S_\kappa^I = S, \bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_\mathcal{K}|\vec{x})$ itself, do not depend on $x_\ell$.

Otherwise if $\ell \in \mathcal{N} \setminus S$, then using again the inclusion-exclusion principle one can write:

$$ 
\begin{align} 
p(S_{\kappa}^{I} = S, \bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x}) &= p\left(\bigwedge_{i,i' \in S} (A_i \not\asymp A_{i'}), (S \not\asymp A_{\ell}), \bigwedge_{j \in \mathcal{N} \setminus S \setminus \ell} (S \not\asymp A_j), \bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x}\right) \nonumber \\
&= \sum_{\mathcal{J} \subseteq \mathcal{N} \setminus S \setminus \ell} (-1)^{|\mathcal{J}|} p\left(\bigwedge_{i,i' \in S} (A_i \not\asymp A_{i'}), (S \not\asymp A_{\ell}), \bigwedge_{j \in \mathcal{J}} (S \not\asymp A_j), \bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x}\right) \nonumber \\
&= \sum_{\mathcal{J} \subseteq \mathcal{N} \setminus S \setminus \ell} (-1)^{|\mathcal{J}|} \sum_{\substack{\bar{\kappa}(S \cup \mathcal{J} \cup \mathcal{K} \cup \{\ell\}) \text{ s.t.} \\ \bigwedge_{i,i' \in S} (A_i \not\asymp A_{i'}), (S \not\asymp A_{\ell}), \bigwedge_{j \in \mathcal{J}} (S \not\asymp A_j), \bar{\kappa}(\mathcal{K} \cup \{\ell\}) = \bar{\kappa}(\mathcal{K} \cup \{\ell\})}} p(\bar{\bar{\kappa}}(S \cup \mathcal{J} \cup \mathcal{K} \cup \{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x}). \tag{A11}
\end{align} 
$$

Now, one can see that $\bigwedge_{i,i' \in S} (A_i \not\asymp A_{i'})$ and $(S \not\asymp A_\ell)$ together imply that $A_\ell \not\asymp S$, and that $(S \not\asymp A_\ell)$ and $\bigwedge_{j \in \mathcal{J}} (S \not\asymp A_j)$ together imply that $A_\ell \not\asymp \mathcal{J}$. The constraint that $\bar{\bar{\kappa}}(\mathcal{K} \cup \{\ell\}) = \bar{\kappa}(\mathcal{K} \cup \{\ell\})$ again implies that the condition $A_\ell \not\asymp \mathcal{K}$ also holds for $\bar{\bar{\kappa}}$. Hence all the $\bar{\bar{\kappa}}$'s considered in the sum above satisfy $A_\ell \not\asymp (S \cup \mathcal{J} \cup \mathcal{K})$. From Eq. (A7) (with now $\mathcal{K} \to S \cup \mathcal{J} \cup \mathcal{K}$, after marginalising over some of the outputs $a_k$) it then follows that the terms $p(\bar{\bar{\kappa}}(S \cup \mathcal{J} \cup \mathcal{K} \cup \{\ell\}), \vec{a}_\mathcal{K}|\vec{x})$ that appear in the sum, and therefore $p(S_\kappa^I = S, \bar{\kappa}(\mathcal{K} \cup \{\ell\}), \vec{a}_\mathcal{K}|\vec{x})$ itself, do not depend on $x_\ell$—which concludes the proof of Eq. (A9).

Now that we have this in place, let us introduce some arbitrary choice function $\underline{k}_I$ which, to each nonempty subset $S \subseteq \mathcal{N}$, assigns one of its elements, $\underline{k}_I(S) \in S$ (which will be “taken to come first”); and for any SPO $\kappa$, let us define $\underline{k}_{I,\kappa} := \underline{k}_I(S_\kappa^I)$ (where $S_\kappa^I$ is the “first consecutive set” of $\kappa$, as introduced above).

Notice that for $\mathcal{K} = \emptyset$, Eq. (A9) implies that $\forall S \subseteq \mathcal{N}$, $p(S_\kappa^I = S|\vec{x})$ does not depend on any $x_\ell$, i.e., it does not depend on $\vec{x}$ at all; and that for $\mathcal{K} = \{k_1\} \subseteq S$ (so that $S_\kappa^I = S$ implies $A_\ell \not\asymp A_{k_1}$ for any $\ell \neq k_1$), Eq. (A9) implies that $\forall S \subseteq \mathcal{N}, \forall k_1 \in S, p(S_\kappa^I = S, a_{k_1}|\vec{x})$ does not depend on any $x_\ell$ with $\ell \neq k_1$, i.e., it only depends on $x_{k_1}$. It then follows that for any given $k_1 \in \mathcal{N}$,

$$ 
\begin{align} 
p(\underline{k}_{I,\kappa} = k_1|\vec{x}) &= \sum_{S \text{ s.t. } \underline{k}_I(S)=k_1} p(S_\kappa^I = S|\vec{x}) \quad \text{does not depend on } \vec{x} \nonumber \\
\text{and } p(\underline{k}_{I,\kappa} = k_1, a_{k_1}|\vec{x}) &= \sum_{S \text{ s.t. } \underline{k}_I(S)=k_1} p(S_\kappa^I = S, a_{k_1}|\vec{x}) \quad \text{only depends on } x_{k_1}. \tag{A12}
\end{align} 
$$

One can then define$^{20}$

$$ q_{k_1} := p(\underline{k}_{I,\kappa} = k_1), \quad p_{k_1}(a_{k_1}|x_{k_1}) := \frac{p(\underline{k}_{I,\kappa} = k_1, a_{k_1}|x_{k_1})}{q_{k_1}}, $$

$$ 
\begin{align} 
\text{for any SPO } \kappa'(\mathcal{N}\backslash k_1), \quad & p_{\mathcal{N}\backslash k_1, x_{k_1}, a_{k_1}}(\kappa'(\mathcal{N}\backslash k_1), \vec{a}_{\mathcal{N}\backslash k_1}|\vec{x}_{\mathcal{N}\backslash k_1}) := \frac{p(\underline{k}_{I,\kappa} = k_1, \kappa'(\mathcal{N}\backslash k_1), \vec{a}|\vec{x})}{p(\underline{k}_{I,\kappa} = k_1, a_{k_1}|x_{k_1})}, \nonumber \\
\text{and } \quad & p_{\mathcal{N}\backslash k_1, x_{k_1}, a_{k_1}}(\vec{a}_{\mathcal{N}\backslash k_1}|\vec{x}_{\mathcal{N}\backslash k_1}) := \sum_{\kappa'(\mathcal{N}\backslash k_1)} p_{\mathcal{N}\backslash k_1, x_{k_1}, a_{k_1}}(\kappa'(\mathcal{N}\backslash k_1), \vec{a}_{\mathcal{N}\backslash k_1}|\vec{x}_{\mathcal{N}\backslash k_1}), \tag{A13}
\end{align} 
$$

<footnote>$^{20}$ Again we assume for simplicity, in these definitions, that the denominators are nonzero. The terms for which these are zero do not contribute to the argument (see Footnote 15).</footnote>
so that the decomposition $p(\vec{a}|\vec{x}) = \sum_{\kappa} p(\kappa, \vec{a}|\vec{x})$ can be written as

$$p(\vec{a}|\vec{x}) = \sum_{k_1} p(\underline{k}_{1,\kappa} = k_1, \vec{a}|\vec{x}) = \sum_{k_1} q_{k_1} p_{k_1}(a_{k_1}|x_{k_1}) p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1}), \quad (A14)$$

i.e., in exactly the same form as in Eq. (A1). Clearly $q_{k_1} \ge 0$, $\sum_{k_1} q_{k_1} = 1$, and $p_{k_1}(a_{k_1}|x_{k_1})$ is a valid probability distribution. It remains to verify that each $(N-1)$-partite probability distribution $p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1})$ is causal (according to Abbott et al.'s definition).

To see this, consider $\mathcal{K}' \subset \mathcal{N}' := \mathcal{N}\setminus k_1$, $\ell \in \mathcal{N}'\setminus\mathcal{K}'$, and $\bar{\kappa}' = \bar{\kappa}'(\mathcal{K}' \cup \{\ell\})$ for which $A_\ell \not\subset \mathcal{K}'$. Defining $\mathcal{K} := \{k_1\} \cup \mathcal{K}'$, one has

$$p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\bar{\kappa}'(\mathcal{K}' \cup \{\ell\}), \vec{a}_{\mathcal{K}'}|\vec{x}_{\mathcal{N}\setminus k_1}) = \frac{p(\underline{k}_{1,\kappa} = k_1, \bar{\kappa}'(\mathcal{K}' \cup \{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x})}{p(\underline{k}_{1,\kappa} = k_1, a_{k_1}|x_{k_1})} \\ = \sum_{\substack{\mathcal{S} \text{ s.t. } \underline{k}_1(\mathcal{S})=k_1, \\ \bar{\kappa}(\mathcal{K}\cup\{\ell\}) \text{ s.t. } \bar{\kappa}(\mathcal{K}'\cup\{\ell\})=\bar{\kappa}'(\mathcal{K}'\cup\{\ell\})}} p(\mathcal{S}_{\kappa}^{\mathcal{I}} = \mathcal{S}, \bar{\kappa}(\mathcal{K}\cup\{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x}) / p(\underline{k}_{1,\kappa} = k_1, a_{k_1}|x_{k_1}). \quad (A15)$$

Now, $\bar{\kappa}(\mathcal{K}' \cup \{\ell\}) = \bar{\kappa}'(\mathcal{K}' \cup \{\ell\})$ implies that $\bar{\kappa}(\mathcal{K} \cup \{\ell\})$ is also such that $A_\ell \not\subset \mathcal{K}'$. Furthermore, if $\mathcal{S}_\kappa^I = \mathcal{S}$, with $\underline{k}_1(\mathcal{S}) = k_1$, then $k_1 \in \mathcal{S}_\kappa^I$ and therefore $A_\ell \not\subset A_{k_1}$ for all $\bar{\kappa}(\mathcal{K} \cup \{\ell\})$ that contribute to the sum. All in all, these thus satisfy $A_\ell \not\subset \{k_1\} \cup \mathcal{K}' = \mathcal{K}$. From Eq. (A9) it follows that the terms $p(\mathcal{S}_\kappa^I = \mathcal{S}, \bar{\kappa}(\mathcal{K}\cup\{\ell\}), \vec{a}_{\mathcal{K}}|\vec{x})$ in the sum above do not depend on $x_\ell$; given that the same holds for the denominator $p(\underline{k}_{1,\kappa} = k_1, a_{k_1}|x_{k_1})$, we obtain that the term $p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\bar{\kappa}'(\mathcal{K}' \cup \{\ell\}), \vec{a}_{\mathcal{K}'}|\vec{x}_{\mathcal{N}\setminus k_1})$ itself does not depend on $x_\ell$, i.e., $p_{\mathcal{N}\setminus k_1, x_{k_1}, a_{k_1}}(\vec{a}_{\mathcal{N}\setminus k_1}|\vec{x}_{\mathcal{N}\setminus k_1})$ satisfies Eq. (A7). By our induction hypothesis, it also satisfies Eq. (A1), i.e., it is causal according to Abbott et al.'s definition—which concludes the proof that Oreshkov and Giarmatzi's definition is equivalent to that of Abbott et al.

By unravelling our inductive proof that (A7) ⇒ (A1) above, one can see that each SPO $\kappa$ gets extended to a total order (a permutation) $\pi_\kappa$ of $\mathcal{N}$ that is “compatible” with $\kappa$, i.e., that preserves all pairwise relations of the form $A_i \prec A_j$. Specifically, $\pi_\kappa = (k_1, k_2, \dots, k_N)$ is obtained inductively as follows, using the choice function $\underline{k}_1$: $k_1 = \underline{k}_1(\mathcal{S}_{\kappa(\mathcal{N})}^I)$, $k_2 = \underline{k}_1(\mathcal{S}_{\kappa(\mathcal{N}\setminus\{k_1\})}^I)$, $k_3 = \underline{k}_1(\mathcal{S}_{\kappa(\mathcal{N}\setminus\{k_1, k_2\})}^I)$, etc. It can be seen that the decomposition $p(\vec{a}|\vec{x}) = \sum_\kappa p(\kappa, \vec{a}|\vec{x})$ thus provides a new decomposition

$$p(\vec{a}|\vec{x}) = \sum_{\kappa} p(\kappa, \vec{a}|\vec{x}) = \sum_{\pi} \sum_{\kappa \text{ s.t. } \pi_\kappa = \pi} p(\kappa, \vec{a}|\vec{x}) = \sum_{\pi} p(\pi, \vec{a}|\vec{x}), \quad (A16)$$

with $p(\pi, \vec{a}|\vec{x}) := \sum_{\kappa \text{ s.t. } \pi_\kappa = \pi} p(\kappa, \vec{a}|\vec{x})$ satisfying Eq. (3) (as it follows from the proof that (A1) ⇒ (3) in the previous subsection).

Note that compatible extensions of a given SPO to a total order are in general not unique. For the proof above to work, one could however not just take any arbitrary extension, independently for each SPO $\kappa$. Indeed it was important that the choice of the “first party” (when $\mathcal{S}_\kappa^I$ was not a singleton) only depended on the set $\mathcal{S}_{\kappa'}^I$, rather than on $\kappa$ directly—i.e., for two SPOs $\kappa, \kappa'$ with the same first consecutive set $\mathcal{S}_\kappa^I = \mathcal{S}_{\kappa'}^I$, the (otherwise arbitrary) choice of the first party $\underline{k}_{1,\kappa(\ell)}$ must be the same. (That choice could also be probabilistic, but with probabilities that do not depend on the settings $\vec{x}$.) Otherwise one can construct counterexamples, for which extending each SPO independently to a total order leads to a decomposition $p(\vec{a}|\vec{x}) = \sum_\pi p(\pi, \vec{a}|\vec{x})$ as in Eq. (A16) that does not satisfy Eq. (3).$^{21}$

<footnote>$^{21}$ For an explicit such counterexample: consider for instance 3 parties A, B, C with the two SPOs $\kappa_0 = (A \not\asymp B, A \prec C, B \not\asymp C)$ and $\kappa_1 = (A \not\asymp B, A \prec C, B \prec C)$, which both have the same first consecutive set $\mathcal{S}_{\kappa_0}^I = \mathcal{S}_{\kappa_1}^I = \{A, B\}$, and the distribution (with no output for any party and only an input $x = 0, 1$ for A) $p(\kappa|x) = \delta_{\kappa, \kappa_x}$, which satisfies Eq. (A7). If one were to extend $\kappa_0$ to $\pi_{\kappa_0} = (A, B, C)$ and $\kappa_1$ to $\pi_{\kappa_1} = (B, A, C)$, i.e. with different choices for the first party, then this would result in $p(\pi|x) = \begin{cases} \delta_{\pi, (A,B,C)} & \text{if } x = 0 \\ \delta_{\pi, (B,A,C)} & \text{if } x = 1 \end{cases}$, which does not satisfy Eq. (3) (as for instance $p((k_1) = (A)|x) = \delta_{x,0}$ then depends on $x$).</footnote>
### 3. Two more equivalent characterisations of causal correlations

Here we provide two additional equivalent characterisations of multipartite causal correlations. The first one is that a correlation $p(\vec{a}|\vec{x})$ is causal if and only if it can be decomposed in terms of (well-defined, normalised) probability distributions $\tilde{p}((k_n), a_{k_n} | (k_1, \dots, k_{n-1}), \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}})$ as

$$ p(\vec{a}|\vec{x}) = \sum_{\pi} p(\pi, \vec{a}|\vec{x}) \\ \text{with } p(\pi = (k_1, \dots, k_N), \vec{a}|\vec{x}) = \prod_{n=1}^{N} \hat{p}((k_n), a_{k_n} | (k_1, \dots, k_{n-1}), \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}), \\ \text{s.t. } \forall n, \sum_{a_{k_n}} \hat{p}((k_n), a_{k_n} | (k_1, \dots, k_{n-1}), \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}) \text{ does not depend on } x_{k_n}. \quad (A17) $$

The last characterisation we provide is that a correlation $p(\vec{a}|\vec{x})$ is causal if and only if it can be decomposed in terms of (well-defined, normalised) probability distributions $\hat{p}((k_{n+1}), a_{k_n} | (k_1, \dots, k_n), \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}})$—which reduce to just $\hat{p}((k_1))$ for $n=0$ and to $\hat{p}(a_{k_N} | (k_1, \dots, k_N), \vec{x}, \vec{a}_{\mathcal{N}\setminus k_N})$ for $n=N$—as

$$ p(\vec{a}|\vec{x}) = \sum_{\pi} p(\pi, \vec{a}|\vec{x}) \\ \text{with } p(\pi = (k_1, \dots, k_N), \vec{a}|\vec{x}) = \prod_{n=0}^{N} \hat{p}((k_{n+1}), a_{k_n} | (k_1, \dots, k_n), \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}). \quad (A18) $$

Each term $\tilde{p}((k_n), a_{k_n} | (k_1, \dots, k_{n-1}), \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}})$ in Eq. (A17) corresponds to the probability for the “next” ($n^{th}$) party to be $A_{k_n}$ and to output $a_{k_n}$, given that the previous parties were (in that order) those labelled $(k_1, \dots, k_{n-1})$, given all previous parties’ as well as $A_{k_n}$’s inputs $\vec{x}_{k_1, \dots, k_n}$, and given all previous parties’ outputs $\vec{a}_{k_1, \dots, k_{n-1}}$. Somewhat analogously, each term $\hat{p}((k_{n+1}), a_{k_n} | (k_1, \dots, k_n), \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}})$ in Eq. (A18) corresponds to the probability that party $A_{k_n}$ outputs $a_{k_n}$ and that the next ($n+1$)th party will be $A_{k_{n+1}}$, given that the order of the parties so far was $(k_1, \dots, k_n)$, given all of those parties’ inputs $\vec{x}_{k_1, \dots, k_n}$, and given all previous parties’ outputs $\vec{a}_{k_1, \dots, k_{n-1}}$. Both decompositions thus translate—in two slightly different manners—the idea that the causal order can be established step by step, with each of the parties’ outputs and the choice of the “next” party depending on all previous available information (the order of the previous parties, all inputs so far, and all previous outputs).

As we will see, the characterisation of Eq. (A17) will be useful in particular in our proofs that QC-QCs only generate causal correlations, and reciprocally that any causal correlation can be obtained from a QC-QC; see Appendices E 2a and E 3b.

* Proof that (A17) ⇒ (3): For a distribution $p(\pi = (k_1, \dots, k_N), \vec{a}|\vec{x})$ that factorises as in Eq. (A17), one easily obtains, recursively (from $n = N - 1$ down to $n = 0$), that

$$ p((k_1, \dots, k_n, k_{n+1}), \vec{a}_{k_1, \dots, k_n} | \vec{x}) = \left( \prod_{j=1}^{n} \tilde{p}((k_j), a_{kj} | (k_1, \dots, k_{j-1}), \vec{x}_{k_1, \dots, k_j}, \vec{a}_{k_1, \dots, k_{j-1}}) \right) \tilde{p}((k_{n+1}) | (k_1, \dots, k_n), \vec{x}_{k_1, \dots, k_{n+1}}, \vec{a}_{k_1, \dots, k_n}). \quad (A19) $$

Clearly the first product within brackets does not depend on $\vec{x}_{\mathcal{N}\setminus\{k_1, \dots, k_n\}}$; the last term$^{22}$ $\tilde{p}((k_{n+1})|\cdot, \cdot, \cdot) := \sum_{a_{k_{n+1}}} \tilde{p}((k_{n+1}), a_{k_{n+1}}|\cdot, \cdot, \cdot)$ also clearly does not depend on $\vec{x}_{\mathcal{N}\setminus\{k_1, \dots, k_{n+1}\}}$, and is further required (from Eq. (A17)) not to depend on $x_{k_{n+1}}$. All in all, $p((k_1, \dots, k_n, k_{n+1}), \vec{a}_{k_1, \dots, k_n} | \vec{x})$ does not depend on $\vec{x}_{\mathcal{N}\setminus\{k_1, \dots, k_n\}}$, as required in Eq. (3).

* Proof that (3) ⇒ (A17): From a decomposition as in Eq. (3), one can define $\tilde{p}((k_1), a_{k_1} | x_{k_1}) := p((k_1), a_{k_1} | \vec{x})$ (which indeed only depends on $x_{k_1}$) and (for $n = 2, \dots, N$)$^{23}$ $\tilde{p}((k_n), a_{k_n} | (k_1, \dots, k_{n-1}), \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}) := p((k_1, \dots, k_n), \vec{a}_{k_1, \dots, k_n} | \vec{x})/p((k_1, \dots, k_{n-1}), \vec{a}_{k_1, \dots, k_{n-1}} | \vec{x})$ (which indeed only depends on the inputs $\vec{x}_{k_1, \dots, k_n}$). It is easy to see that these are normalised probability distributions whose product gives $p(\pi = (k_1, \dots, k_N), \vec{a}|\vec{x})$ as in the second line of Eq. (A17), and such that (for each $n$) $\sum_{a_{k_n}} \tilde{p}((k_n), a_{k_n} | \cdot, \cdot, \cdot)$ does not depend on $x_{k_n}$.

<footnote>$^{22}$ In order to lighten the notations we sometimes write $\tilde{p}((k_{n+1}), a_{k_{n+1}} | \cdot, \cdot, \cdot)$ for $\tilde{p}((k_{n+1}), a_{k_{n+1}} | (k_1, \dots, k_n), \vec{x}_{k_1, \dots, k_{n+1}}, \vec{a}_{k_1, \dots, k_n})$.</footnote>

<footnote>$^{23}$ We once again assume for simplicity that the denominators are nonzero; the terms for which these are zero do not contribute to the decomposition of $p(\vec{a}|\vec{x})$.</footnote>
The proofs that (A18) ⇒ (3) and (3) ⇒ (A18) are quite similar: from Eq. (A18) one easily obtains re-
cursively that $p((k_1, \dots, k_n, k_{n+1}), \vec{a}_{k_1, \dots, k_n} | \vec{x}) = \prod_{j=0}^{n} \hat{p}((k_{j+1}), a_{k_j} | (k_1, \dots, k_j), \vec{x}_{k_1, \dots, k_j}, \vec{a}_{k_1, \dots, k_{j-1}})$, which clearly
does not depend on $\vec{x}_{\mathcal{N}\setminus\{k_1, \dots, k_n\}}$; from Eq. (3), one can define the normalised probability distributions
$\hat{p}((k_1)) := p((k_1) | \vec{x})$ (which indeed does not depend on $\vec{x}$), $\hat{p}((k_{n+1}), a_{k_n} | (k_1, \dots, k_n), \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}) :=$
$p((k_1, \dots, k_n, k_{n+1}), \vec{a}_{k_1, \dots, k_n} | \vec{x})/p((k_1, \dots, k_n), \vec{a}_{k_1, \dots, k_{n-1}} | \vec{x})$ (which indeed only depends on the inputs $\vec{x}_{k_1, \dots, k_n}$), and
$\hat{p}(a_{k_N} | (k_1, \dots, k_N), \vec{x}, \vec{a}_{\mathcal{N}\setminus k_N}) := p((k_1, \dots, k_N), \vec{a} | \vec{x})/p((k_1, \dots, k_N), \vec{a}_{\mathcal{N}\setminus k_N} | \vec{x})$, whose product reproduces Eq. (A18).

4. Equivalent definitions for correlations with non-influenceable causal orders

Recall that we defined correlations with non-influenceable causal order (Eq. (12)) by referring to our definition of
causal correlations based on decompositions of the form $p(\vec{a}|\vec{x}) = \sum_{\pi} p(\pi, \vec{a}|\vec{x})$.

One could however also refer to Oreshkov and Giarmatzi's definition, namely by defining correlations with NIO as
those with a decomposition of the form $p(\vec{a}|\vec{x}) = \sum_{\kappa} p(\kappa, \vec{a}|\vec{x})$, as in (A7), which further satisfies

$$
\forall \kappa, p(\kappa|\vec{x}) \text{ does not depend on } \vec{x}. \qquad (A20)
$$

It is however easy to see, following the previous subsection, that the two definitions are equivalent. Indeed a total order $\pi$ is a particular case of an SPO $\kappa$, so that if a decomposition of the form $p(\vec{a}|\vec{x}) = \sum_{\pi} p(\pi, \vec{a}|\vec{x})$ (satisfying Eq. (3)) with $p(\pi|\vec{x})$ being independent of $\vec{x}$ exists, then this readily provides a decomposition of the form $p(\vec{a}|\vec{x}) = \sum_{\kappa} p(\kappa, \vec{a}|\vec{x})$ (satisfying Eq. (A7), as we have seen before) with $p(\kappa|\vec{x})$ that does not depend on $\vec{x}$. Conversely, if a decomposition of the form $p(\vec{a}|\vec{x}) = \sum_{\kappa} p(\kappa, \vec{a}|\vec{x})$ (satisfying Eq. (A7)) exists, then we have just seen above how to extend each SPO $\kappa$ to a total order $\pi$, and obtain a decomposition $p(\vec{a}|\vec{x}) = \sum_{\pi} p(\pi, \vec{a}|\vec{x})$ as in Eq. (A16), with $p(\pi, \vec{a}|\vec{x}) = \sum_{\kappa \text{ s.t. } \pi_{\kappa}=\pi} p(\kappa, \vec{a}|\vec{x})$ satisfying Eq. (3); if $p(\kappa|\vec{x})$ does not depend on $\vec{x}$, then neither does the distribution $p(\pi|\vec{x})$ thus obtained.

Appendix B: Tripartite causal correlations

1. The “simplest” tripartite scenario with dynamical causal order

Consider a tripartite scenario in which the three parties A, B, C have binary inputs x, y, z = 0, 1, party A has no output, while parties B and C have a binary output b, c = 0, 1 only when their input is 1 (B and C are in the so-called “lazy scenario”). This scenario is simple enough that the polytopes of causal correlations ($\mathcal{P}_{\text{causal}}$), of correlations with static causal order ($\mathcal{P}_{\text{convFO}}$), as well as of all valid probability distributions ($\mathcal{P}_{\text{all}}$) can be fully characterised:

* The causal polytope $\mathcal{P}_{\text{causal}}$ has 144 vertices: 112 of them are compatible with a fixed causal order—of the form $p(b, c|x, y, z) = \delta_{b, y\beta_x}\delta_{c, z\gamma_{x,y}}$ or $p(b, c|x, y, z) = \delta_{b, y\beta_{x,z}}\delta_{c, z\gamma_{x,z}}$, or both, for some $\beta_{x,(z)}, \gamma_{x,(y)} = 0, 1$—and 32 of them feature dynamical causal order—of the form $p(b, c|x, y, z) = \delta_{x,0}\delta_{b, y\beta_0}\delta_{c, z\gamma_{0,y}} + \delta_{x,1}\delta_{b, y\beta_{1,z}}\delta_{c, z\gamma_{1,z}}$ or $p(b, c|x, y, z) = \delta_{x,1}\delta_{b, y\beta_1}\delta_{c, z\gamma_{1,y}} + \delta_{x,0}\delta_{b, y\beta_{0,z}}\delta_{c, z\gamma_{0,z}}$, with $\beta_{x,z}$ and $\gamma_{x,y}$ having a nontrivial dependence on $z$ and $y$, resp.

Solving the facet enumeration problem, we find that $\mathcal{P}_{\text{causal}}$ has 8 facets of the “Lazy Guess Your Neighbour’s Input” (LGYNI) [34] form$^{24}$

$$
p(b=c=yz|x) \le \frac{3}{4} \qquad (B1)
$$

(for some fixed value $x$, with $p(b=c=yz|x) := \frac{1}{4} \sum_{y,z} p(b=c=yz|x,y,z)$), in addition to 8 trivial facets of the form $p(b|x,y=1,z) \ge 0$ and 8 trivial facets of the form $p(b,c|x,y=z=1) \ge 0$.

* The polytope $\mathcal{P}_{\text{convFO}}$ only has the 112 vertices compatible with a fixed order given above. We find that it has the same facets as $\mathcal{P}_{\text{causal}}$, plus 8 facets of the form

$$
I_3 := p(x=0, c=yz) + p(x=1, b=yz) \le \frac{7}{8}, \qquad (B2)
$$

<footnote n="24">24 Here we only write explicitly a single representative for each type of facet. The other facets “of the same form” are obtained by exchanging the parties B and C, by flipping A’s input x, and/or by flipping B and/or C’s outputs when their input is 1.</footnote>
as in Eqs. (6)–(7) of the main text.

Let us present here a direct proof of the latter inequality. Consider a fixed order in which $B$ comes before $C$, so that $p(b|x, y, z)$ does not depend on $z$: we shall write $p(b|x, y, z) = p(b|x, y, \not z)$. We then have

$$ 
\begin{aligned}
I_3 &:= p(x=0, c=yz) + \underbrace{p(x=1, b=yz)}_{\le p(x=0)=\frac{1}{2}} + \underbrace{p(b=yz|x=1, y,z)}_{=\frac{1}{8}\sum_{y,z} p(b=yz|x=1, y,z)} \\
&\le \frac{1}{2} + \frac{1}{8} \sum_{z=0,1} \underbrace{[p(b=0|x=1, y=0, \not z) + p(b=z|x=1, y=1, \not z)]}_{\le 1} \le \frac{1}{2} + \frac{1}{4} + \frac{1}{8} = \frac{7}{8}. \quad (B3)
\end{aligned}
$$

The same bound holds, by symmetry, for any fixed order in which $C$ comes before $B$, and by linearity, for any convex combination of fixed orders: $I_3 \le_{\text{convFO}} \frac{7}{8}$.

* The polytope $P_{\text{all}}$ of all valid probability distributions is only delimited by the 16 trivial facets of the form $p(b|x, y=1, z) \ge 0$ and $p(b, c|x, y=1, z) \ge 0$. Solving the vertex enumeration problem, we find that it has the same 144 vertices as $P_{\text{causal}}$, plus 112 non-causal vertices that feature 2-way signalling, of the form $p(b, c|x, y, z) = \delta_{b,y\beta_{x,z}}\delta_{c,z\gamma_{x,y}}$, with both $\beta_{0,z}$ and $\gamma_{0,y}$, and/or both $\beta_{1,z}$ and $\gamma_{1,y}$, having a nontrivial dependence on $z$ and $y$, resp.

Notice that the scenario considered here is the “smallest” one—in the sense of minimising the number of parties and the number of inputs and outputs for each party individually$^{25}$—that can feature dynamical causal order. With two parties causal correlations indeed reduce to convex mixtures of the two possible orders as in Eq. (1); if one of the three parties had no input then it could always be considered to come last,$^{26}$ and causal correlations would reduce to convex mixtures of the two possible orders for the other two parties; and if a second party had no output then all probability distributions (for just the single remaining output) could be obtained causally, with the two parties with no output coming first. It is in fact rather remarkable that the dynamical property appears already in a tripartite scenario where one of the parties has no output.

## 2. $P_{\text{NIO}}$ and $P_{\text{NIO}'}$ reduce to $P_{\text{convFO}}$ for $N=3$

While, as just seen, a tripartite scenario can exhibit dynamical causal order, we show here that it cannot exhibit “dynamical but non-influenceable causal order”—that is, correlations with non-influenceable causal order (in $P_{\text{NIO}}$) reduce to convex mixtures of correlations with fixed orders (i.e., they are in $P_{\text{convFO}}$).

To see this, notice that for $N=3$, the causality conditions of Eq. (3) imply in particular that for all $\pi = (k_1, k_2, k_3)^{,27}$

$$ 
\begin{aligned}
p((k_1, k_2), a_{k_1} | \vec{x}) &= p(\pi, a_{k_1} | \vec{x}) \text{ does not depend on } \vec{x}_{k_2, k_3} \\
\text{and } p((k_1, k_2, k_3), a_{k_1}, a_{k_2} | \vec{x}) &= p(\pi, a_{k_1}, a_{k_2} | \vec{x}) \text{ does not depend on } x_{k_3}.
\end{aligned}
\quad (B4)
$$

Assuming the non-influenceability condition of Eq. (12) and writing

$$ p(\vec{a}|\vec{x}) = \sum_{\pi} p(\pi, \vec{a}|\vec{x}) = \sum_{\pi} p(\pi) p(\vec{a}|\vec{x}, \pi), \quad (B5) $$

<footnote>$^{25}$ Note however that one could also consider even “smaller” scenarios where certain combinations of inputs, for the different parties, are further restricted. In fact, the expression $I_3$ does not involve (in any nontrivial way) terms with $(x, z) = (0, 0)$, nor with $(x, y) = (1, 0)$. Hence one can already distinguish dynamical orders in scenarios where these combinations of inputs never appear.</footnote>

<footnote>$^{26}$ More specifically: if one party, say $A_N$, has no input, then starting from a probability distribution $p(\pi = (k_1, \dots, k_N), \vec{a}|\vec{x})$ one can define $p'(\pi = (k_1, \dots, k_{N-1}, N), \vec{a}|\vec{x}) := \sum_{i=1}^N p(\pi = (k_1, \dots, k_{i-1}, N, k_i, \dots, k_{N-1}), \vec{a}|\vec{x})$, such that party $A_N$ always comes last in $\pi = (k_1, \dots, k_{N-1}, N)$.</footnote>

<footnote>Similarly, if one party, say $A_1$, has no output, then starting from $p(\pi = (k_1, \dots, k_N), \vec{a}|\vec{x})$ one can define $p'(\pi = (1, k_2, \dots, k_N), \vec{a}|\vec{x}) := \sum_{i=1}^N p(\pi = (k_2, \dots, k_i, 1, k_{i+1}, \dots, k_N), \vec{a}|\vec{x})$, such that party $A_1$ always comes first in $\pi = (1, k_2, \dots, k_N)$.</footnote>

<footnote>One can verify that in both cases, if the original distribution $p(\pi, \vec{a}|\vec{x})$ satisfies the causal constraints of Eq. (3), then so does $p'(\pi, \vec{a}|\vec{x})$; if $p(\pi, \vec{a}|\vec{x})$ satisfies the NIO constraints of Eq. (12), then so does $p'(\pi, \vec{a}|\vec{x})$; and if $p(\pi, \vec{a}|\vec{x})$ satisfies the NIO' constraints of Eq. (13), then so does $p'(\pi, \vec{a}|\vec{x})$.</footnote>

<footnote>$^{27}$ Notice that the following argument does not work in general for $N \ge 4$—unless one party has no input or one party has no output, using the observation made in the previous footnote—because $p((k_1, k_2), a_{k_1}|\vec{x})$ cannot be readily identified with $p(\pi, a_{k_1}|\vec{x})$ as we do in Eq. (B4), and the terms $p(\vec{a}|\vec{x}, \pi)$ in Eq. (B5) are in general not compatible with the causal order $\pi$.</footnote>

<footnote>As an explicit counter-example, one can take for instance the NIO correlation in Eq. (C20) of the next appendix, with its causal decomposition as proposed just below Eq. (C20). For these one gets $p(a, b, c, d|x, y, z, t, \pi=(A, B, C, D)) = \delta_{a=b=xy} \delta_{c,0} \delta_{d,zt}$ and $p(a, b, c, d|x, y, z, t, \pi=(A, B, D, C)) = \delta_{a,x\bar{y}} \delta_{b,\bar{x}y} \delta_{d,0} \delta_{c,zt}$ (with $\bar{x} := 1-x, \bar{y} := 1-y$), which are not compatible with any fixed causal order.</footnote>
we then have that, for $\pi = (k_1, k_2, k_3)$,

$$ 
\begin{aligned}
p(a_{k_1}|\vec{x}, \pi) &= \frac{p(\pi, a_{k_1}|\vec{x})}{p(\pi)} \quad \text{does not depend on } \vec{x}_{k_2,k_3}, \\
p(a_{k_1}, a_{k_2}|\vec{x}, \pi) &= \frac{p(\pi, a_{k_1}, a_{k_2}|\vec{x})}{p(\pi)} \quad \text{does not depend on } x_{k_3},
\end{aligned} 
\quad (B6) $$

so that $p(\vec{a}|\vec{x}, \pi)$ is compatible with the fixed causal order defined by $\pi$, and Eq. (B5) indeed provides a convex decomposition of $p(\vec{a}|\vec{x})$ onto correlations compatible with fixed causal orders.

We further note that for $N = 3$, the “non-influenceable coarse-grained order” condition of Eq. (13) reduces to the mere “non-influenceable order” condition of Eq. (12) (since Eq. (13) implies that $p((k_1, k_2, k_3)|\vec{x}) = p((k_1, k_2)|\vec{x}) = p((\{k_1\}, \{k_2\})|\vec{x})$ does not depend on $\vec{x}$). Hence, $P_{\text{NIO}}$ also reduces in the tripartite case to $P_{\text{convFO}}$.

## Appendix C: Proofs of the different causal bounds on $I_4 := p(a=b=xy, d=zt) + p(\neg(a=b=xy), c=zt)$

We prove in this Appendix the various causal bounds on the expression $I_4$ that we introduced in the main text to distinguish between correlations in $P_{\text{convFO}}$, $P_{\text{NIO}}$, $P_{\text{NIO}'}$ and $P_{\text{causal}}$.

Recall that we consider here a 4-partite scenario with parties denoted A, B, C, D, with binary inputs $x, y, z, t = 0, 1$, each party having a trivial output $a, b, c, d = 0$ if their input is 0, or a binary output $a, b, c, d = 0, 1$ if their input is 1 (the so-called “lazy scenario”). This is the “smallest” scenario (with the minimal number of parties, and of inputs and outputs for each party individually$^{28}$) in which one can find correlations with dynamical but non-influenceable causal order: if one of the four parties has no output or no input at all, then using the observation from Footnote 26, a similar argument to that for $N = 3$ parties (just above) shows that correlations in $P_{\text{NIO}}$ and $P_{\text{NIO}'}$ are necessarily convex combinations of correlations with fixed order (cf also Footnote 27).

### 1. For (convex mixtures of) fixed orders: $I_4 \le_{\text{convFO}}^{15}$

By linearity and convexity, to obtain the bound on $I_4$ for correlations in $P_{\text{convFO}}$, it is sufficient to calculate the bound for each possible fixed order independently. Consider therefore a correlation $p(a, b, c, d|x, y, z, t)$ compatible with a given fixed order $\pi$ (described as a permutation of the parties). We will first distinguish whether $C$ comes before or after $D$ in $\pi$:

* if $C$ comes before $D$ in $\pi$, then let us write

$$ 
\begin{aligned}
I_4 &= p(a=b=xy, d=zt) + p(\neg(a=b=xy), c=zt) \\
&\le p(a=b=xy) + p(\neg(a=b=xy), c=zt) \\
&= \frac{1}{16} \sum_{x,y,z,t=0,1} [p(a=b=xy|x,y,z,t) + p(\neg(a=b=xy), c=zt|x,y,z,t)] \\
&= \frac{1}{16} \sum_{x,y,t} [p(a=b=xy|x,y,z=0,t) + p(\neg(a=b=xy), e=0|x,y,z=0,t) \\
&\qquad + p(a=b=xy|x,y,z=1,t) + p(\neg(a=b=xy), c=t|x,y,z=1,t)] \\
&= \frac{1}{16} \sum_{x,y,t} [1 + p(a=b=xy|x,y,z=1,t) + p(\neg(a=b=xy), c=t|x,y,z=1,t)],
\end{aligned} 
\quad (C1) $$

where we used the fact that for an input 0 (here, $z=0$), the output is necessarily 0 ($c=0$).

Let us further distinguish here the different cases according to which party comes last in $\pi$:

<footnote>$^{28}$ Note, as in Footnote 25, that one can in fact still further restrict the number of allowed combinations of inputs for the different parties. E.g., the expression $I_4$ does not involve (in any nontrivial way) terms with $(z, t) = (0, 0)$, nor with $(x, y, z, t) = (0, 0, 1, 0)$. Hence one can already distinguish correlations with dynamical but non-influenceable causal order in scenarios where these combinations of inputs never appear. Restricting to such smaller spaces of correlations (and perhaps also restricting to the probabilities of certain combinations of outputs only, e.g. only those that appear nontrivially in $I_4$), may help to get a better characterisation of the different polytopes of correlations under consideration.</footnote>
– If $D$ comes last in $\pi$, then<fnref n="29" />

$$ 
\begin{aligned}
I_4 &\le \frac{1}{16} \sum_{x,y,t} [1 + p(a=b=xy|x,y,z=1,t) + p(\neg(a=b=xy), c=t|x,y,z=1,t)] \\
&= \frac{1}{16} \sum_{x,y} [2 + 2p(a=b=xy|x,y,z=1) + p(\neg(a=b=xy)|x,y,z=1)] \\
&= \frac{1}{16} \sum_{x,y} [3 + p(a=b=xy|x,y,z=1)] = \frac{1}{4} \left(3 + \frac{1}{4} \sum_{x,y} p(a=b=xy|x,y,z=1)\right) \le \frac{1}{4} \left(3 + \frac{3}{4}\right) = \frac{15}{16}, \quad (C2)
\end{aligned}
$$

where the last inequality just follows from the LGYNI inequality [34] for A and B (for which conditioning on the input $z=1$ of another party does not change the causal bound).

– If $B$ comes last in $\pi$, then

$$ 
\begin{aligned}
I_4 &\le \frac{1}{16} \sum_t \left[ \underbrace{4 + p(a=b=0|x=y=0,z=1,t)}_{1} + \underbrace{p(\neg(a=b=0), c=t|x=y=0,z=1,t)}_{0} \right. \\
&\qquad + \underbrace{p(a=b=0|x=0,y=1,z=1,t)}_{\le p(\neg(a=b=0)|x=0,y=1,z=1,t)} + \underbrace{p(\neg(a=b=0), c=t|x=0,y=1,z=1,t)}_{p(a=1,c=t|x=1,y=0,z=1,t)} \\
&\qquad + \underbrace{p(a=b=0|x=1,y=0,z=1,t)}_{p(a=0|x=1,y=0,z=1,t)} + \underbrace{p(\neg(a=b=0), c=t|x=1,y=0,z=1,t)}_{p(a=1,c=t|x=1,y=0,z=1,t)} \\
&\qquad \left. + \underbrace{p(a=b=1|x=y=1,z=1,t) + p(\neg(a=b=1), c=t|x=y=1,z=1,t)}_{p(a=b=1,c=\bar{t}|x=y=1,z=1,t)+p(c=t|x=\bar{t}=1,z=1,t)} \right] \\
&\le \frac{1}{16} \sum_t \left[ 6 + p(a=0|x=z=1,t) + p(a=1,c=t|x=z=1,t) \right. \\
&\qquad \left. + \underbrace{p(a=b=1,c=\bar{t}|x=y=z=1,t)}_{\le p(a=1,c=\bar{t}|x=\bar{t}=z=1,t)} + p(c=t|x=z=1) \right] \\
&\le \frac{1}{16} \sum_t \left[ 7 + p(c=t|x=z=1) \right] = \frac{15}{16} \quad (C3)
\end{aligned}
$$

(where we used the notation $\bar{t} := 1 - t$).

– If $A$ comes last in $\pi$, then by symmetry (with respect to $A \leftrightarrow B$), we also get the bound $I_4 \le \frac{15}{16}$.

• if $D$ comes before $C$ in $\pi$, then let us write (considering the case where $x = y = 0$ separately, and noting that $a = b = xy$ always holds in this case):

$$ 
\begin{aligned}
I_4 &= p(a=b=xy,d=zt) + p(\neg(a=b=xy),c=zt) \\
&= \frac{1}{16} \left[ \sum_{z,t=0,1} p(d=zt|x=y=0,\neq,t) \right. \\
&\qquad + \sum_{x,y,z,t=0,1: (x,y)\neq(0,0)} \left[ \underbrace{p(a=b=xy,d=zt|x,y,z,t) + p(\neg(a=b=xy),c=zt|x,y,z,t)}_{\le 1} \right] \\
&\le \frac{1}{16} \left[ \underbrace{\sum_z p(d=0|x=y=0,t=0)}_{2} + \underbrace{\sum_z p(d=z|x=y=0,t=1)}_{1} + 12 \right] = \frac{15}{16}. \quad (C4)
\end{aligned}
$$

All in all, for any fixed causal order, and by linearity for any convex combination of fixed causal orders, we obtained the bound

$$ I_4 \le \frac{15}{\text{convFO} 16}, \quad (C5) $$

<footnote n="29">²⁹ In the proofs we shall indicate that a probability does not depend on a given input, according to some causality condition, by striking out the corresponding input; on the subsequent lines we will simply not write that input anymore.</footnote>
as in Eq. (15).

This bound can be reached for instance by the correlation (compatible with any fixed order where C comes before D) $p(a, b, c, d|x, y, z, t) = \delta_{a,0} \delta_{b,0} \delta_{c,0} \delta_{d,zt}$.

## 2. For correlations with non-influenceable causal orders: $I_4 \le_{\text{NIO}}^{31}$

Consider a causal correlation $p(\vec{a}|\vec{x})$, for which there exists $p(\pi, \vec{a}|\vec{x})$ that satisfies Eq. (3). One can then write

$$I_4 = \sum_{\pi} I_{\pi} \quad \text{with} \quad I_{\pi} := p(\pi, a = b = xy, d = zt) + p(\pi, \neg(a = b = xy), c = zt). \qquad (C6)$$

Following similar calculations as in the different cases with fixed order above, we see that:

* If C comes before D in $\pi$, then (similarly to Eq. (C1))

$$I_{\pi} \le \frac{1}{16} \sum_{x,y,t} \left[ p(\pi|x, y, z = 0, t) + p(\pi, a = b = xy|x, y, z = 1, t) + p(\pi, \neg(a = b = xy), c = t|x, y, z = 1, t) \right]. \qquad (C7)$$

- If D comes last in $\pi$, then it follows from the causality constraints of Eq. (3) that $p(\pi, a, b, c|x, y, z, t)$, and hence $p(\pi, a, b|x, y, z, t)$ and $p(\pi|x, y, z, t)$, do not depend on $t$. We then have (similarly to Eq. (C2))

$$\begin{aligned} I_{\pi} &\le \frac{1}{16} \sum_{x,y,t} \left[ p(\pi|x, y, z=0, t) + p(\pi, a=b=xy|x, y, z=1, t) + p(\pi, \neg(a=b=xy), c=t|x, y, z=1, t) \right] \\ &= \frac{1}{16} \sum_{x,y} \left[ 2p(\pi|x, y, z=0) + p(\pi|x, y, z=1) + p(\pi, a=b=xy|x, y, z=1) \right] \\ &= \frac{1}{8} \sum_{x,y,z} p(\pi|x, y, z) - \frac{1}{16} \sum_{x,y} p(\pi, \neg(a=b=xy)|x, y, z=1). \end{aligned} \qquad (C8)$$

If, in addition, A comes before B in $\pi$, then we have that

$$\begin{aligned} & \sum_{x,y} p(\pi, \neg(a=b=xy)|x,y,z=1) \\ &= p(\pi, a=1|x=1,y=0,z=1) + \underbrace{p(\pi, b=1|x=0,y=1,z=1)}_{\ge 0} + \underbrace{p(\pi, \neg(a=b=1)|x=1,y=1,z=1)}_{\ge p(\pi,a=0|x=1,y=1,z=1)} \\ & \ge \sum_{y} p(\pi, a=\bar{y}|x=1,y,z=1), \end{aligned} \qquad (C9)$$

so that

$$I_{\pi} \le \frac{1}{8} \sum_{x,y,z} p(\pi|x, y, z) - \frac{1}{16} \sum_{y} p(\pi, a = \bar{y}|x=1, y, z=1). \qquad (C10)$$

Similarly, if B comes before A in $\pi$ instead (still in addition to D coming last), then

$$I_{\pi} \le \frac{1}{8} \sum_{x,y,z} p(\pi|x, y, z) - \frac{1}{16} \sum_{x} p(\pi, b = \bar{x}|x, y=1, z=1). \qquad (C11)$$
– If B comes last in $\pi$, then $p(\pi, a, c|x, y, z, t)$ does not depend on $y$ and we have (similarly to Eq. (C3))

$$
\begin{align*}
I_{\pi} \le \frac{1}{16} \sum_{t} & \left[ p(\pi|x=0, y=\emptyset, z=0, t) + p(\pi|x=0, y=\emptyset, z=1, t) \right. \\
& \left. \qquad + p(\pi|x=0, y=\text{1}, z=0, t) + p(\pi|x=0, y=\text{1}, z=1, t) \right. \\
& \left. \qquad + p(\pi|x=1, y=\emptyset, z=0, t) + p(\pi, a=0|x=1, y=\emptyset, z=1, t) + p(\pi, a=1, c=t|x=1, y=\emptyset, z=1, t) \right. \\
& \left. \qquad + p(\pi|x=1, y=\text{1}, z=0, t) + p(\pi, a=1, c=\bar{t}|x=1, y=\text{1}, z=1, t) + p(\pi, c=t|x=1, y=\text{1}, z=1, t) \right] \\
&= \frac{1}{16} \sum_{t} \left[ 2p(\pi|x=z=0, t) + 2p(\pi|x=0, z=1, t) + 2p(\pi|x=1, z=0, t) \right. \\
& \qquad \left. \qquad + p(\pi|x=z=1, t) + p(\pi, c=t|x=z=1, t) \right] \\
&= \frac{1}{8} \sum_{x,z,t} p(\pi|x, z, t) - \frac{1}{16} \sum_{t} p(\pi, c=\bar{t}|x=z=1, t). \tag{C12}
\end{align*}
$$

– If A comes last in $\pi$, then by symmetry the same bound holds (just replacing $x$ by $y$ in the above expression):

$$ I_{\pi} \le \frac{1}{8} \sum_{y,z,t} p(\pi|y,z,t) - \frac{1}{16} \sum_{t} p(\pi,c=\bar{t}|y=z=1,t). \quad (C13) $$

• If D comes before C in $\pi$, then (similarly to Eq. (C4))

$$
\begin{align}
I_{\pi} \le \frac{1}{16} \left[ \sum_{z=0,1} \left[ p(\pi|x=y=0,z,t=0) + p(\pi,d=z|x=y=0,z,t=1) \right] + \sum_{\substack{x,y,z,t=0,1: \\ (x,y) \ne (0,0)}} p(\pi|x,y,z,t) \right] \nonumber \\
&= \frac{1}{16} \sum_{x,y,z,t} p(\pi|x,y,z,t) - \frac{1}{16} \sum_{z} p(\pi,d=\bar{z}|x=y=0,z,t=1). \tag{C14}
\end{align}
$$

Now, it follows from the causality constraints of Eq. (3) that $p(\pi:D\prec C, d|x, y, z, t) := \sum_{\pi:D\prec C} p(\pi, d|x, y, z, t)$ and $p(\pi:D\prec C|x, y, z, t) := \sum_{\pi:D\prec C} p(\pi|x, y, z, t)$ do not depend on $z$.<fnref n="30" /> We then have (again, similarly to Eq. (C4))

$$
\begin{align}
\sum_{\pi:D\prec C} I_{\pi} \le \frac{1}{16} \sum_{x,y,z,t} p(\pi:D\prec C|x,y,\not\prec,t) - \frac{1}{16} \sum_{z} p(\pi:D\prec C, d=\bar{z}|x=y=0,\not\prec,t=1) \nonumber \\
&= \frac{1}{8} \sum_{x,y,t} p(\pi:D\prec C|x,y,t) - \frac{1}{16} p(\pi:D\prec C|x=y=0,t=1). \tag{C15}
\end{align}
$$

All in all, we obtain

$$
\begin{align}
I_4 &= \sum_{\pi} I_{\pi} = \sum_{\substack{\pi:D \text{ last,} \\ A \prec B}} I_{\pi} + \sum_{\substack{\pi:D \text{ last,} \\ B \prec A}} I_{\pi} + \sum_{\substack{\pi:C \prec D, \\ A \text{ last}}} I_{\pi} + \sum_{\substack{\pi:C \prec D, \\ B \text{ last}}} I_{\pi} + \sum_{\pi:D \prec C} I_{\pi} \nonumber \\
&\le \sum_{\substack{\pi:D \text{ last,} \\ A \prec B}} \left[ \frac{1}{8} \sum_{x,y,z} p(\pi|x,y,z) - \frac{1}{16} \sum_{y} p(\pi, a=\bar{y}|x=1,y,z=1) \right] + \sum_{\substack{\pi:D \text{ last,} \\ B \prec A}} \left[ \frac{1}{8} \sum_{x,y,z} p(\pi|x,y,z) - \frac{1}{16} \sum_{x} p(\pi, b=\bar{x}|x,y=z=1) \right] \nonumber \\
&\quad + \sum_{\substack{\pi:C \prec D, \\ B \text{ last}}} \left[ \frac{1}{8} \sum_{x,z,t} p(\pi|x,z,t) - \frac{1}{16} \sum_{t} p(\pi, c=\bar{t}|x=z=1,t) \right] + \sum_{\substack{\pi:C \prec D, \\ A \text{ last}}} \left[ \frac{1}{8} \sum_{y,z,t} p(\pi|y,z,t) - \frac{1}{16} \sum_{t} p(\pi, c=\bar{t}|y=z=1,t) \right] \nonumber \\
&\quad + \frac{1}{8} \sum_{x,y,t} p(\pi:D \prec C|x,y,t) - \frac{1}{16} p(\pi:D \prec C|x=y=0,t=1) \nonumber \\
&= 1 - \frac{1}{16} \left( J_{C \prec D} + p(\pi:D \prec C|x=y=0,t=1) \right), \tag{C16}
\end{align}
$$

<footnote n="30">³⁰ As indicated by the conditions 'π:D<sub>C</sub>', the sums ∑<sub>π:D<sub>C</sub></sub> are over all permutations in which D comes before C. To see that p(π:D<sub>C</sub>, d|x, y, z, t) does not depend on z, one can write p(π:D<sub>C</sub>, d|x, y, z, t) = p((k₁, k₂, k₃) = (A, B, D), d|x, y, f, t) + p((k₁, k₂, k₃) = (B, A, D), d|x, y, f, t) + p((k₁, k₂) = (A, D), d|x, y, f, t) + p((k₁, k₂) = (B, D), d|f, y, f, t) + p((k₁, k₂) = (D), d|f, y, f, t), where all independencies (struck-out inputs) follow from Eq. (3).</footnote>
with

$$
\begin{align*}
J_{C\prec D} &:= \sum_{\substack{\pi:D \text{ last,} \\ A\prec B}} \sum_y p(\pi, a = \bar{y} | x = 1, y, z = 1) + \sum_{\substack{\pi:D \text{ last,} \\ B\prec A}} \sum_x p(\pi, b = \bar{x} | x, y = z = 1) \\
&\quad + \sum_{\substack{\pi:C\prec D, \\ B \text{ last}}} \sum_t p(\pi, c = \bar{t} | x = z = 1, t) + \sum_{\substack{\pi:C\prec D, \\ A \text{ last}}} \sum_t p(\pi, c = \bar{t} | y = z = 1, t) \\
&= \sum_y \underbrace{p(\pi = (A, B, C, D), a = \bar{y} | x = 1, y, z = 1)}_{\ge p(\pi = (A, B, C, D) | x=1, y) - p((k_1, k_2) = (A, B), a=y | x=1, \not y)} + \sum_{\substack{\pi=(A,C,B,D), \\ (C,A,B,D)}} \underbrace{\frac{\sum_y p(\pi, a = \bar{y} | x = 1, \not y, z = 1)}{p(\pi | x=z=1)}}_{\phantom{\pi=(A,C,B,D)} p(\pi | x=1)} \\
&\quad + \sum_x \underbrace{p(\pi = (B, A, C, D), b = \bar{x} | x, y = \not z = 1)}_{\ge p(\pi = (B, A, C, D) | x, y=1) - p((k_1, k_2) = (B, A), b=x | \not x, y=1)} + \sum_{\substack{\pi=(B,C,A,D), \\ (C,B,A,D)}} \underbrace{\frac{\sum_x p(\pi, b = \bar{x} | \not x, y = z = 1)}{p(\pi | y=z=1)}}_{\phantom{\pi=(B,C,A,D)} p(\pi | y=1)} \\
&\quad + \sum_t p(\pi = (C, D, A, B), c = \bar{t} | \not y = z = 1, t) + \sum_{\substack{\pi=(C,A,D,B), \\ (A,C,D,B)}} \underbrace{\frac{\sum_t p(\pi, c = \bar{t} | x = z = 1, \not t)}{p(\pi | x=z=1)}}_{\phantom{\pi=(C,A,D,B)} p(\pi | x=1)} \\
&\quad + \sum_t p(\pi = (C, D, B, A), c = \bar{t} | y = z = 1, t) + \sum_{\substack{\pi=(C,B,D,A), \\ (B,C,D,A)}} \underbrace{\frac{\sum_t p(\pi, c = \bar{t} | y = z = 1, \not t)}{p(\pi | y=z=1)}}_{\phantom{\pi=(C,B,D,A)} p(\pi | y=1)} \\
&\ge \sum_y p(\pi = (A, B, C, D) | x = 1, y) + \sum_x p(\pi = (B, A, C, D) | x, y = 1) \\
&\quad - p((k_1, k_2) = (A, B) | x = 1) - p((k_1, k_2) = (B, A) | y = 1) \\
&\quad + p((k_1, k_2) = (A, C) | x = \not z = 1) + p((k_1, k_2) = (C, A) | \not y = z = 1) \\
&\quad + p((k_1, k_2) = (B, C) | y = \not z = 1) + p((k_1, k_2) = (C, B) | \not y = z = 1) \\
&\quad + \underbrace{\sum_t p((k_1, k_2) = (C, D), c = \bar{t} | z = 1, \not t)}_{p((k_1, k_2) = (C, D) | z=1)} \\
&= \sum_y p(\pi = (A, B, C, D) | x = 1, y) + \sum_x p(\pi = (B, A, C, D) | x, y = 1) \\
&\quad - p((k_1, k_2) = (A, B) | x = 1) - p((k_1, k_2) = (B, A) | y = 1) \\
&\quad + p((k_1, k_2) = (A, C) | x = 1) + p((k_1, k_2) = (B, C) | y = 1) + p((k_1) = (C) | z = 1), \tag{C17}
\end{align*}
$$

where we repeatedly used the causality constraints of Eq. (3) to get rid of some dependencies and simplify the expressions.

Note that we have not used the non-influenceable order (NIO) assumption of Eq. (12) yet: the derivations above hold for all causal correlations. Assuming it now—that is, assuming $p(\pi|x, y, z, t) = p(\pi)$—we then have:

$$
\begin{align}
J_{C\prec D} + p(\pi:D\prec C|x=y=0, t=1) &\ge \frac{1}{2} J_{C\prec D} + p(\pi:D\prec C) \nonumber \\
&\ge p(\pi = (A, B, C, D)) + p(\pi = (B, A, C, D)) - \frac{1}{2}p((k_1, k_2) = (A, B)) - \frac{1}{2}p((k_1, k_2) = (B, A)) \nonumber \\
&\quad + \frac{1}{2}p((k_1, k_2) = (A, C)) + \frac{1}{2}p((k_1, k_2) = (B, C)) + \frac{1}{2}p((k_1) = (C)) + p(\pi:D\prec C) \nonumber \\
&= p(\pi = (A, B, C, D) \lor (B, A, C, D)) + p((k_1, k_2) = (A, C) \lor (B, C)) + p((k_1) = (C)) + p(\pi:D\prec C) \nonumber \\
&\quad - \frac{1}{2} \underbrace{\left[ p((k_1, k_2) = (A, B) \lor (B, A) \lor (A, C) \lor (B, C)) + p((k_1) = (C)) \right]}_{\le 1} \ge \frac{1}{2}, \tag{C18}
\end{align}
$$
where we used the shorthand notations $p(\pi = (A, B, C, D) \lor (B, A, C, D)) = p(\pi = (A, B, C, D)) + p(\pi = (B, A, C, D))$, $p((k_1, k_2) = (A, C) \lor (B, C)) = p((k_1, k_2) = (A, C)) + p((k_1, k_2) = (B, C))$ etc. Recalling Eq. (C16), we then obtain, for correlations with NIO:

$$I_4 \le \frac{1}{16} \left( J_{C \prec D} + p(\pi:D \prec C | x = y = 0, t = 1) \right) \le \frac{31}{32}, \qquad (C19)$$

as in Eq. (16).

This bound can be reached for instance by the correlation

$$p(a, b, c, d|x, y, z, t) = \underbrace{\left\{ \begin{array}{ll} \delta_{a,0} & \text{if } x=0 \\ \frac{1}{2} & \text{if } x=1 \end{array} \right\}}_{p(a|x)} \underbrace{\left\{ \begin{array}{ll} \delta_{b,0} & \text{if } y=0 \\ \frac{1}{2} & \text{if } y=1, x=0 \\ \delta_{b,a} & \text{if } y=1, x=1 \end{array} \right\}}_{p(b|x,y,a)} \underbrace{\left\{ \begin{array}{ll} \frac{1}{2} \delta_{c,0} \delta_{d,zt} + \frac{1}{2} \delta_{d,0} \delta_{c,zt} & \text{if } x=y=0 \\ \left\{ \begin{array}{ll} \delta_{c,0} \delta_{d,zt} & \text{if } a=b=xy \\ \delta_{d,0} \delta_{c,zt} & \text{if } \neg(a=b=xy) \end{array} \right. & \text{if } \neg(x=y=0) \end{array} \right\}}_{p(c,d|x,y,z,t,a,b)}, \qquad (C20)$$

which can easily be seen to be causal. In fact, an explicit causal decomposition as in Eq. (3) can be obtained by taking $p(\pi, a, b, c, d|x, y, z, t)$ to be of the same form as $p(a, b, c, d|x, y, z, t)$ above, after just multiplying the terms $\delta_{c,0} \delta_{d,zt}$ by $\delta_{\pi,(A,B,C,D)}$ and the terms $\delta_{d,0} \delta_{c,zt}$ by $\delta_{\pi,(A,B,D,C)}$.31 For such a decomposition, it is then easy to see that $p(\pi = (A, B, C, D)|x, y, z, t) = p(\pi = (A, B, D, C)|x, y, z, t) = \frac{1}{2}$ does not depend on the inputs $x, y, z, t$, which indeed proves that the correlation is in $\mathcal{P}_{\text{NIO}}$—and not in $\mathcal{P}_{\text{convFO}}$, since it violates the bound $I_4 \le \frac{15}{16}$.

### 3. For correlations with non-influenceable coarse-grained causal orders: $I_4 \le \text{NIO}' \frac{47}{48}$

Let us now relax the NIO assumption, and just consider the “non-influenceable coarse-grained causal orders” (NIO') assumption of Eq. (13), that $p((K_{n-1}, k_n)|\vec{x}) = p((K_{n-1}, k_n))$ does not depend on $\vec{x}$. Note that it implies in particular, here, that

$$\begin{aligned} p(\pi:D \prec C | x = y = 0, t = 1) \\ = p((K_2, k_3) = (\{A, B\}, D)|x = y = 0, t = 1) + p((K_2, k_3) = (\{A, D\}, B)|x = y = 0, t = 1) \\ + p((K_2, k_3) = (\{B, D\}, A)|x = y = 0, t = 1) + p((K_2, k_3) = (\{A, D\}, C)|x = y = 0, t = 1) \\ + p((K_2, k_3) = (\{B, D\}, C)|x = y = 0, t = 1) + p((K_1, k_2) = (\{D\}, C)|x = y = 0, t = 1) = p(\pi:D \prec C) \end{aligned} \qquad (C21)$$

does not depend on the inputs $x, y, t$.

Coming back to Eq. (C17)—which, as we emphasised, holds for all causal correlations—we can now write (instead

<footnote n="31">31 One may notice that the marginal correlation $p(a, b|x, y) = \begin{cases} \delta_{a,0} \delta_{b,0} & \text{if } x = y = 0 \\ \frac{1}{2} \delta_{b,0} & \text{if } x = 1, y = 0 \\ \frac{1}{2} \delta_{a,b} & \text{if } x = y = 1 \end{cases}$ ; $\frac{1}{2} \delta_{a,0}$ if $x = 0, y = 1$ (which does not depend on $z, t$) is non-signalling—and in fact, even Bell-local [45] (as is any non-signalling correlation in the “lazy” scenario, where each party has nontrivial outputs for at most one input): $p(a, b|x, y) = \sum_{\lambda=0,1} \frac{1}{2} \delta_{a,\lambda x} \delta_{b,\lambda y}$—so one could also decompose this correlation onto different orders for A and B.</footnote>
of Eq. (C18))

$$
\begin{align*}
J_{C\prec D} + p(\pi:D\prec C|x=y=0, t=1) &\ge \frac{1}{3} J_{C\prec D} + p(\pi:D\prec C) \\
&\ge \frac{1}{3} \Biggl[ \begin{aligned}[t]
    &p(\pi = (A, B, C, D)|x=1, y=0) + p(\pi = (B, A, C, D)|x=0, y=1) + p((K_2, k_3) = (\{A, B\}, C)|x=y=1) \\
    &\quad - p((k_1, k_2) = (A, B)|x=1) - p((k_1, k_2) = (B, A)|y=1) \\
    &\quad + p((k_1, k_2) = (A, C)|x=1) + p((k_1, k_2) = (B, C)|y=1) + p((k_1) = (C)|z=1) + \\
    &\quad \phantom{p((k_1, k_2) = (A, C)|x=1)} \underbrace{3p(\pi:D\prec C)}_{\ge p(\pi:D\prec C)+2p((K_2, k_3) = (\{A, B\}, D))}
  \end{aligned} \Biggr] \\
&\ge \frac{1}{3} \Biggl[ \begin{aligned}[t]
    &\underbrace{p((K_2, k_3) = (\{A, B\}, C)) + p((k_1, k_2) = (A, C) \lor (B, C)) + p((k_1) = (C)) + p(\pi:D\prec C)}_{=1} \\
    &+ p((K_2, k_3) = (\{A, B\}, D)) - \underbrace{p((k_1, k_2) = (A, B)) - p(\pi = (A, B, C, D)|x=1, y=0)}_{p(\pi=(A,B,D,C)|x=1,y=0)} \\
    &+ p((K_2, k_3) = (\{A, B\}, D)) - \underbrace{p((k_1, k_2) = (B, A)) - p(\pi = (B, A, C, D)|x=0, y=1)}_{p(\pi=(B,A,D,C)|x=0,y=1)}
  \end{aligned} \Biggr] \\
&= \frac{1}{3} \Biggl[ 1 + p(\pi = (B, A, D, C)|x=1, y=0) + p(\pi = (A, B, D, C)|x=0, y=1) \Biggr] \ge \frac{1}{3}. \tag{C22}
\end{align*}
$$

Recalling again Eq. (C16), we then obtain, for correlations with non-influenceable coarse-grained causal orders:

$$I_4 \le 1 - \frac{1}{16} \left( J_{C\prec D} + p(\pi:D\prec C|x=y=0, t=1) \right) \stackrel{\text{NIO'}}{\le} \frac{47}{48}, \quad (C23)$$

as in Eq. (17).

This bound can be reached for instance by the correlation

$$p(a, b, c, d|x, y, z, t) = \frac{2}{3} \begin{cases} \delta_{a,0} \delta_{b,0} \delta_{c,0} \delta_{d,zt} & \text{if } x=0 \\ \frac{1}{2} \delta_{b,y} \begin{cases} \delta_{c,0} \delta_{d,zt} & \text{if } y=a \\ \delta_{d,0} \delta_{c,zt} & \text{if } y=\bar{a} \end{cases} & \text{if } x=1 \end{cases} + \frac{1}{3} \delta_{b,y} \delta_{a,xy} \begin{cases} \delta_{d,0} \delta_{c,zt} & \text{if } x=0 \\ \delta_{c,0} \delta_{d,zt} & \text{if } x=1 \end{cases}, \quad (C24)$$

which can easily be seen to be causal. To see that it is in $\mathcal{P}_{\text{NIO}}'$, notice that one can decompose it as

$$p((k_1, k_2, k_3, k_4), a, b, c, d|x, y, z, t) = \frac{2}{3} \delta_{(k_1, k_2),(A,B)} \begin{cases} \delta_{a,0} \delta_{b,0} \delta_{(k_3,k_4),(C,D)} \delta_{c,0} \delta_{d,zt} & \text{if } x=0 \\ \frac{1}{2} \delta_{b,y} \begin{cases} \delta_{(k_3,k_4),(C,D)} \delta_{c,0} \delta_{d,zt} & \text{if } y=a \\ \delta_{(k_3,k_4),(D,C)} \delta_{d,0} \delta_{c,zt} & \text{if } y=\bar{a} \end{cases} & \text{if } x=1 \\ + \frac{1}{3} \delta_{(k_1,k_2),(B,A)} \delta_{b,y} \delta_{a,xy} \begin{cases} \delta_{(k_3,k_4),(D,C)} \delta_{d,0} \delta_{c,zt} & \text{if } x=0 \\ \delta_{(k_3,k_4),(C,D)} \delta_{c,0} \delta_{d,zt} & \text{if } x=1 \end{cases}, & \text{if } x=1 \end{cases}, \quad (C25)$$

such that

$$p((k_1, k_2, k_3, k_4)|x, y, z, t) = \begin{cases} \frac{2}{3} \delta_{(k_1, k_2, k_3, k_4), (A, B, C, D)} + \frac{1}{3} \delta_{(k_1, k_2, k_3, k_4), (B, A, D, C)} & \text{if } x=0 \\ \frac{1}{3} \delta_{(k_1, k_2, k_3, k_4), (A, B, C, D)} + \frac{1}{3} \delta_{(k_1, k_2, k_3, k_4), (A, B, D, C)} + \frac{1}{3} \delta_{(k_1, k_2, k_3, k_4), (B, A, C, D)} & \text{if } x=1 \end{cases}. \quad (C26)$$

It is then easy to verify that $p((k_1) = (A)|x, y, z, t) = p((k_1, k_2) = (A, B)|x, y, z, t) = \frac{2}{3}$, $p((k_1) = (B)|x, y, z, t) = p((k_1, k_2) = (B, A)|x, y, z, t) = \frac{1}{3}$, $p((K_2, k_3) = (\{A, B\}, C)|x, y, z, t) = p((K_3, k_4) = (\{A, B, C\}, D)|x, y, z, t) = \frac{2}{3}$ and $p((K_2, k_3) = (\{A, B\}, D)|x, y, z, t) = p((K_3, k_4) = (\{A, B, D\}, C)|x, y, z, t) = \frac{1}{3}$ do not depend on $x, y, z, t$ (with all other probabilities $p((K_{n-1}, k_n)|\bar{x})$ being null), which indeed proves that the correlation is in $\mathcal{P}_{\text{NIO}}'$—and not in $\mathcal{P}_{\text{NIO}}$, since it violates the bound $I_4 < \frac{31}{32}$.