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

We conclude this appendix with the bound for general causal correlations, which is simply the trivial algebraic bound:

$$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)) = 1. \quad (C27)$$

An example of a causal correlation that indeed reaches this algebraic maximum is

$$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 (C28)$$

which can be decomposed as

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

in which the causal order between C and D depends on the product of inputs xy (indeed the causal order has to be “influenceable” so as to violate the previous bounds).

## Appendix D: Description and characterisation of our different classes of quantum circuits

In this appendix we provide more details on the description and characterisation of the different classes of quantum circuits with classical and quantum control of causal order considered in the paper. These are described within the wider framework of process matrices [3]. We start by recalling, for completeness, the validity constraints for general process matrices that the characterisations of some of our classes refer to.

### 1. Validity constraints for general process matrices

The process matrix framework was first introduced to characterise the set of all possible correlations that can be established (in a consistent manner) by a number of parties implementing operations that are locally described by the quantum formalism (as quantum instruments [24]), but without assuming a priori that these are applied in any specific, well-defined causal order [3]. Under some reasonable assumptions (in particular: dependency of the probabilities on the realised operations only rather than on the full quantum instruments; linearity of the probabilities to preserve the interpretation of probabilistic mixtures of operations and coarse-graining of outcomes), it was shown that all such correlations could be written in the form of the generalised Born rule of Eq. (22), for some “process matrix” $W \in \mathcal{L}(\mathcal{H}_{\mathcal{N}}^{A^I})$ (where $\mathcal{N} = \{1, \dots, N\}$ refers to the set of parties, each having input/output spaces $\mathcal{H}_{\mathcal{N}}^{A^I} / \mathcal{H}_{\mathcal{N}}^{A^O}$, and with $\mathcal{H}_{\mathcal{N}}^{A^I} = \bigotimes_{k \in \mathcal{N}} \mathcal{H}_{\mathcal{N}}^{A^I} = \bigotimes_{k \in \mathcal{N}} \mathcal{H}_{\mathcal{N}}^{A^I} \otimes \mathcal{H}_{\mathcal{N}}^{A^O}$).

Requiring that the probabilities thus obtained are nonnegative, even when the parties share other auxiliary systems and their instruments can also act on these, imposes that the process matrix must be positive semidefinite (PSD): $W \ge 0$. Recalling that the elements of a quantum instrument must sum to a trace-preserving (TP) map, and that the TP condition for a map $M_k : \mathcal{L}(\mathcal{H}_{\mathcal{N}}^{A^I}) \to \mathcal{L}(\mathcal{H}_{\mathcal{N}}^{A^O})$ translates in terms of its Choi matrix into $\text{Tr}_{A_k^O} M_k = 1$, then the requirement that the probabilities must be normalised, on the other hand, can be phrased as follows:

$$\forall M_1 \in \mathcal{L}(\mathcal{H}_{1}^{A^I}), \dots, M_N \in \mathcal{L}(\mathcal{H}_{N}^{A^I}) \text{ such that } \text{Tr}_{A_1^O} M_1 = 1, \dots, \text{Tr}_{A_N^O} M_N = 1, \text{ Tr} \left[ \left( \bigotimes_k M_k \right)^T W \right] = 1. \quad (D1)$$

This was shown to be equivalent to imposing some linear and affine constraints on W, which can be written as $[8, 18]^{32}$

$$\forall \emptyset \subsetneq \mathcal{K} \subseteq \mathcal{N}, \quad \prod_{k \in \mathcal{K}} [1 - A_k^O] \text{Tr}_{\mathcal{N} \setminus \mathcal{K}} A_k^O W = 0 \quad \text{and} \quad \text{Tr} W = d_{\mathcal{N}}^O, \quad (D2)$$

<footnote n="32">32 We note that another equivalent formulation of these constraints was also given in terms of “allowed” and “forbidden” terms in a Hilbert-Schmidt basis decomposition of W [3, 14].</footnote>
where we used the notation $[1-A_k^O]W := W - (\mathrm{Tr}_{A_k^O} W) \otimes \frac{1}{d_k^O}$ (with $d_k^O$ denoting the dimension of $\mathcal{H}^{A_k^O}$), such that $\prod_{k \in \mathcal{K}} [1-A_k^O]W = [1-A_{k_1}^O]([1-A_{k_2}^O](\cdots([1-A_{k_{|\mathcal{K}|}}^O]W)))$ for $\mathcal{K} = \{k_1, k_2, \dots, k_{|\mathcal{K}|}\}$, and where $d_{\mathcal{N}}^O := \prod_{k \in \mathcal{N}} d_k^O$ is the product of the dimensions of all parties' output spaces.

As recalled in the main text, another version of the process matrix framework was introduced in Ref. [27], with some “open” past and future spaces $\mathcal{H}^P, \mathcal{H}^F$. Here the process matrix acts as a “supermap” [28] that transforms the parties’ local maps to a new quantum map from $\mathcal{H}^P$ to $\mathcal{H}^F$, given by the further generalised Born rule of Eq. (23). Requiring that completely positive (CP) maps thereby get transformed to a CP map (even when involving auxiliary systems: the supermap must be “completely CP-preserving”) imposes again that $W$ must be PSD. The requirement that TP maps (corresponding e.g. to the sum of the parties’ instrument elements) get transformed to a TP map (the supermap must be “TP-preserving”), on the other hand, can be written here as in Eq. (D1), just replacing the last equality by $\mathrm{Tr}_F[(\otimes_k M_k)^T W] = \mathbb{1}^P$. It can be shown to be equivalent to the following linear and affine constraints:$^{33}$

$$ \forall \emptyset \subset \mathcal{K} \subset \mathcal{N}, \prod_{k \in \mathcal{K}} [1-A_k^O] \mathrm{Tr}_{A_{\mathcal{N}\setminus\mathcal{K}}^O} W = 0 \quad \text{and} \quad \mathrm{Tr}_{A_{\mathcal{N}}^O} W = d_{\mathcal{N}}^O \mathbb{1}^P. \qquad (\mathrm{D}3) $$

Let us emphasise again that the validity constraints of Eqs. (D2) and (D3) correspond to the requirement that the generalised Born rule of Eq. (22) gives the constant value 1, or that the alternative version of Eq. (23) returns a trace-preserving global map $M_{\vec{a}|\vec{x}}^{PF}$, whenever one plugs in TP external operations (obtained e.g. as the sum of the elements of the parties’ instruments). When dealing with process matrices, one is often interested in the linear parts of the validity constraints, ignoring the affine part, i.e. ignoring the constraint $\mathrm{Tr} W = d_{\mathcal{N}}^O$ in Eq. (D2), or only imposing $\mathrm{Tr}_{A_{\mathcal{N}}^{IO}F} W \propto \mathbb{1}^P$ in Eq. (D3). One then refers to matrices that are valid process matrices up to normalisation only$^{34}$—as in the characterisations of our classes QC-NICC and QC-NIQC, see Eqs. (26) and (33). Requiring validity up to normalisation only, for a given $W$, therefore has the following interpretation: when plugging in TP external operations, the generalised Born rules of Eq. (22) or (23) must return a constant value, or a global induced map whose output state has a constant trace, respectively, whatever the choice of the TP external operations.

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

Let us now come to a more in-depth presentation of QC-CCs, and of the subclasses of QC-convFOs and QC-NICCs that we considered in this work. Secs. D2a (general QC-CCs) and D2b (QC-convFOs) below are essentially just reviews of previous work, to set up the stage for the presentation and characterisation of our new class of QC-NICCs in Sec. D2c.

QC-CCs were introduced and characterised in Ref. [21], which we refer to for more details. One technical ingredient that we will use below is the so-called *link product* [32, 33]. It is defined, for two matrices $M_1^{XY} \in \mathcal{L}(\mathcal{H}^{XY})$ and $M_2^{XY} \in \mathcal{L}(\mathcal{H}^{YZ})$ that share a common space $\mathcal{H}^Y$, as

$$ \begin{aligned} M_1^{XY} * M_2^{YZ} &:= (\mathbb{1}^{XZ} \otimes \langle\!\langle \mathbb{1} |^{YY} \rangle\!\rangle)(M_1^{XY} \otimes M_2^{YZ})(\mathbb{1}^{XZ} \otimes |\mathbb{1}\rangle\!\rangle^{YY}) \\ &= \mathrm{Tr}_Y \left[ (M_1^{XY})^{T_Y} \otimes \mathbb{1}^Z \right] (\mathbb{1}^X \otimes M_2^{YZ}) \in \mathcal{L}(\mathcal{H}^{XZ}), \end{aligned} \qquad (\mathrm{D}4) $$

where $|\mathbb{1}\rangle\!\rangle^{YY} := \sum_j |i\rangle\!\rangle^Y \otimes |i\rangle\!\rangle^Y$ denotes the unnormalised maximally entangled state (defined for two copies of the space $\mathcal{H}^Y$ with computational basis $\{|i\rangle\!\rangle^Y\}_i$), and where $\mathrm{Tr}_Y$ and $^{T_Y}$ denote the partial trace and partial transpose over $\mathcal{H}^Y$, respectively. The link product corresponds in the Choi picture to the composition of maps: if $M_1^{XY}$ and $M_2^{YZ}$ are the Choi matrices of two linear maps $M_1: \mathcal{L}(\mathcal{H}^X) \to \mathcal{L}(\mathcal{H}^Y)$ and $M_2: \mathcal{L}(\mathcal{H}^Y) \to \mathcal{L}(\mathcal{H}^Z)$, then $M_1^{XY} * M_2^{YZ}$ is the Choi matrix of their composition $M_2 \circ M_1: \mathcal{L}(\mathcal{H}^X) \to \mathcal{L}(\mathcal{H}^Z)$. (The same interpretation in terms of composition also applies if the output and input spaces of $M_1$ and $M_2$ do not match [21, 32, 33].)

The link product is commutative (up to a re-ordering of the tensor products) and associative (provided each Hilbert space is involved at most twice in an $n$-fold link product—as will always be the case here). It reduces to a standard tensor product $M_1^X * M_2^Z = M_1^X \otimes M_2^Z$ if the space $\mathcal{H}^Y$ is trivial, and to a scalar product $M_1^Y * M_2^Y = \mathrm{Tr}[(M_1^Y)^T M_2^Y]$ if the spaces $\mathcal{H}^X$ and $\mathcal{H}^Z$ are trivial. Noticing that the Choi matrix of the preparation of a state $\rho$ coincides with the density matrix $\rho$ itself, one can write the output state of a map $M$ (with Choi matrix $M$) applied to $\rho$ as the composition $M(\rho) = \rho * M$. Notice also that the generalised Born rule of Eq. (23) can be written in a simple form as a link product, namely: $M_{\vec{a}|\vec{x}}^{PF} = (\otimes_k M_{a_k|x_k}^{A_k}) * W$.

<footnote>$^{33}$ These can be verified to be equivalent to the set of constraints obtained (after certain simplifications) from Eq. (D1), when one attributes $\mathcal{H}^P$ and $\mathcal{H}^F$ to two additional parties with trivial input and output spaces, respectively.</footnote>

<footnote>$^{34}$ Notice that this includes in particular the null matrix, $W = 0$.</footnote>
<figure><img src="image_10.png" /><figcaption>Figure 9. Graphical representation of a QC-CC: a more detailed version than Fig. 2 (clarifying here the internal structure of the circuit operations $\tilde{M}_n$), reproduced from Fig. 9 of Ref. [21].</figcaption></figure>

### a. General QC-CCs

**Construction of a QC-CC.** As briefly introduced in the main text, a QC-CC consists in the application of a number of “internal operations”, each of which determines which “external operation” (implemented by one of the $N$ parties $A_k$) is to be applied next—with each of the latter being applied once and only once by the end of the protocol.

One way to understand this is to consider that each internal operation corresponds to a quantum instrument $\{\mathcal{M}_{(k_1, \dots, k_n)}^{\to k_{n+1}}\}_{k_{n+1} \notin \{k_1, \dots, k_n\}}$, whose classical output value $k_{n+1}$ indicates the label of the next external operation to be applied, conditioned on the previous operations being those labelled $(k_1, \dots, k_n)$, in that order. The instrument corresponding to the first internal operation consists of CP maps $\mathcal{M}_{\emptyset}^{\to k_1} : \mathcal{L}(\mathcal{H}^P) \to \mathcal{L}(\mathcal{H}^{A_{k_1}^I \alpha_1})$ that transform the input state in the “global past” space $\mathcal{H}^P$ into a state in the input space $\mathcal{H}^{A_{k_1}^I}$ of the first operation to be applied, as well as in some auxiliary “memory” space $\mathcal{H}^{\alpha_1}$.35 The subsequent internal operations, for $n = 1, \dots, N-1$, consist of CP maps $\mathcal{M}_{(k_1, \dots, k_n)}^{\to k_{n+1}} : \mathcal{L}(\mathcal{H}^{A_{k_n}^O \alpha_n}) \to \mathcal{L}(\mathcal{H}^{A_{k_{n+1}}^I \alpha_{n+1}})$ that transform (conditioned on the previous external operations being $(k_1, \dots, k_n)$, in that order) the output state of the latest external operation, together with the memory system, into a state in the input space $\mathcal{H}^{A_{k_{n+1}}^I}$ of the next operation to be applied, as well as in some new memory space $\mathcal{H}^{\alpha_{n+1}}$. Finally, the last internal operation consists of just a single CPTP map $\mathcal{M}_{(k_1, \dots, k_n)}^{\to F} : \mathcal{L}(\mathcal{H}^{A_{k_N}^O \alpha_N}) \to \mathcal{L}(\mathcal{H}^F)$ (since there is no choice of next operation to be made) that transforms (conditioned on all external operations having been applied in the order $(k_1, \dots, k_N)$) the output state of the last external operation, together with the memory system, into a state in the “global future” space $\mathcal{H}^F$.

Another equivalent way to describe such a protocol—as depicted in Fig. 2 of the main text, or with more details in Fig. 9 here—is to encode the output of these instruments into a physical (effectively classical) system and consider the internal operations to also act on this system, which is used to control the subsequent operations. This can be done by introducing, for each time-slot $t_n$ ($n = 1, \dots, N$) at which an external operation is to be applied, a Hilbert space $\mathcal{H}^{C_n}$ carrying orthogonal control states of the form

$$ \llbracket (k_1, \dots, k_n) \rrbracket^{C_n} := |(k_1, \dots, k_n)\rangle\langle(k_1, \dots, k_n)|^{C_n}, \qquad (D5) $$

which keeps track of all previous external operations, as well as of the current one to be applied.

In order to define a controlled version of the external operations, it is assumed for simplicity that all input Hilbert spaces $\mathcal{H}^{A_k^I}$ (all output Hilbert spaces $\mathcal{H}^{A_k^O}$, respectively) of all external operations are isomorphic. One can then introduce, for each time-slot $t_n$, a “generic” input Hilbert space $\mathcal{H}^{\tilde{A}_n^I}$ (a “generic” output Hilbert space $\mathcal{H}^{\tilde{A}_n^O}$, resp.), isomorphic to all $\mathcal{H}^{A_k^I}$’s (isomorphic to all $\mathcal{H}^{A_k^O}$’s, resp.). In this way, when an external operation36 $A_{k_n} : \mathcal{L}(\mathcal{H}^{A_{k_n}^I}) \to \mathcal{L}(\mathcal{H}^{A_{k_n}^O})$ (with Choi matrix $A_{k_n} \in \mathcal{L}(\mathcal{H}^{A_{k_n}^O})$) is applied at time-slot $t_n$, one can identify it formally with an operation of the type $\tilde{A}_{k_n} : \mathcal{L}(\mathcal{H}^{\tilde{A}_n^I}) \to \mathcal{L}(\mathcal{H}^{\tilde{A}_n^O})$ (with Choi matrix $\tilde{A}_{k_n} : \mathcal{L}(\mathcal{H}^{\tilde{A}_n^O})$). This allows one to write all the external operations that may be applied at time-slot $t_n$ as acting in the same generic input and output spaces, and to embed

<footnote n="35">35 The auxiliary “memory” systems are not touched by the external operations. Notice that these may just be trivial.</footnote>

<footnote n="36">36 Here for simplicity we allow for some double-use of notation, using the same $A_k$ for the Choi matrix of an external operation and the party that implements it, as considered in the main text. The operations $A_k$ (in the Choi picture) considered here correspond to the individual CP maps $M_{a_k|x_k}^{A_k}$ considered in the main text to be part of each party’s instrument.</footnote>
these into some “larger” controlled operation $\tilde{\mathcal{A}}_n$, which applies the desired operation $\tilde{\mathcal{A}}_{k_n}$ depending on the state of the control (more specifically, on its last label $k_n$):

$$ \tilde{\mathcal{A}}_n := \sum_{(k_1, \dots, k_n)} \tilde{\mathcal{A}}_{k_n} \otimes \pi_{(k_1, \dots, k_n)}^{C_n \to C'_n} : \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_n^I C_n}) \to \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_n^O C'_n}), \quad (D6) $$

where for later convenience we introduced a copy $\mathcal{H}^{C'_n}$ of the Hilbert space $\mathcal{H}^{C_n}$, and where $\pi_{(k_1, \dots, k_n)}^{C_n \to C'_n}$ is the (classical) map that projects the control system onto the state $\llbracket (k_1, \dots, k_n) \rrbracket^{C_n}$, while re-labelling the control system $C_n$ to $C'_n$.

Similarly, one can formally write the internal operations $\tilde{\mathcal{M}}_{(k_1, \dots, k_n)}^{\to k_{n+1}} : \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_n^O \alpha_n}) \to \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_{n+1}^I \alpha_{n+1}})$ (for each $n = 1, \dots, N-1$) as maps of the type $\tilde{\mathcal{M}}_{(k_1, \dots, k_n)}^{\to k_{n+1}} : \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_n^O \alpha_n}) \to \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_{n+1}^I \alpha_{n+1}})$ acting in the generic Hilbert space introduced above. These can then be embedded into some “larger” operation $\tilde{\mathcal{M}}_{n+1}$ that also involves the control system: upon receiving the latter in the state $\llbracket (k_1, \dots, k_n) \rrbracket^{C'_n}$ (as outputted by the operation $\tilde{\mathcal{A}}_n$), $\tilde{\mathcal{M}}_{n+1}$ applies the operations $\tilde{\mathcal{M}}_{(k_1, \dots, k_n)}^{\to k_{n+1}}$ and updates the control system into the corresponding state $\llbracket (k_1, \dots, k_n, k_{n+1}) \rrbracket^{C_n}$. Formally:

$$ \tilde{\mathcal{M}}_{n+1} := \sum_{(k_1, \dots, k_n, k_{n+1})} \tilde{\mathcal{M}}_{(k_1, \dots, k_n)}^{\to k_{n+1}} \otimes \pi_{(k_1, \dots, k_n), k_{n+1}}^{C_n \to C_{n+1}} : \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_n^O \alpha_n C'_n}) \to \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_{n+1}^I \alpha_{n+1} C_{n+1}}), \quad (D7) $$

where $\pi_{(k_1, \dots, k_n), k_{n+1}}^{C_n \to C_{n+1}} : \mathcal{L}(\mathcal{H}^{C'_n}) \to \mathcal{L}(\mathcal{H}^{C_{n+1}})$ is the (classical) map that projects the control system onto $\llbracket (k_1, \dots, k_n) \rrbracket^{C'_n}$ and updates it to $\llbracket (k_1, \dots, k_n, k_{n+1}) \rrbracket^{C_{n+1}}$. For the first and last internal operations, one similarly defines

$$ \tilde{\mathcal{M}}_1 := \sum_{k_1} \tilde{\mathcal{M}}_{\emptyset}^{\to k_1} \otimes \pi_{\emptyset, k_1}^{\emptyset \to C_1} : \mathcal{L}(\mathcal{H}^P) \to \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_1^I \alpha_1 C_1}) \quad (D8) $$

$$ \text{and } \tilde{\mathcal{M}}_{N+1} := \sum_{(k_1, \dots, k_N)} \tilde{\mathcal{M}}_{(k_1, \dots, k_N)}^{\to F} \otimes \pi_{(k_1, \dots, k_N), F}^{C'_N \to \emptyset} : \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_N^O \alpha_N C'_N}) \to \mathcal{L}(\mathcal{H}^F), \quad (D9) $$

where $\pi_{\emptyset, k_1}^{\emptyset \to C_1}$ and $\pi_{(k_1, \dots, k_N), F}^{C'_N \to \emptyset}$ are the maps that create the initial control states $\llbracket (k_1) \rrbracket^{C_1}$ and that project onto the final control state $\llbracket (k_1, \dots, k_N) \rrbracket^{C'_N}$, respectively.

In the Choi representation, all these embedding operations are written

$$ \tilde{\mathcal{A}}_n = \sum_{(k_1, \dots, k_n)} \tilde{\mathcal{A}}_{k_n} \otimes \llbracket (k_1, \dots, k_n) \rrbracket^{C_n} \otimes \llbracket (k_1, \dots, k_n) \rrbracket^{C'_n} \in \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_n^I C_n \tilde{\mathcal{A}}_n^O C'_n}), \quad (D10) $$

$$ \tilde{\mathcal{M}}_1 = \sum_{k_1} \tilde{\mathcal{M}}_{\emptyset}^{\to k_1} \otimes \llbracket (k_1) \rrbracket^{C_1} \in \mathcal{L}(\mathcal{H}^{P \tilde{\mathcal{A}}_1^I \alpha_1 C_1}), \quad (D11) $$

$$ \tilde{\mathcal{M}}_{n+1} = \sum_{(k_1, \dots, k_n, k_{n+1})} \tilde{\mathcal{M}}_{(k_1, \dots, k_n)}^{\to k_{n+1}} \otimes \llbracket (k_1, \dots, k_n) \rrbracket^{C'_n} \otimes \llbracket (k_1, \dots, k_n, k_{n+1}) \rrbracket^{C_{n+1}} \in \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_n^O \alpha_n C'_n \tilde{\mathcal{A}}_{n+1}^I \alpha_{n+1} C_{n+1}}) \quad (\text{for } n = 1, \dots, N-1), \quad (D12) $$

$$ \tilde{\mathcal{M}}_{N+1} = \sum_{(k_1, \dots, k_N)} \tilde{\mathcal{M}}_{(k_1, \dots, k_N)}^{\to F} \otimes \llbracket (k_1, \dots, k_N) \rrbracket^{C'_N} \in \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_N^O \alpha_N C'_N F}). \quad (D13) $$

These allow one, in particular, to conveniently evaluate the state of all systems at any point in the circuit. Consider, for that, inputting some state $\rho \in \mathcal{L}(\mathcal{H}^P)$ in the global past of the circuit. The states $\varrho'_{(n)}$ before and $\varrho_{(n+1)}$ after each operation $\tilde{\mathcal{M}}_{n+1}$ are found (recursively) to be

$$ \varrho'_{(0)} = \rho \in \mathcal{L}(\mathcal{H}^P), \quad (D14) $$

$$ \begin{aligned} \varrho'_{(n)} &= \rho * \tilde{\mathcal{M}}_1 * \tilde{\mathcal{A}}_1 * \tilde{\mathcal{M}}_2 * \dots * \tilde{\mathcal{M}}_n * \tilde{\mathcal{A}}_n \\ &= \sum_{(k_1, \dots, k_n)} (\rho \otimes A_{k_1} \otimes \dots \otimes A_{k_n}) * (M_{\emptyset}^{\to k_1} * M_{(k_1)}^{\to k_2} * \dots * M_{(k_1, \dots, k_{n-1})}^{\to k_n}) * |1\rangle\langle 1| |A_{k_n}^{\tilde{\mathcal{A}}_n} \tilde{\mathcal{A}}_n^O \rangle \otimes \llbracket (k_1, \dots, k_n) \rrbracket^{C'_n} \\ &\qquad \in \mathcal{L}(\mathcal{H}^{\tilde{\mathcal{A}}_n^O \alpha_n C'_n}) \quad \text{for } n \ge 1 \quad (D15) \end{aligned} $$
and

$$
\begin{align}
\varrho_{(n+1)} &= \rho * \tilde{M}_1 * \tilde{A}_1 * \tilde{M}_2 * \cdots * \tilde{M}_n * \tilde{A}_n * \tilde{M}_{n+1} \nonumber \\
&= \sum_{(k_1, \dots, k_n, k_{n+1})} (\rho \otimes A_{k_1} \otimes \cdots \otimes A_{k_n}) * (M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \cdots * M_{(k_1, \dots, k_{n-1})}^{\rightarrow k_n} * M_{(k_1, \dots, k_n)}^{\rightarrow k_{n+1}} * |1\rangle\langle1| \left\langle 1 \middle|^{A_{k_{n+1}}^I \tilde{A}_{n+1}^I} \right. \nonumber \\
&\qquad \left. \otimes \left\langle (k_1, \dots, k_n, k_{n+1}) \right\rangle \right\rangle^{C_{n+1}} \in \mathcal{L}(\mathcal{H}^{\tilde{A}_{n+1}^I \alpha_{n+1} C_{n+1}}) \quad \text{for } n \le N-1, \tag{D16}
\end{align}
$$

$$
\begin{align}
\varrho_{(N+1)} &= \rho * \tilde{M}_1 * \tilde{A}_1 * \tilde{M}_2 * \cdots * \tilde{M}_N * \tilde{A}_N * \tilde{M}_{N+1} \nonumber \\
&= \sum_{(k_1, \dots, k_N)} (\rho \otimes A_{k_1} \otimes \dots \otimes A_{k_N}) * (M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \dots * M_{(k_1, \dots, k_{N-1})}^{\rightarrow k_N} * M_{(k_1, \dots, k_N)}^{\rightarrow F}) \nonumber \\
&= (\rho \otimes A_1 \otimes \dots \otimes A_N) * \left( \sum_{(k_1, \dots, k_N)} M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \dots * M_{(k_1, \dots, k_{N-1})}^{\rightarrow k_N} * M_{(k_1, \dots, k_N)}^{\rightarrow F} \right) \in \mathcal{L}(\mathcal{H}^F), \tag{D17}
\end{align}
$$

where $|1\rangle\langle1|\left\langle 1 \middle|^{A_{k_n}^O \tilde{A}_n^O}$ and $|1\rangle\langle1|\left\langle 1 \middle|^{A_{k_{n+1}}^I \tilde{A}_{n+1}^I}$ in Eqs. (D15) and (D16) simply represent some trivial mappings from the external operations' output and input spaces $\mathcal{H}^{A_{k_n}^O}$ and $\mathcal{H}^{A_{k_{n+1}}^I}$ to the corresponding generic output and input spaces $\mathcal{H}^{\tilde{A}_n^O}$ and $\mathcal{H}^{A_{k_{n+1}}^I \tilde{A}_{n+1}^I}$ (notice how the tildes were removed between the first and second lines in each equation).

Trace-preserving conditions. In order to define a TP-preserving quantum circuit—such that when one plugs in TP external operations, the induced global map remains TP—one requires all internal operations $\tilde{M}_{n+1}$ to preserve the trace of their input state (they must be TP on their effective input space, in which their input state $\varrho'_n$ may effectively be found). In fact, a stronger condition is imposed here: the control system must evolve in a consistent way, so that for any $n \le N-1$ and any given sequence $(k_1, \dots, k_n)$, the probabilities of finding the control in the state $\left\langle (k_1, \dots, k_n, k_{n+1}) \right\rangle^{C_{n+1}}$ after the operation $\tilde{M}_{n+1}$ (and of the operations $A_{k_1}, \dots, A_{k_n}$ to be applied, when these are part of quantum instruments) sum up, for all possible $k_{n+1} \notin \{k_1, \dots, k_n\}$, to the probability of finding the control in the state $\left\langle (k_1, \dots, k_n) \right\rangle'^{C'_n}$ before $\tilde{M}_{n+1}$ (and of the operations $A_{k_1}, \dots, A_{k_n}$ to be applied). From Eqs. (D15) and (D16), these probabilities are

$$
\begin{align}
& \sum_{k_{n+1}} \mathrm{Tr} \left[ (1^{\tilde{A}_{n+1}^I \alpha_{n+1}} \otimes \left\langle (k_1, \dots, k_n, k_{n+1}) \right\rangle^{C_{n+1}}) \varrho_{(n+1)} \right] \nonumber \\
&= \sum_{k_{n+1}} \mathrm{Tr} \left[ (\rho \otimes A_{k_1} \otimes \dots \otimes A_{k_n}) * (M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \dots * M_{(k_1, \dots, k_{n-1})}^{\rightarrow k_n} * M_{(k_1, \dots, k_n)}^{\rightarrow k_{n+1}}) \right] \nonumber \\
&= \mathrm{Tr} \left[ (\rho \otimes A_{k_1} \otimes \dots \otimes A_{k_n})^T \sum_{k_{n+1}} \mathrm{Tr}_{A_{k_{n+1}}^I \alpha_{n+1}} (M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \dots * M_{(k_1, \dots, k_{n-1})}^{\rightarrow k_n} * M_{(k_1, \dots, k_n)}^{\rightarrow k_{n+1}}) \right]. \tag{D18}
\end{align}
$$

and

$$
\begin{align}
\mathrm{Tr} \left[ (1^{\tilde{A}_O^n \alpha_n} \otimes \left\langle (k_1, \dots, k_n) \right\rangle'^{C'_n}) \varrho'_n \right] &= \mathrm{Tr} \left[ (\rho \otimes A_{k_1} \otimes \dots \otimes A_{k_n}) * (M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \dots * M_{(k_1, \dots, k_{n-1})}^{\rightarrow k_n}) \right] \nonumber \\
&= \mathrm{Tr} \left[ (\rho \otimes A_{k_1} \otimes \dots \otimes A_{k_n})^T \left( \mathrm{Tr}_{\alpha_n} (M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \dots * M_{(k_1, \dots, k_{n-1})}^{\rightarrow k_n}) \right) \right]. \tag{D19}
\end{align}
$$

As these two expressions must be equal for all possible $\rho \otimes A_{k_1} \otimes \dots \otimes A_{k_n}$, which span the whole space $\mathcal{L}(\mathcal{H}^{PA_{\{k_1, \dots, k_n\}}^I})$, then the second terms inside both final traces must themselves be equal:

$$
\sum_{k_{n+1}} \mathrm{Tr}_{A_{k_{n+1}}^I \alpha_{n+1}} (M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \cdots * M_{(k_1, \dots, k_{n-1})}^{\rightarrow k_n} * M_{(k_1, \dots, k_n)}^{\rightarrow k_{n+1}}) = \mathrm{Tr}_{\alpha_n} (M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \cdots * M_{(k_1, \dots, k_{n-1})}^{\rightarrow k_n} * M_{(k_1, \dots, k_n)}^{\rightarrow F}) \otimes 1^{A_{k_n}^O}. \quad (D20)
$$

For the limiting cases $n=0$ and $n=N$, we correspondingly obtain the constraints:

$$
\sum_{k_1} \mathrm{Tr}_{A_{k_1}^I \alpha_1} (M_{\emptyset}^{\rightarrow k_1}) = 1^P \qquad (D21)
$$

and

$$
\mathrm{Tr}_F (M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \cdots * M_{(k_1, \dots, k_{N-1})}^{\rightarrow k_N} * M_{(k_1, \dots, k_N)}^{\rightarrow F}) = \mathrm{Tr}_{\alpha_N} (M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \cdots * M_{(k_1, \dots, k_{N-1})}^{\rightarrow k_N} * M_{(k_1, \dots, k_N)}^{\rightarrow A_N^O}) \otimes 1^{A_N^O}. \quad (D22)
$$
Process matrix description and characterisation. The expression for $\rho_{N+1}$ in Eq. (D17) allows one to readily obtain the process matrix description of the QC-CC under consideration. Indeed, it follows from the generalised Born rule of Eq. (23) (or its form given on p. 39 after the introduction of the link product) that the final state in the global future should be $\rho_{N+1} = (\rho \otimes A_1 \otimes \cdots \otimes A_N) * W$. Since the $\rho \otimes A_1 \otimes \cdots \otimes A_N$'s span the whole space $\mathcal{L}(\mathcal{H}^{PA_{N}^{IO}})$, there is only one matrix $W$ that gives the correct output state through this expression. From Eq. (D17) we can thus directly identify the process matrix of the QC-CC under consideration to be

$$W = \sum_{(k_1, \dots, k_N)} M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \cdots * M_{(k_1, \dots, k_{N-1})}^{\rightarrow k_N} * M_{(k_1, \dots, k_N)}^{\rightarrow F} \in \mathcal{L}(\mathcal{H}^{PA_{N}^{IO} F}). \quad (D23)$$

Defining, for all $n = 1, \dots, N$ and all $(k_1, \dots, k_n)$,

$$W_{(k_1, \dots, k_n)} := \mathrm{Tr}_{\alpha_n} (M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \cdots * M_{(k_1, \dots, k_{n-1})}^{\rightarrow k_n}) \in \mathcal{L}(\mathcal{H}^{PA_{\{k_1, \dots, k_{n-1}\}}^{IO}})^{A_n^I}), \quad (D24)$$

$$W_{(k_1, \dots, k_N, F)} := M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \cdots * M_{(k_1, \dots, k_{N-1})}^{\rightarrow k_N} * M_{(k_1, \dots, k_N)}^{\rightarrow F} \in \mathcal{L}(\mathcal{H}^{PA_N^{IO} F}), \quad (D25)$$

then it follows directly from Eq. (D23) and the TP conditions of Eqs. (D20)–(D22) that the process matrix $W (\ge 0)$ of a QC-CC has a characterisation as in Eq. (24).

Conversely, from any decomposition of a matrix $W$ in terms of PSD matrices $W_{(k_1, \dots, k_N, F)}$ and $W_{(k_1, \dots, k_n)}$ as in Eq. (24), one can explicitly reconstruct (in a non-unique manner) the internal operations $M_{(k_1, \dots, k_n)}^{\rightarrow k_{n+1}}$ and $M_{(k_1, \dots, k_N)}^{\rightarrow F}$ of a QC-QC (satisfying the required TP conditions), whose composition reproduces $W_{(k_1, \dots, k_n)}$, $W_{(k_1, \dots, k_N, F)}$ and $W$ as in Eqs. (D23)–(D25) above. This shows that Eq. (24) is also a sufficient condition for $W$ to be a QC-CC. An explicit procedure for such a reconstruction was detailed in Appendix B of Ref. [21].

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

Quantum circuits with fixed causal order (QC-FOs). QC-FOs have been described and characterised previously, under the alternative names of channels with memory [30], quantum strategies [31], or quantum combs [32, 33]. One may describe them in a similar and in fact much simpler way to QC-CCs above, without the need to introduce the control system. For a given fixed order $(k_1, \dots, k_N)$, the internal operations would simply be of the form $\tilde{M}_{n+1} = \tilde{M}_{(k_1, \dots, k_n)}^{\rightarrow k_{n+1}}$. The TP conditions they satisfy are as in Eqs. (D20)–(D22), just without the sums $\sum_{k_{n+1}}$, $\sum_{k_1}$. One can identify their process matrix representation in the same way as we did above, and one simply gets

$$W = W_{(k_1, \dots, k_N, F)} = M_{\emptyset}^{\rightarrow k_1} * M_{(k_1)}^{\rightarrow k_2} * \cdots * M_{(k_1, \dots, k_{N-1})}^{\rightarrow k_N} * M_{(k_1, \dots, k_N)}^{\rightarrow F} \in \mathcal{L}(\mathcal{H}^{PA_N^{IO} F}). \quad (D26)$$

From the TP conditions, and defining$^{37}$ $W_{(k_1, \dots, k_n)}$ as in Eq. (D24) above, one can readily see that the process matrix $W = W_{(k_1, \dots, k_N, F)} (\ge 0)$ of a quantum circuit with fixed causal order $(k_1, \dots, k_N)$ is necessarily such that for all $n = 1, \dots, N$, there exist PSD matrices $W_{(k_1, \dots, k_n)} \in \mathcal{L}(\mathcal{H}^{PA_{\{k_1, \dots, k_{n-1}\}}^{IO}})^{A_n^I}$ such that

$$\left\{ \begin{array}{l} \mathrm{Tr}_F W = \mathrm{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, \quad \mathrm{Tr}_{A_{k_{n+1}}^I} W_{(k_1, \dots, k_{n+1})} = W_{(k_1, \dots, k_n)} \otimes 1^{A_{k_n}^O}, \\ \mathrm{Tr}_{A_{k_1}^I} W_{(k_1)} = 1^P. \end{array} \right. \quad (D27)$$

Conversely, for any PSD matrix $W \in \mathcal{L}(\mathcal{H}^{PA_N^{IO} F})$ satisfying the above constraint, one can construct (in a similar way to the case of general QC-CCs) internal circuit operations $\tilde{M}_{n+1} = \tilde{M}_{(k_1, \dots, k_n)}^{\rightarrow k_{n+1}}$, whose composition as in Eq. (D26) gives precisely $W$ [21, 31, 33]. This shows that Eq. (D27) is also a sufficient characterisation of the class of QC-FOs.

<footnote>$^{37}$ Notice that in contrast to the general QC-CC case, the matrices $W_{(k_1, \dots, k_n)}$ defined here are all valid process matrices (indeed, one can readily verify explicitly that the constraints of Eq. (D3) are satisfied). This implies in particular that the matrices $W_{(k_1, \dots, k_N)}^{(k_{n+1}, \dots, k_N)}$ that appear in the QC-convFO decomposition of Eq. (25), defined below as $W_{(k_1, \dots, k_N)}^{(k_{n+1}, \dots, k_N)} := q_{\pi} = (k_1, \dots, k_N) \tilde{W}_{(k_1, \dots, k_N)}$, are also valid process matrices up to normalisation.</footnote>
Convex mixtures of QC-FOs (QC-convFOs). The process matrix representation of a convex mixture of QC-FOs is then of the form $W = \sum_{\pi=(k_1, \dots, k_N)} q_\pi \tilde{W}(k_1, \dots, k_N, F)$, with $q_\pi \ge 0$, $\sum_\pi q_\pi = 1$, and each $\tilde{W}(k_1, \dots, k_N, F)$ satisfying the constraints of Eq. (D27). By defining the subnormalised process matrices $W_{(k_1, \dots, k_N, F)} := q_{\pi=(k_1, \dots, k_N)} \tilde{W}(k_1, \dots, k_N, F)$ and $W_{(k_1, \dots, k_n)}^{(k_{n+1}, \dots, k_N)} := q_{\pi=(k_1, \dots, k_N)} \tilde{W}(k_1, \dots, k_n)$ (with $\tilde{W}(k_1, \dots, k_n)$ obtained from the QC-FO decomposition of $\tilde{W}(k_1, \dots, k_N, F)$), one readily gets the characterisation of Eq. (25) for the class of QC-convFOs. The fact that Eq. (25) is a sufficient condition for $W$ to be a QC-convFO also follows straightforwardly from the sufficiency of Eq. (D27) above.

An alternative description of QC-convFOs. We note that one could present an alternative description of QC-convFOs, by encoding each order in the mixture into a classical system that is then used to control all operations and their order—as in a general QC-CC, except that the complete order $(k_1, \dots, k_N)$ would be decided, and encoded in the control system, from the very beginning (and independently of the global input state of the circuit).

This approach is the one we will follow to define the class of quantum circuits with superposition of fixed causal orders (QC-supFO), after turning the classical control system into a quantum control, whose initial state will encode the complete order; see Sec. D3b below.

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

Let us now come to our new class of QC-NICCs, defined in Sec. III B 3 of the main text as follows:

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,

with here the external operations referring to the parties' whole instruments (or simply a quantum channel they apply) rather than the individual CP maps that comprise them, and the state of the control system being considered after summing over all these individual CP maps.

The states $\varrho_{(n)}$, $\varrho'_{(n)}$ of all systems at any intermediate time step $t_n$ (for $n = 1, \dots, N$, just before or just after the operation $\tilde{A}_n$) were given in Eqs. (D15) and (D16). Considering the case where all external operations $A_k$ are TP (equivalently, summing over the CP maps that constitute the parties' instruments), the reduced state of the control system is obtained as<fnref n="38" />

$$ \begin{aligned} \mathrm{Tr}_{\tilde{A}_n^I \alpha_n} \varrho_{(n)} &= \mathrm{Tr}_{\tilde{A}_n^O \alpha_n} \varrho'_{(n)} = \sum_{(k_1, \dots, k_n)} \mathrm{Tr} \left[ (\rho \otimes A_{k_1} \otimes \dots \otimes A_{k_{n-1}}) * \left( M_{\emptyset}^{\to k_1} * M_{(k_1)}^{\to k_2} * \dots * M_{(k_1, \dots, k_{n-1})}^{\to k_n} \right) \right] \llbracket (k_1, \dots, k_n) \rrbracket^{C_n^{(t)}} \\ &= \sum_{(k_1, \dots, k_n)} \mathrm{Tr} \left[ (\rho \otimes A_{k_1} \otimes \dots \otimes A_{k_{n-1}}) * W_{(k_1, \dots, k_n)} \right] \llbracket (k_1, \dots, k_n) \rrbracket^{C_n^{(t)}}, \end{aligned} \quad (D28) $$

with $W_{(k_1, \dots, k_n)}$ as defined in Eq. (D24), and contributing to the decomposition of the process matrix $W$ of the QC-CC under consideration, as in Eq. (24).

The condition that the state of the control system should be independent of $\rho$ and of the previously applied external operations translates into the constraint that for all $(k_1, \dots, k_n)$,

$$ \mathrm{Tr}[(\rho \otimes A_{k_1} \otimes \dots \otimes A_{k_{n-1}}) * W_{(k_1, \dots, k_n)}] \text{ does not depend on } \rho, A_{k_1}, \dots, A_{k_{n-1}} \\ \text{whenever } A_{k_1}, \dots, A_{k_{n-1}} \text{ are TP (and } \mathrm{Tr} \, \rho = 1). \quad (D29) $$

Recalling the discussion at the end of Sec. D1, this is equivalent to

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

as in Eq. (26).

Conversely, as we recalled above, from a decomposition of $W$ in terms of $W_{(k_1, \dots, k_N, F)}$ and $W_{(k_1, \dots, k_n)}$ as in Eq. (24), one can reconstruct some internal operations $M_{(k_1, \dots, k_n)}^{\to k_{n+1}}$ (and $M_{(k_1, \dots, k_N)}^{\to F}$) of a QC-QC such that $\mathrm{Tr}_{\alpha_n} (M_{\emptyset}^{\to k_1} * M_{(k_1)}^{\to k_2} * \dots * M_{(k_1, \dots, k_{n-1})}^{\to k_n}) = W_{(k_1, \dots, k_n)}$. If each $W_{(k_1, \dots, k_n)}$ is proportional to a valid process matrix, then the reduced state of the control system at time step $t_n$, as given in Eq. (D28) above, does not depend on the operations $A_k$ when these are TP. It follows that $W$ is the process matrix of a QC-NICC.

<footnote n="38">³⁸ In Eq. (D28) we used the TP property $\mathrm{Tr}_{A_n^O} A_{k_n} = 1$ to remove $A_{k_n}$ from the expression of $\mathrm{Tr}_{\tilde{A}_n^I \alpha_n} \varrho'_{(n)}$. Since we formally get the same reduced state of the control before and after the operation $\tilde{A}_n$, we ignore here the distinction between systems $C_n$ and $C'_n$.</footnote>
d. Inclusion relations

It is quite clear, from the definition of the QC-NICC class just above, that QC-NICC ⊂ QC-CC. To see that QC-convFO ⊂ QC-NICC, consider a process matrix W ∈ QC-convFO, with a decomposition in terms of PSD matrices (and even valid process matrices, up to normalisation; see Footnote 37) W(k₁,...,kN,F) and W(kn₁,...,kN) as in Eq. (25); defining, for each (k₁,...,kN), W(k₁,...,kN) := Σ(kn₁,...,kN) W(kn₁,...,kN) one can easily see that these satisfy the QC-CC decomposition of Eq. (24), and that these are themselves valid process matrices (up to normalisation), which proves that W ∈ QC-NICC. Hence, we obtain the general inclusion relations of Eq. (27):

$$ \mathrm{QC-convFO} \subset \mathrm{QC-NICC} \subset \mathrm{QC-CC}. \qquad (\mathrm{D}31) $$

It is straightforward to see that all these classes reduce to the same one (which also matches the whole class of valid process matrices, see Sec. D 1) for N = 1.

For N = 2 already, with a nontrivial global past space H^P, one finds a strict separation between QC-NICC and QC-CC: an example of a process matrix in QC-CC\QC-NICC was given by the “classical switch” WCS, Eq. (30) of the main text. If H^P is trivial on the other hand, QC-NICC and QC-CC coincide for N = 2 (see the proof below), and one needs to go to N ≥ 3 to see a strict separation.

As for QC-convFO vs QC-NICC, these can be seen to coincide for N ≤ 3 (proof below). A strict separation can be found for N ≥ 4: an example of a process matrix in QC-NICC\QC-convFO, for N = 4 with trivial global past and future spaces H^P, H^F, was given by WNICC from Eq. (29).

* Proof that QC-NICC = QC-CC for N = 2 and a trivial H^P: Given the general inclusion QC-NICC ⊂ QC-CC, it remains to prove the inclusion in the reverse direction.

Consider for that the process matrix W of a QC-CC in that scenario. It decomposes in terms of PSD matrices W(k₁,k₂,F), W(k₁,k₂) and W(k₁) as in Eq. (24)—satisfying in particular TrAᵢⱼ W(k₁,k₂) = W(k₁) ⊗ 1Aᵢⱼ. Now, according to Eq. (D3), the validity constraints, up to normalisation, for W(k₁,k₂) ∈ L(HAᵢⱼAᵢⱼ) (with a trivial H^P) reduce to [1-AᵢⱼAᵢⱼ] TrAᵢⱼ W(k₁,k₂) = 0, which is indeed implied by TrAᵢⱼ W(k₁,k₂) = W(k₁) ⊗ 1Aᵢⱼ. Hence, the W(k₁,k₂)'s are valid process matrices up to normalisation, which implies that W is a QC-NICC, and therefore that QC-CC ⊂ QC-NICC in the scenario under consideration. (Recall that it is enough here to check the validity for the W(k₁,k₂)'s; in any case, the validity constraints for W(k₁) ∈ L(HAᵢⱼ), with no H^P, are trivially satisfied.)

* Proof that QC-convFO = QC-NICC for N ≤ 3: Given the general inclusion QC-convFO ⊂ QC-NICC, it remains to prove the inclusion in the reverse direction; furthermore, it is enough to consider N = 3, since any scenario with fewer parties can be considered as a 3-partite scenario where some party(-ies) have trivial input and output spaces.

Consider, therefore, the process matrix W of a tripartite (N = 3) QC-NICC. It decomposes in terms of PSD matrices W(k₁,k₂,k₃,F), W(k₁,k₂,k₃), W(k₁,k₂) and W(k₁) as in Eq. (24), with all of these being valid process matrices (up to normalisation). Defining W(k₁,k₂,k₃) := W(k₁,k₂,k₃) ≥ 0 and W(k₁,k₂) := W(k₁,k₂) ≥ 0 (for k₃ ≠ k₁,k₂), one can see that these (together with W(k₁,k₂,k₃,F)) satisfy the first two lines of Eq. (25), as well as the third constraint thereof, for n = 2. Furthermore, the validity of W(k₁,k₂) ∈ L(HAᵢⱼAᵢⱼ) implies (according to Eq. (D3)) that [1-AᵢⱼAᵢⱼ] TrAᵢⱼ W(k₁,k₂) = 0, i.e., TrAᵢⱼ W(k₁,k₂) = 1/dᵢⱼ TrAᵢⱼAᵢⱼ W(k₁,k₂) ⊗ 1Aᵢⱼ, so that by defining W(k₁,k₂) := 1/dᵢⱼ TrAᵢⱼAᵢⱼ W(k₁,k₂) ≥ 0, the third constraint of Eq. (25) gets also satisfied for n = 1. The validity of W(k₁,k₂) also implies that [1-P] TrAᵢⱼAᵢⱼ W(k₁,k₂) = 0, i.e., TrAᵢⱼ W(k₁,k₂) = (1/dᵢⱼ Tr W(k₁,k₂))1P, so that final constraint of Eq. (25) is also satisfied, with qᵢ=(k₁,k₂,k₃) = 1/dᵢⱼ Tr W(k₁,k₂) ≥ 0, such that Σᵢ qᵢ = Σ(k₁,k₂,k₃) 1/dᵢⱼ Tr W(k₁,k₂) = Σk₁ 1/dᵢⱼdᵢⱼ Σk₂ Tr W(k₁,k₂) = 1/dᵢⱼ Σk₁ Tr W(k₁) = 1 as required (where we used Σk₂ Tr W(k₁,k₂) = Tr(W(k₁) ⊗ 1Aᵢⱼ) and Σk₁ Tr W(k₁) = dP, which follow from Eq. (24)).

We thus obtained a decomposition of W that satisfies all constraints of Eq. (25), which shows that W is a QC-convFO, and therefore that QC-NICC ⊂ QC-convFO, for the (at most) tripartite case considered here.
e. Explicit decompositions of our specific examples of QC-CCs

To close this section on QC-CCs, we now provide explicit decompositions of our examples of QC-CCs from Sec. III B 4, in the appropriate form so as to match the characterisation of the class that they belong to.

Our first example, $W_{\text{convFO}} = \frac{1}{2}|\psi\rangle\langle\psi|^A \otimes |1\rangle\langle 1|^B \otimes |1\rangle\langle 1|^A + \frac{1}{2}|\psi\rangle\langle\psi|^B \otimes |1\rangle\langle 1|^A \otimes |1\rangle\langle 1|^B$, from Eq. (28), is clearly of the QC-convFO form of Eq. (25), with

$$ 
\left\{ 
\begin{aligned}
W_{(A,B)}^{\emptyset} &= \frac{1}{2} |\psi\rangle\langle\psi|^A \otimes |1\rangle\langle 1|^B \langle 1|^A \otimes |1\rangle\langle 1|^B \otimes |1\rangle\langle 1|^A, && W_{(B,A)}^{\emptyset} = \frac{1}{2} |\psi\rangle\langle\psi|^B \otimes |1\rangle\langle 1|^A \otimes |1\rangle\langle 1|^B, \\
W_{(A)}^{(B)} &= \frac{1}{2} |\psi\rangle\langle\psi|^A, && W_{(B)}^{(A)} = \frac{1}{2} |\psi\rangle\langle\psi|^B, && (D32) \\
q_{(A,B)} &= q_{(B,A)} = \frac{1}{2}
\end{aligned}
\right. 
$$

(and with $W_{(k_1,k_2,F)} = W_{(k_1,k_2)}^{\emptyset} \otimes 1^{A_{k_2}^O}$, since $\mathcal{H}^F$ is trivial).

Our second example, $W_{\text{NICC}} = \frac{1}{2}W_{+\alpha} \otimes |\psi\rangle\langle\psi|^C \otimes |1\rangle\langle 1|^D \otimes 1^{C^O} + \frac{1}{2}W_{-\alpha} \otimes |\psi\rangle\langle\psi|^D \otimes |1\rangle\langle 1|^D \otimes 1^{D^O}$ from Eq. (29), admits a QC-NICC decomposition of the form of Eq. (24), with for instance<fnref n="39" /> the valid process matrices (up to normalisation, as required the QC-NICC condition of Eq. (26))

$$ 
\left\{ 
\begin{aligned}
W_{(A,B,C,D)} &= \frac{1}{2}W_{+\alpha} \otimes |\psi\rangle\langle\psi|^C \otimes |1\rangle\langle 1|^D \otimes 1^{C^O} \otimes 1^{D^I}, && W_{(A,B,D,C)} = \frac{1}{2}W_{-\alpha} \otimes |\psi\rangle\langle\psi|^D \otimes |1\rangle\langle 1|^C \otimes 1^{D^I}, \\
W_{(A,B,C)} &= \frac{1}{2}W_{+\alpha} \otimes |\psi\rangle\langle\psi|^C, && W_{(A,B,D)} = \frac{1}{2}W_{-\alpha} \otimes |\psi\rangle\langle\psi|^D, && (D33) \\
W_{(A,B)} &= \frac{1}{4}1^{A^O B^I}, \\
W_{(A)} &= \frac{1}{2}1^{A^I},
\end{aligned}
\right. 
$$

and all other $W_{(k_1,...,k_n)} = 0$ (and again with $W_{(k_1,...,k_4,F)} = W_{(k_1,...,k_4)} \otimes 1^{A_{k_4}^O}$, since $\mathcal{H}^F$ is trivial). Notice that while the $W_{\pm\alpha}$'s are valid process matrices, the fact that they are causally nonseparable prevents one from obtaining a QC-convFO decomposition of $W_{\text{NICC}}$ (and indeed no such decomposition exists, as can be checked via SDP).

Our third example, $W_{\text{CS}} = |0\rangle\langle 0|^P \otimes |\psi\rangle\langle\psi|^A \otimes |1\rangle\langle 1|^B \otimes |1\rangle\langle 1|^A \otimes 1^{B^O} + |1\rangle\langle 1|^P \otimes |\psi\rangle\langle\psi|^B \otimes |1\rangle\langle 1|^D \otimes 1^{B^O}$ from Eq. (30), can be decomposed in the general QC-CC form of Eq. (24) as follows:

$$ 
\left\{ 
\begin{aligned}
W_{(A,B)} &= |0\rangle\langle 0|^P \otimes |\psi\rangle\langle\psi|^A \otimes |1\rangle\langle 1|^B \otimes 1^{A^O B^I}, && W_{(B,A)} = |1\rangle\langle 1|^P \otimes |\psi\rangle\langle\psi|^B \otimes |1\rangle\langle 1|^A \otimes 1^{B^O A^I}, \\
W_{(A)} &= |0\rangle\langle 0|^P \otimes |\psi\rangle\langle\psi|^A, && W_{(B)} = |1\rangle\langle 1|^P \otimes |\psi\rangle\langle\psi|^B
\end{aligned}
\right. 
(D34) 
$$

(and once again with $W_{(k_1,k_2,F)} = W_{(k_1,k_2)} \otimes 1^{A_{k_2}^O}$, since $\mathcal{H}^F$ is trivial). Notice that none of the matrices in the above decomposition are valid process matrices; indeed it can be shown via SDP that no decomposition of the form of Eq. (24) exists for $W_{\text{CS}}$ with only valid $W_{(k_1,(k_2))}$'s, which implies that $W_{\text{CS}}$ is not a QC-NICC.

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

We now move to the more in-depth presentation of QC-QCs and of our new subclasses of QC-supFOs and QC-NIQC.

QC-QCs were introduced and characterised in Ref. [21]. The basic idea was to turn the classical control of QC-CCs into a quantum control, so as to allow for coherently controlled superpositions of different causal orders.

To describe such coherent superpositions, it is more convenient to work in the “pure” picture of quantum theory: we will deal here with pure quantum states described by ket vectors of the form $|\psi\rangle \in \mathcal{H}$ (rather than with density matrices $\rho \in \mathcal{L}(\mathcal{H}))$, that evolve through pure linear operators of the form $V : \mathcal{H}^X \to \mathcal{H}^Y$ (rather than through CP maps $M : \mathcal{L}(\mathcal{H}^X) \to \mathcal{L}(\mathcal{H}^Y)$). Correspondingly, we will use the “pure” version of the Choi–Jamiołkowski isomorphism

<footnote n="39">³⁹ It is clear here that other decompositions are also possible, e.g. involving terms with $B \prec A$ rather than with $A \prec B$ (notice that $A$ and $B$ come in parallel in the implementation of Fig. 4, which is compatible with both orders), or with a mixture of the orders $A \prec B$ and $B \prec A$.</footnote>
<figure><img src="image_11.png" /><figcaption>Figure 10. Graphical representation of a QC-QC: a more detailed version than Fig. 5 (clarifying here the internal structure of the circuit operations $\tilde{V}_n$), reproduced from Fig. 10 of Ref. [21].</figcaption></figure>

and of the link product. Namely, for any given operator $V: \mathcal{H}^X \to \mathcal{H}^Y$, we define its Choi vector as the “double-ket” vector

$$|V\rangle^{XY} := (1^X \otimes V)|1\rangle^{XX} = \sum_i |i\rangle^X \otimes V|i\rangle^X \in \mathcal{H}^{XY} \qquad (D35)$$

(with $\{|i\rangle^X\}_i$ denoting the computational basis of $\mathcal{H}^X$, $|1\rangle^{XX} := \sum_i |i\rangle^X \otimes |i\rangle^X$); and for two vectors $|V_1\rangle \in \mathcal{H}^{XY}$ and $|V_2\rangle \in \mathcal{H}^{YZ}$ that share a common space $\mathcal{H}^Y$, we define their pure link product as [21]

$$|V_1\rangle^{XY} * |V_2\rangle^{YZ} := (|1\rangle^{XZ} \otimes \langle 1|^{YY})(|V_1\rangle^{XY} \otimes |V_2\rangle^{YZ}) = (|V_1\rangle^{XY})^{T_Y} \otimes |1\rangle^{Z}|V_2\rangle^{YZ} \in \mathcal{H}^{XZ}. \qquad (D36)$$

The pure link product has the same commutativity and associativity properties as in the mixed state, and similarly reduces to a tensor product if $\mathcal{H}^Y$ is trivial, or to a scalar product if $\mathcal{H}^X$ and $\mathcal{H}^Z$ are trivial. As in the mixed case, when $|V_1\rangle^{XY}$ and $|V_2\rangle^{YZ}$ are the Choi vectors of two linear operators $V_1: \mathcal{H}^X \to \mathcal{H}^Y$ and $V_2: \mathcal{H}^Y \to \mathcal{H}^Z$, then their link product is the Choi vector of their composition (or simply their product, here).

### a. General QC-QCs

**Construction of a QC-QC.** The general construction of a QC-QC, depicted in Fig. 5 of the main text or with more details in Fig. 10 here, is quite similar to that of a QC-CC; we will simply highlight here the essential differences, referring again to Ref. [21] for more details.

As just mentioned, here we work in the “pure” picture, so we now describe both internal and external operations as linear operators $\tilde{V}_1: \mathcal{H}^P \to \mathcal{H}^{\tilde{A}_1^I \alpha_1 C_1}$, $\tilde{V}_{n+1}: \mathcal{H}^{\tilde{A}_n^O \alpha_n C'_n} \to \mathcal{H}^{\tilde{A}_{n+1}^I \alpha_{n+1} C_{n+1}}$ (for $n = 1, \dots, N-1$), $\tilde{V}_{N+1}: \mathcal{H}^{\tilde{A}_N^O \alpha_N C'_N} \to \mathcal{H}^{F \alpha_F}$ (instead of $\tilde{M}_{n+1}: \mathcal{L}(\mathcal{H}^{\tilde{A}_n^O \alpha_n C'_n}) \to \mathcal{L}(\mathcal{H}^{\tilde{A}_{n+1}^I \alpha_{n+1} C_{n+1}})$ etc.), and $A_k: \mathcal{H}^{A_k^I} \to \mathcal{H}^{A_k^O}$ (instead of $A_k: \mathcal{L}(\mathcal{H}^{A_k^I}) \to \mathcal{L}(\mathcal{H}^{A_k^O})$).$^{40}$

The structure of the control system is somewhat different here. While in the QC-CC case the (effectively classical) control states were keeping track of the whole order of the previous operations, for QC-QCs the control system at each time-slot $t_n$ only encodes the unordered set $K_{n-1}$ of the $n-1$ previous operations, as well as the label $k_n(\notin K_{n-1})$ of the current operation. Thus, the (orthogonal) basis states of the control system take the form

$$|K_{n-1}, k_n\rangle^{C_n^{(i)}} \qquad (D37)$$

(instead of $|(k_1, \dots, k_n)\rangle|C_n^{(i)} := |(k_1, \dots, k_n)\rangle|(k_1, \dots, k_n)|C_n^{(i)}$ as in Eq. (D5)). Such states control which external operation $A_{k_n}$ is to be applied at time-slot $t_n$ by embedding these into the larger controlled operation

$$\tilde{A}_n := \sum_{K_{n-1}, k_n} \tilde{A}_{k_n} \otimes |K_{n-1}, k_n\rangle^{C'_n} \langle K_{n-1}, k_n| : \mathcal{H}^{\tilde{A}_n^I C_n} \to \mathcal{H}^{\tilde{A}_n^O C'_n} \qquad (D38)$$

<footnote>$^{40}$ We again introduce “generic” input (respectively output) spaces $\mathcal{H}^{\tilde{A}_n^I}$ (resp. $\mathcal{H}^{\tilde{A}_n^O}$) for the external operations to be applied at time-slot $t_n$, assuming that all their input (resp. output) spaces are isomorphic.</footnote>

<footnote>Notice also that we introduce an additional auxiliary system $\alpha_F$ in the global future. This system will ultimately be traced out (see Fig. 5) so as to still allow for some mixtures in the general definition of QC-QCs.</footnote>

<footnote>And we again allow for a slight conflict of notation with $A_k$. Here in the pure picture, $A_k: \mathcal{H}^{A_k^I} \to \mathcal{H}^{A_k^O}$ (with Choi vector $|A_k\rangle \in \mathcal{H}^{A_k^{IO}}$) can be understood as a Kraus operator of the operation applied by party $A_k$ (rather than the Choi matrix of their CP map, as we wrote in the context of QC-CCs).</footnote>
(instead of Eq. (D6)). They similarly control the internal operations through$^{41}$

$$ \tilde{V}_1 := \sum_{k_1} \tilde{V}_{\emptyset, \emptyset}^{\to k_1} \otimes |\emptyset, k_1\rangle^{C_1}: \qquad \mathcal{H}^P \to \mathcal{H}^{\tilde{A}_1^I \alpha_1 C_1}, \qquad (\text{D39}) $$

$$ \tilde{V}_{n+1} := \sum_{\substack{\mathcal{K}_{n-1}, \\ k_n, k_{n+1}}} \tilde{V}_{\mathcal{K}_{n-1}, k_n}^{\to k_{n+1}} \otimes |\mathcal{K}_{n-1} \cup k_n, k_{n+1}\rangle^{\mathcal{C}_{n+1}} \langle \mathcal{K}_{n-1}, k_n|^{\mathcal{C}'_n}: \qquad \mathcal{H}^{\tilde{A}_n^O \alpha_n C'_n} \to \mathcal{H}^{\tilde{A}_{n+1}^I \alpha_{n+1} C_{n+1}}, \qquad (\text{D40}) $$

$$ \tilde{V}_{N+1} := \sum_{k_N} \tilde{V}_{\mathcal{N}\setminus k_N, k_N}^{\to F} \otimes \langle \mathcal{N}\setminus k_N, k_N|^{\mathcal{C}'_N}: \qquad \mathcal{H}^{\tilde{A}_N^O \alpha_N C'_N} \to \mathcal{H}^{F \alpha_F} \qquad (\text{D41}) $$

(instead of Eqs. (D7)–(D9)), where the operators $\tilde{V}_{\emptyset, \emptyset}^{\to k_1}$, $\tilde{V}_{\mathcal{K}_{n-1}, k_n}^{\to k_{n+1}}$ and $\tilde{V}_{\mathcal{N}\setminus k_N, k_N}^{\to F}$ act on the target and auxiliary memory systems in an analogous (now coherently) controlled manner to $\tilde{M}_{\emptyset}^{\to k_1}$, $\tilde{M}_{(k_1, \dots, k_n)}^{\to k_{n+1}}$ and $\tilde{M}_{(k_1, \dots, k_N)}^{\to F}$ in the QC-CC case. Notice in particular how the specific position of $k_n$ gets erased in Eq. (D40), by merging (in the control state) $\mathcal{K}_{n-1}$ and $k_n$ into the unordered set $\mathcal{K}_{n-1} \cup k_n$; forgetting about the specific order of the past operations will allow different orders to interfere.

The state of all systems at any point in the circuit is simply obtained by composing the above internal and external operations—which is conveniently done in terms of their Choi vectors, using the pure link product. Inputting some initial state $|\psi\rangle \in \mathcal{H}^P$ in the global past of the circuit, and defining (for any subset $\mathcal{K}_n$ of $\mathcal{N}$) the vectors $|\psi, A_{\mathcal{K}_n}\rangle := |\psi\rangle \otimes_{k \in \mathcal{K}_n} |A_k\rangle \in \mathcal{H}^{\mathcal{P} A_{\mathcal{K}_n}^I}$, the states $|\varphi'_{(n)}\rangle$ before and $|\varphi_{(n+1)}\rangle$ after each operation $\tilde{V}_{n+1}$ are found to be

$$ |\varphi'_{(0)}\rangle = |\psi\rangle \in \mathcal{H}^P, \qquad (\text{D42}) $$

$$ \begin{aligned} |\varphi'_{(n)}\rangle &= |\psi\rangle * |\tilde{V}_1\rangle * |\tilde{A}_1\rangle * |\tilde{V}_2\rangle * \dots * |\tilde{V}_n\rangle * |\tilde{A}_n\rangle \\ &= \sum_{(k_1, \dots, k_n)} \left( |\psi\rangle \otimes |A_{k_1}\rangle \otimes \dots \otimes |A_{k_n}\rangle \right) * \left( |V_{\emptyset, \emptyset}^{\to k_1}\rangle * |V_{\emptyset, k_1}^{\to k_2}\rangle * \dots * |V_{\{k_1, \dots, k_{n-2}\}, k_{n-1}}^{\to k_n}\rangle * |1\rangle \right)^{A_{k_n}^O \tilde{A}_n^O} \\ &\qquad \otimes |\{k_1, \dots, k_{n-1}\}, k_n\rangle^{C'_n} \\ &= \sum_{\mathcal{K}_n, k_n \in \mathcal{K}_n} \left( |\psi, A_{\mathcal{K}_n}\rangle * |w_{(\mathcal{K}_n \setminus k_n, k_n)}\rangle * |1\rangle \right)^{A_{k_n}^O \tilde{A}_n^O} \otimes |\mathcal{K}_n \setminus k_n, k_n\rangle^{C'_n} \in \mathcal{H}^{\tilde{A}_{n+1}^I \alpha_{n+1} C_{n+1}} \quad \text{for } n \ge 1 \end{aligned} \qquad (\text{D43}) $$

and

$$ \begin{aligned} |\varphi_{(n+1)}\rangle &= |\psi\rangle * |\tilde{V}_1\rangle * |\tilde{A}_1\rangle * \dots * |\tilde{V}_n\rangle * |\tilde{A}_n\rangle * |\tilde{V}_{n+1}\rangle \\ &= \sum_{(k_1, \dots, k_n, k_{n+1})} \left( |\psi\rangle \otimes |A_{k_1}\rangle \otimes \dots \otimes |A_{k_n}\rangle \right) * \left( |V_{\emptyset, \emptyset}^{\to k_1}\rangle * \dots \right. \\ & \qquad \left. \dots * |V_{\{k_1, \dots, k_{n-2}\}, k_{n-1}}^{\to k_n}\rangle * |V_{\{k_1, \dots, k_{n-1}\}, k_n}\rangle * |1\rangle \right)^{A_{k_{n+1}}^I \tilde{A}_{n+1}^I} \otimes |\{k_1, \dots, k_n\}, k_{n+1}\rangle^{C_{n+1}} \\ &= \sum_{\mathcal{K}_n, k_{n+1} \notin \mathcal{K}_n} \left( |\psi, A_{\mathcal{K}_n}\rangle * |w_{(\mathcal{K}_n, k_{n+1})}\rangle * |1\rangle \right)^{A_{k_{n+1}}^I \tilde{A}_{n+1}^I} \otimes |\mathcal{K}_n, k_{n+1}\rangle^{C_{n+1}} \\ &\qquad \in \mathcal{H}^{\tilde{A}_{n+1}^I \alpha_{n+1} C_{n+1}} \quad \text{for } n \le N-1, \end{aligned} \qquad (\text{D44}) $$

$$ |\varphi_{(N+1)}\rangle = |\psi, A_{\mathcal{N}}\rangle * |w_{(\mathcal{N}, F)}\rangle \in \mathcal{H}^{F \alpha_F} \qquad (\text{D45}) $$

(instead of Eqs. (D14)–(D17)), with

$$ |w_{(\mathcal{K}_{n-1}, k_n)}\rangle := \sum_{(k_1, \dots, k_{n-1}) \in \mathcal{K}_{n-1}} |V_{\emptyset, \emptyset}^{\to k_1}\rangle * |V_{\emptyset, k_1}^{\to k_2}\rangle * \dots * |V_{\{k_1, \dots, k_{n-2}\}, k_{n-1}}^{\to k_n}\rangle \in \mathcal{H}^{\mathcal{P} A_{\mathcal{K}_{n-1}}^{I O} A_{k_n}^I \alpha_n}, \qquad (\text{D46}) $$

$$ |w_{(\mathcal{N}, F)}\rangle := \sum_{(k_1, \dots, k_N)} |V_{\emptyset, \emptyset}^{\to k_1}\rangle * |V_{\emptyset, k_1}^{\to k_2}\rangle * \dots * |V_{\{k_1, \dots, k_{N-2}\}, k_{N-1}}^{\to k_N}\rangle * |V_{\{k_1, \dots, k_{N-1}\}, k_N}\rangle \in \mathcal{H}^{\mathcal{P} A_{\mathcal{N}}^{I O} F \alpha_F}. \qquad (\text{D47}) $$

<footnote>$^{41}$ We use the short-hand notations $\mathcal{K}_{n-1} \cup k_n = \mathcal{K}_{n-1} \cup \{k_n\}$, $\mathcal{N}\setminus k_N = \mathcal{N}\setminus \{k_N\}$ (and, further below, $\mathcal{K}_n\setminus k_n = \mathcal{K}_n\setminus \{k_n\}$).</footnote>
*Trace-preserving conditions.* The TP conditions correspond here to the requirement that all internal operations $\tilde{V}_{n+1}$ preserve the norm of their input state $|\varphi'_{(n)}\rangle$: they must act as isometries on their effective input space. The squared norms of $|\varphi'_{(n)}\rangle$ and $|\varphi_{(n+1)}\rangle$ (for $1 \le n \le N-1$) can be obtained from Eqs. (D43)–(D44) above as

$$ \langle\varphi'_{(n)}|\varphi'_{(n)}\rangle = \sum_{\mathcal{K}_n, k_n \in \mathcal{K}_n} \mathrm{Tr} \left[ |\psi, A_{\mathcal{K}_n}\rangle\langle\psi, A_{\mathcal{K}_n}| * |w_{(\mathcal{K}_n \setminus k_n, k_n)}\rangle\langle w_{(\mathcal{K}_n \setminus k_n, k_n)}| \right] \\ = \sum_{\mathcal{K}_n} \mathrm{Tr} \left[ (|\psi, A_{\mathcal{K}_n}\rangle\langle\psi, A_{\mathcal{K}_n}|)^T \left( \sum_{k_n \in \mathcal{K}_n} \mathrm{Tr}_{\alpha_n} |w_{(\mathcal{K}_n \setminus k_n, k_n)}\rangle\langle w_{(\mathcal{K}_n \setminus k_n, k_n)}| \otimes 1^{A_{k_n}^O} \right) \right], \quad (\text{D48}) $$

$$ \langle\varphi_{(n+1)}|\varphi_{(n+1)}\rangle = \sum_{\mathcal{K}_n, k_{n+1} \notin \mathcal{K}_n} \mathrm{Tr} \left[ |\psi, A_{\mathcal{K}_n}\rangle\langle\psi, A_{\mathcal{K}_n}| * |w_{(\mathcal{K}_n, k_{n+1})}\rangle\langle w_{(\mathcal{K}_n, k_{n+1})}| \right] \\ = \sum_{\mathcal{K}_n} \mathrm{Tr} \left[ (|\psi, A_{\mathcal{K}_n}\rangle\langle\psi, A_{\mathcal{K}_n}|)^T \left( \sum_{k_{n+1} \notin \mathcal{K}_n} \mathrm{Tr}_{A_{k_{n+1}}^I} \alpha_{n+1} |w_{(\mathcal{K}_n, k_{n+1})}\rangle\langle w_{(\mathcal{K}_n, k_{n+1})}| \right) \right]. \quad (\text{D49}) $$

Equality between these two expressions, for any possible choice of $|\psi\rangle$ and of the $A_k$'s, implies that the last terms in round brackets must themselves be equal, for any $\mathcal{K}_n$:

$$ \sum_{k_{n+1} \notin \mathcal{K}_n} \mathrm{Tr}_{A_{k_{n+1}}^I} |w_{(\mathcal{K}_n, k_{n+1})}\rangle\langle w_{(\mathcal{K}_n, k_{n+1})}| = \sum_{k_n \in \mathcal{K}_n} \mathrm{Tr}_{\alpha_n} |w_{(\mathcal{K}_n \setminus k_n, k_n)}\rangle\langle w_{(\mathcal{K}_n \setminus k_n, k_n)}| \otimes 1^{A_{k_n}^O}. \quad (\text{D50}) $$

For the extremal cases $n=0$ and $n=N$, the corresponding constraints are

$$ \sum_{k_1 \in \mathcal{N}} \mathrm{Tr}_{A_{k_1}^I} |w_{(\emptyset, k_1)}\rangle\langle w_{(\emptyset, k_1)}| = 1^P \quad (\text{D51}) $$

$$ \text{and} \quad \mathrm{Tr}_{F_{\alpha_F}} |w_{(\mathcal{N}, F)}\rangle\langle w_{(\mathcal{N}, F)}| = \sum_{k_N \in \mathcal{N}} \mathrm{Tr}_{\alpha_N} |w_{(\mathcal{N} \setminus k_N, k_N)}\rangle\langle w_{(\mathcal{N} \setminus k_N, k_N)}| \otimes 1^{A_{k_N}^O}. \quad (\text{D52}) $$

*Process matrix description and characterisation.* From the expression for $|\varphi_{(N+1)}\rangle$ in Eq. (D45), one gets the (in general, mixed) global output state of the whole QC-QC, after tracing out $\alpha_F$:

$$ \varrho_{N+1} = \mathrm{Tr}_{\alpha_F} |\varphi_{(N+1)}\rangle\langle\varphi_{(N+1)}| = |\psi, A_{\mathcal{N}}\rangle\langle\psi, A_{\mathcal{N}}| * \left( \mathrm{Tr}_{\alpha_F} |w_{(\mathcal{N}, F)}\rangle\langle w_{(\mathcal{N}, F)}| \right) \in \mathcal{L}(\mathcal{H}^F). \quad (\text{D53}) $$

With this, one can readily identify the process matrix that describes the QC-QC under consideration (as we did in the QC-CC case), namely

$$ W = \mathrm{Tr}_{\alpha_F} |w_{(\mathcal{N}, F)}\rangle\langle w_{(\mathcal{N}, F)}| \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{N}}^{IO}}), \quad (\text{D54}) $$

with $|w_{(\mathcal{N}, F)}\rangle$ defined in Eq. (D47) above, as a coherent superposition of terms corresponding to different causal orders.

Defining, for all $n=1, \dots, N$, all strict subsets $\mathcal{K}_{n-1}$ of $\mathcal{N}$ and all $k_n \in \mathcal{N} \setminus \mathcal{K}_{n-1}$,

$$ W_{(\mathcal{K}_{n-1}, k_n)} := \mathrm{Tr}_{\alpha_n} |w_{(\mathcal{K}_{n-1}, k_n)}\rangle\langle w_{(\mathcal{K}_{n-1}, k_n)}| \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{K}_{n-1}}^{IO}} A_{k_n}^I), \quad (\text{D55}) $$

it then follows directly from Eq. (D54) and the TP conditions of Eqs. (D50)–(D52) that the process matrix $W (\ge 0)$ of a QC-QC has a characterisation as in Eq. (31).

Conversely, from any decomposition of a process matrix $W$ in terms of PSD matrices $W_{(\mathcal{K}_{n-1}, k_n)}$ satisfying Eq. (31), one can explicitly reconstruct (in a non-unique manner) the internal operations $V_{\mathcal{K}_{n-1}, k_n}^{\rightarrow k_{n+1}}$ and $V_{\mathcal{N} \setminus k_N, k_N}^{\rightarrow F}$ of a QC-QC (satisfying the required TP conditions), whose composition reproduces $|w_{(\mathcal{N}, F)}\rangle$ and, subsequently, $W$ as in Eqs. (D47) and (D54) above. This shows that Eq. (31) is also a sufficient condition for $W$ to be a QC-QC. An explicit procedure for such a reconstruction was detailed in Appendix B of [21].

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

As succinctly introduced in the main text, we define the class of quantum circuits with superposition of fixed causal orders as a modification of the general QC-QC construction above, in which the control system at any time-slot $t_n$
now encodes (in addition to the past and current operations) the full causal order $(k_{n+1}, \dots, k_N)$ of the upcoming external operations that are still to be applied. The weight of each total order $\pi = (k_1, \dots, k_N)$ is fixed from the very beginning to some value $q_\pi$ (such that $q_\pi \ge 0$, $\sum_\pi q_\pi = 1$). When updating the control system, the internal operations may again erase the order of previous operations, but they should not modify the weight of each remaining “future” order $(k_{n+2}, \dots, k_N)$.

The construction, the derivation of the TP conditions, the process matrix description and the characterisation of QC-supFOs align quite closely to the case of general QC-QCs recalled above. We will just point out the differences.

**Construction of a QC-supFO.** As just said, the control system should now also encode the order of future operations; we thus take its (orthogonal) basis states to be of the form

$$ |\mathcal{K}_{n-1}, k_n; (k_{n+1}, \dots, k_N)\rangle^{C'_n}, \qquad (D56) $$

with $k_n, k_{n+1}, \dots, k_N \notin \mathcal{K}_{n-1}$, instead of just $|\mathcal{K}_{n-1}, k_n\rangle^{C'_n}$ as in Eq. (D37).

These states control the external and internal operations through

$$ \tilde{A}_n := \sum_{\substack{\mathcal{K}_{n-1}, \\ (k_n, k_{n+1}, \dots, k_N)}} \tilde{A}_{k_n} \otimes |\mathcal{K}_{n-1}, k_n; (k_{n+1}, \dots, k_N)\rangle^{C'_n} \langle \mathcal{K}_{n-1}, k_n; (k_{n+1}, \dots, k_N)|^{C_n} \qquad (D57) $$

and

$$ \tilde{V}_1 := \sum_{(k_1, k_2, \dots, k_N)} \tilde{V}_{\emptyset, \emptyset}^{\to k_1; (k_2, \dots, k_N)} \otimes |\emptyset, k_1; (k_2, \dots, k_N)\rangle^{C_1}, \qquad (D58) $$

$$ \tilde{V}_{n+1} := \sum_{\substack{\mathcal{K}_{n-1}, \\ (k_n, k_{n+1}, k_{n+2}, \dots, k_N)}} \tilde{V}_{\mathcal{K}_{n-1}, k_n}^{\to k_{n+1}; (k_{n+2}, \dots, k_N)} \otimes |\mathcal{K}_{n-1} \cup k_n, k_{n+1}; (k_{n+2}, \dots, k_N)\rangle^{C_{n+1}} \langle \mathcal{K}_{n-1}, k_n; (k_{n+1}, k_{n+2}, \dots, k_N)|^{C'_n}, \qquad (D59) $$

$$ \tilde{V}_{N+1} := \sum_{k_N} \tilde{V}_{\mathcal{N}\setminus k_N, k_N}^{\to F} \otimes \langle \mathcal{N}\setminus k_N, k_N; \emptyset |^{C'_N}, \qquad (D60) $$

instead of Eqs. (D38)–(D41) for the general QC-QC case. Notice that the operators $\tilde{V}_{\emptyset, \emptyset}^{\to k_1; (k_2, \dots, k_N)}$ and $\tilde{V}_{\mathcal{K}_{n-1}, k_n}^{\to k_{n+1}; (k_{n+2}, \dots, k_N)}$ that act on the target and auxiliary memory systems can depend in general on the order of future operations, as encoded in the system $C_{n+1}^{(l)}$ that controls them.

Composing the above internal and external operations, we obtain the state of all systems before and after each operation $\tilde{V}_{n+1}$:

$$ |\varphi'_{(0)}\rangle = |\psi\rangle, \qquad (D61) $$

$$ \begin{aligned} |\varphi'_{(n)}\rangle &= |\psi\rangle * |\tilde{V}_1\rangle * |\tilde{A}_1\rangle * |\tilde{V}_2\rangle * \dots * |\tilde{V}_n\rangle * |\tilde{A}_n\rangle \\ &= \sum_{(k_1, \dots, k_N)} (|\psi\rangle \otimes |A_{k_1}\rangle \otimes \dots \otimes |A_{k_N}\rangle) \\ & \quad * (|V_{\emptyset, \emptyset}^{\to k_1; (k_2, \dots, k_N)}\rangle * |V_{\emptyset, k_1}^{\to k_2; (k_3, \dots, k_N)}\rangle * \dots * |V_{\{k_1, \dots, k_{n-2}\}, k_{n-1}}^{\to k_n; (k_{n+1}, \dots, k_N)}\rangle * |1\rangle^{A_{k_n}^O \tilde{A}_n^O}) \\ & \quad \otimes |\{k_1, \dots, k_{n-1}\}, k_n; (k_{n+1}, \dots, k_N)\rangle^{C'_n} \\ &= \sum_{\substack{\mathcal{K}_n, k_n \in \mathcal{K}_n, \\ (k_{n+1}, \dots, k_N) \notin \mathcal{K}_n}} (|\psi, A_{\mathcal{K}_n}\rangle * |w_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)}\rangle * |1\rangle^{A_{k_n}^O \tilde{A}_n^O}) \otimes |\mathcal{K}_n \setminus k_n, k_n; (k_{n+1}, \dots, k_N)\rangle^{C'_n} \end{aligned} \qquad (D62) $$
and

$$
\begin{align*}
|\varphi_{(n+1)}\rangle &= |\psi\rangle * |\tilde{V}_1\rangle * |\tilde{A}_1\rangle * \cdots * |\tilde{V}_n\rangle * |\tilde{A}_n\rangle * |\tilde{V}_{n+1}\rangle \\
&= \sum_{(k_1, \dots, k_N)} (|\psi\rangle \otimes |A_{k_1}\rangle \otimes \cdots \otimes |A_{k_N}\rangle) \\
&\qquad * (|V_{\emptyset, \emptyset}^{\rightarrow k_1; (k_2, \dots, k_N)}\rangle * \cdots * |V_{\{k_1, \dots, k_{n-2}\}, k_{n-1}}^{\rightarrow k_n; (k_{n+1}, \dots, k_N)}\rangle * |V_{\{k_1, \dots, k_{n-1}\}, k_n}^{\rightarrow k_{n+1}; (k_{n+2}, \dots, k_N)}\rangle * |1\rangle^{A_{k_{n+1}}^I \tilde{A}_{n+1}^I}) \\
&\qquad \otimes |\{k_1, \dots, k_n\}, k_{n+1}; (k_{n+2}, \dots, k_N)\rangle^{C_{n+1}} \\
&= \sum_{(\mathcal{K}_n, k_{n+1}, k_{n+2}, \dots, k_N) \notin \mathcal{K}_n} (|\psi, A_{\mathcal{K}_n}\rangle * |w_{(\mathcal{K}_n, k_{n+1})}^{(k_{n+2}, \dots, k_N)}\rangle * |1\rangle^{A_{k_{n+1}}^I \tilde{A}_{n+1}^I}) \otimes |\mathcal{K}_n, k_{n+1}; (k_{n+2}, \dots, k_N)\rangle^{C_{n+1}}, \quad (\text{D63})
\end{align*}
$$

$$
|\varphi_{(N+1)}\rangle = |\psi, A_N\rangle * |w_{(N,F)}\rangle \qquad (\text{D64})
$$

with

$$
|w_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_N)}\rangle := \sum_{(k_1, \dots, k_{n-1}) \in \mathcal{K}_{n-1}} |V_{\emptyset, \emptyset}^{\rightarrow k_1; (k_2, \dots, k_N)}\rangle * |V_{\emptyset, k_1}^{\rightarrow k_2; (k_3, \dots, k_N)}\rangle * \dots * |V_{\{k_1, \dots, k_{n-2}\}, k_{n-1}}^{\rightarrow k_n; (k_{n+1}, \dots, k_N)}\rangle, \quad (\text{D65})
$$

$$
|w_{(\mathcal{N}, F)}\rangle := \sum_{(k_1, \dots, k_N)} |V_{\emptyset, \emptyset}^{\rightarrow k_1; (k_2, \dots, k_N)}\rangle * |V_{\emptyset, k_1}^{\rightarrow k_2; (k_3, \dots, k_N)}\rangle * \dots * |V_{\{k_1, \dots, k_{N-2}\}, k_{N-1}}^{\rightarrow k_N; \emptyset}\rangle * |V_{\{k_1, \dots, k_{N-1}\}, k_N}^{\rightarrow F}\rangle \quad (\text{D66})
$$

instead of Eqs. (D42)–(D47).

Trace-preserving conditions. As specified above, the weight of each total order $\pi = (k_1, \dots, k_N)$ of all parties, which is encoded in the state $|\emptyset, k_1; (k_2, \dots, k_N)\rangle^{C_1}$ of the control system right after $\tilde{V}_1$, is fixed to some predefined value $q_\pi$. This weight—which can be interpreted as the probability that the control system is found in the state corresponding to that order (if it were measured in the appropriate basis)—can be obtained from the expression of $\varphi_{(1)}$ in Eq. (D63):

$$
\begin{align}
\left| \left( 1^{\tilde{A}_n^I \alpha_1} \otimes \langle \emptyset, k_1; (k_2, \dots, k_N) |^{C_1} \right) |\varphi_{(1)}\rangle \right|^2 &= \left| |\psi\rangle * |w_{(\emptyset, k_1)}^{(k_2, \dots, k_N)}\rangle \right|^2 \nonumber \\
&= \operatorname{Tr} \left[ \left( |\psi\rangle\langle\psi| \right)^T \left( \operatorname{Tr}_{A_{k_1}^I \alpha_1} |w_{(\emptyset, k_1)}^{(k_2, \dots, k_N)}\rangle \langle w_{(\emptyset, k_1)}^{(k_2, \dots, k_N)}| \right) \right] = q_{\pi} = (k_1, \dots, k_N). \tag{D67}
\end{align}
$$

Imposing that this equality holds for all possible (normalised) input states $|\psi\rangle \in \mathcal{H}^P$ requires that

$$
\mathrm{Tr}_{A_{k_1}^I \alpha_1} |w_{(\emptyset, k_1)}^{(k_2, \dots, k_N)}\rangle\langle w_{(\emptyset, k_1)}^{(k_2, \dots, k_N)}| = q_{\pi} = (k_1, \dots, k_N) \mathbf{1}^P, \quad (\text{D68})
$$

instead of the TP constraint of Eq. (D51) in the general QC-QC case.

Additionally, we impose that the internal operations $\tilde{V}_{n+1}$ preserve the weight of each future order $(k_{n+1}, \dots, k_N)$.
The total weight attached to that order before $\tilde{V}_{n+1}$ is obtained as the sum over $k_n$ of the weights corresponding to $(k_n, k_{n+1}, \dots, k_N)$ in the state $|\varphi'_{(n)}\rangle$. Namely, for $\mathcal{K}_n = \mathcal{N} \setminus \{k_{n+1}, \dots, k_N\}$ (using Eq. (D62)):

$$
\begin{align}
\sum_{k_n \in \mathcal{K}_n} \left| \left( 1^{\tilde{A}_n^O \alpha_n} \otimes \langle \mathcal{K}_n \setminus k_n, k_n; (k_{n+1}, \dots, k_N) |^{C'_n} \right) |\varphi'_{(n)}\rangle \right|^2 &= \sum_{k_n \in \mathcal{K}_n} \left| |\psi, A_{\mathcal{K}_n}\rangle * |w_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)}\rangle \right|^2 \nonumber \\
&= \operatorname{Tr} \left[ \left( |\psi, A_{\mathcal{K}_n}\rangle\langle\psi, A_{\mathcal{K}_n}| \right)^T \left( \sum_{k_n \in \mathcal{K}_n} \operatorname{Tr}_{\alpha_n} |w_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)}\rangle \langle w_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)}| \otimes 1^{A_{k_n}^O} \right) \right]. \tag{D69}
\end{align}
$$

The weight of $(k_{n+1}, \dots, k_N)$ after $\tilde{V}_{n+1}$ on the other hand is simply (using Eq. (D63))

$$
\begin{align}
& \left| \left( 1^{\tilde{A}_{n+1}^I \alpha_{n+1}} \otimes \langle \mathcal{K}_n, k_{n+1}; (k_{n+2}, \dots, k_N) |^{C_{n+1}} \right) |\varphi_{(n+1)}\rangle \right|^2 \nonumber \\
&= \left| |\psi, A_{\mathcal{K}_n}\rangle * |w_{(\mathcal{K}_n, k_{n+1})}^{(k_{n+2}, \dots, k_N)}\rangle \right|^2 \nonumber \\
&= \operatorname{Tr} \left[ \left( |\psi, A_{\mathcal{K}_n}\rangle\langle\psi, A_{\mathcal{K}_n}| \right)^T \left( \operatorname{Tr}_{A_{k_{n+1}}^I \alpha_{n+1}} |w_{(\mathcal{K}_n, k_{n+1})}^{(k_{n+2}, \dots, k_N)}\rangle \langle w_{(\mathcal{K}_n, k_{n+1})}^{(k_{n+2}, \dots, k_N)}| \right) \right]. \tag{D70}
\end{align}
$$
Imposing that these two expressions are equal, for any $|\psi\rangle$ and any $A_{\mathcal{K}_n}$, implies that one must have (for any $\mathcal{K}_n$, any $k_{n+1}, \dots, k_N \notin \mathcal{K}_n$)

$$ \mathrm{Tr}_{A_{\mathcal{K}_{n+1}}^I \alpha_{n+1}} |w_{(\mathcal{K}_n, k_{n+1})}^{(k_{n+2}, \dots, k_N)}\rangle \langle w_{(\mathcal{K}_n, k_{n+1})}^{(k_{n+2}, \dots, k_N)}| = \sum_{k_n \in \mathcal{K}_n} \mathrm{Tr}_{\alpha_n} |w_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)}\rangle \langle w_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)}| \otimes 1^{A_{\mathcal{K}_n}^O}, \quad (\text{D71}) $$

instead of Eq. (D50). For the final case of $n = N$, the corresponding constraint is

$$ \mathrm{Tr}_{F_{\alpha_F}} |w_{(\mathcal{N},F)}\rangle \langle w_{(\mathcal{N},F)}| = \sum_{k_N \in \mathcal{N}} \mathrm{Tr}_{\alpha_N} |w_{(\mathcal{N} \setminus k_N, k_N)}^{\emptyset}\rangle \langle w_{(\mathcal{N} \setminus k_N, k_N)}^{\emptyset}| \otimes 1^{A_{\mathcal{N}}^O}. \quad (\text{D72}) $$

instead of Eq. (D52).

*Process matrix description and characterisation.* As in the general QC-QC case, from the expression for $|\varphi_{(N+1)}\rangle$ in Eq. (D64), one gets the global output state of the whole QC-supFO, after tracing out $\alpha_F$:

$$ \varrho_{N+1} = \mathrm{Tr}_{\alpha_F} |\varphi_{(N+1)}\rangle\langle\varphi_{(N+1)}| = |\psi, A_{\mathcal{N}}\rangle\langle\psi, A_{\mathcal{N}}| * (\mathrm{Tr}_{\alpha_F} |w_{(\mathcal{N},F)}\rangle\langle w_{(\mathcal{N},F)}|) \in \mathcal{L}(\mathcal{H}^F). \quad (\text{D73}) $$

One can then identify the process matrix that describes the QC-supFO under consideration as

$$ W = \mathrm{Tr}_{\alpha_F} |w_{(\mathcal{N},F)}\rangle\langle w_{(\mathcal{N},F)}| \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{N}}^{IO}}), \quad (\text{D74}) $$

with $|w_{(\mathcal{N},F)}\rangle$ defined in Eq. (D66) above.

Defining, for all $n = 1, \dots, N$, all $\mathcal{K}_{n-1} \subsetneq \mathcal{N}$ and all $(k_n, k_{n+1}, \dots, k_N) \notin \mathcal{K}_{n-1}$,

$$ W_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_N)} := \mathrm{Tr}_{\alpha_n} |w_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_N)}\rangle \langle w_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_N)}| \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{K}_{n-1}}^{IO}} A_{k_n}^I), \quad (\text{D75}) $$

then it follows directly from Eq. (D74) and the TP conditions of Eqs. (D68), (D71) and (D72) that the process matrix $W (\ge 0)$ of a QC-supFO has a characterisation as in Eq. (32). Notice that this characterisation implies in particular that the $W_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_N)}$'s are valid process matrices, up to normalisation—as it was the case for the $W_{(k_1, \dots, k_n)}^{(k_{n+1}, \dots, k_N)}$'s in the decomposition of a QC-convFO (cf Footnote 37).

Conversely, the procedure of Ref. [21] that allows one to reconstruct the internal operations $V_{\mathcal{K}_{n-1}, k_n}^{\to k_{n+1}}$ and $V_{\mathcal{N} \setminus k_N, k_N}^{\to F}$ of a QC-QC from its characterisation as in Eq. (31) can be adapted here, implying that Eq. (32) is also a sufficient condition for $W$ to be a QC-supFO.

*Another perspective: QC-supFO as a recursive generalisation of the Sup class from Ref. [36].* Another subclass of QC-QCs was introduced in Ref. [36], which could also have been seen as a potential candidate to define quantum circuits with superpositions of fixed orders—it was indeed simply called Sup by the authors of [36]. We will argue however that its definition has an undesirable feature that should rule it out as such a meaningful definition of a relevant class of circuits, and that by generalising the Sup class so as to avoid this unwanted feature, we naturally recover our QC-supFO class.

Formally, the Sup class was defined as follows: $W \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{N}}^{IO}})$ is in Sup iff $W \ge 0$, and

$$ \left\{ \begin{array}{l} \mathrm{Tr}_F W = \sum_{\pi} q_{\pi} \tilde{W}_{\pi}, \\ \forall \pi, \tilde{W}_{\pi} \in \text{QC-FO}_{\pi}, q_{\pi} \ge 0, \sum_{\pi} q_{\pi} = 1. \end{array} \right. \quad (\text{D76}) $$

where QC-FO$_\pi$ is the class of quantum circuits with fixed causal order $\pi$, i.e., for $\pi = (k_1, \dots, k_N)$, of PSD matrices $W$ that admit a decomposition as in Eq. (D27). This class was meant to generalise the “static” quantum switch, in which the control system is initially prepared in some predefined quantum state corresponding to a superposition of fixed orders and ultimately sent to $\mathcal{H}^F$ in the global future, so that tracing $\mathcal{H}^F$ out leaves the rest of the parties in an incoherent mixture of processes with fixed causal order.

The unwanted feature we identify in the definition of Sup above is that it crucially depends on the labelling of $\mathcal{H}^F$. More specifically, recall first that considering the future space $\mathcal{H}^F$ as “open” or attributing it to an additional party, with no output space, leads to formally equivalent frameworks [21, 27]. Now, if one were to rename $\mathcal{H}^F$ and consider it as the input space of a new party, treated on equal footing with the other ones, then the definition of the Sup class above would change.
Concretely, it can be seen for example that the process matrix of the “static” quantum switch, $W_{supFO}$ from Eq. (35), is in Sup. However, if one were to attribute $\mathcal{H}^F$—or even just $\mathcal{H}^{F_c}$—to another party (call it C) and write $W_{supFO} = |w_{supFO}\rangle\langle w_{supFO}|$ with $|w_{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^{C_I} + \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^{C_I}$ instead of Eq. (35), then one would conclude that $W_{supFO} \notin \text{Sup}$—even though the situation is physically exactly the same as the one in which one concludes that $W_{supFO} \in \text{Sup}$.

This observation leads us to argue that any physically meaningful definition of a class of quantum circuits should not depend on the labellings of the different parties, including (crucially) parties in the global past or future.42 In particular, if two parties have no output space, the class should not depend on whose input space if called $\mathcal{H}^F$; similarly if two parties have no input space, the class should not depend on whose output space if called $\mathcal{H}^P$. One can verify that all our classes satisfy this requirement.43 We will now see how one can modify the Sup class so as to also satisfy it.

For this, recall that the defining property of Sup is that if one traces out $\mathcal{H}^F$, one should be left with an incoherent mixture of fixed causal orders. If one attributes $\mathcal{H}^F$ to another party, we would hence like that there is different party in the future, such that if one traces them out, the rest should be in an incoherent mixture of fixed orders.

The key insight we can take from the example of $W_{supFO}$ just discussed is that in order to conclude that $W_{supFO} \in \text{Sup}$, it may not be enough to just trace one future party out; after tracing out one party, one may need to check whether one is left in a situation where another party can be considered to be in the future of the remaining ones, such that tracing it out leaves the other ones in an incoherent mixture of orders—or more generally, whether one is left in an (incoherent) mixture of such situations, with fixed weights. This suggests considering a recursive generalisation of the Sup class that would formalise this.

As it turns out, following this idea provides an alternative characterisation of our class QC-supFO. More formally: let us add subscripts and write QC-supFO$_{P,N,F}$ to specify the global past Hilbert space $\mathcal{H}^P$, the set of parties $N$, and the global future Hilbert space $\mathcal{H}^F$ considered in the definition of QC-supFO. We show below that QC-supFO = QC-supFO$_{P,N,F}$ has the following recursive characterisation, which formalises precisely our suggestion above for generalising the Sup class:

$$ \text{QC-supFO}_{P,N,F} = \left\{ W \in \mathcal{L}(\mathcal{H}^{PA^{IO}_N F}) \left| \begin{array}{l} W \ge 0, \text{Tr}_F W = \sum_{k_N \in N} q^{[k_N]} \tilde{W}^{[k_N]} \otimes 1^{A^{O}_{k_N}}, \\ q^{[k_N]} \ge 0, \sum_{k_N} q^{[k_N]} = 1, \\ \tilde{W}^{[k_N]} \in \text{QC-supFO}_{P,N \setminus k_N, A^{I}_{k_N}} \end{array} \right. \right\} \quad \text{for } |N| \ge 1, \\ \text{QC-supFO}_{P,\emptyset,F} = \left\{ W \in \mathcal{L}(\mathcal{H}^{PF}) \left| W \ge 0, \text{Tr}_F W = 1^P \right. \right\}. \qquad (D77) $$

This characterisation could also be taken as a definition of our class QC-supFO, which can therefore be seen, from this perspective, as a natural generalisation of the Sup class of Ref. [36]. It can indeed be checked that if two parties $F_1, F_2$ have no output Hilbert spaces, then QC-supFO$_{P,N \cup F_1, F_2} = \text{QC-supFO}_{P,N \cup F_2, F_1}$: the above characterisation does not depend on which of $F_1, F_2$ is labelled F, thus indeed resolving the issue with the Sup class that we pinpointed above.

**Proof of Eq. (D77):** Let us denote by QC-supFO'$_{P,N,F}$ the RHS of the first equation in (D77) (adding the prime recursively, to QC-supFO$_{P,N \setminus k_N, A^{I}_{k_N}}$ and QC-supFO$_{P,\emptyset,F}$ as well)—so that our task here is to prove that QC-supFO$_{P,N,F}$ = QC-supFO'$_{P,N,F}$, with QC-supFO$_{P,N,F}$ defined by Eq. (32).

* For $|N| = N = 1$ ($N = \{A\}$), it is easy to see that the set QC-supFO'$_{P,\{A\},F}$ = $\{W \in \mathcal{L}(\mathcal{H}^{PA^{IO}F}) | W \ge 0, \text{Tr}_F W = \tilde{W}^{[A]} \otimes 1^{A^O}, \text{Tr}_{A_I} \tilde{W}^{[A]} = 1^P\}$ coincides with QC-supFO$_{P,\{A\},F}$ as characterised by Eq. (32). (These in fact also coincide with the set of all valid process matrices, as characterised through Eq. (D3).)

* Assume that QC-supFO$_{P,N',F}$ = QC-supFO'$_{P,N',F}$ for all $N'$ such that $|N'| = N - 1 \ge 1$.

<footnote n="42">42 Unless the class one wishes to define refers explicitly to a certain labelling of the parties. E.g. the class QC-FO$_{\pi=(A,B)}$ of quantum circuits with the fixed causal order (A, B) is of course different from the class QC-FO$_{\pi=(B,A)}$ obtained by swapping the two parties' labels.</footnote>

<footnote n="43">43 Except for QC-FO$_{\pi}$, see the previous footnote.</footnote>
Consider then $W \in \text{QC-supFO}'_{P,\mathcal{N}',F}$; by definition $\text{Tr}_F W$ can be decomposed as a convex mixture

$$ \text{Tr}_F W = \sum_{k_N \in \mathcal{N}} q^{[k_N]} \tilde{W}^{[k_N]} \otimes 1^{A_{k_N}^O} \qquad (\text{D78}) $$

with each $\tilde{W}^{[k_N]} \in \text{QC-supFO}_{P,\mathcal{N}\setminus k_N, A_{k_N}^I}$, which therefore has a decomposition in terms of PSD matrices $\tilde{W}_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_{N-1})};[k_N] \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{K}_{n-1}}^{IO}} A_{k_n}^I)$ as in Eq. (32):

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

Defining $W_{(\mathcal{N}\setminus\{k_N\}, k_N)}^{\emptyset} := q^{[k_N]} \tilde{W}^{[k_N]}$, $W_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_{N-1}, k_N)} := q^{[k_N]} \tilde{W}_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_{N-1});[k_N]}$ and $q_{\pi'}=(k_1, \dots, k_{N-1}, k_N) := q^{[k_N]} q_{\pi'}^{[k_N]}$, one can see that Eqs. (D78) and (D79) together provide a decomposition of $W$ as in Eq. (32), which proves that $W \in \text{QC-supFO}_{P,\mathcal{N},F}$.

Conversely, consider $W \in \text{QC-supFO}_{P,\mathcal{N}',F}$, with a decomposition as in Eq. (32). Defining, for each $k_N$, $q^{[k_N]} := \sum_{(k_1, \dots, k_{N-1}) \in \mathcal{N} \setminus k_N} q_{\pi'}=(k_1, \dots, k_{N-1}, k_N)$ and $\tilde{W}^{[k_N]} := W_{(\mathcal{N} \setminus \{k_N\}, k_N)}^{\emptyset}/q^{[k_N]}$ (when $q^{[k_N]} > 0$; otherwise, $\tilde{W}^{[k_N]} := 0$), then one obtains a decomposition of $\text{Tr}_F W$ as in Eq. (D78) above, with $q^{[k_N]} \ge 0$, $\sum_{k_N} q^{[k_N]} = 1$, and one can further see that each $\tilde{W}^{[k_N]}$ admits itself a decomposition of the form of Eq. (32), in terms of PSD matrices $\tilde{W}_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_{N-1})};[k_N] := W_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_{N-1}, k_N)}/q^{[k_N]}$ and with weights $q_{\pi'}^{[k_N]}_{\pi'}=(k_1, \dots, k_{N-1}) := q_{\pi'}=(k_1, \dots, k_{N-1}, k_N) / q^{[k_N]}$ in the final constraint. This implies that each $\tilde{W}^{[k_N]} \in \text{QC-supFO}_{P,\mathcal{N}\setminus k_N, F}$, and hence that $W \in \text{QC-supFO}'_{P,\mathcal{N},F}$. We thus have that $\text{QC-supFO}'_{P,\mathcal{N},F} = \text{QC-supFO}_{P,\mathcal{N},F}$. This, by recursion, concludes the proof of Eq. (D77).

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

The last class we introduced is that of QC-NIQCs, defined in Sec. III C 3 of the main text as follows:

QC-NIQCs are the QC-QCs for which at any intermediate time step, the classical weights of each term in the basis $\{|\mathcal{K}_{n-1}, k_n\rangle\rangle^{C_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.

(with, as for QC-NICCs, the external operations referring to the parties' whole instruments rather than the individual CP maps that compose them, and the state of the control system being considered after summing over all these individual CP maps—and over all their Kraus operators when one starts from a description in the “pure” picture).

The state $|\varphi_{(n)}\rangle$ of all systems at any intermediate time step $t_n$ (for $n = 1, \dots, N$, just before$^{44}$ applying the operator $\tilde{A}_n$) is given by Eq. (D44). From this, the weight of each component $|\mathcal{K}_{n-1}, k_n\rangle\rangle^{C_n}$ of the control system is obtained as

$$ \left\| |\psi, A_{\mathcal{K}_{n-1}}\rangle * |w_{(\mathcal{K}_{n-1}, k_n)}\rangle \right\|^2 = \text{Tr} \left[ \left( |\psi\rangle\langle\psi| \bigotimes_{k \in \mathcal{K}_{n-1}} |A_k\rangle\rangle \langle\langle A_k| \right) * W_{(\mathcal{K}_{n-1}, k_n)} \right], \qquad (\text{D80}) $$

with $W_{(\mathcal{K}_{n-1}, k_n)} = \text{Tr}_{\alpha_n} |w_{(\mathcal{K}_{n-1}, k_n)}\rangle\langle w_{(\mathcal{K}_{n-1}, k_n)}|$ as defined in Eq. (D55). Summing over the Kraus operators $A_k$ so as to obtain a CPTP map for each party—whose Choi matrix, abusing the notation slightly, we still denote by $A_k$ (see Footnote 40)—the requirement expressed above translates into the constraint that for all $\mathcal{K}_{n-1}, k_n$,

$$ \text{Tr} \left[ \left( |\psi\rangle\langle\psi| \bigotimes_{k \in \mathcal{K}_{n-1}} A_k \right) * W_{(\mathcal{K}_{n-1}, k_n)} \right] \text{ does not depend on } \rho \text{ nor on the } A_k\text{'s,} \\ \text{whenever all } A_k\text{'s are TP (and } |\psi\rangle\text{ is normalised)}. \qquad (\text{D81}) $$

<footnote>$^{44}$ Considering the case where the external operations are TP, the reduced state of the control system after the operator $\tilde{A}_n$ (and after summing over the corresponding Kraus operators) will be the same; as in Eq. (D28) (see also Footnote 38).</footnote>
Recalling the discussion at the end of Sec. D 1, this is equivalent to

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

as in Eq. (33).

Conversely, as recalled above, from the characterisation of a QC-QC as in Eq. (31), one can reconstruct internal operations that realise it; one can verify that the additional validity constraint above implies indeed that these internal operations are such that the diagonal elements of the state of the control system are independent of the external TP operations—implying that the QC-QC under consideration is then a QC-NIQC.

### d. Inclusion relations

Let us start here by noting that each of the three classes of quantum circuits with quantum control considered above contains the corresponding class with classical control as a subclass: QC-convFO $\subset$ QC-supFO, QC-NICC $\subset$ QC-NIQC and QC-CC $\subset$ QC-QC. In the latter case for instance, this can be seen by starting from a QC-CC decomposition in terms of PSD matrices $W_{(k_1,...,k_N,F)}$ and $W_{(k_1,...,k_n)}$ as in Eq. (24), and defining $W_{(\mathcal{K}_{n-1},k_n)} := \sum_{(k_1,...,k_{n-1}) \in \mathcal{K}_{n-1}} W_{(k_1,...,k_n)}$, which indeed readily provide a QC-QC decomposition as in Eq. (31). For QC-convFO $\subset$ QC-supFO, a similar construction works, after just adding the appropriate superscripts $(k_{n+1},...,k_N)$. For QC-NICC $\subset$ QC-NIQC, we further note that if $W_{(k_1,...,k_n)}$'s are valid process matrices (up to normalisation), then so are the $W_{(\mathcal{K}_{n-1},k_n)}$'s just defined.

Quite trivially, for $N = 1$ all six classes reduce to the same one—which is also the whole class of all valid process matrices. For $N = 2$, with a nontrivial global future space $\mathcal{H}^F$, one already obtains a strict separation between the three QC-QC classes and their QC-CC counterparts: indeed the “static quantum switch”, $W_{\text{supFO}}$ from Eq. (35), provides in that scenario an example in QC-supFO (hence also in QC-NIQC and QC-QC, see below) but not in QC-CC (nor in any of its subclasses). If $\mathcal{H}^F$ is trivial on the other hand, one can easily see that for $N = 2$ each of the three QC-QC classes reduces to its QC-CC counterpart; one then needs to go to $N \ge 3$ to see a strict separation.

Let us now compare the three (sub)classes of QC-QCs.

It is again quite clear, from the definition of the QC-NIQC class just above, that QC-NIQC $\subset$ QC-QC. To see that QC-supFO $\subset$ QC-NIQC, consider a process matrix $W \in \text{QC-supFO}$, with a decomposition in terms of PSD matrices (and even valid process matrices, up to normalisation) $W_{(\mathcal{K}_{n-1},k_n)}$ as in Eq. (32); defining, for each $(\mathcal{K}_{n-1}, k_n)$, $W_{(\mathcal{K}_{n-1},k_n)} := \sum_{(k_{n+1},...,k_N)} W_{(\mathcal{K}_{n-1},k_n)}$, one can easily see that these satisfy the QC-QC decomposition of Eq. (31), and that these are themselves valid process matrices (up to normalisation), which proves that $W \in \text{QC-NIQC}$. Hence, we obtain the general inclusion relations of Eq. (34):

$$ \text{QC-supFO} \subset \text{QC-NIQC} \subset \text{QC-QC}. \qquad (\text{D83}) $$

For $N = 2$ already, with a nontrivial global past space $\mathcal{H}^P$, one finds a strict separation between QC-NIQC and QC-QC. An example of a process matrix in QC-QC\QC-NIQC was given by the quantum switch $W_{\text{QS}}$, Eq. (39) of the main text (for $N = 2$ indeed, with a nontrivial space $\mathcal{H}^P$ but also a nontrivial space $\mathcal{H}^F$ to avoid falling back into the QC-CC class; see above). If $\mathcal{H}^P$ is trivial on the other hand, QC-NIQC and QC-QC coincide for $N = 2$ (the proof being quite similar to that for QC-NICC = QC-CC in the same scenario, see p. 45), and one needs to go to $N \ge 3$ to see a strict separation.

As for QC-supFO vs QC-NIQC, these can be seen to coincide for $N \le 3$ (again, the proof is quite similar to that for QC-convFO = QC-NICC in the same $N \le 3$ case, on p. 45). A strict separation can be found for $N \ge 4$: an example of a process matrix in QC-NIQC\QC-supFO (which was also not in QC-CC), for $N = 4$ with trivial global past and future spaces $\mathcal{H}^P, \mathcal{H}^F$, was given by $W_{\text{NIQC}}$ from Eq. (29).

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

We finish this section on QC-QCs by providing explicit decompositions of our examples of QC-QCs from Sec. III C 4, in the appropriate form so as to match the characterisation of the class that they belong to.

The process matrix $W_{\text{supFO}} = |w_{\text{supFO}}\rangle\langle w_{\text{supFO}}|$, with $|w_{\text{supFO}}\rangle = \frac{1}{\sqrt{2}}|\psi\rangle^{A^I} \otimes |1\rangle\rangle^{A^O B^I} \otimes |1\rangle\rangle^{B^O F_t} \otimes |0\rangle\rangle^{F_t} + \frac{1}{\sqrt{2}}|\psi\rangle^{B^I} \otimes |1\rangle\rangle^{B^O A^I} \otimes |1\rangle\rangle^{A^O F_t} \otimes |1\rangle\rangle^{F_t}$ of the “static”, or “non-dynamical” quantum switch, Eq. (35), can be decomposed in the
QC-supFO form of Eq. (32), with

$$
\left\{
\begin{array}{l}
W_{\{A\},B\}}^{\emptyset} = \frac{1}{2}|\psi\rangle\langle\psi|^A \otimes |1\rangle\langle 1|^A, \qquad W_{\{B\},A\}}^{\emptyset} = \frac{1}{2}|\psi\rangle\langle\psi|^B \otimes |1\rangle\langle 1|^B, \\
\\
W_{\emptyset,A}^{(B)} = \frac{1}{2}|\psi\rangle\langle\psi|^A, \qquad W_{\emptyset,B}^{(A)} = \frac{1}{2}|\psi\rangle\langle\psi|^B, \\
\\
q_{(A,B)} = q_{(B,A)} = \frac{1}{2}.
\end{array}
\right.
\qquad (\text{D84})
$$

Notice that this is (up to very slightly different notations) the same decomposition as that given for $W_{\text{convFO}}$ in Eq. (D32). This is because $\text{Tr}_F W_{\text{supFO}} = W_{\text{convFO}}$, and because the QC-supFO constraints for $\text{Tr}_F W_{\text{supFO}}$ reduce (in the $N=2$ case, with no more $\mathcal{H}^F$) to the QC-convFO constraints. Besides, it is also well-known—and easy to see—that $W_{\text{supFO}}$ is not a QC-CC (noting that $W_{\text{supFO}} = |w_{\text{supFO}}\rangle\langle w_{\text{supFO}}|$ is rank-1, so that any decomposition of $W_{\text{supFO}}$ directly into PSD matrices can only contain terms that are proportional to itself).

Our example of a QC-NIQC, $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^{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^{C^O}$ from Eq. (38), with $W_0$ and $W_1$ two (valid) process matrices defined in Eq. (37) and satisfying $\frac{1}{2}W_0 + \frac{1}{2}W_1 = \frac{1}{8}(21^{\otimes 4} + 2Z1Z1 + XZX1 - YZY1 + X1XZ - Y1YZ)^{A^I B^{I^O}}$, admits a QC-NIQC decomposition of the form of Eq. (31), with the valid process matrices (up to normalisation, as required the QC-NIQC condition of Eq. (33))

$$
\left\{
\begin{aligned}
W_{\{(A,B,C),D\}} &= \frac{1}{2}W_0 \otimes |0\rangle\langle 0|^{C^I} \otimes |1\rangle\langle 1|^{C^O D^I}, & W_{\{(A,B,D),C\}} &= \frac{1}{2}W_1 \otimes |0\rangle\langle 0|^{D^I} \otimes |1\rangle\langle 1|^{D^O C^I}, \\
W_{\{(A,B),C\}} &= \frac{1}{2}W_0 \otimes |0\rangle\langle 0|^{C^I}, & W_{\{(A,B),D\}} &= \frac{1}{2}W_1 \otimes |0\rangle\langle 0|^{D^I}, \\
W_{\{(A),B\}} &= \frac{1}{8}(1^{\otimes 3} + Z1Z + XZX - YZY)^{A^I B^{I^O}}, & W_{\{(B),A\}} &= \frac{1}{8}(1^{\otimes 3} + ZZ1 + XXZ - YYZ)^{A^I B^{I^O}}, \\
W_{\emptyset,A} &= \frac{1}{4}1^{A^I}, & W_{\emptyset,B} &= \frac{1}{4}1^{B^I},
\end{aligned}
\right.
\qquad (\text{D85})
$$

and all other $W_{(\mathcal{K}_{n-1},k_n)} = 0$.

Finally, the process matrix $W_{QS} = |w_{QS}\rangle\langle w_{QS}|$, with $|w_{QS}\rangle = |0\rangle^P \otimes |\psi\rangle^A \otimes |1\rangle^A \otimes |1\rangle^B \otimes |1\rangle^B \otimes |0\rangle^F_c + |1\rangle^P \otimes |\psi\rangle^B \otimes |1\rangle^B \otimes |1\rangle^B \otimes |1\rangle^B \otimes |0\rangle^F_c$ of the “dynamical” quantum switch, Eq. (39), can be decomposed in the general QC-QC form of Eq. (31) as follows:

$$
\left\{
\begin{array}{l}
W_{\{(A),B\}} = |0\rangle\langle 0|^P \otimes |\psi\rangle\langle\psi|^{A^I} \otimes |1\rangle\langle 1|^{A^O B^I}, \quad W_{\{(B),A\}} = |1\rangle\langle 1|^P \otimes |\psi\rangle\langle\psi|^{B^I} \otimes |1\rangle\langle 1|^{B^O A^I}, \\
\\
W_{\emptyset,A} = |0\rangle\langle 0|^P \otimes |\psi\rangle\langle\psi|^{A^I}, \quad W_{\emptyset,B} = |1\rangle\langle 1|^P \otimes |\psi\rangle\langle\psi|^{B^I}.
\end{array}
\right.
\qquad (\text{D86})
$$

Notice that this is again essentially the same decomposition as that given for the process matrix of the classical switch $W_{\text{CS}}$ in Eq. (D34). This is because $\text{Tr}_F W_{\text{QS}} = W_{\text{CS}}$, and because the QC-QC constraints for $\text{Tr}_F W_{\text{QS}}$ reduce (in the $N=2$ case, with no more $\mathcal{H}^F$) to the QC-CC constraints. As in the case of $W_{\text{CS}}$, none of the matrices in the above decomposition are valid process matrices; indeed it can be shown via SDP that no decomposition of the form of Eq. (31) exists for $W_{\text{QS}}$ with only valid $W_{\{(k_1),k_2\}}$'s and $W_{\emptyset,k_1}$'s, which implies that $W_{\text{QS}}$ is not a QC-NIQC. Besides, it is also well-known—and again easy to see—that $W_{\text{QS}}$ is not a QC-CC (e.g., by contradiction: otherwise, feeding the state $|+\rangle = \frac{|0\rangle+|1\rangle}{\sqrt{2}}$ into $\mathcal{H}^P$ would otherwise imply that $W_{\text{supFO}}$ is a QC-CC).

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

Looking at the SDP constraints that characterise each of the classes we considered in this work (see Eqs. (24), (25), (31), and (32)), one may notice some similar structure in the different decompositions. Here we propose a graphical representation of these constraints that exploits their common features and helps visualise the structure of the different classes.

Each of the decompositions under consideration involves PSD matrices in $\mathcal{L}(\mathcal{H}^{PA_{K_{n-1}}^{I^O} A_{k_n}^I})$ (for some subset $K_{n-1} \subsetneq \mathcal{N}$ and some $k_n \notin K_{n-1}$) and in $\mathcal{L}(\mathcal{H}^{PA_N^F})$, as well as the identity matrix $1^P \in \mathcal{L}(\mathcal{H}^P)$. The idea of the representation we propose is to organise these PSD matrices in a graph, defined as follows.
* The nodes are the various PSD matrices that appear in the decomposition. These are organised in $N + 2$ layers: matrices in some $\mathcal{L}(\mathcal{H}^{PA_{K_{n-1}}^{IO}}_{k_n})$ appear on the $n^{th}$ layer, for each $n = 1, \dots, N$ (from the bottom up), matrices in $\mathcal{L}(\mathcal{H}^{PA_N F})$ appear on the $(n = N + 1)^{th}$ (top) layer, while the $1$'s (i.e. the $1^P$'s; we will drop the superscript $P$) appear on the $(n = 0)^{th}$ (bottom) layer.

* For any SDP constraint of the general form $(\sum_{k_{n+1}}) \text{Tr}_{A_{k_{n+1}}^I} W(\dots, k_{n+1}) = (\sum_{k_n}) W(\dots, k_n) \otimes 1^{A_{k_n}^O}$, with $1 \le n \le N - 1$, all matrices $W(\dots, k_{n+1})$ appearing on the LHS of the equality (and on the $(n+1)^{th}$ layer in the graph) are connected to all matrices $W(\dots, k_n)$ appearing on the RHS of the equality (and on the $n^{th}$ layer in the graph).

* For any SDP constraint of the form $\text{Tr}_F W(\dots) = (\sum_{k_N}) W(\dots, k_N) \otimes 1^{A_N^O}$, for some $W(\dots) \in \mathcal{L}(\mathcal{H}^{PA_N F})$, the matrix $W(\dots)$ (that appears on the top layer in the graph) is connected to all matrices $W(\dots, k_N)$ appearing on the RHS of the equality (and on the $N^{th}$ layer in the graph).

* For any SDP constraint of the form $(\sum_{k_1}) \text{Tr}_{A_{k_1}^I} W(\dots, k_1) = q(\dots) 1^P$ (possibly with $q(\dots) = 1$), all matrices $W(\dots, k_1)$ appearing on the LHS of the equality (and on the $(n=1)^{th}$ layer in the graph) are connected to $q(\dots) 1$ (that appears on the bottom layer in the graph).

For concreteness, let us start by illustrating this for the QC-CC class, characterised in Eq. (24). From the bottom to the top: the matrix $1 = 1^P$, on the bottom layer) is connected to all $W(k_1)$'s (on the $(n=1)^{th}$ layer); then each $W(k_1, \dots, k_n)$ (for $n=1, \dots, N-1$, on the $n^{th}$ layer) is connected to all $W(k_1, \dots, k_n, k_{n+1})$'s (with the same first labels $(k_1, \dots, k_n)$, on the $(n+1)^{th}$ layer); finally, each $W(k_1, \dots, k_N)$ (on the $N^{th}$ layer) is connected to $W(k_1, \dots, k_N, F)$ (on the top layer). We thus obtain a branch-graph structure, as illustrated in Fig. 11 for the $N=3$ case.

<figure><img src="image_12.png" /><figcaption>Figure 11. Graphical representation of the SDP constraints of Eq. (24), for the QC-CC class with $N=3$. For the QC-NICC class, all matrices that appear in the graph must be valid process matrices (up to normalisation), see Eq. (26).</figcaption></figure>

Following the above construction, we can similarly build the graphs that represent the SDP constraints for our other classes: these are shown in Fig. 12 for the QC-convFO class (with $N=3$), in Fig. 13 for the QC-QC class (with $N=3$ and $4$), and in Fig. 14 for the QC-supFO class (with $N=3$). These representations help visualise certain features of each class: e.g., that the QC-convFO class involves independent orders, in parallel; that the graph of the QC-QC class has an “upside-down symmetry”; that the graph of the QC-supFO class is the “upside-down version” of that of the QC-CC class (reflecting the comment made a couple of paragraphs below Eq. (32)).

Conversely, rather than building the graph corresponding to a given set of SDP constraints, one can take a given graph to define a set of SDP constraints, and thereby a class of quantum circuits.

An “SDP-constraints-defining graph” must be of a certain form:

* It must be a layered graph, with $N+2$ layers for a class of $N$-slot circuits, each being referred to by an integer $n=0, \dots, N+1$.

* To each node on a layer $n=1, \dots, N$, one attaches an $(n-1)$-partite set of parties $K_{n-1} \subset \mathcal{N}$, a party labelled by $k_n \notin K_{n-1}$ (these could be the same for two different nodes on the same layer), and a PSD matrix in $\mathcal{L}(\mathcal{H}^{PA_{K_{n-1}}^{IO}}_{k_n})$. As a general convention these matrices are denoted $W_{\dots}^{\dots}$, where the subscript contains $n$.
<figure><img src="image_13.png" /><figcaption>Figure 12. Graphical representation of the SDP constraints of Eq. (25), for the QC-convFO class with $N = 3$.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 13. Graphical representation of the SDP constraints of Eq. (31), for the QC-QC class with $N = 3$ (top) and $N = 4$ (bottom, where we drew the edges between the middle two layers with colours to help visualise which matrices are connected together, in the different “branches”). For the QC-NIQC class, all matrices that appear in the graph must be valid process matrices (up to normalisation), see Eq. (33).</figcaption></figure>

Notice the upside-down symmetry of the graph: flipping the graph upside-down and relabelling the nodes according to $W_{(\mathcal{K}_{n-1},k_n)} \leftrightarrow W_{(\mathcal{N}\setminus\mathcal{K}_{n-1}\setminus k_n, k_n)}$, $W \leftrightarrow 1$ gives the same graph.
<figure><img src="image_15.png" /><figcaption>Figure 14. Graphical representation of the SDP constraints of Eq. (32), for the QC-supFO class with $N = 3$. Notice that this graph is the upside-down version of that of the QC-CC class (that one obtains by flipping the graph here and relabelling the nodes according to $W \to 1$, $W_{(K_{n-1}, k_n)}^{(k_{n+1}, \dots, k_N)} \to W_{(k_N, \dots, k_n)}$, $q_{(k_1, \dots, k_N)} \to W_{(k_N, \dots, k_1, F)}$).</figcaption></figure>

parties: the first $n-1$ parties altogether form $K_{n-1}$, while the last party in the subscript is $k_n$ (so that the notations themselves define $K_{n-1}, k_n$ unambiguously).

* To each node on layer $n = N + 1$ one attaches a PSD matrix in $\mathcal{L}(\mathcal{H}^{PA_{N}^{IO}F})$.

* To each node on layer $n = 0$ one attaches a PSD matrix in $\mathcal{L}(\mathcal{H}^P)$—typically, $1$ or $q...1$, for some $q... \ge 0$.

* Edges only connect nodes in subsequent layers. The edges between any two subsequent layers $n, n+1$ (for $n = 0, \dots, N$) define a so-called “branched relation” [37]: the sets $S_n, S_{n+1}$ of matrices in the lower and upper layers are partitioned into $S_n = \cup_j S_{n,j}^{\uparrow}$ and $S_{n+1} = \cup_j S_{n+1,j}^{\downarrow}$, with the $S_{n,j}^{\uparrow}$’s and the $S_{n+1,j}^{\downarrow}$’s being in one-to-one correspondence, such that for each $j$, all matrices in $S_{n,j}^{\uparrow}$ are connected to all matrices in $S_{n+1,j}^{\downarrow}$.<fnref n="45" /> Each pair $B_{n,j} = (S_{n,j}^{\uparrow}, S_{n+1,j}^{\downarrow})$ defines a so-called “branch”.

Furthermore, for $n = 1, \dots, N-1$, it is required that in any branch $B_{n,j} = (S_{n,j}^{\uparrow}, S_{n+1,j}^{\downarrow})$, the sets $K_{n-1} \cup k_n$ attached to all matrices in $S_{n,j}^{\uparrow}$ are the same, and are the same as all sets $K_n$ attached to all matrices in $S_{n+1,j}^{\downarrow}$.<fnref n="46" />

Any graph of the above form then defines a set of linear constraints (hence, SDP constraints when one further requires that all matrices are PSD) as follows:

* for all matrices $W_i$ of the top ($n = N + 1$) layer: $W = \sum_i W_i$;

* for $n = 1, \dots, N-1$: for any branch $B_{n,j} = (S_{n,j}^{\uparrow}, S_{n+1,j}^{\downarrow})$, $\sum_{W(\dots, k_{n+1}) \in S_{n+1,j}^{\downarrow}} \text{Tr}_{A_{k_{n+1}}^I} W(\dots, k_{n+1}) = \sum_{W(\dots, k_n) \in S_{n,j}^{\uparrow}} W(\dots, k_n) \otimes 1^{A_{k_n}^O}$;<fnref n="47" />

* for all matrices $W_i$ of the bottom ($n = 0$) layer: $\sum_i W_i = 1^P$.

The set of all $W$'s that satisfy these constraints forms a certain class of process matrices, thus directly defined from the graph under consideration.

One can verify that the graphs in Figs. 11 to 14 are indeed of the required form specified above, and that starting from these graphs, one obtains the constraints that characterise the QC-CC, QC-convFO, QC-QC and QC-supFO classes, as given in Eqs. (24), (25), (31), and (32), respectively (for the specified values of $N$). An example of a class only defined through its graph representation will be given in Appendix E 2d (see Fig. 16); this will illustrate how convenient the graph representation is, compared to the explicit specification of all constraints separately, and how it allows one to nicely visualise their structure. It would be interesting to explore which further insights can be gained, or which properties of the process matrices can be read, directly from such a graphical representation.

<footnote n="45">⁴⁵ Each layer (each set of matrices $S_n$), for $n = 1, \dots, N$, is thus partitioned in two different ways, $S_n = \cup_j S_{n,j}^{\uparrow} = \cup_k S_{n,k}^{\downarrow}$. The number of subsets in both partitions can be different.</footnote>

<footnote n="46">⁴⁶ Recall from the second bullet point above that a subset $K_{n-1}$ and a party $k_n$ are attached to each node in $S_{n,j}^{\uparrow}$; similarly, a subset $K_n$ and a party $k_{n+1}$ are attached to each node in $S_{n+1,j}^{\downarrow}$.</footnote>

<footnote n="47">⁴⁷ The last requirement on the general form of an “SDP-constraints-defining graph”, as stated above, ensures that all terms (on both sides of the equality) live in the same space.</footnote>
# Appendix E: Correlations induced by quantum circuits with classical or quantum control of causal order

In this appendix, we prove the claims that each of the classes of quantum circuits with classical or quantum control of causal order considered in the paper generate correlations in a given set.

Recall that these are given by the generalised Born rule of Eq. (22) (considering here trivial global past and future spaces $\mathcal{H}^P, \mathcal{H}^F$): $p(\vec{a}|\vec{x}) = \text{Tr}[(M_{\vec{a}|\vec{x}})^T W]$ with $\vec{x} = (x_1, \dots, x_N)$, $\vec{a} = (a_1, \dots, a_N)$, where for convenience we introduced here the notation $M_{\vec{a}|\vec{x}} := \bigotimes_{k=1}^N M_{a_k|x_k}$ (not to be confused with the resulting global map $M_{\vec{a}|\vec{x}}^{PF}$ of Eq. (23), in the presence of $\mathcal{H}^P, \mathcal{H}^F$), and where each $\{M_{a_k|x_k}\}_{a_k}$, for each $x_k$, denotes a quantum instrument (in the Choi picture).

## 1. Correlations induced by QC-CCs

Let us start with the correlations induced by QC-CCs. As described in the previous appendix, in these circuits one can identify some control system that encodes in a classical manner the causal order (which may be established dynamically). It is then rather straightforward to see the connection between the (sub)class of QC-CCs under consideration and the type of correlations that can be generated, and to construct the causal decompositions $p(\vec{a}|\vec{x}) = \sum_\pi p(\pi, \vec{a}|\vec{x})$ explicitly.

### a. Correlations induced by QC-CCs are in $\mathcal{P}_{\text{causal}}$

A process matrix $W \in \text{QC-CC}$ has a decomposition as in Eq. (24); recalling that we consider here some trivial global past $(\mathcal{H}^P)$ and future $(\mathcal{H}^F)$ spaces, we have in particular that $W = \sum_{(k_1, \dots, k_N)} W_{(k_1, \dots, k_N)} \otimes 1^{A_{k_N}^O}$.

Let us then define

$$ p((k_1, \dots, k_N), \vec{a}|\vec{x}) := \text{Tr}[(M_{\vec{a}|\vec{x}})^T (W_{(k_1, \dots, k_N)} \otimes 1^{A_{k_N}^O})], \quad \text{such that } p(\vec{a}|\vec{x}) = \sum_{(k_1, \dots, k_N)} p((k_1, \dots, k_N), \vec{a}|\vec{x}). \quad (\text{E1}) $$

From Eq. (24) and using the trace-preserving property that $\sum_{a_k} \text{Tr}_{A_k^O} M_{a_k|x_k} = 1^{A_k^I}$ for each instrument, it is easy to see, recursively, that (for all $n = 0, \dots, N-1$ and all $(k_1, \dots, k_n, k_{n+1})$)

$$ \begin{aligned} p((k_1, \dots, k_n, k_{n+1}), \vec{a}_{k_1, \dots, k_n} | \vec{x}) &= \sum_{\substack{(k_{n+2}, \dots, k_N) \\ \vec{a}_{k_{n+1}, k_{n+2}, \dots, k_N}}} p((k_1, \dots, k_n, k_{n+1}, k_{n+2}, \dots, k_N), \vec{a} | \vec{x}) \\ &= \text{Tr} \left[ (M_{\vec{a}_{k_1, \dots, k_n} | \vec{x}_{k_1, \dots, k_n}})^T \left( \text{Tr}_{A_{k_{n+1}}^I} W_{(k_1, \dots, k_{n+1})} \right) \right]. \end{aligned} \quad (\text{E2}) $$

Indeed, for $n = N-1$,

$$ \begin{aligned} p((k_1, \dots, k_N), \vec{a}_{k_1, \dots, k_{N-1}} | \vec{x}) &= \sum_{a_{k_N}} \text{Tr}[(M_{\vec{a}|\vec{x}})^T (W_{(k_1, \dots, k_N)} \otimes 1^{A_{k_N}^O})] \\ &= \text{Tr} \left[ \underbrace{(M_{\vec{a}_{k_1, \dots, k_{N-1}} | \vec{x}_{k_1, \dots, k_{N-1}}} \otimes \sum_{a_{k_N}} \text{Tr}_{A_{k_N}^O} M_{a_{k_N}|x_{k_N}})^T}_{1} W_{(k_1, \dots, k_N)} \right] \\ &= \text{Tr} \left[ (M_{\vec{a}_{k_1, \dots, k_{N-1}} | \vec{x}_{k_1, \dots, k_{N-1}}})^T \left( \text{Tr}_{A_{k_N}^I} W_{(k_1, \dots, k_N)} \right) \right]. \end{aligned} \quad (\text{E3}) $$
Assuming then that Eq. (E2) holds for some value $n = 1, \dots, N - 1$, we have, for $n' = n - 1$,

$$
\begin{align*}
p((k_1, \dots, k_{n'}, k_{n'+1}), \vec{a}_{k_1, \dots, k_{n'}} | \vec{x}) &= \sum_{a_{k_{n'+1}}, k_{n'+2}} p((k_1, \dots, k_{n'}, k_{n'+1}, k_{n'+2}), \vec{a}_{k_1, \dots, k_{n'}, k_{n'+1}} | \vec{x}) \\
&= \sum_{a_{k_{n'+1}}, k_{n'+2}} \operatorname{Tr} \left[ (M_{\vec{a}_{k_1, \dots, k_{n'+1}}} | \vec{x}_{k_1, \dots, k_{n'+1}})^T \left( \operatorname{Tr} A_{k_{n'+2}}^I W_{(k_1, \dots, k_{n'+1}, k_{n'+2})} \right) \right] \\
&= \operatorname{Tr} \left[ (M_{\vec{a}_{k_1, \dots, k_{n'}}} | \vec{x}_{k_1, \dots, k_{n'}} \otimes \sum_{a_{k_{n'+1}}} M_{a_{k_{n'+1}} | x_{k_{n'+1}}})^T \left( \underbrace{\sum_{k_{n'+2}} \operatorname{Tr} A_{k_{n'+2}}^I W_{(k_1, \dots, k_{n'+1}, k_{n'+2})}}_{W_{(k_1, \dots, k_{n'+1})} \otimes 1^{A_{k_{n'+1}}^O}} \right) \right] \\
&= \operatorname{Tr} \left[ (M_{\vec{a}_{k_1, \dots, k_{n'}}} | \vec{x}_{k_1, \dots, k_{n'}} \otimes \underbrace{\sum_{a_{k_{n'+1}}} \operatorname{Tr} A_{k_{n'+1}}^O M_{a_{k_{n'+1}} | x_{k_{n'+1}}} }_{1^{A_{k_{n'+1}}^I}})^T W_{(k_1, \dots, k_{n'+1})} \right] \\
&= \operatorname{Tr} \left[ (M_{\vec{a}_{k_1, \dots, k_{n'}}} | \vec{x}_{k_1, \dots, k_{n'}})^T \left( \operatorname{Tr} A_{k_{n'+1}}^I W_{(k_1, \dots, k_{n'+1})} \right) \right], \tag{E4}
\end{align*}
$$

which shows that Eq. (E2) holds for the value $n' = n - 1$, and indeed recursively proves that it holds for all $n = 0, \dots, N - 1$.

Eq. (E2) implies that $p((k_1, \dots, k_n, k_{n+1}), \vec{a}_{k_1, \dots, k_n} | \vec{x})$ does not depend on $\vec{x}_N \setminus \{k_1, \dots, k_n\}$, so that the decomposition $p(\vec{a}|\vec{x}) = \sum_{(k_1, \dots, k_N)} p((k_1, \dots, k_N), \vec{a} | \vec{x})$ from Eq. (E1) satisfies Eq. (3)—which formally proves that the correlations $p(\vec{a}|\vec{x})$ obtained from any QC-CC are causal.

b. Correlations induced by QC-convFOs are in $\mathcal{P}_{\text{convFO}}$

By definition a quantum circuit with fixed causal order can only generate correlations that are compatible with the same fixed causal order.

It then straightforwardly follows, by linearity, that any quantum circuit in QC-convFO can only generate correlations in $\mathcal{P}_{\text{convFO}}$.

c. Correlations induced by QC-NICCs are in $\mathcal{P}_{\text{NIO}}$

Recall that according to Eq. (26), process matrices in QC-NICC are QC-CCs with a decomposition in which all $W_{(k_1, \dots, k_N)}$'s (and hence all $W_{(k_1, \dots, k_N)} \otimes 1^{A_{k_N}^O}$'s) are proportional to valid process matrices; let us write $W_{(k_1, \dots, k_N)} \otimes 1^{A_{k_N}^O} = q_{(k_1, \dots, k_N)} \tilde{W}_{(k_1, \dots, k_N)}$, for some fixed weights $q_{(k_1, \dots, k_N)} (\ge 0)$ and some valid (now properly normalised) process matrices $\tilde{W}_{(k_1, \dots, k_N)}$.

Recall also that valid process matrices $\tilde{W}$ satisfy $\sum_{\vec{a}} \operatorname{Tr} [(M_{\vec{a}|\vec{x}})^T \tilde{W}] = 1$, independently of $\vec{x}$. Hence, for a process matrix in QC-NICC and its appropriate decomposition, $p((k_1, \dots, k_N), \vec{a} | \vec{x}) := \operatorname{Tr} [(M_{\vec{a}|\vec{x}})^T (W_{(k_1, \dots, k_N)} \otimes 1^{A_{k_N}^O})]$ as defined in Eq. (E1) above (and which, as we showed already, provides a causal decomposition for $p(\vec{a}|\vec{x})$ satisfying Eq. (3)) is then such that $p((k_1, \dots, k_N)|\vec{x}) = \sum_{\vec{a}} p((k_1, \dots, k_N), \vec{a} | \vec{x}) = \sum_{\vec{a}} \operatorname{Tr} [(M_{\vec{a}|\vec{x}})^T (W_{(k_1, \dots, k_N)} \otimes 1^{A_{k_N}^O})] = q_{(k_1, \dots, k_N)}$, independently of $\vec{x}$ (notice that this implies that $\sum_{(k_1, \dots, k_N)} q_{(k_1, \dots, k_N)} = 1$). This shows (recalling Eq. (12)) that the correlation $p(\vec{a}|\vec{x})$ is indeed in $\mathcal{P}_{\text{NIO}}$.

2. Correlations induced by QC-QCs

Although QC-QCs can be causally nonseparable [3], and therefore feature some form of indefinite causal orders, it was shown in Ref. [21] that they can only generate causal correlations. This result is less trivial than for QC-CCs. We will present below a new way to write its proof, which provides a causal decomposition of the form $p(\vec{a}|\vec{x}) = \sum_{\pi} p(\pi, \vec{a}|\vec{x})$, as in Eq. (3), and thereby makes more explicit (and may perhaps provide a better intuition of) how the causal order arises in the induced correlations.
a. *Correlations induced by QC-QCs are in $\mathcal{P}_{\text{causal}}$*

Consider the process matrix $W$ of a QC-QC, which has a decomposition as in Eq. (31) (once again, considering here trivial global past and future spaces $\mathcal{H}^P, \mathcal{H}^F$), and let us define, $\forall n = 1, \dots, N, \forall \mathcal{K}_n \subseteq \mathcal{N}, \forall k_n \in \mathcal{K}_n$,

$$ 
\begin{aligned}
s_{(\mathcal{K}_n \setminus k_n, k_n)}(\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}) &:= \operatorname{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}})^T (W_{(\mathcal{K}_n \setminus k_n, k_n)} \otimes \mathbb{1}^{A_{\mathcal{K}_n}^O}) \right] \ge 0 \\
\text{and } f_{\mathcal{K}_n}(\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}) &:= \sum_{k_n \in \mathcal{K}_n} s_{(\mathcal{K}_n \setminus k_n, k_n)}(\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}) = \operatorname{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}})^T \left( \sum_{k_n \in \mathcal{K}_n} W_{(\mathcal{K}_n \setminus k_n, k_n)} \otimes \mathbb{1}^{A_{\mathcal{K}_n}^O} \right) \right] \ge 0. \quad (\text{E5})
\end{aligned}
$$

With these,<fnref n="48" /> we easily obtain, iteratively, that

$$ 
\begin{aligned}
p(\vec{a}|\vec{x}) &= \sum_{k_N} s_{(\mathcal{N}\setminus k_N, k_N)}(\vec{a}|\vec{x}) = \sum_{k_N} f_{\mathcal{N}\setminus k_N}(\cdot|\cdot) \frac{s_{(\mathcal{N}\setminus k_N, k_N)}(\cdot|\cdot)}{f_{\mathcal{N}\setminus k_N}(\cdot|\cdot)} \\
&= \sum_{(k_{N-1}, k_N)} s_{(\mathcal{N}\setminus\{k_{N-1}, k_N\}, k_{N-1})}(\cdot|\cdot) \frac{s_{(\mathcal{N}\setminus k_N, k_N)}(\cdot|\cdot)}{f_{\mathcal{N}\setminus k_N}(\cdot|\cdot)} = \sum_{k_{N-1}, k_N} f_{\mathcal{N}\setminus\{k_{N-1}, k_N\}}(\cdot|\cdot) \frac{s_{(\mathcal{N}\setminus\{k_{N-1}, k_N\}, k_{N-1})}(\cdot|\cdot)}{f_{\mathcal{N}\setminus\{k_{N-1}, k_N\}}(\cdot|\cdot)} \frac{s_{(\mathcal{N}\setminus k_N, k_N)}(\cdot|\cdot)}{f_{\mathcal{N}\setminus k_N}(\cdot|\cdot)} \\
&= \sum_{(k_{N-2}, k_{N-1}, k_N)} s_{(\mathcal{N}\setminus\{k_{N-2}, k_{N-1}, k_N\}, k_{N-2})}(\cdot|\cdot) \frac{s_{(\mathcal{N}\setminus\{k_{N-1}, k_N\}, k_{N-1})}(\cdot|\cdot)}{f_{\mathcal{N}\setminus\{k_{N-1}, k_N\}}(\cdot|\cdot)} \frac{s_{(\mathcal{N}\setminus k_N, k_N)}(\cdot|\cdot)}{f_{\mathcal{N}\setminus k_N}(\cdot|\cdot)} \\
&= \dots \\
&= \sum_{(k_1, \dots, k_N)} \underbrace{s_{(\emptyset, k_1)}(\cdot|\cdot)}_{\tilde{p}((k_1), a_{k_1} | x_{k_1})} \underbrace{\frac{s_{(\{k_1\}, k_2)}(\cdot|\cdot)}{f_{\{k_1\}}(\cdot|\cdot)}}_{\tilde{p}((k_2), a_{k_2} | (k_1), \vec{x}_{k_1}, a_{k_1})} \underbrace{\frac{s_{(\{k_1, k_2\}, k_3)}(\cdot|\cdot)}{f_{\{k_1, k_2\}}(\cdot|\cdot)}}_{\tilde{p}((k_3), a_{k_3} | (k_1, k_2), \vec{x}_{k_1}, k_2, \vec{a}_{k_1, k_2})} \dots \underbrace{\frac{s_{(\{k_1, \dots, k_{N-1}\}, k_N)}(\cdot|\cdot)}{f_{\{k_1, \dots, k_{N-1}\}}(\cdot|\cdot)}}_{\tilde{p}((k_N), a_{k_N} | (k_1, \dots, k_{N-1}), \vec{x}_{k_1}, \dots, \vec{a}_{k_1}, \dots, k_{N-1})} \\
&= \sum_{(k_1, \dots, k_N)} \prod_{n=1}^{N} \tilde{p}((k_n), a_{k_n} | (k_1, \dots, k_{n-1}), \vec{x}_{k_1}, \dots, \vec{x}_{k_n}, \vec{a}_{k_1}, \dots, \vec{a}_{k_{n-1}}) = \sum_{(k_1, \dots, k_N)} p((k_1, \dots, k_N), \vec{a}|\vec{x}), \quad (\text{E6})
\end{aligned}
$$

where we defined, for $n = 1, \dots, N$ (and with $f_\emptyset(\vec{a}_\emptyset|\vec{x}_\emptyset) := 1$),

$$ 
\begin{aligned}
\tilde{p}((k_n), a_{k_n} | (k_1, \dots, k_{n-1}), \vec{x}_{k_1}, \dots, \vec{x}_{k_n}, \vec{a}_{k_1}, \dots, \vec{a}_{k_{n-1}}) &:= \frac{s_{(\{k_1, \dots, k_{n-1}\}, k_n)}(\vec{a}_{k_1}, \dots, \vec{a}_{k_n} | \vec{x}_{k_1}, \dots, \vec{x}_{k_n})}{f_{\{k_1, \dots, k_{n-1}\}}(\vec{a}_{k_1}, \dots, \vec{a}_{k_{n-1}} | \vec{x}_{k_1}, \dots, \vec{x}_{k_{n-1}})} \ge 0 \\
\text{and } p((k_1, \dots, k_N), \vec{a}|\vec{x}) &:= \prod_{n=1}^{N} \tilde{p}((k_n), a_{k_n} | (k_1, \dots, k_{n-1}), \vec{x}_{k_1}, \dots, \vec{x}_{k_n}, \vec{a}_{k_1}, \dots, \vec{a}_{k_{n-1}}) \ge 0. \quad (\text{E7})
\end{aligned}
$$

Using the trace-preserving property $(\sum_{a_k} \operatorname{Tr}_{A_k^O} M_{a_k|x_k} = \mathbb{1}^{A_k^I})$, we have that

$$ 
\begin{aligned}
\tilde{p}((k_n) | (k_1, \dots, k_{n-1}), \vec{x}_{k_1}, \dots, \vec{x}_{k_n}, \vec{a}_{k_1}, \dots, \vec{a}_{k_{n-1}}) &:= \sum_{a_{k_n}} \tilde{p}((k_n), a_{k_n} | (k_1, \dots, k_{n-1}), \vec{x}_{k_1}, \dots, \vec{x}_{k_n}, \vec{a}_{k_1}, \dots, \vec{a}_{k_{n-1}}) \\
&= \frac{\sum_{a_{k_n}} \operatorname{Tr} \left[ (M_{\vec{a}_{k_1}, \dots, k_n} | \vec{x}_{k_1}, \dots, k_n)^T (W_{(\{k_1, \dots, k_{n-1}\}, k_n)} \otimes \mathbb{1}^{A_{k_n}^O}) \right]}{f_{\{k_1, \dots, k_{n-1}\}}(\vec{a}_{k_1}, \dots, \vec{a}_{k_{n-1}} | \vec{x}_{k_1}, \dots, \vec{x}_{k_{n-1}})} \\
&= \frac{\operatorname{Tr} \left[ (M_{\vec{a}_{k_1}, \dots, k_{n-1}} | \vec{x}_{k_1}, \dots, \vec{x}_{k_{n-1}} \otimes \underbrace{\sum_{a_{k_n}} \operatorname{Tr}_{A_k^O} M_{a_{k_n}|x_{k_n}}}_{\mathbb{1}^{A_{k_n}^I}})^T W_{(\{k_1, \dots, k_{n-1}\}, k_n)} \right]}{f_{\{k_1, \dots, k_{n-1}\}}(\vec{a}_{k_1}, \dots, \vec{a}_{k_{n-1}} | \vec{x}_{k_1}, \dots, \vec{x}_{k_{n-1}})} \\
&= \frac{\operatorname{Tr} \left[ (M_{\vec{a}_{k_1}, \dots, k_{n-1}} | \vec{x}_{k_1}, \dots, \vec{x}_{k_{n-1}})^T (\operatorname{Tr}_{A_k^I} W_{(\{k_1, \dots, k_{n-1}\}, k_n)}) \right]}{f_{\{k_1, \dots, k_{n-1}\}}(\vec{a}_{k_1}, \dots, \vec{a}_{k_{n-1}} | \vec{x}_{k_1}, \dots, \vec{x}_{k_{n-1}})} \quad (\text{E8})
\end{aligned}
$$

<footnote n="48">⁴⁸ The watchful reader may notice that we introduce here the same definitions for $s_{(\mathcal{K}_n \setminus k_n, k_n)}(\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n})$ and $f_{\mathcal{K}_n}(\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n})$ as in the proof of Ref. [21]. Since it is always clear what the arguments $(\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n})$ of $s_{(\mathcal{K}_n \setminus k_n, k_n)}$ and $f_{\mathcal{K}_n}$ must be, to lighten the notations we shall sometimes just write $s_{(\mathcal{K}_n \setminus k_n, k_n)}(\cdot|\cdot)$ and $f_{\mathcal{K}_n}(\cdot|\cdot)$, as e.g. in Eq. (E6). For simplicity we assume in the upcoming equations that all $f_{\{k_1, \dots, k_{n-1}\}}(\cdot|\cdot) > 0$; otherwise the corresponding summands in Eq. (E6), i.e. $p((k_1, \dots, k_N), \vec{a}|\vec{x})$, are simply 0.</footnote>
does not depend on $x_{k_n}$. Using the constraints of Eq. (31), Eq. (E8) further leads, for $n \ge 2$ and with $\mathcal{K}_{n-1} := \{k_1, \dots, k_{n-1}\}$, to

$$ \sum_{k_n, a_{k_n}} \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}}) = \frac{\mathrm{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_{n-1}} | \vec{x}_{\mathcal{K}_{n-1}}}^I)^T \left( \sum_{k_n \notin \mathcal{K}_{n-1}} \mathrm{Tr}_{A_{k_n}^I} W_{(\mathcal{K}_{n-1}, k_n)} \right) \right]}{\mathrm{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_{n-1}} | \vec{x}_{\mathcal{K}_{n-1}}}^I)^T \left( \sum_{k'_n \in \mathcal{K}_{n-1}} W_{(\mathcal{K}_{n-1} | k'_n, k'_n)} \right) \otimes \mathbf{1}^{A_{k'_n}^O} \right]} = 1, \quad (E9) $$

and similarly for $n=1$, $\sum_{k_1, a_{k_1}} \tilde{p}((k_1), a_{k_1} | x_{k_1}) = \sum_{k_1} \mathrm{Tr}[W_{(\emptyset, k_1)}] = 1$.

Hence Eq. (E6) provides a decomposition of $p(\vec{a}|\vec{x})$ as in Eq. (A17) of Appendix A3, with each $\tilde{p}((k_n), a_{k_n} | \cdot, \cdot, \cdot)$ satisfying the necessary constraints, which indeed proves that the correlations induced by a QC-QC are causal.

b. Correlations induced by QC-supFOs are in $\mathcal{P}_{\mathrm{convFO}}$

Consider now a process matrix $W \in \mathcal{H}^P, \mathcal{H}^F$), which has a decomposition as in Eq. (32) (still with some trivial $\mathcal{H}^P, \mathcal{H}^F$), and let us now define, $\forall n = 1, \dots, N$, $\forall \mathcal{K}_n \subseteq \mathcal{N}$, $\forall k_n \in \mathcal{K}_n$, $\forall (k_{n+1}, \dots, k_N) \in \mathcal{N} \setminus \mathcal{K}_n$,

$$ \begin{gathered} s_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)} (\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}) := \mathrm{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}})^T (W_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)} \otimes \mathbf{1}^{A_{k_n}^O}) \right] \ge 0 \\ \text{and } f_{\mathcal{K}_n}^{(k_{n+1}, \dots, k_N)} (\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}) := \sum_{k_n \in \mathcal{K}_n} s_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)} (\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}) = \mathrm{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}})^T \left( \sum_{k_n \in \mathcal{K}_n} W_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)} \otimes \mathbf{1}^{A_{k_n}^O} \right) \right] \ge 0. \end{gathered} \quad (E10) $$

Following similar calculations as in the first few lines of Eq. (E6) (just adding the superscripts $(k_{n+1}, \dots, k_N)$ wherever we need them), we can write here$^{49}$

$$ \begin{aligned} p(\vec{a}|\vec{x}) &= \sum_{\pi=(k_1, \dots, k_N)} \underbrace{s_{(\emptyset, k_1)}^{(k_2, \dots, k_N)}(\cdot|\cdot)}_{q_{\pi} \tilde{p}_{\pi,k_1}(a_{k_1}|x_{k_1})} \underbrace{\frac{s_{(k_3, \dots, k_N)}^{(k_1,k_2)}(\cdot|\cdot)}{f_{\{k_1\}}^{(k_2, \dots, k_N)}(\cdot|\cdot)}}_{\tilde{p}_{\pi,k_2}(a_{k_2}|\vec{x}_{k_1,k_2},a_{k_1})} \underbrace{\frac{s_{(k_4, \dots, k_N)}^{(k_1,k_2,k_3)}(\cdot|\cdot)}{f_{\{k_1,k_2\}}^{(k_3, \dots, k_N)}(\cdot|\cdot)}}_{\tilde{p}_{\pi,k_3}(a_{k_3}|\vec{x}_{k_1,k_2,k_3}, \vec{a}_{k_1,k_2})} \dots \underbrace{\frac{s_{(\{k_1, \dots, k_{N-1}\},k_N)}^{\emptyset}(\cdot|\cdot)}{f_{\{k_1, \dots, k_{N-1}\}}^{(k_N)}(\cdot|\cdot)}}_{\tilde{p}_{\pi,k_N}(a_{k_N}|\vec{x}_{k_1, \dots, k_N}, \vec{a}_{k_1, \dots, k_{N-1}})} \\ &= \sum_{\pi=(k_1, \dots, k_N)} q_{\pi} \prod_{n=1}^{N} \tilde{p}_{\pi,k_n}(a_{k_n}|\vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}) = \sum_{\pi=(k_1, \dots, k_N)} q_{\pi} p_{\pi}(\vec{a}|\vec{x}), \end{aligned} \quad (E11) $$

with, for $\pi = (k_1, \dots, k_N)$,

$$ \begin{aligned} \tilde{p}_{\pi,k_1}(a_{k_1}|x_{k_1}) &:= \frac{s_{(\emptyset, k_1)}^{(k_2, \dots, k_N)}(a_{k_1}|x_{k_1})}{q_{\pi}} \ge 0, \\ \tilde{p}_{\pi,k_n}(a_{k_n}|\vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}) &:= \frac{s_{(\{k_1, \dots, k_{n-1}\},k_n)}^{(k_{n+1}, \dots, k_N)}(\vec{a}_{k_1, \dots, k_n}|\vec{x}_{k_1, \dots, k_n})}{f_{\{k_1, \dots, k_{n-1}\}}^{(k_N)}(\vec{a}_{k_1, \dots, k_{n-1}}|\vec{x}_{k_1, \dots, k_{n-1}})} \ge 0 \quad \text{for } n=2, \dots, N, \\ \text{and } p_{\pi}(\vec{a}|\vec{x}) &:= \prod_{n=1}^{N} \tilde{p}_{\pi,k_n}(a_{k_n}|\vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}) \ge 0. \end{aligned} \quad (E12) $$

Now, using again the trace-preserving property together with the constraints of Eq. (32), we have that

$$ \sum_{a_{k_1}} \tilde{p}_{\pi, k_1}(a_{k_1} | x_{k_1}) = \frac{\mathrm{Tr} \left[ \left( \sum_{a_{k_1}} \mathrm{Tr}_{A_{k_1}^O} M_{a_{k_1} | x_{k_1}} \right)^T W_{(\emptyset, k_1)}^{(k_2, \dots, k_N)} \right]}{q_{\pi}} = \frac{\mathrm{Tr} \left[ W_{(\emptyset, k_1)}^{(k_2, \dots, k_N)} \right]}{q_{\pi}} = 1 \quad (E13) $$

<footnote>$^{49}$ In Eq. (E11) we again assume, for simplicity, that all $f_{(k_1, \dots, k_{n-1})}^{(k_n, \dots, k_N)}(\cdot|\cdot) > 0$; otherwise, the corresponding summands are simply 0. In the first line of Eq. (E12) we assume that $q_{\pi} > 0$; otherwise $\tilde{p}_{\pi,k_1}(a_{k_1}|x_{k_1})$ can be taken to be any valid conditional probability distribution.</footnote>
and for $n \ge 2$, with $\mathcal{K}_{n-1} := \{k_1, \dots, k_{n-1}\}$ (similarly to Eqs. (E8)–(E9) before)

$$ 
\begin{aligned}
\sum_{a_{k_n}} \tilde{p}_{\pi, k_n}(a_{k_n} | \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}) &= \frac{\mathrm{Tr} \left[ \left( M_{\vec{a}_{k_1, \dots, k_{n-1}}} | \vec{x}_{k_1, \dots, k_{n-1}} \otimes \overbrace{\sum_{a_{k_n}} \mathrm{Tr}_{\mathcal{A}_{k_n}^O} M_{a_{k_n} | x_{k_n}}}^{\mathbf{1}^{A_{k_n}^I}} \right)^T W_{(\{k_1, \dots, k_{n-1}\}, k_n)}^{(k_{n+1}, \dots, k_N)} \right]}{f_{\{k_1, \dots, k_{n-1}\}}^{(k_n, \dots, k_N)} (\vec{a}_{k_1, \dots, k_{n-1}} | \vec{x}_{k_1, \dots, k_{n-1}})} \\
&= \frac{\mathrm{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_{n-1}}} | \vec{x}_{\mathcal{K}_{n-1}})^T (\mathrm{Tr}_{\mathcal{A}_{k_n}^I} W_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_N)}) \right]}{\mathrm{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_{n-1}}} | \vec{x}_{\mathcal{K}_{n-1}})^T \left( \sum_{k'_{n-1} \in \mathcal{K}_{n-1}} W_{(\mathcal{K}_{n-1} \setminus k'_{n-1}, k'_{n-1})}^{(k_n, \dots, k_N)} \otimes \mathbf{1}^{A_{k'_{n-1}}^{O}} \right) \right]} = 1. \quad (\text{E14})
\end{aligned}
$$

Hence for each $n = 1, \dots, N$, $\tilde{p}_{\pi, k_n}(a_{k_n} | \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}})$ defines a valid (normalised) probability distribution for party $A_{k_n}$'s output, which only depends on the inputs and outputs of the parties in the past of $A_{k_n}$, according to the order $\pi = (k_1, \dots, k_N)$, and of $A_{k_n}$'s own input. The definition of $p_{\pi}(\vec{a}|\vec{x})$ in Eq. (E12) then implies that $p_{\pi}(\vec{a}_{k_1, \dots, k_n}|\vec{x}) = \prod_{j=1}^n \tilde{p}_{\pi, k_j}(a_{k_j} | \vec{x}_{k_1, \dots, k_j}, \vec{a}_{k_1, \dots, k_{j-1}})$ does not depend on $\vec{x}_{k_{n+1}, \dots, k_N}$, i.e., that $p_{\pi}(\vec{a}|\vec{x})$ is compatible with the fixed causal order $\pi$.

From the decomposition of Eq. (E11), we then conclude that process matrices in QC-supFO only give correlations that are convex mixtures of correlations with fixed orders, i.e., correlations in $\mathcal{P}_{\text{convFO}}$.

### c. Correlations induced by QC-NIQCs are in $\mathcal{P}_{\text{NIO}}$

Consider a process matrix $W$ in QC-NIQC (still with some trivial $\mathcal{H}^P, \mathcal{H}^F$), i.e., according to Eq. (33), a QC-QC with a decomposition as in Eq. (31), in which all $W_{(\mathcal{K}_{n-1}, k_n)}$'s are proportional to valid process matrices.

As we have seen in Appendix E2 a above, the correlations induced by such a process matrix are causal, and an explicit causal decomposition for these can be constructed as in Eq. (E6). For this decomposition, let us calculate (for any $n = 1, \dots, N$, any $\mathcal{K}_{n-1} \subsetneq \mathcal{N}$ and any $k_n \in \mathcal{N} \setminus \mathcal{K}_{n-1}$, using in particular Eq. (A19)):

$$ 
\begin{aligned}
p((\mathcal{K}_{n-1}, k_n), \vec{a}_{\mathcal{K}_{n-1}, k_n} | \vec{x}) &:= \sum_{(k_1, \dots, k_{n-1}) \in \mathcal{K}_{n-1}} p((k_1, \dots, k_{n-1}, k_n), \vec{a}_{k_1, \dots, k_{n-1}, k_n} | \vec{x}) = \sum_{(k_1, \dots, k_{n-1}) \in \mathcal{K}_{n-1}} \prod_{j=1}^n \tilde{p}((k_j), a_{k_j} | \cdot, \cdot) \\
&= \sum_{(k_1, \dots, k_{n-1}) \in \mathcal{K}_{n-1}} \frac{s_{(\emptyset, k_1)}(\cdot|\cdot)}{f_{\{k_1\}}(\cdot|\cdot)} \frac{s_{(\{k_1\}, k_2)}(\cdot|\cdot)}{f_{\{k_1, k_2\}}(\cdot|\cdot)} \dots \frac{s_{(\{k_1, \dots, k_{n-2}\}, k_{n-1})}(\cdot|\cdot)}{f_{\{k_1, \dots, k_{n-2}\}}(\cdot|\cdot)} \frac{s_{(\{k_1, \dots, k_{n-1}\}, k_n)}(\cdot|\cdot)}{f_{\{k_1, \dots, k_{n-1}\}}(\cdot|\cdot)} \\
&= \sum_{(k_3, \dots, k_{n-1}) \in \mathcal{K}_{n-1} \setminus \mathcal{K}_2} \left( \sum_{k_2 \in \mathcal{K}_2} s_{(\mathcal{K}_2 \setminus k_2, k_2)}(\cdot|\cdot) \right) \frac{s_{(\mathcal{K}_2, k_3)}(\cdot|\cdot)}{f_{\mathcal{K}_2}(\cdot|\cdot)} \frac{s_{(\mathcal{K}_2 \cup \{k_3\}, k_4)}(\cdot|\cdot)}{f_{\mathcal{K}_2 \cup \{k_3\}}(\cdot|\cdot)} \dots \\
&\qquad \frac{s_{(\mathcal{K}_2 \cup \{k_3, \dots, k_{n-2}\}, k_{n-1})}(\cdot|\cdot)}{f_{\mathcal{K}_2 \cup \{k_3, \dots, k_{n-2}\}}(\cdot|\cdot)} \frac{s_{(\mathcal{K}_2 \cup \{k_3, \dots, k_{n-1}\}, k_n)}(\cdot|\cdot)}{f_{\mathcal{K}_2 \cup \{k_3, \dots, k_{n-1}\}}(\cdot|\cdot)} \\
&= \sum_{(k_3, \dots, k_{n-1}) \in \mathcal{K}_{n-1} \setminus \mathcal{K}_3} \left( \sum_{k_3 \in \mathcal{K}_3} s_{(\mathcal{K}_3 \setminus k_3, k_3)}(\cdot|\cdot) \right) \frac{s_{(\mathcal{K}_3, k_4)}(\cdot|\cdot)}{f_{\mathcal{K}_3}(\cdot|\cdot)} \dots \frac{s_{(\mathcal{K}_3 \cup \{k_4, \dots, k_{n-2}\}, k_{n-1})}(\cdot|\cdot)}{f_{\mathcal{K}_3 \cup \{k_4, \dots, k_{n-2}\}}(\cdot|\cdot)} \frac{s_{(\mathcal{K}_3 \cup \{k_4, \dots, k_{n-1}\}, k_n)}(\cdot|\cdot)}{f_{\mathcal{K}_3 \cup \{k_4, \dots, k_{n-1}\}}(\cdot|\cdot)} \\
&= \dots = \sum_{\substack{\mathcal{K}_{n-2} \subsetneq \mathcal{K}_{n-1}, \\ k_{n-1} \in \mathcal{K}_{n-1} \setminus \mathcal{K}_{n-2}}} \left( \sum_{k_{n-2} \in \mathcal{K}_{n-2}} s_{(\mathcal{K}_{n-2} \setminus k_{n-2}, k_{n-2})}(\cdot|\cdot) \right) \frac{s_{(\mathcal{K}_{n-2}, k_{n-1})}(\cdot|\cdot)}{f_{\mathcal{K}_{n-2}}(\cdot|\cdot)} \frac{s_{(\mathcal{K}_{n-2} \cup \{k_{n-1}\}, k_n)}(\cdot|\cdot)}{f_{\mathcal{K}_{n-2} \cup \{k_{n-1}\}}(\cdot|\cdot)} \\
&= \left( \sum_{k_{n-1} \in \mathcal{K}_{n-1}} s_{(\mathcal{K}_{n-1} \setminus k_{n-1}, k_{n-1})}(\cdot|\cdot) \right) \frac{s_{(\mathcal{K}_{n-1}, k_n)}(\cdot|\cdot)}{f_{\mathcal{K}_{n-1}}(\cdot|\cdot)} = s_{(\mathcal{K}_{n-1}, k_n)}(\cdot|\cdot) \\
&= \mathrm{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_{n-1} \cup k_n} | \vec{x}_{\mathcal{K}_{n-1}, k_n}})^T (W_{(\mathcal{K}_{n-1}, k_n)} \otimes \mathbf{1}^{A_{k_n}^O}) \right]. \quad (\text{E15})
\end{aligned}
$$

By assumption all $W_{(\mathcal{K}_{n-1}, k_n)}$'s are valid up to normalisation, so that we can write $W_{(\mathcal{K}_{n-1}, k_n)} \otimes \mathbf{1}^{A_{k_n}^O} = q_{(\mathcal{K}_{n-1}, k_n)} \tilde{W}_{(\mathcal{K}_{n-1}, k_n)}$, for some weights $q_{(\mathcal{K}_{n-1}, k_n)}(\ge 0)$ and some (properly normalised) valid process matrices $\tilde{W}_{(\mathcal{K}_{n-1}, k_n)}$, which by definition satisfy $\sum_{\vec{a}_{\mathcal{K}_{n-1} \cup k_n}} \mathrm{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_{n-1} \cup k_n} | \vec{x}_{\mathcal{K}_{n-1} \cup k_n}})^T \tilde{W}_{(\mathcal{K}_{n-1}, k_n)} \right] = 1$, independently of
$\vec{x}_{\mathcal{K}_{n-1} \cup k_n}$. Hence we obtain that

$$ 
\begin{aligned}
p((\mathcal{K}_{n-1}, k_n) | \vec{x}) &= \sum_{\vec{a}_{\mathcal{K}_{n-1} \cup k_n}} p((\mathcal{K}_{n-1}, k_n), \vec{a}_{\mathcal{K}_{n-1}, k_n} | \vec{x}) \\
&= q_{(\mathcal{K}_{n-1}, k_n)} \sum_{\vec{a}_{\mathcal{K}_{n-1} \cup k_n}} \mathrm{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_{n-1} \cup k_n} | \vec{x}_{\mathcal{K}_{n-1} \cup k_n}})^T \tilde{W}_{(\mathcal{K}_{n-1}, k_n)} \right] = q_{(\mathcal{K}_{n-1}, k_n)} \quad (\text{E16})
\end{aligned}
$$

does not depend on $\vec{x}$ (notice that $\sum_{(\mathcal{K}_{n-1}, k_n)} q_{(\mathcal{K}_{n-1}, k_n)} = 1$). This proves that the correlations generated by the process matrix $W$ in QC-NIQC are indeed in $\mathcal{P}_{\text{NIO}}$.

d. Defining a new class whose correlations are in $\mathcal{P}_{\text{NIO}}$

While we showed above that correlations induced by QC-NICCs are in $\mathcal{P}_{\text{NIO}}$ (as one may have expected), we could only show that correlations induced by QC-NIQCs are in $\mathcal{P}_{\text{NIO}}$, an (in general) strict superset of $\mathcal{P}_{\text{NIO}}$. This is due to the structure of the quantum control system, which does not encode the full order of past operations, but only their unordered list. It remains an open question, whether one can find correlations from QC-NIQCs that are in $\mathcal{P}_{\text{NIO}} \setminus \mathcal{P}_{\text{NIO}}$.

One may also wonder whether one could define any other subclass of QC-NIQCs, larger than that of QC-NICCs, for which we could prove that the correlations are in $\mathcal{P}_{\text{NIO}}$. We propose here such a subclass, inspired directly from the structure of the proofs above, by introducing precisely what was missing to prove that the correlations are in $\mathcal{P}_{\text{NIO}}$ rather than just in $\mathcal{P}_{\text{NIO}}$. The basic intuition is that in order to prove that the correlations are in $\mathcal{P}_{\text{NIO}}$, we need each full order $(k_1, \dots, k_N)$ to appear “somewhere in the decomposition”, and to have a valid process matrix (up to normalisation) attached to it (so as to generate a probability for that order that does not depend on the instruments).

Specifically, let us first define, for some fixed value of $n^* = 1, \dots, N$, the class QC-NIO$_{n^*}$ to be the set of $W \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{N}^*}^O F})$, $W \ge 0$ such that there exist PSD matrices $W_{(k_1, \dots, k_n)} \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{N}^*}^O \{k_1, \dots, k_{n-1}\} A_{k_n}^I})$ (for all $n=1, \dots, n^* - 1$ and all $(k_1, \dots, k_n)$), $W_{(k_1, \dots, k_{n^*})}^{(k_{n^*+1}, \dots, k_N)} \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{N}^*}^O \{k_1, \dots, k_{n^*-1}\} A_{k_{n^*}}^I})$ (for all $(k_1, \dots, k_{n^*}, \dots, k_N)$), $W_{(\mathcal{K}_{n-1}, k_n)}^{(k_{n+1}, \dots, k_N)} \in \mathcal{L}(\mathcal{H}^{PA_{\mathcal{N}^*}^O A_{k_n}^I})$ (for all strict subsets $\mathcal{K}_{n-1}$ of $\mathcal{N}$ with $n > n^*$ and all $(k_n, k_{n+1}, \dots, k_N) \in \mathcal{N} \setminus \mathcal{K}_{n-1}$) such that, defining $W_{(k_1, \dots, k_{n^*})} := \sum_{(k_{n^*+1}, \dots, k_N)} W_{(k_1, \dots, k_{n^*})}^{(k_{n^*+1}, \dots, k_N)}$ and $W_{(\mathcal{K}_{n^*} \setminus k_{n^*}, k_{n^*})} := \sum_{(k_1, \dots, k_{n^*-1}) \in \mathcal{K}_{n^*} \setminus k_{n^*}} W_{(k_1, \dots, k_{n^*-1}, k_{n^*})}$, we have

$$ 
\left\{
\begin{array}{l}
\mathrm{Tr}_F W = \sum_{k_N \in \mathcal{N}} W_{(\mathcal{N} \setminus k_N, k_N)}^0 \otimes 1^{A_{k_N}^O}, \\
\quad \forall n = n^*, \dots, N-1, \forall \mathcal{K}_n \subset \mathcal{N}, \forall (k_{n+1}, \dots, k_N) \in \mathcal{N} \setminus \mathcal{K}_n, \\
\mathrm{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}, \\
\quad \forall n = 1, \dots, n^* - 1, \forall (k_1, \dots, k_n), \\
\sum_{k_{n+1}} \mathrm{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}} \mathrm{Tr}_{A_{k_1}^I} W_{(k_1)} = 1^P,
\end{array}
\right.
\quad (\text{E17})
$$

and such that

$$ \text{all } W_{(k_1, \dots, k_n)}^{(k_{n^*+1}, \dots, k_N)}, \text{'}s \text{ are valid process matrices (up to normalisation).}^{50} \quad (\text{E18}) $$

As an illustration, the above set of constraints is depicted in Fig. 15 for the case of $N = 4, n^* = 2$, using the graphical representation introduced in Appendix D 4.

One can see that these classes QC-NIO$_{n^*}$ interpolate between QC-NICC (obtained$^{51}$ for $n^* = N$) and QC-supFO

<footnote>$^{50}$ Notice that this, together with the constraints of Eq. (E17), implies that all $W_{(k_1, \dots, k_n)}$'s, for $n = 1, \dots, n^*$, are also valid process matrices, up to normalisation.</footnote>

<footnote>$^{51}$ More precisely: with a trivial $\mathcal{H}^F$ (as we consider when only looking at correlations) we get exactly QC-NICC for $n^* = N$. With a nontrivial $\mathcal{H}^F$, for $n^* = N$ we get in fact a larger class than QC-NICC, for which the first two lines of Eq. (24) are replaced by $\mathrm{Tr}_F W = \sum_{(k_1, \dots, k_N)} W_{(k_1, \dots, k_N)} \otimes 1^{A_{k_N}^O}$. (This larger class includes in particular the class Sup from Ref. [36], characterised as in Eq. (D76); it thus contains QC-QCs that are not QC-CCs.)</footnote>
<figure><img src="image_16.png" /><figcaption>Figure 15. Graphical representation (as introduced in Appendix D4) of the SDP constraints of Eq. (E17), for the QC-NIO\*_n class with N = 4 and n* = 2. All matrices of the form W(k_3,k_4), in the layer corresponding to n* = 2, are assumed to be valid process matrices (up to normalisation)—which, here, implies the same for the matrices W(k_1) in the lower layer. Compared to the graph for the general QC-QC class (for N = 4 as well, shown in Fig. 13, bottom), one can see that the matrices on the n* = 2 layer split in two matrices each (corresponding to the two possible orders of the future parties)—to help visualise the changes, we kept the same colours as in Fig. 13 (bottom).</figcaption></figure>

For N = 4, n* = 3 the structure of the graph would look symmetric to the present one, just upside-down: it is the matrices on the n* = 3 layer that would split in two matrices each (corresponding to the two possible orders of the past parties).
(obtained for $n^* = 1$).<fnref n="52" /> From these we define the class QC-NIO to be their convex hull:

$$ \mathrm{QC-NIO} = \mathrm{conv} \left( \bigcup_{n^* = 1}^{N} \mathrm{QC-NIO}_{n^*} \right), \qquad (\mathrm{E19}) $$

which thus includes both QC-NICC and QC-supFO. We will now show that process matrices in QC-NIO only generate correlations in $\mathcal{P}_{\mathrm{NIO}}$.

By convexity, it suffices to prove that the same claim holds true for process matrices in QC-NIO, for any fixed value of $n^*$.<fnref n="53" />

Consider therefore a process matrix $W \in \mathrm{QC-NIO}_{n^*}$ with a decomposition as in Eq. (E17) with the $W_{(k_1, \dots, k_{n^*})}^{(k_{n^*}+1, \dots, k_N)}$, being proportional to valid process matrices, and with now some trivial $\mathcal{H}^P$ and $\mathcal{H}^F$. Similarly to what we did before, let us start by defining here, for all subsets $\mathcal{K}_n$ of $\mathcal{N}$ with $n \ge n^*$, all $k_n \in \mathcal{K}_n$ and all $(k_{n+1}, \dots, k_N) \in \mathcal{N} \setminus \mathcal{K}_n$,

$$ \begin{gathered} s_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)} (\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}) := \mathrm{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}})^T (W_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)} \otimes 1^{A_{k_n}^O}) \right] \ge 0 \\ \mathrm{and} \quad f_{\mathcal{K}_n}^{(k_{n+1}, \dots, k_N)} (\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}) := \sum_{k_n \in \mathcal{K}_n} s_{(\mathcal{K}_n \setminus k_n, k_n)}^{(k_{n+1}, \dots, k_N)} (\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}) = \mathrm{Tr} \left[ (M_{\vec{a}_{\mathcal{K}_n} | \vec{x}_{\mathcal{K}_n}})^T \left( \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} \right) \right] \ge 0. \end{gathered} \qquad (\mathrm{E20}) $$

Following the first steps of Eq. (E6), while adding the superscripts $(k_{n+1}, \dots, k_N)$ as in Eq. (E11), we can write<fnref n="54" />

$$ p(\vec{a}|\vec{x}) = \sum_{(k_n^*, \dots, k_N)} s_{(\mathcal{N}\setminus\{k_n^*, \dots, k_N\}, k_n^*)}^{(k_n^*+1, \dots, k_N)} (\cdot|\cdot) \frac{s_{(\mathcal{N}\setminus\{k_n^*+1, \dots, k_N\}, k_n^*)}^{(k_{n^*+2}, \dots, k_N)} (\cdot|\cdot)}{f_{(\mathcal{N}\setminus\{k_n^*+1, \dots, k_N\})}^{(k_{n^*+1}, \dots, k_N)} (\cdot|\cdot)} \dots \frac{s_{(\mathcal{N}\setminus\{k_n, \dots, k_N\})}^{0} (\cdot|\cdot)}{f_{(\mathcal{N}\setminus\{k_n, \dots, k_N\})}^{(k_N)} (\cdot|\cdot)}. \qquad (\mathrm{E21}) $$

Let us then further define, for all $\pi = (k_1, \dots, k_{n^*}, \dots, k_N)$,

$$ \begin{gathered} \tilde{p}(\pi, \vec{a}_{k_1, \dots, k_{n^*}} | \vec{x}_{k_1, \dots, k_{n^*}}) := \mathrm{Tr} \left[ (M_{\vec{a}_{k_1, \dots, k_{n^*}} | \vec{x}_{k_1, \dots, k_{n^*}}})^T (W_{(k_1, \dots, k_{n^*})}^{(k_{n^*}+1, \dots, k_N)} \otimes 1^{A_{k_{n^*}}^O}) \right] \ge 0, \\ \mathrm{and} \quad \tilde{p}_{\pi, k_n}(a_{k_n} | \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}) := \frac{s_{(\mathcal{N}\setminus\{k_n, \dots, k_N\}, k_n)}^{(k_{n+1}, \dots, k_N)} (\cdot|\cdot)}{f_{(\mathcal{N}\setminus\{k_n, \dots, k_N\})}^{(k_{n}, \dots, k_N)} (\cdot|\cdot)} \ge 0 \quad \text{for } n = n^* + 1, \dots, N. \end{gathered} \qquad (\mathrm{E22}) $$

From the definition of $W_{(\mathcal{K}_n^* \setminus k_{n^*}, k_{n^*})}^{(k_{n^*}+1, \dots, k_N)}$ just before Eq. (E17), it follows that $s_{(\mathcal{K}_n^* \setminus k_{n^*}, k_{n^*})}^{(k_{n^*}+1, \dots, k_N)} (\cdot|\cdot) = \sum_{(k_1, \dots, k_{n^*+1}) \in \mathcal{K}_n^* \setminus k_{n^*}} \tilde{p}(\pi, \vec{a}_{k_1, \dots, k_{n^*}} | \vec{x}_{k_1, \dots, k_{n^*}})$, so that from Eq. (E21) we can write

$$ \begin{gathered} p(\vec{a}|\vec{x}) = \sum_{\pi=(k_1, \dots, k_{n^*}, \dots, k_N)} \tilde{p}(\pi, \vec{a}_{k_1, \dots, k_{n^*}} | \vec{x}_{k_1, \dots, k_{n^*}}) \prod_{n=n^*+1}^{N} \tilde{p}_{\pi, k_n}(a_{k_n} | \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}) = \sum_{\pi} p(\pi, \vec{a}|\vec{x}) \\ \text{with} \quad p(\pi = (k_1, \dots, k_{n^*}, \dots, k_N), \vec{a}|\vec{x}) := \tilde{p}(\pi, \vec{a}_{k_1, \dots, k_{n^*}} | \vec{x}_{k_1, \dots, k_{n^*}}) \prod_{n=n^*+1}^{N} \tilde{p}_{\pi, k_n}(a_{k_n} | \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}). \end{gathered} \qquad (\mathrm{E23}) $$

Now, it can be shown as in Eq. (E14) that $\sum_{a_{k_n}} \tilde{p}_{\pi, k_n}(a_{k_n} | \vec{x}_{k_1, \dots, k_n}, \vec{a}_{k_1, \dots, k_{n-1}}) = 1$. Hence for $n \ge n^*$ and any $(k_1, \dots, k_n, k_{n+1})$, $p((k_1, \dots, k_{n+1}), \vec{a}_{k_1, \dots, k_n} | \vec{x}) = \sum_{(k_{n+2}, \dots, k_N), \vec{a}_{k_{n+1}, \dots, k_N}} p(\pi=(k_1, \dots, k_N), \vec{a}|\vec{x}) = \sum_{(k_{n+2}, \dots, k_N)} \tilde{p}(\pi=(k_1, \dots, k_N), \vec{a}_{k_1, \dots, k_{n^*}} | \vec{x}_{k_1, \dots, k_{n^*}}) \prod_{j=n^*+1}^{n} \tilde{p}_{\pi=(k_1, \dots, k_N), k_j}(a_{k_j} | \vec{x}_{k_1, \dots, k_j}, \vec{a}_{k_1, \dots, k_{j-1}})$ does not depend on $\vec{x}_{\mathcal{N}\setminus\{k_1, \dots, k_n\}}$. For $n < n^*$ on the other hand, and still any $(k_1, \dots, k_n, k_{n+1})$, it can be shown recursively from the second to last constraint in Eq. (E17) (in a similar way to Eqs. (E2)-(E4), and using the definition of $W_{(k_1, \dots, k_{n^*})}$ just before Eq. (E17) for the case $n = n^* - 1$) that $p((k_1, \dots, k_n, k_{n+1}), \vec{a}_{k_1, \dots, k_n} | \vec{x}) =$

<footnote n="52">52 Notice also that for $N = 3$, the intermediate value $n^* = 2$ recovers the QC-QC class.</footnote>

<footnote n="53">53 Since the claim is already known to be true for $n^* = N$ (the QC-NICC class) and for $n^* = 1$ (the QC-supFO class), we can restrict in the proof to $1 < n^* < N$, to avoid bothering with these limit cases.</footnote>

<footnote n="54">54 Still assuming, for simplicity, that all denominators are nonzero. Cf. Footnotes 48 and 49.</footnote>
$$
\sum_{(k_{n+2}, \dots, k_N), \vec{a}_{k_{n+1}, \dots, k_{n*}}} \tilde{p}(\pi=(k_1, \dots, k_N), \vec{a}_{k_1, \dots, k_{n*}} | \vec{x}_{k_1, \dots, k_{n*}}) = \text{Tr} \left[ (M_{\vec{a}_{k_1, \dots, k_n}} | \vec{x}_{k_1, \dots, k_n})^T (\text{Tr}_{A_{k_{n+1}}^I} W_{(k_1, \dots, k_{n+1})}) \right],
$$
which also does not depend on $\vec{x}_N \setminus \{k_1, \dots, k_n\}$.

All in all, we thus find that Eq. (E23) provides a causal decomposition of $p(\vec{a}|\vec{x}) = \sum_{\pi} p(\pi, \vec{a}|\vec{x})$ that satisfies Eq. (3). Recalling that each $W_{(k_1, \dots, k_{n*})}^{(k_{n*}+1, \dots, k_N)}$ is assumed to be proportional to a valid process matrix, we can write $W_{(k_1, \dots, k_{n*})}^{(k_{n*}+1, \dots, k_N)} = q_{(k_1, \dots, k_{n*}, \dots, k_N)} \tilde{W}_{(k_1, \dots, k_{n*})}^{(k_{n*}+1, \dots, k_N)}$, for some fixed weight $q_{(k_1, \dots, k_{n*}, \dots, k_N)}$ and some now properly normalised process matrix $\tilde{W}_{(k_1, \dots, k_{n*})}^{(k_{n*}+1, \dots, k_N)}$. We then have, for all $(k_1, \dots, k_{n*}, \dots, k_N)$,

$$
\begin{align*}
p(\pi = (k_1, \dots, k_{n*}, \dots, k_N) | \vec{x}) &= \sum_{\vec{a}} p(\pi = (k_1, \dots, k_{n*}, \dots, k_N), \vec{a} | \vec{x}) \\
&= \sum_{\vec{a}_{k_1, \dots, k_{n*}}} \tilde{p}(\pi = (k_1, \dots, k_{n*}, \dots, k_N), \vec{a}_{k_1, \dots, k_{n*}} | \vec{x}_{k_1, \dots, k_{n*}}) \\
&= q_{(k_1, \dots, k_{n*}, \dots, k_N)} \underbrace{\sum_{\vec{a}_{k_1, \dots, k_{n*}}} \text{Tr} \left[ (M_{\vec{a}_{k_1, \dots, k_{n*}}} | \vec{x}_{k_1, \dots, k_{n*}})^T (\tilde{W}_{(k_1, \dots, k_{n*})}^{(k_{n*}+1, \dots, k_N)} \otimes \mathbb{1}^{A_{k_{n*}}^O}) \right]}_{=1 \text{ (validity and normalisation of } \tilde{W}_{(k_1, \dots, k_{n*})}^{(k_{n*}+1, \dots, k_N)} \text{)}} = q_{(k_1, \dots, k_{n*}, \dots, k_N)}, \quad (\text{E24})
\end{align*}
$$

which does not depend on $\vec{x}$ and concludes the proof that the correlations are in $\mathcal{P}_{\text{NIO}}$.

Beyond the QC-NIO class introduced here, one may also construct even larger classes whose correlations are restricted to be in $\mathcal{P}_{\text{NIO}}$. E.g., one can conceive classes of a similar type as QC-NIO$_{n*}$, but allowing for different critical values $n^*$ attached to different orders $(k_1, \dots, k_N)$ (and then considering convex combinations of such classes). Formalising this properly becomes rather tedious—we only illustrate it with a specific example, depicted in Fig. 16 using the graphical representation of Appendix D 4.

<figure><img src="image_17.png" /><figcaption>Figure 16. An example of a class of quantum circuits with $N = 4$, defined through the graphical representation of Appendix D 4. Assuming that the matrices of the form $W_{(k_1, k_2)}^{(k_3, k_4)}$ (in the left part of the graph) and of the form $W_{(k_1, k_2, k_3)}^{(k_4)}$ (in the right part) are valid process matrices (up to normalisation), one can show that this class only generates correlations in $\mathcal{P}_{\text{NIO}}$.</figcaption></figure>

3. Obtaining any correlation in $\mathcal{P}_{\text{convFO}}$ or $\mathcal{P}_{\text{causal}}$ with a QC-convFO or a QC-CC

Here we show, for any correlation in $\mathcal{P}_{\text{convFO}}$, how to construct a convex mixture of quantum—and even classical—circuits with fixed causal order that generates it; and similarly for any correlation in $\mathcal{P}_{\text{causal}}$, how it can be obtained from a quantum—and even classical—circuit with classical control of causal order.
The basic idea of the construction is that the correlation one wishes to reproduce is established “inside” the process matrix. The process just indicates to each party what they should output, for each of their possible inputs; the party then does as instructed and indicate to the process which was their input.

To formalise this, we attribute to each party $A_k$ an input Hilbert space $\mathcal{H}_k^{A_k}$ whose basis states describe the list of all possible outputs for the party, for all of its possible inputs: these are taken to be of the form $|\vec{\alpha}_k\rangle_k^{A_k}$, with $\vec{\alpha}_k = (\alpha_{k,x_k})_{x_k}$ and with the understanding that each $\alpha_{k,x_k}$ corresponds to the output that the party should return when their input is $x_k$. As for the output Hilbert space $\mathcal{H}_k^{A_k}$, its basis states are taken to be of the form $|x_k\rangle_k^{A_k}$, so as to encode the party's input. The (classical) instrument consisting in reading off from $\mathcal{H}_k^{A_k}$ the value $a_k$ to be outputted for input $x_k$, and sending out in $\mathcal{H}_k^{A_k}$ the value of that input, is then described in the Choi picture by

$$ M_{a_k|x_k} = \sum_{\vec{\alpha}_k} \delta_{a_k, \alpha_{k,x_k}} \llbracket \vec{\alpha}_k \rrbracket_k^{A_k} \otimes \llbracket x_k \rrbracket_k^{A_k}, \qquad (E25) $$

where we again used the notation $\llbracket \vec{\alpha}_k \rrbracket_k^{A_k} := |\vec{\alpha}_k\rangle_k^{A_k} \langle \vec{\alpha}_k|$ and $\llbracket x_k \rrbracket_k^{A_k} := |x_k\rangle_k^{A_k} \langle x_k|$ for effectively classical states.

a. Any correlation in $\mathcal{P}_{\text{convFO}}$ can be obtained from a QC-convFO

Consider a correlation in $\mathcal{P}_{\text{convFO}}$, i.e. a mixture of correlations $p_\pi(\vec{a}|\vec{x})$ compatible with the fixed causal order $\pi = (k_1, \dots, k_N)$. Recalling from Eq. (2) that (for $n = 1, \dots, N-1$) $p_\pi(\vec{a}_{k_1, \dots, k_n}|\vec{x})$ does not depend on $\vec{x}_{\mathcal{N}\setminus\{k_1, \dots, k_n\}}$, one can thus decompose $p(\vec{a}|\vec{x})$ as

$$ \begin{aligned} p(\vec{a}|\vec{x}) &= \sum_{\pi} q_{\pi} p_{\pi}(\vec{a}|\vec{x}) \quad \text{with } q_{\pi} \ge 0, \sum_{\pi} q_{\pi} = 1, \\ \text{and } p_{\pi=(k_1, \dots, k_N)}(\vec{a}|\vec{x}) &= p_{\pi}(a_{k_1}|x_{k_1}) p_{\pi}(a_{k_2}|x_{k_1}, a_{k_1}, x_{k_2}) \cdots p_{\pi}(a_{k_N}|\vec{x}_{k_1, \dots, k_{N-1}}, \vec{a}_{k_1, \dots, k_{N-1}}, x_{k_N}) \\ &= \prod_{n=1}^{N} p_{\pi}(a_{k_n}|\vec{x}_{k_1, \dots, k_{n-1}}, \vec{a}_{k_1, \dots, k_{n-1}}, x_{k_n}). \end{aligned} \qquad (E26) $$

Let us then define, for any $n = 1, \dots, N$, with $\vec{\alpha}_{k_j} = (\alpha_{k_j, x_{k_j}})_{x_{k_j}}$ as above, and with the shorthand notation $\overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}} := (\alpha_{k_1, x_{k_1}}, \dots, \alpha_{k_{n-1}, x_{k_{n-1}}})$,

$$ \tilde{q}(\vec{\alpha}_{k_n}|\vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}) := \prod_{x'_{k_n}} p_{\pi}(\alpha_{k_n, x'_{k_n}}|\vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}, x'_{k_n}), \qquad (E27) $$

such that (for some $a_{k_n}, x_{k_n}$)

$$ \sum_{\vec{\alpha}_{k_n}} \delta_{a_{k_n}, \alpha_{k_n, x_{k_n}}} \tilde{q}(\vec{\alpha}_{k_n} | \vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}) = p_{\pi}(a_{k_n} | \vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}, x_{k_n}), \qquad (E28) $$

and

$$ W := \sum_{\pi=(k_1, \dots, k_N)} q_{\pi} \sum_{\substack{\vec{\alpha}_{k_1}, \dots, \vec{\alpha}_{k_N}, \\ x_{k_1}, \dots, x_{k_N}}} \bigotimes_{n=1}^{N} \left( \tilde{q}(\vec{\alpha}_{k_n} | \vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}) \llbracket \vec{\alpha}_{k_n} \rrbracket_k^{A_k} \otimes \llbracket x_{k_n} \rrbracket_k^{A_k} \right). \qquad (E29) $$

It can be verified that $W$ thus defined is the process matrix of a QC-convFO,<fnref n="55" /> and that with the choice of instruments of Eq. (E25) for each of the parties, it reproduces the correlation $p(\vec{a}|\vec{x})$ under consideration, as desired.

$$ W_{(k_1, \dots, k_N, F)} = q_{\pi} = (k_1, \dots, k_N) \sum_{x_{k_1}, \dots, x_{k_N}} \otimes_{n=1}^{N} (\tilde{q}(\vec{\alpha}_{k_n} | \vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}) \llbracket \vec{\alpha}_{k_n} \rrbracket_k^{A_k} \otimes \llbracket x_{k_n} \rrbracket_k^{A_k}), $$

$$ W_{(k_1, \dots, k_n)} = q_{(k_1, \dots, k_n)} \sum_{x_{k_1}, \dots, x_{k_n-1}} \left( \bigotimes_{j=1}^{n-1} \tilde{q}(\vec{\alpha}_{kj} | \vec{x}_{k_1, \dots, k_{j-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{j-1}}}) \llbracket \vec{\alpha}_{kj} \rrbracket_k^{A_k} \otimes \llbracket x_{kj} \rrbracket_k^{A_k} \right) \otimes (\tilde{q}(\vec{\alpha}_{k_n} | \vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}) \llbracket \vec{\alpha}_{k_n} \rrbracket_k^{A_k}), $$

$$ \text{where } q_{(k_1, \dots, k_n)} := \sum_{(k_{n+1}, \dots, k_N)} q_{\pi} = (k_1, \dots, k_n, k_{n+1}, \dots, k_N). $$

<footnote n="55">⁵⁵ Indeed, it has a decomposition as in Eq. (25), with</footnote>
b. Any correlation in $\mathcal{P}_{\text{causal}}$ can be obtained from a QC-CC

Consider now a correlation in $\mathcal{P}_{\text{causal}}$, which can be decomposed as in Eq. (A17):

$$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} \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}}), \quad (E30)$$

such that (for all $n$) $\sum_{a_{k_n}} \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}})$ does not depend on $x_{k_n}$.

The latter requirement allows us to write $\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}}) = \tilde{p}((k_n)| (k_1, \dots, k_{n-1}), \vec{x}_{k_1, \dots, k_{n-1}}, \vec{a}_{k_1, \dots, k_{n-1}}) \tilde{p}((a_{k_n} | (k_1, \dots, k_{n-1}, k_n), \vec{x}_{k_1, \dots, k_{n-1}}, \vec{a}_{k_1, \dots, k_{n-1}}, x_{k_n}).$ Following a similar construction as above, let us then define

$$\tilde{q}((k_n), \vec{\alpha}_{k_n} | \vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}) := \tilde{p}((k_n)| (k_1, \dots, k_{n-1}), \vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}) \\ \times \prod_{x'_{k_n}} \tilde{p}(\alpha_{k_n, x'_{k_n}} | (k_1, \dots, k_{n-1}, k_n), \vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}, x'_{k_n}), \quad (E31)$$

such that

$$\sum_{\vec{\alpha}_{k_n}} \delta_{a_{k_n}, \alpha_{k_n}, x_{k_n}} \tilde{q}((k_n), \vec{\alpha}_{k_n} | \vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}) = \tilde{p}((k_n), a_{k_n} | (k_1, \dots, k_{n-1}), \vec{x}_{k_1, \dots, k_n}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}), \quad (E32)$$

and

$$W := \sum_{\pi=(k_1, \dots, k_N)} \sum_{\substack{\vec{\alpha}_{k_1}, \dots, \vec{\alpha}_{k_N} \\ x_{k_1}, \dots, x_{k_N}}} \bigotimes_{n=1}^{N} \left( \tilde{q}((k_n), \vec{\alpha}_{k_n} | \vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}) \right) \llbracket \vec{\alpha}_{k_n} \rrbracket^{A_{k_n}^I} \otimes \llbracket x_{k_n} \rrbracket^{A_{k_n}^O}. \quad (E33)$$

It can be verified here that $W$ thus defined is the process matrix of a QC-CC,<fnref n="56" /> and that with the choice of instruments of Eq. (E25) for each of the parties, it reproduces the correlation $p(\vec{a}|\vec{x})$ under consideration, as desired.

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

While the constructions above are quite general and allow one to find process matrices reproducing any desired correlation in $\mathcal{P}_{\text{convFO}}$ or $\mathcal{P}_{\text{causal}}$, in some cases (in particular, if some party does not signal to any other party, or if only limited communication is required) there also exist simpler process matrix realisations.

For instance, the correlation $p(a, b, c, d|x, y, z, t) = \delta_{a,0} \delta_{b,0} \delta_{c,0} \delta_{d,zt}$ (given below Eq. (15)), compatible with any causal order where $C \prec D$ and which saturates $I_4 \le_{\text{convFO}} \frac{15}{16}$, can be rather trivially obtained from the QC-FO $W = \llbracket 1 \rrbracket^{C_0 D_I} := \sum_{z=0,1} \llbracket z \rrbracket^{C_0} \otimes \llbracket z \rrbracket^{D_I} \in \text{QC-convFO} \subset \text{QC-supFO}$, representing a classical identity (or quantum dephasing) channel between $\mathcal{H}^{C_0}$ and $\mathcal{H}^{D_I}$ (with trivial systems for $A, B, C_I$ and $D_O$), and with the instruments $M_{a|x}^A = \delta_{a,0}$, $M_{b|y}^B = \delta_{b,0}$, $M_{c|z}^C = \delta_{c,0} \llbracket z \rrbracket^{C_0}$, $M_{0|t=0}^D = \mathbb{1}^{D_I}$ and $M_{d|t=1}^D = \llbracket d \rrbracket^{D_I}$.

Similarly, one can obtain the correlation $p(a, b, c, d|x, y, z, t) = \delta_{a,0} \delta_{b,0} \left\{ \begin{array}{ll} \delta_{c,0} \delta_{d,zt} & \text{if } xy = 0 \\ \delta_{d,0} \delta_{c,zt} & \text{if } xy = 1 \end{array} \right.$ of Eq. (19), which saturates the trivial bound $I_4 \le_{\text{causal}} 1$, with $W = (\llbracket 0,0 \rrbracket + \llbracket 0,1 \rrbracket + \llbracket 1,0 \rrbracket)^{A_0 B_0} \otimes \llbracket 0 \rrbracket^{C_I} \otimes \llbracket 1 \rrbracket^{C_0 D_I} \otimes \mathbb{1}^{D_O} + \llbracket 1,1 \rrbracket^{A_0 B_0} \otimes \llbracket 0 \rrbracket^{D_I} \otimes \llbracket 1 \rrbracket^{D_O C_I} \otimes \mathbb{1}^{C_0} \in \text{QC-CC} \subset \text{QC-QC}$ (with trivial systems for $A_I, B_I$) and the instruments $M_{a|x}^A = \delta_{a,0} |x\rangle\langle x|^A$, $M_{b|y}^B = \delta_{b,0} |y\rangle\langle y|^B$, $M_{0|z=0}^C = \mathbb{1}^{C_I} \otimes \llbracket 0 \rrbracket^{C_0}$, $M_{c|z=1}^C = \llbracket c \rrbracket^{C_I} \otimes \llbracket 1 \rrbracket^{C_0}$, $M_{0|t=0}^D = \mathbb{1}^{D_I} \otimes \llbracket 0 \rrbracket^{D_O}$ and $M_{d|t=1}^D = \llbracket d \rrbracket^{D_I} \otimes \llbracket 1 \rrbracket^{D_O}$.

$$W_{(k_1, \dots, k_N, F)} = \sum_{x_{k_1}, \dots, x_{k_N}} \otimes_{n=1}^{N} (\tilde{q}((k_n), \vec{\alpha}_{k_n} | \vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}) \llbracket \vec{\alpha}_{k_n} \rrbracket^{A_{k_n}^I} \otimes \llbracket x_{k_n} \rrbracket^{A_{k_n}^O}), \\ W_{(k_1, \dots, k_n)} = \sum_{x_{k_1}, \dots, x_{k_{n-1}}} (\otimes_{j=1}^{n-1} \tilde{q}((k_j), \vec{\alpha}_{k_j} | \vec{x}_{k_1, \dots, k_{j-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{j-1}}}) \llbracket \vec{\alpha}_{k_j} \rrbracket^{A_{k_j}^I} \otimes \llbracket x_{k_j} \rrbracket^{A_{k_j}^O}) \\ \qquad \otimes (\tilde{q}((k_n), \vec{\alpha}_{k_n} | \vec{x}_{k_1, \dots, k_{n-1}}, \overrightarrow{[\alpha_x]_{k_1, \dots, k_{n-1}}}) \llbracket \vec{\alpha}_{k_n} \rrbracket^{A_{k_n}^I}).$$

<footnote n="56">⁵⁶ Indeed, it has a decomposition as in Eq. (24), with</footnote>
Let us now turn to the correlation with non-influenceable causal order of Eq. (C20), which saturates the $I_4 \le_{\text{NIO}}^{31/32}$ bound. Applying our construction above for correlations in $\mathcal{P}_{\text{causal}}$, we find that it can be obtained from the process matrix

$$W = W_{\to} \otimes [0]^C_I \otimes [1]^C_{D_I} \otimes 1^{D_O} + W_{\leftarrow} \otimes [0]^D_I \otimes [1]^D_{O_I} \otimes 1^{C_O} \quad (\text{E34})$$

with

$$W_{\to} = \frac{1}{8} 1^{A_I} [0]^{A_O} 1^{B_I} [0]^{B_O} + \frac{1}{4} 1^{A_I} [0]^{A_O} [0]^{B_I} [1]^{B_O} + \frac{1}{2} [0]^{A_I} [1]^{A_O} [0]^{B_I} [0]^{B_O} + \frac{1}{2} [1]^{A_I} [1]^{A_O} [1]^{B_I} [1]^{B_O}, \\ W_{\leftarrow} = \frac{1}{8} 1^{A_I} [0]^{A_O} 1^{B_I} [0]^{B_O} + \frac{1}{4} 1^{A_I} [0]^{A_O} [0]^{B_I} [1]^{B_O} + \frac{1}{2} [1]^{A_I} [1]^{A_O} [1]^{B_I} [0]^{B_O} + \frac{1}{2} [0]^{A_I} [1]^{A_O} [0]^{B_I} [1]^{B_O} \quad (\text{E35})$$

(with implicit tensor products), together with Alice's instruments $M_{0|x=0}^A = 1^{A_I} \otimes [0]^{A_O}$ and $M_{a|x=1}^D = [a]^{A_I} \otimes [1]^{A_O}$, and with the three other parties' instruments defined in the same way. Noting in particular that $(W_{\to} + W_{\leftarrow})$ defines a process matrix compatible with the fixed order $A \prec B$, it can be seen that $W \in \text{QC-CC}$, with Eq. (E34) readily providing a QC-CC decomposition as in Eq. (24). However, $W_{\to}$ and $W_{\leftarrow}$, individually, are not valid process matrices, and Eq. (24) does not give a QC-NICC decomposition. In fact $W$ above can generate correlations with influenceable causal order, hence $W \notin \text{QC-NICC}$. As we explain in the main text, we were not able to saturate the $I_4 \le_{\text{NIO}}^{31/32}$ bound with process matrices in QC-NICC.

The same holds for the $I_4 \le_{\text{NIO}'}^{47/48}$ bound: one can construct the process matrix of a QC-QC that reproduces the correlation with non-influenceable coarse-grained order of Eq. (C24), which saturates this bound. However that process matrix is not a QC-NIQC; we were also not able to saturate the $I_4 \le_{\text{NIO}'}^{47/48}$ bound with process matrices in QC-NIQC.

## 4. Dynamical correlations from quantum circuits with non-influenceable control of causal order

As mentioned in the main text, we could not find any violation of our inequality (15), $I_4 \le_{\text{convFO}}^{15/16}$, with the explicit examples of process matrices $W_{\text{NICC}}$ and $W_{\text{NIQC}}$ that we presented in the main text (Eqs. (29) and (38)). The violations reported in Fig. 8 were instead obtained numerically, with process matrices and instruments that are difficult to interpret. Nonetheless, we were able to come up with another inequality that also bounds correlations in $\mathcal{P}_{\text{convFO}}$, and find explicit analytical violations with $W_{\text{NICC}}$ as well as with another example $W'_{\text{NIQC}} \in \text{QC-NIQC} \setminus (\text{QC-supFO} \cup \text{QC-NICC})$ that is defined below.

We recall that given a convex polytope $\mathcal{P}$, which can be characterised in terms of its $n_{\mathcal{P}}$ vertices $\{\vec{p}_i\}_{i=1}^{n_{\mathcal{P}}}$, one can use the following linear program to test whether a correlation vector $\vec{p}$ is inside or outside the polytope:

$$\min_{r, \vec{\lambda}} r \quad \text{s.t.} \quad M_{\mathcal{P}} \vec{\lambda} = \vec{p} + r \vec{u}, \quad \vec{\lambda} \ge 0, \quad r \ge 0 \quad (\text{E36})$$

where $\vec{u} = \frac{1}{n_{\mathcal{P}}} \sum_{i=1}^{n_{\mathcal{P}}} \vec{p}_i$, and $M_{\mathcal{P}}$ is the matrix formed by the vectors $\{\vec{p}_i\}_i$ in column. If the optimal value $r^*$ is zero, then the correlation vector $\vec{p}$ belongs to the polytope, while if $r^* > 0$, then the correlation vector $\vec{p}$ is outside of the polytope, and one can consider the dual optimisation problem to Eq. (E36) to derive an inequality satisfied by any point in $\mathcal{P}$ and violated by the correlation of interest $\vec{p}$.

To produce such an inequality and show that a correlation created by $W_{\text{NICC}}$ in the fourpartite lazy scenario is outside $\mathcal{P}_{\text{convFO}}$, we considered the following quantum instruments for each party A, B, C and D:

$$\begin{aligned} M_{0|0}^A &= M_{0|0}^B = |1\rangle\langle 1|, & M_{0|1}^A &= M_{0|1}^B = |0\rangle\langle 0| \otimes |0\rangle\langle 0|, & M_{1|1}^A &= M_{1|1}^B = |1\rangle\langle 1| \otimes |0\rangle\langle 0|, \\ M_{0|0}^C &= M_{0|0}^D = |1\rangle\langle 1|, & M_{0|1}^C &= M_{0|1}^D = |0\rangle\langle 0| \otimes |1\rangle\langle 1|, & M_{1|1}^C &= M_{1|1}^D = |1\rangle\langle 1| \otimes |1\rangle\langle 1|. \end{aligned} \quad (\text{E37})$$

The instruments for parties A and B correspond to the ones chosen in Ref. [9] to show that $W_{+\alpha}$ violates the LGYNI inequality: on input 0, A and B output 0 (as required here in the lazy scenario), and simply transmit the physical system they received, untouched; while on input 1, they perform a measurement in the Z basis, output its classical outcome, and send out a physical system in the state $|0\rangle\langle 0|$. The parties C and D act in a similar way to A and B, except that on input 1 they send out a physical system in the state $|1\rangle\langle 1|$. Solving the optimisation problem of Eq. (E36) for the correlation vector $\vec{p}_{\text{NICC}} = (p_{\text{NICC}}(\vec{a}|\vec{x}))_{\vec{a},\vec{x}}$, defined with the process $W_{\text{NICC}}$ and the instruments of Eq. (E37) using generalised Born rule (see Eq. (22)), we obtained $r_{\text{NICC}}^* \approx 0.063 > 0$, proving that $\vec{p}_{\text{NICC}}$ is outside
$P_{\text{convFO}}$. Solving the corresponding dual optimisation problem, we could derive the following inequality, which is satisfied by any correlation in $P_{\text{convFO}}$ but violated by $\vec{p}_{\text{NICC}}$:

$$ I'_4 := p(a=1, c=0|x=1, y=0, z=1, t=1) + p(a=1, c=1|x=1, y=0, z=1, t=0) \\ + p(b=1, c=0|x=0, y=1, z=1, t=1) + p(b=1, c=1|x=0, y=1, z=1, t=0) \\ + p(a=1, b=1, d=1|x=1, y=1, z=0, t=1) - p(a=1, b=1, c=0, d=1|x=1, y=1, z=1, t=1) \geq 0. \quad (E38) $$

This inequality can indeed be verified to hold for all the 481 776 (deterministic) vertices of $P_{\text{convFO}}$ (and thus for any point in $P_{\text{convFO}}$, since any correlation in this polytope can be expressed as a convex combination of its vertices). One can then see that the correlation vector $\vec{p}_{\text{NICC}}$ violates this inequality, reaching $I'_4 = \frac{6-5\sqrt{2}}{16} \approx -0.067 < 0$.

We could not find any analogous violation with $W_{\text{NIQC}}$, or any correlation outside of $P_{\text{convFO}}$. Nevertheless, we could come up with another example of a fourpartite quantum circuit with dynamical but non-influenceable quantum control of causal order in QC-NIQC \ (QC-supFO $\cup$ QC-NICC), and show that this process violates Eq. (E38) with the same instruments as those considered in Eq. (E37) above. This process is defined analogously to $W_{\text{NICC}}$ from Eq. (29), replacing $W_{-\alpha}$ by $W_{+\beta} := \frac{1}{4}(1^{\otimes 4} + \beta(ZZZ1 + Z1XX)) \in \mathcal{L}(\mathcal{H}^{A^{IO}B^{IO}})$ with $\beta = 1 - \frac{1}{\sqrt{2}}$ as$^{57}$

$$ W'_{\text{NIQC}} = \frac{1}{2} W_{+\alpha} \otimes |0\rangle\langle 0|^{C'} \otimes |1\rangle\langle 1|^{C'} \langle 1|^{C'0} \otimes 1^{D0} + \frac{1}{2} W_{+\beta} \otimes |0\rangle\langle 0|^{D'} \otimes |1\rangle\langle 1|^{D'} \langle 1|^{D'0} \otimes 1^{C'0}. \quad (E39) $$

One also obtains $I'_4 = \frac{6-5\sqrt{2}}{16} \approx -0.067 < 0$ for the correlation thus generated, showing that it is indeed outside of $P_{\text{convFO}}$.

Let us provide, for completeness, the other bounds on the expression $I'_4$ for the other polytopes considered in this work: we find $I'_4 \geq_{\text{NIO}} -\frac{1}{2}$, $I'_4 \geq_{\text{NIO}'} -\frac{2}{3}$, $I'_4 \geq_{\text{causal}} -1$. While, by construction, $I'_4 \geq_{\text{convFO}} 0$ is a facet of $P_{\text{convFO}}$, we do not expect these other bounds to define facets of the corresponding polytopes.

The technique we used above, consisting of cooking up some particular correlation and finding the facet of the $P_{\text{convFO}}$ polytope “right below” it, could be exploited further to find other inequalities, possibly with some particular form, or some nice interpretation in terms of games. As explained in the main text, it is much more challenging to obtain facet inequalities for the $P_{\text{NIO}}$ and $P_{\text{NIO}'}$ polytopes. Still, for some specific expression obtained as a facet for $P_{\text{convFO}}$, one can easily obtain the corresponding bound for $P_{\text{NIO}}$ and $P_{\text{NIO}'}$ (and potentially test if, by any chance, it also corresponds to a facet of these polytopes).

<footnote n="57">57 As already mentioned in the main text, one can construct an explicit “witness” to prove that this process is indeed not in QC-NICC, using the technique of causal witnesses [8, 34].</footnote>