The process formalism, causal order and signalling

Let us start by setting out some necessary background and essential concepts. In quantum theory, a system A is associated with a complex Hilbert space $$ {\mathcal{H}}_A$$, and its state is a density operator $$ {\rho }_A\in \mathcal{L}\left({\mathcal{H}}_A\right)$$, where $$ \mathcal{L}\left({\mathcal{H}}_A\right)$$ is the space of linear operators over $$ {\mathcal{H}}_A$$. The most general evolution of a system, assuming that it is initially uncorrelated with its environment, is given by a completely positive trace-preserving (CPTP) map $$ \mathcal{E}:\mathcal{L}\left({\mathcal{H}}_A\right)\to \mathcal{L}\left({\mathcal{H}}_B\right)$$, where this notation allows the output system to be different from the input system. The most general operation that an agent can perform from an input system A to an output system B has a classical outcome k and specifies the transformation from A to B conditioned on each value of k being obtained. Mathematically, the operation corresponds to a quantum instrument, which is a collection of completely positive (CP) maps $$ \left\{{\mathcal{E}}^k:\mathcal{L}\left({\mathcal{H}}_A\right)\to \mathcal{L}\left({\mathcal{H}}_B\right)\right\}$$, such that $$ \mathcal{E}={\sum }_k{\mathcal{E}}^k$$ is a trace-preserving CP map.

It is convenient to represent CP maps with operators, via a variant of the Choi-Jamiołkowski (CJ) isomorphism^52,53, which to a given CP map $$ \mathcal{E}:\mathcal{L}\left({\mathcal{H}}_A\right)\to \mathcal{L}\left({\mathcal{H}}_B\right)$$ associates the CJ operator $$ {\rho }_{B\mid A}^{\mathcal{E}}:={\sum }_{i,j}\mathcal{E}\left({∣i⟩}_A⟨j∣\right)\otimes {∣i⟩}_{A^{*}}⟨j∣$$, where $$ \left\{{∣i⟩}_A\right\}$$ is an orthonormal basis of $$ {\mathcal{H}}_A$$, and $$ \left\{{∣i⟩}_{A^{*}}\right\}$$ the corresponding dual basis. The CJ operator for a CPTP map $$ \mathcal{E}$$ satisfies $$ {\mathrm{Tr}}_B\left[{\rho }_{B\mid A}^{\mathcal{E}}\right]={\mathbb{1}}_{A^{*}}$$. This variant of the CJ isomorphism is used in refs. ^34,35, and has the advantage that the CJ operator is both positive semi-definite and independent of the basis used in its definition.

The idea behind the process formalism³ is that there is a fixed set of locations A_i, i = 1, ⋯, n, which in this work we call quantum nodes, at each of which an agent can perform an operation on a quantum system. A quantum node A_i is associated with two Hilbert spaces, an input Hilbert space $$ {\mathcal{H}}_{A_i^{\mathrm{in}}}$$ and an output Hilbert space $$ {\mathcal{H}}_{A_i^{\mathrm{out}}}$$ (both here assumed finite-dimensional). The input Hilbert space carries the state of the input system just before the operation by the agent, and the output Hilbert space carries the state of the output system just after the operation. The operation itself corresponds to a quantum instrument $$ \left\{{\mathcal{E}}_A^{k_A}:\mathcal{L}\left({\mathcal{H}}_{A^{\mathrm{in}}}\right)\to \mathcal{L}\left({\mathcal{H}}_{A^{\mathrm{out}}}\right)\right\}$$. Conceptually, a quantum node is sometimes thought of as representing a small, localized laboratory in some region of spacetime, but may also be conceived more abstractly, for example as occupying a particular position in between the gates of a quantum circuit.

The aim of the process formalism is to describe the correlations between the outcomes of the operations that are performed at the separate quantum nodes. Given a set of instruments at the quantum nodes A₁, ..., A_n, the joint probability for their outcomes is given by

A process operator $$ {\sigma }_{A_1...A_n}$$, which up to a different convention of the CJ isomorphism is the same as a process matrix³, obeys constraints, designed to ensure that valid joint probabilities are returned by Eq. (1) for any possible choices of the operations performed by the agents, and that the same holds even when the agents have pre-shared entanglement. These constraints are³: $$ {\sigma }_{A_1...A_n}\ge 0$$ and $$ \mathrm{Tr}\left[{\sigma }_{A_1...A_n}\left({\tau }_{A_1}\otimes \cdots \otimes {\tau }_{A_n}\right)\right]=1$$, for any set of CPTP maps $$ \left\{{\tau }_{A_i}\right\}$$ at the n nodes. Simple-to-check necessary and sufficient conditions for an operator in $$ \mathcal{L}\left({⨂}_i{\mathcal{H}}_{A_i^{\mathrm{in}}}\otimes {\mathcal{H}}_{A_i^{\mathrm{out}}}^{*}\right)$$ to be a valid process operator can be found in refs. ^6,7. To avoid clutter when tracing over a node A we will write $$ {\mathrm{Tr}}_A\left[\_\_\right]:={\mathrm{Tr}}_{A^{\mathrm{in}}{\left(A^{\mathrm{out}}\right)}^{*}}\left[\_\_\right]$$.

A question of central interest in the study of the process formalism has been whether a given process operator is compatible with the existence of a definite causal order of its nodes. A closely related question concerns how this relates to the possibilities for signalling between different nodes. Let us first make these notions more precise.

Consider the sequence of quantum operations represented in the form of a circuit in Fig. 1.

Fig. 1

Simple circuit with two quantum nodes A and B.

For any state ρ and any CPTP map $$ \mathcal{E}$$ this defines a process operator over A and B.

The gate in the circuit corresponds to an arbitrary CPTP map $$ \mathcal{E}$$, and the initial preparation to an arbitrary bipartite state ρ. Quantum nodes A and B correspond to positions in the circuit in between gates, at which an agent can choose to perform a quantum instrument on the system at that position. The nodes are represented as broken wires, with it understood that the agent’s instrument mediates the two pieces. The lower piece of the wire corresponds to the input Hilbert space of the quantum node and the upper piece of the wire to the output Hilbert space. Any circuit with some wires broken defines a partial order over the quantum nodes, with a node N preceding node $$ N^{\prime }$$ in the partial order if and only if there is a path from N to $$ N^{\prime }$$ along the (broken or unbroken) wires of the circuit. We call this partial order the causal order. In the example, node A precedes node B in the causal order. The circuit defines joint probabilities for the outcomes of any quantum instruments that are performed at nodes A and B, hence defines a process operator over the nodes A and B.

An important concept is now that of causal separability, first introduced in ref. ³ for the bipartite case. A bipartite process σ_AB is called causally separable iff it can be seen to arise as a convex mixture of processes with a fixed causal order between A and B, i.e., $$ {\sigma }_{AB}=p{\sigma }_{AB}^{A⋠B}+\left(1-p\right){\sigma }_{AB}^{B⋠A}$$, with 0 ≤ p ≤ 1, where $$ {\sigma }_{AB}^{B⋠A}$$ is a process that can arise from a sequence of operations of the form of Fig. 1, and $$ {\sigma }_{AB}^{A⋠B}$$ is a process that can arise from a different sequence of operations, of the same form except that B precedes A. Otherwise σ_AB is causally nonseparable. The idea is that a causally separable process can be thought to describe a situation in which a well-defined, though possibly unknown, causal order of the nodes exists, whereas a causally nonseparable process is not compatible with such an interpretation.

The connection with signalling between the nodes is as follows. Given a bipartite process σ_AB, we say that there is no signalling from quantum node B to quantum node A if and only if for all quantum instruments $$ {\tau }_A^{k_A}$$ at A and all deterministic quantum instruments τ_B at B, the probability distribution $$ P\left(k_A\right)=\mathrm{Tr}\left[{\sigma }_{AB}\left({\tau }_A^{k_A}\otimes {\tau }_B\right)\right]$$ is independent of τ_B. This condition is equivalent to $$ {\sigma }_{AB}={\sigma }_{A{B}^{\mathrm{in}}}\otimes {\mathbb{1}}_{{\left(B^{\mathrm{out}}\right)}^{*}}$$³. The connection between signalling and causal order is that in any sequence of operations of the form of Fig. 1, there is no signalling from B to A. Moreover, every bipartite process operator with no-signalling from B to A is known to have a realisation as the process operator arising from a circuit of the form of Fig. 1⁵⁴.

The formal definition of the multipartite generalization of causal separability is more intricate than in the bipartite case: beyond just convex mixtures of fixed causal orders, the definition allows for a dynamical causal order in which the causal order at later quantum nodes can depend on the events taking place at earlier quantum nodes. This definition is postponed to a later section dedicated to causal separability. See also refs. ^7,23 for a detailed discussion. A discussion of signalling in a multipartite process is also more involved, since whether a subset of quantum nodes can signal to another subset of quantum nodes depends on the interventions performed at other quantum nodes not in the two subsets.

Causal influence vs signalling

This work is concerned with a notion of causal structure, which is distinct from the causal order defined by a circuit, and which also needs to be carefully distinguished from the possibilities for signalling afforded by a general process operator. In order to motivate the idea, consider a circuit of the form of Fig. 1, with each wire representing a qubit, with $$ \rho ={\rho }_{A^{\mathrm{in}}}\otimes {∣0⟩}_{A^{\prime }}⟨0∣$$, and with the channel $$ \mathcal{E}$$ being a quantum Controlled-NOT gate with the control on the output wire of the A node. This circuit defines a process operator $$ {\sigma }_{AB}^0$$ on the A and B nodes, which may easily be computed, and it can be verified that $$ {\sigma }_{AB}^0$$ allows signalling from A to B. Similarly, in the same circuit except with $$ \rho ={\rho }_{A^{\mathrm{in}}}\otimes {∣1⟩}_{A^{\prime }}⟨1∣$$, the process operator $$ {\sigma }_{AB}^1$$ is easily computed, and it can be verified that signalling is possible from A to B.

Now consider the same experiment, except with the preparation of the $$ A^{\prime }$$ system given by flipping a fair coin, and preparing $$ {∣0⟩}_{A^{\prime }}⟨0∣$$ on heads and $$ {∣1⟩}_{A^{\prime }}⟨1∣$$ on tails. If the outcome of the coin flip is unknown, then the state of the $$ A^{\prime }$$ system is the mixed state $$ \mathbb{1}/2$$, and the corresponding process operator over A and B is

In the process $$ {\sigma }_{AB}^{\mathrm{mix}}$$, there is no signalling from A to B. Indeed the very same process operator could arise from a situation in which A and B are independent and spacelike separated.

In the experiment with the coin flip, it is clear that A has a causal influence on B, since agents who know the value of the coin flip would be able to send signals from A to B. From the perspective of agents who do not know the value of the coin flip, however, signalling is washed out by the randomness of the unobserved system. A similar phenomenon is well understood in the literature on classical causal modelling. In a canonical example, A, B, and C are all classical bits, with A and C causes of B such that B is equal to the parity of A and C. If C is inaccessible, or hidden, and satisfies P(C = 0) = P(C = 1) = 1/2, then B is randomly distributed regardless of the value of A. Hence as long as C remains hidden, signals cannot be sent from A to B. (See Section 2.4 of ref. ³⁵.)

The conclusion that should be drawn from the example with process $$ {\sigma }_{AB}^{\mathrm{mix}}$$ is that causal influence between quantum nodes should not be defined in terms of the possibilities for signalling afforded by a process operator, at least not if there is a chance that unobserved systems ($$ A^{\prime }$$ in the example) are interacting with the systems under study (A and B in the example). Given only a process operator σ_AB and no other data, although signalling is sufficient for causal influence, it can happen that A has a causal influence upon B even though there is no signalling from A to B in σ_AB.

Quantum causal models

The framework of quantum causal models, introduced in refs. ^34,35, is based on the idea that in an example like that just above, statements about causal influence can be defined in terms of signalling, but only once all relevant systems are included in the description. At this point, the description is of a closed system, and at least in standard quantum theory, evolution of a closed system is unitary. Hence quantum causal models define causal influence in terms of unitary transformations. Reference ³⁵ shows that in the case of unitary circuits with broken wires representing quantum nodes, the causal relations between the quantum nodes can be summarized in the form of a DAG, where the DAG imposes constraints on the process operator over the quantum nodes.

These leaves open the question of what the pattern of causal influence might be in causally nonseparable processes described in the literature. Can it even be well defined or must one conclude that these processes are not amenable to causal explanation at all, or that all that can be discussed is signalling between the nodes? Our idea is that such processes can be understood in causal terms, if the framework of quantum causal modelling is extended to allow causal cycles. We will show that the resulting formalism can be used successfully to describe some of the much-studied instances of causally nonseparable processes from the literature. Later, we show the utility of this approach by using it to settle previously open questions concerning causally nonseparable processes.

The following definition generalizes that of refs. ^34,35, by allowing cyclic graphs (along with a more minor generalization, which is that the input and output Hilbert spaces of a quantum node can here have different dimensions).

Definition 1 (Quantum causal model (QCM)—generalized) A QCM is given by:

a causal structure represented by a directed graph G with vertices corresponding to quantum nodes A₁, . . . , A_n,

for each A_i, a quantum channel $$ {\rho }_{A_i\mid Pa\left(A_i\right)}\in \mathcal{L}\left({\mathcal{H}}_{A_i^{\mathrm{in}}}\otimes {\mathcal{H}}_{Pa{\left(A_i\right)}^{\mathrm{out}}}^{*}\right)$$, where Pa(A_i) denotes the set of parents of A_i according to G, such that $$ \left[{\rho }_{A_i\mid Pa\left(A_i\right)},{\rho }_{A_j\mid Pa\left(A_j\right)}\right]=0$$ for all i, j and such that $$ {\sigma }_{A_1...A_n}={\prod }_i{\rho }_{A_i\mid Pa\left(A_i\right)}$$ is a process operator over the quantum nodes A₁, . . . , A_n.

When writing products of the form $$ {\prod }_i{\rho }_{A_i\mid Pa\left(A_i\right)}$$, it is understood implicitly that each factor is padded with an identity operator in tensor product for all other spaces. A QCM is called cyclic iff its causal structure contains directed cycles, and acyclic otherwise.

It is useful to define a term to express the fact that a given process operator σ has the correct form with respect to a given causal structure to define a QCM.

Definition 2 (Quantum Markov condition—generalized) A process $$ {\sigma }_{A_1...A_n}$$ is called Markov for a directed graph G with quantum nodes A₁, …, A_n as its vertices iff it admits a factorization into pairwise commuting channels of the form $$ {\sigma }_{A_1...A_n}={\prod }_{i=1}^n{\rho }_{A_i\mid Pa\left(A_i\right)}$$.

Note that the Markov condition of classical causal models^47,48 is a special case of Definition 2, obtained when the graph is acyclic and $$ {\sigma }_{A_1...A_n}$$ is diagonal in a product basis, and encodes a classical probability distribution³⁵. The following first sets out some further terminology and basic properties of Definition 1 and then turns to motivating and explaining Definition 1, making the link with unitary transformations, and showing why it is that for a particular directed graph, condition (2) should hold.

First, observe that not every cyclic graph supports a QCM in an interesting way. Consider, for example, the two-node cyclic graph of Fig. 2a. A QCM with such a causal structure would come with a process operator

Fig. 2

Examples of cyclic directed graphs.

a A cyclic directed graph that does not admit a faithful quantum causal model; b A cyclic directed graph that admits a faithful quantum causal model.

More generally, we will say that a QCM is faithful iff each of the channels $$ {\rho }_{A_i\mid Pa\left(A_i\right)}$$ is signalling from $$ A_j^{\mathrm{out}}$$ to $$ A_i^{\mathrm{in}}$$ for every A_j ∈ Pa(A_i), i.e.,

Proposition 1 There is no faithful cyclic quantum causal model with two nodes.

Proof See Methods.

Now consider the cyclic graph $$ G^{\prime }$$ in Fig. 2b A QCM with $$ G^{\prime }$$ as its causal structure comes with the data

Note that, given a cyclic graph such as that in Fig. 2b, even when a faithful QCM exists it is not in general the case that any set of commuting channels $$ {\rho }_{A_i\mid Pa\left(A_i\right)}$$ defines a process operator. (See Methods for an explicit demonstration of this fact.) The constraint in the definition of a QCM that $$ {\sigma }_{A_1...A_n}={\prod }_i{\rho }_{A_i\mid Pa\left(A_i\right)}$$ is a valid process operator is essential, and is what guarantees that grandfather-type paradoxes do not arise³. This is in contrast to the acyclic case, where, given an acyclic causal structure, it is not hard to argue that any product of commuting channels of the form $$ {\prod }_i{\rho }_{A_i\mid Pa\left(A_i\right)}$$ is a valid process operator³⁵, hence in particular a faithful QCM with that causal structure can always be found.

Unitarity and causal structure

The definition of a QCM above is predicated on the idea that causal structure should be represented by a directed graph. This idea, however, along with the stipulation that the accompanying process is Markov for the graph, was presented without much justification or further comment. Why is causal structure represented by a directed graph, for example, as opposed to a different mathematical object, such as a partial order, or a preorder, or some kind of hypergraph? This section considers a subclass of processes—unitary processes, defined momentarily—and shows that a unitary process is associated with a causal structure, which can indeed be represented with a directed graph, and that the unitary process is Markov for that graph. In other words, a unitary process, along with its causal structure, defines a QCM.

In order to define a unitary process, observe that a process operator $$ {\sigma }_{A_1...A_n}$$ has the mathematical form of the CJ operator for a channel $$ \mathcal{P}:\mathcal{L}\left({⨂}_i{\mathcal{H}}_{A_i^{\mathrm{out}}}\right)\to \mathcal{L}\left({⨂}_i{\mathcal{H}}_{A_i^{\mathrm{in}}}\right)$$³. Where it is convenient to emphasise this form, we will sometimes write $$ {\sigma }_{A_1...A_n}={\rho }_{A_1...A_n\mid A_1...A_n}^{\mathcal{P}}$$, where it is understood implicitly that an A_i to the right of the bar stands for $$ A_i^{\mathrm{out}}$$, while an A_i to the left of the bar stands for $$ A_i^{\mathrm{in}}$$. A unitary process is a process (where some of the input or output spaces may be trivial, i.e., 1-dimensional) such that the channel $$ \mathcal{P}$$ is a unitary channel.

The first step is to define a notion of causal structure that pertains to the inputs and outputs of a unitary channel.

Definition 3 (Causal structure of a unitary channel) Given a unitary channel $$ {\rho }_{CD\mid AB}^{\mathcal{U}}$$, write A ↛ D (A does not influence D), iff $$ {\mathrm{Tr}}_C\left[{\rho }_{CD\mid AB}^{\mathcal{U}}\right]={\rho }_{D\mid B}^{\mathcal{M}}\otimes {\mathbb{1}}_{A^{*}}$$ for some marginal channel $$ \mathcal{M}$$. If A can influence D, i.e. ¬(A ↛ D), A is a direct cause of D. For any unitary channel $$ {\rho }_{C_1...C_l\mid B_1...B_k}^{\mathcal{U}}$$ with k input and l output subsystems its causal structure is then the set of causal relations between input and output subsystems and can be represented by a DAG with vertices B₁, ..., B_k and C₁, ..., C_l and an arrow B_j → C_i whenever B_j is a direct cause of C_i.

This definition (which, given the correspondence between unitary maps U and unitary channels $$ \mathcal{U}\left(\_\right)=U\left(\_\right)U^{†}$$, we let refer to either) lifts naturally to the case of a unitary process, in such a way that causal relationships are defined between the nodes of the process, rather than between inputs and outputs of a channel.

Definition 4 (Causal structure of a unitary process) Given a unitary process $$ {\sigma }_{A_1...A_n}={\rho }_{A_1...A_1\mid A_1...A_n}^{\mathcal{U}}$$, write A_j ↛ A_i (node A_j does not influence node A_i), iff $$ A_j^{\mathrm{out}}$$ does not influence $$ A_i^{\mathrm{in}}$$ in $$ \mathcal{U}$$. If node A_j can influence node A_i, then A_j is a direct cause of A_i. The causal structure of the unitary process is the set of all causal relations between its quantum nodes, and is representable as the directed graph with vertices A₁, ..., A_n and an arrow A_j → A_i, whenever A_j is a direct cause of A_i.

The fact that any unitary process is Markov for its causal structure, hence defines a QCM, is then immediate from the following theorem of refs. ^34,35.

Theorem 1 (References ^34,35) Given a unitary channel $$ {\rho }_{C_1...C_l\mid B_1...B_k}^{\mathcal{U}}$$, let $$ {\left\{Pa\left(C_i\right)\right\}}_{i=1}^l$$ be the parental sets as defined by its causal structure. Then the CJ operator factorizes as $$ {\rho }_{C_1...C_l\mid B_1...B_k}^{\mathcal{U}}={\prod }_{i=1}^l{\rho }_{C_i\mid Pa\left(C_i\right)}$$, where the marginal channels commute pairwise, $$ \left[{\rho }_{C_i\mid Pa\left(C_i\right)},{\rho }_{C_j\mid Pa\left(C_j\right)}\right]=0$$ for all i, j.

The case of non-unitary processes, and their relationship to causal structure is presented below. First, we describe a well-known example of a causally nonseparable process—the quantum SWITCH²—and show explicitly that it defines a unitary process operator with cyclic causal structure, hence a cyclic QCM.

Example: the quantum SWITCH

The quantum SWITCH² was the first example described of a causally non-separable process. The SWITCH is standardly defined as a higher-order map^2,54,55 that takes as input two CP maps $$ {\mathcal{F}}_A:\mathcal{L}\left({\mathcal{H}}_{A^{\mathrm{in}}}\right)\to \mathcal{L}\left({\mathcal{H}}_{A^{\mathrm{out}}}\right)$$ and $$ {\mathcal{G}}_B:\mathcal{L}\left({\mathcal{H}}_{B^{\mathrm{in}}}\right)\to \mathcal{L}\left({\mathcal{H}}_{B^{\mathrm{out}}}\right)$$, where $$ d_{A^{\mathrm{in}}}=d_{A^{\mathrm{out}}}=d_{B^{\mathrm{in}}}=d_{B^{\mathrm{out}}}=d$$, and gives as an output a CP map $$ \mathcal{E}:\mathcal{L}\left({\mathcal{H}}_Q\otimes {\mathcal{H}}_S\right)\to \mathcal{L}\left({\mathcal{H}}_{Q^{\prime }}\otimes {\mathcal{H}}_{S^{\prime }}\right)$$, where $$ d_Q=d_{Q^{\prime }}=2$$ and $$ d_S=d_{S^{\prime }}=d$$. Here, $$ {\mathcal{H}}_Q$$ and $$ {\mathcal{H}}_{Q^{\prime }}$$ are interpreted as the Hilbert spaces of a control qubit at some initial and some final time, respectively, and $$ {\mathcal{H}}_S$$ and $$ {\mathcal{H}}_{S^{\prime }}$$ as the Hilbert spaces of some target system at the same two times. Intuitively, the effect of the quantum SWITCH is to transform the target system from the initial to the final time by the sequential application of the CP maps $$ {\mathcal{F}}_A$$ and $$ {\mathcal{G}}_B$$, where the order in which the two CP maps are applied is conditioned coherently on the logical value of the control qubit.

To formulate this precisely, we will describe the quantum SWITCH directly as a 4-node process (see Fig. 3), which involves the nodes A and B, where $$ {\mathcal{F}}_A$$ and $$ {\mathcal{G}}_B$$ are inserted, a node P with P^out = QS, where the control qubit and target system at the initial time are prepared in some state, and node F with $$ F^{\mathrm{in}}=Q^{\prime }{S}^{\prime }$$, where the control qubit and the system at the final time are subject to some measurement. The SWITCH is then a unitary four-partite process with process operator $$ {\sigma }_{ABPF}^{\mathrm{SWITCH}}={\rho }_{ABF\mid ABP}^{\mathcal{U}}=∣W⟩⟨W∣$$, where

Fig. 3

A unitary process with nodes A and B, root node P (in the global past) and leaf node F (in the global future).

Here with P^out = QS and $$ F^{\mathrm{in}}=Q^{\prime }{S}^{\prime }$$; the quantum SWITCH is an example of such a process.

Fig. 4

The causal structure G_SWITCH of the quantum SWITCH.

Any unitary process of the form as in Fig. 3 has a causal structure that is a subgraph of G_SWITCH.

Compatibility vs Markovianity

This section extends the discussion of causal structure to non-unitary processes. Briefly, in a QCM involving a non-unitary process σ, the arrows of the graph are taken to represent facts about the causal structure of some underlying unitary process, with the property that σ is recovered from the unitary process when marginalizing over auxiliary systems. The auxiliary systems take the form of a final system F, along with uncorrelated local disturbances, where the latter are inputs to the unitary process in a direct product state, with the property that each of them is a direct cause of at most one of the nodes of σ. As we shall show, it then follows that the process σ is Markov for the graph.

The following was introduced in ref. ⁵¹ (there under the name purifiability), and will help make these ideas precise.

Definition 5 (Unitary extendibility) A process $$ {\sigma }_{A_1...A_n}$$ is called unitarily extendible iff there exists a unitary process $$ {\sigma }_{A_1...A_{n}PF}={\rho }_{A_1...A_{n}F\mid A_1...A_{n}P}^{\mathcal{U}}$$ on the quantum nodes A₁, …, A_n, plus additional root node P and leaf node F, such that $$ {\sigma }_{A_1...A_n}={\mathrm{Tr}}_{FP}\left[{\sigma }_{A_1...A_{n}PF}{\tau }_P\right]$$ for some state $$ {\tau }_P\in \mathcal{L}\left({\mathcal{H}}_{P^{\mathrm{out}}}^{*}\right)$$. The process $$ {\sigma }_{A_1...A_{n}PF}$$ is called a unitary extension of $$ {\sigma }_{A_1...A_n}$$.

It was found in ref. ⁵¹ that not all process operators are unitarily extendible. The reason for this is that, although for any process $$ {\sigma }_{A_1...A_n}={\rho }_{A_1...A_n\mid A_1...A_n}^{\mathcal{P}}$$, corresponding to a channel $$ \mathcal{P}$$, the channel $$ \mathcal{P}$$ admits a dilation to a unitary channel, this unitary channel does not necessarily correspond to a valid process itself. Process operators that are not unitarily extendible are those for which no dilation exists such that the unitary channel corresponds to a valid process.

Now suppose that a process $$ {\sigma }_{A_1...A_n}$$ does have a unitary extension $$ {\sigma }_{A_1...A_{n}PF}$$, involving the additional root node P. As per Def. 4, the unitary extension $$ {\sigma }_{A_1...A_{n}PF}$$ has a causal structure given by some directed graph G with nodes A₁, ..., A_n, P, F. Let $$ G^{\prime }$$ be the subgraph with nodes A₁, ... ,A_n, along with all arrows that connect only these nodes in G. In general, in the graph G, the node P will have arrows to several of the A_i, meaning that P is a common cause for these nodes. There will then, in general, be correlations in σ that are explained by the common cause P. This means that the graph $$ G^{\prime }$$, which omits P, is at best an incomplete causal explanation for the correlations in σ, since it does not explain those correlations due to P. In this case, there is no reason why σ should be Markov for the graph $$ G^{\prime }$$.

Consider now a unitary extension of $$ {\sigma }_{A_1...A_n}$$ with the feature that the node P can be factored into uncorrelated local disturbances λ_i, such that each λ_i is a direct cause of at most one of the nodes A_i. In this case, the graph $$ G^{\prime }$$, obtained by omitting all of the λ_i and leaf node F, can be seen as a causal explanation for correlations described by the process $$ {\sigma }_{A_1...A_n}$$, which omits only local disturbances and the final effect F, and which does not omit common causes. In this case, we will say that σ is compatible with the graph $$ G^{\prime }$$. In fact, it is more useful to define this term more broadly: we will say that σ is compatible with any graph, with nodes A₁, ..., A_n, that contains $$ G^{\prime }$$ as a subgraph. The following definition makes this precise, generalizing that of ref. ³⁵ to the cyclic case.

Definition 6 (Compatibility with a directed graph) A process $$ {\sigma }_{A_1...A_n}$$ is compatible with a directed graph G with nodes A₁, ..., A_n, iff $$ {\sigma }_{A_1...A_n}$$ is extendible to a unitary process $$ {\sigma }_{A_1...A_n{\lambda }_1...{\lambda }_{n}F}$$, with an extra root node λ_i for i = 1, ..., n and an extra leaf node F, such that:

there exists a product state $$ {\tau }_{{\lambda }_1}\otimes \cdots \otimes {\tau }_{{\lambda }_n}$$ with $$ {\tau }_{{\lambda }_i}\in \mathcal{L}\left({\mathcal{H}}_{{\lambda }_i^{\mathrm{out}}}^{*}\right)$$ such that $$ {\sigma }_{A_1...A_n}={\mathrm{Tr}}_{{\lambda }_1...{\lambda }_{n}F}\left[{\sigma }_{A_1...A_n{\lambda }_1...{\lambda }_{n}F}\left({\tau }_{{\lambda }_1}\otimes \cdots \otimes {\tau }_{{\lambda }_n}\right)\right]$$,

$$ {\sigma }_{A_1...A_n{\lambda }_1...{\lambda }_{n}F}$$ satisfies the following no-influence conditions (with Pa(A_i) referring to G): $$ {\left\{A_j\nrightarrow A_i\right\}}_{A_j\notin Pa\left(A_i\right)},{\left\{{\lambda }_j\nrightarrow A_i\right\}}_{j\ne i}$$.

The following then justifies the stipulation, as a part of the definition of a QCM, that the process accompanying a graph is Markov for the graph.

Theorem 2 If a process $$ {\sigma }_{A_1...A_n}$$ is compatible with the directed graph G, then it is also Markov for G.

Proof Similarly to the acyclic case in ref. ³⁵, the theorem follows essentially from Theorem 1: the unitary extension, asserted to exist by virtue of the assumed compatibility with G, has to factorize into pairwise commuting operators of the form $$ {\sigma }_{A_1...A_n{\lambda }_1...{\lambda }_{n}F}={\rho }_{F\mid A_1...A_n{\lambda }_1...{\lambda }_n}\left({\prod }_i{\rho }_{A_i\mid Pa\left(A_i\right){\lambda }_i}\right)$$. This yields $$ {\sigma }_{A_1\cdots A_n}={\prod }_i{\mathrm{Tr}}_{{\lambda }_i}\left[{\rho }_{A_i\mid Pa\left(A_i\right){\lambda }_i}{\tau }_{{\lambda }_i}\right]$$, where the factors $$ {\rho }_{A_i\mid Pa\left(A_i\right)}:={\mathrm{Tr}}_{{\lambda }_i}\left[{\rho }_{A_i\mid Pa\left(A_i\right){\lambda }_i}{\tau }_{{\lambda }_i}\right]$$ are pairwise commuting operators.

Reference ³⁵ also establishes a converse to this result, for the case that G is acyclic. For a general directed graph G, however, the same proof does not suffice since, even though a dilation to a unitary channel with the required causal constraints can always be found³⁵, it is not immediate whether this channel can be guaranteed to define a valid process. We pose this as a hypothesis:

Hypothesis 1 If a process $$ {\sigma }_{A_1...A_n}$$ is Markov for a directed graph G, then it is compatible with G.

The hypothesis is satisfied by all examples that we have investigated, but we do not have a proof that it is true in general. Some consequences of the validity or otherwise of this hypothesis are discussed in the “Conclusions” section.

Example: a process that violates a causal inequality

While the quantum SWITCH is causally nonseparable, the correlations that can be established between operations at the nodes of the quantum SWITCH can always be obtained by a causally separable process with sufficiently large input and output dimensions at each node^6,7. There are, however, causally nonseparable processes that can produce correlations violating causal inequalities^{3,7,9,12,56–60}, which are incompatible with the existence of a definite order between the nodes irrespectively of the types of systems or operations performed at those nodes^4,7,61. In the literature such processes are called noncausal⁷.

An example of a tripartite noncausal process is the one which was found by Araújo and Feix (AF) and then published and further studied by Baumeler and Wolf in refs. ^12,62. It is remarkable in that the process is both classical and deterministic (see below for further discussion of classical processes). Any classical process can be viewed as a quantum process, diagonal with respect to a product basis. The AF process, viewed as a quantum process on nodes A, B and C, each with two-dimensional input and output Hilbert spaces, is described by the process operator

As is explicit in this description, the AF process together with the causal structure in Fig. 5 defines a faithful cyclic QCM.

Fig. 5

The causal structure of the AF process.

The fully connected directed graph with three nodes A, B and C.

It was shown by Baumeler and Wolf (BW)⁶² that this process is unitarily extendible (also see refs. ^27,51) with a unitary extension given by

The original AF process is recovered for marginalization over F and feeding in the product state $$ ∣0,0,0⟩$$ for λ_A, λ_B and λ_C. Formally letting the latter three define distinct root nodes λ_A, λ_B and λ_C, it is not too hard to show that this BW unitary extension also satisfies the corresponding causal constraints of Definition 13 to establish $$ {\sigma }_{ABC}^{\mathrm{AF}}$$ to be compatible with the graph of Fig. 5– in keeping with Hypothesis 1.

Cyclicity and extended circuit diagrams

An essential feature of the Markov condition in Definition 2 is the pairwise commutation relation of the operators of the form $$ {\rho }_{A_i\mid Pa\left(A_i\right)}$$, where the parental sets in general overlap. That two commuting operators act non-trivially on the same Hilbert space has consequences for the algebraic structure of the operators and leads to an intimate link between causal and compositional structure.

In order to exemplify the fruitfulness of studying this link the following will revisit the two examples from earlier.

The quantum SWITCH can be considered as a unitary process over 4 nodes, given by $$ {\sigma }_{ABPF}^{\mathrm{SWITCH}}={\rho }_{ABF\mid ABP}^{\mathcal{U}}=∣W⟩⟨W∣$$, where $$ ∣W⟩$$ is defined in Eq. (6). The unitary channel $$ \mathcal{U}$$ corresponds to a unitary map $$ U:{\mathcal{H}}_{A^{\mathrm{out}}}\otimes {\mathcal{H}}_{P^{\mathrm{out}}}\otimes {\mathcal{H}}_{B^{\mathrm{out}}}\to {\mathcal{H}}_{A^{\mathrm{in}}}\otimes {\mathcal{H}}_{F^{\mathrm{in}}}\otimes {\mathcal{H}}_{B^{\mathrm{in}}}$$, which is depicted in Fig. 6 together with its causal structure shown in blue. Observe in particular that in U, A^out does not influence Aⁱⁿ, and similarly B^out does not influence Bⁱⁿ, as must be the case for a well-defined process¹⁸.

Fig. 6

Unitary map U that defines the quantum SWITCH.

The causal structure of U is indicated in blue.

Reference ⁶³ shows that any unitary map U with three in- and output systems, and the causal constraints of Fig. 6, has a decomposition of the following form:

Such a compositional structure with direct sums over tensor products goes beyond what is expressible with ordinary circuit diagrams. Reference ⁶³ therefore introduced extended circuit diagrams to give a graphical representation of such decompositions. Figure 7 arises from that extended circuit diagram representation of Eq. (14) by bending the wires corresponding to Aⁱⁿ and Bⁱⁿ down to re-identify the quantum nodes A and B—thereby filling the black box of the quantum SWITCH from Fig. 3. For details on this diagrammatic language, we refer the reader to ref. ⁶³, but the essential idea is that individual wires with indices on them, such as those between the circles S and V_i and W_i, respectively, represent the families of Hilbert spaces $$ {\left\{{\mathcal{H}}_{P_i^L}\right\}}_{i\in I}$$ and $$ {\left\{{\mathcal{H}}_{P_i^R}\right\}}_{i\in I}$$, while the two parallel wires together represent $$ {⨁}_{i\in I}{\mathcal{H}}_{P_i^L}\otimes {\mathcal{H}}_{P_i^R}$$. An implicit summation over orthogonal subspaces indexed by i allows the representation of the intermediate unitary map ⨁_iV_i ⊗ W_i from Eq. (14).

Fig. 7

Extended circuit diagram decomposition of the quantum SWITCH.

Additionally indicated in grey are the labels of the intermediate families of Hilbert spaces.

It is easy to see what this decomposition is concretely in the case of the quantum SWITCH: the index i takes two values, 0 and 1, corresponding to the logical values of the control qubit, i.e., $$ {\mathcal{H}}_P={\mathcal{H}}_Q\otimes {\mathcal{H}}_S\cong \left(\mathbb{C}\otimes {\mathcal{H}}_S\right)\oplus \left({\mathcal{H}}_S\otimes \mathbb{C}\right)$$ and the unitaries V_i and W_i are either the SWAP transformation on the respective systems or the identity depending on i. We see that even though the causal structure of the full process is cyclic, the process splits into a direct sum of processes in each of which causal influence and the flow of information follow acyclic paths.

This decomposition of the quantum SWITCH applies more generally: seeing as any unitary process of the type depicted in Fig. 3, with a root node P, a leaf node F, and two nodes A and B in between, satisfies A^out ↛ Aⁱⁿ and B^out ↛ Bⁱⁿ, it follows that any such unitary process has a decomposition as in Fig. 7. Note that the below will furthermore establish (as a direct consequence of the proof of Theorem 3) that for each i the summand V_i ⊗ W_i of that corresponding decomposition has to have an acyclic causal structure, that is, any unitary process with nodes A, B, P, F where P is a root node and F a leaf node, is a direct sum of unitary processes in which causal influences flow along acyclic paths.

The second example concerns the tripartite AF process and its BW unitary extension $$ {\rho }_{ABCF\mid ABCP}^U$$ (see Eqs. (12)–(13)).

The root node P has as output space $$ {\mathcal{H}}_{P^{\mathrm{out}}}={\mathcal{H}}_{{\lambda }_A}\otimes {\mathcal{H}}_{{\lambda }_B}\otimes {\mathcal{H}}_{{\lambda }_C}$$, where each λ_X influences only X and F for X = A, B, C. The associated unitary map U and its causal structure are depicted in Fig. 8.

Fig. 8

The unitary map U from Eq. (13) that defines the BW unitary extension of the AF process.

Also depicted is its causal structure, where for better visibility, rather than direct cause relations, the no-influence conditions are shown as red dashed arrows.

The results from ref. ⁶³ allow again the statement of an extended circuit decomposition of U, which is implied by its causal structure and which makes the pathways of causal influence through U graphically evident (the proof is completely analogous to that of Theorem 7 in ref. ⁶³).

This decomposition of U is depicted in Fig. 9 and reads:

Fig. 9

Causally faithful extended circuit decomposition of the unitary U from Fig. 8.

(Up to some swaps for better readability).

By appropriately bending the wires that correspond to Aⁱⁿ, Bⁱⁿ and Cⁱⁿ to re-identify the nodes A, B and C (and swapping some wires for better readability) one obtains Fig. 10, revealing a fine-grained compositional structure of the BW unitary extension.

Fig. 10

Extended circuit diagram decomposition of the BW unitary extension of the AF process.

Compared to Fig. 9 the wires for Aⁱⁿ, Bⁱⁿ and Cⁱⁿ are bent around (as well as some swaps inserted for better visibility).

Note that the stated decomposition is general in the sense that a decomposition of the form as in Fig. 9 exists for any unitary with a causal structure as in Fig. 8. However, in the concrete case of the BW unitary extension one can easily see what the components in Eq. (19) correspond to through a comparison with Eq. (13). All three indices i, j and k are binary and, via the unitaries S, T and V can be seen to correspond to one-dimensional subspaces of A^out, B^out and C^out. Hence, each indexed space, i.e., each element of a family of Hilbert spaces associated with an indexed wire, is a trivial Hilbert space. For any fixed value (i, j, k), the unitary P_ij ⊗ Q_ik ⊗ R_jk is of the type $$ {\mathcal{H}}_{{\lambda }_C}\otimes {\mathcal{H}}_{{\lambda }_B}\otimes {\mathcal{H}}_{{\lambda }_A}\to {\mathcal{H}}_{C^{\mathrm{in}}}\otimes {\mathcal{H}}_{B^{\mathrm{in}}}\otimes {\mathcal{H}}_{A^{\mathrm{in}}}$$, where all spaces are qubits (suppressing all trivial spaces). The unitary $$ P_{ij}:{\mathcal{H}}_{{\lambda }_C}\to {\mathcal{H}}_{C^{\mathrm{in}}}$$ maps $$ ∣{\lambda }_C⟩\mapsto ∣{\lambda }_C\oplus \left(\neg i\wedge j\right)⟩$$, i.e., P_ij is the identity or the NOT gate depending on the values of i and j. The unitaries Q_ik and R_jk can similarly be identified through comparison with Eq. (13).

One thus finds that the BW unitary extension is a direct sum over unitary processes each of which has an acyclic causal structure. Furthermore, it is natural to wonder whether knowing a decomposition of the form as in Fig. 8 might suggest a way in which the process could be implemented—a process, which we recall is one that violates a causal inequality.

How about other unitary processes not of the two presented types? Reference ⁶³ provides extended circuit decompositions for many classes of unitary transformations, where the decompositions are causally faithful, meaning that if A is an input to the unitary U and B an output, then there is a path from A to B in the extended circuit iff A can influence B through U (note this is distinct from the notion of faithfulness of a QCM). Consider now a unitary map U that corresponds to a unitary process, in the sense that the output Hilbert spaces of the nodes correspond to the inputs to U, and the input Hilbert spaces of the nodes correspond to the outputs of U. If U has a causally faithful extended circuit decomposition, then by appropriately bending the wires, as in the above examples, one can always obtain a fine-grained compositional structure of the corresponding unitary process. Reference ⁶³ states the hypothesis that all finite-dimensional unitary transformations (over-specified tensor products of input Hilbert spaces and output Hilbert spaces) have a causally faithful extended circuit decomposition. This would mean that all unitary processes, by bending the wires, would admit causally faithful decompositions in a similar manner. At the time of writing, however, the hypothesis remains unproven.

The bipartite unitarily extendible processes

Understanding which processes have a physical realization is a central open question in the field of indefinite causal order^18,51. While causally nonseparable processes may have a realization in exotic scenarios involving both quantum systems and gravity, it seems clear that any present-day laboratory experiment admits a description in terms of a straightforward, definite, causal ordering of suitably defined parts of the experiment. Nevertheless, various experiments have been performed that are claimed as realizations of nonseparable processes such as the quantum SWITCH^28–32,64. This has caused some debate^18,49,65.

Behind much of this debate, however, lies merely a question of how the abstract mathematical description is assumed to map to physical phenomena. Each of the implementations claimed so far is of a process that involves coherent control over the time-ordering of nodes in a similar manner to the SWITCH, and which cannot therefore violate causal inequalities. Reference ¹⁸ shows that any such implementation can be seen as a valid implementation of a nonseparable process, if the process is understood as being defined over time-delocalized systems, where the input and output Hilbert spaces of the nodes of the process correspond to subsystems of tensor products of Hilbert spaces of systems associated with different times. This raises the question: which processes in general admit a laboratory implementation, at least in terms of time-delocalized systems? In particular, can a process violating causal inequalities be implemented?

There was some hope that a process violating causal inequalities could be implemented, because ref. ¹⁸ also shows that every unitary extension of a bipartite process has a realization in terms of time-delocalized systems. Hence if there were a unitarily extendible bipartite process violating causal inequalities, then it could be implemented, at least via time-delocalized systems. The following theorem, however, shows that there is no such possibility. Any bipartite unitarily extendible process is causally separable, hence, in particular, cannot violate causal inequalities, as conjectured in ref. ⁵¹; furthermore, all unitary extensions of bipartite processes are variations of the quantum SWITCH, realizable by coherent control of the times of the operations of A and B. The argument uses the existence of a faithful extended circuit decomposition of the form as in Eq. (14) that is implied by the causal constraints of Fig. 6.

Theorem 3 All unitarily extendible bipartite processes are causally separable. Given a bipartite process, if it is unitarily extendible, then the unitary extension has a realization in terms of coherent control of the order of the node operations.

Proof See Methods.

As one can see, e.g., from the AF process, being unitarily extendible does not imply causal separability in the general multipartite case. However, the decomposition from Fig. 8 of the BW unitary extension of the AF process proved insightful with regards to how the cyclicity of the causal structure comes from different contributions across the direct sum. More generally, suppose a causally faithful extended circuit decomposition of the unitary extension of some multipartite process is known. It is then natural to ask whether some kind of generalization of the constraints established as part of the proof of Theorem 3 could be derived, which in the bipartite case just happen to give causal separability, while in the general case constrain each summand of the decomposition. As is the case with the bipartite processes, to which Theorem 3 applies, one would expect that such constraints on summands of the unitary extension also manifest themselves in interesting ways for the non-unitary marginal process. We leave this question for future investigation.

Causal nonseparability

The definition of causal separability was given above only for bipartite processes and it was mentioned that the multipartite case, with more than two nodes, is more intricate. This section will first give the general definition, following refs. ^7,23, and then present another main result.

Seeing as the idea of causal separability is to capture whether a process is consistent with our intuitions on causal order, it is natural to let it incorporate the following two features. First, in addition to probabilistic mixtures of fixed orders of nodes it allows for a dynamical causal order of them, that is, the overall causal order of some nodes need not be fixed, but may depend on what happens at some earlier nodes. Second, it demands that causal separability is preserved under extending the process with an arbitrary ancillary input state shared between the nodes (a property called extensibility⁷). A process is thus causally separable if, upon considering arbitrary shared entanglement between auxiliary input systems to all nodes, the resulting extended process can be seen to arise from a probabilistic mixture of particular processes: for each there is a node P in the past such that for all possible interventions at P the marginal process has a fixed causal order, or more generally, is itself again causally separable. Hence, one ends up with an iterative definition of the concept. This notion was originally called extensible causal separability in ref. ⁷ to distinguish it from the analogous concept without extensibility, but as it is undoubtedly the more natural concept, we here refer to it simply as causal separability, as in ref. ²³. (Note, there have been two equivalent definitions of that notion²³, which differ by whether extensibility is imposed at the level of the full process⁷ or at each level of the iteration²³. For the present purposes, it is convenient to use the latter one.) Finally, making the concept precise relies on the following notion of no-signalling in a process, which, along with various equivalent statements, was given in ref. ⁷.

Definition 7 (No signalling in a process) Given a process $$ {\sigma }_{A_1...A_n}$$, we say that there is no signalling from a subset S ⊂ {A₁, …, A_n} of its nodes to the complementary subset $$ \overline{S}:=\left\{A_1,\dots ,A_n\right\}\backslash S$$, iff the probabilities $$ P\left(k_{\overline{S}}\right)=\mathrm{Tr}\left[{\sigma }_{A_1...A_n}\left({\tau }_{\overline{S}}^{k_{\overline{S}}}\otimes {\tau }_S\right)\right]$$ for the outcomes of any operation $$ {\tau }_{\overline{S}}^{k_{\overline{S}}}={⨂}_{A\in \overline{S}}{\tau }_A^{k_A}$$ performed at $$ \overline{S}$$ are independent of the choice of trace-preserving operations τ_S = ⨂_A∈ Sτ_A performed at S.

Now let $$ {\tau }_{A_j}$$ represent a CP map at the node A_j, which is not necessarily trace-preserving. If there is no signalling to a node A_j from {A₁, …, A_n}⧹{A_j}, then for any $$ {\tau }_{A_j}$$, the object $$ {\mathrm{Tr}}_{A_j}\left[{\sigma }_{A_1...A_n}{\tau }_{A_j}\right]$$ is proportional to a process operator. In this case, let $$ \sigma {\mid }_{{\tau }_{A_j}}$$ be the corresponding correctly normalized process operator. We refer to $$ \sigma {\mid }_{{\tau }_{A_j}}$$ as a conditional process. We can now state the formal definition of causal separability.

Definition 8 (Causal separability²³) Every single-node process is causally separable. For n ≥ 2, a process σ on n quantum nodes A₁, …, A_n is said to be causally separable, iff, for any extension of each node A_j with an additional input system $$ {\mathcal{H}}_{{\left(A_j^{\prime }\right)}^{\mathrm{in}}}$$ to a new node $$ {\tilde{A}}_j$$, defined by $$ {\mathcal{H}}_{{\tilde{A}}_j^{\mathrm{in}}}:={\mathcal{H}}_{A_j^{\mathrm{in}}}\otimes {\mathcal{H}}_{{\left(A_j^{\prime }\right)}^{\mathrm{in}}}$$ and $$ {\mathcal{H}}_{{\tilde{A}}_j^{\mathrm{out}}}:={\mathcal{H}}_{A_j^{\mathrm{out}}}$$, and any auxiliary quantum state $$ \rho \in \mathcal{L}\left({\mathcal{H}}_{{\left(A_1^{\prime }\right)}^{\mathrm{in}}}\otimes \dots \otimes {\mathcal{H}}_{{\left(A_n^{\prime }\right)}^{\mathrm{in}}}\right)$$, the process σ ⊗ ρ on the quantum nodes $$ {\tilde{A}}_1$$, …, $$ {\tilde{A}}_n$$ decomposes as

An important question then concerns the relation between causal nonseparability and cyclicity of causal structure. For a QCM that involves a generic (not necessarily unitary) process, the cyclicity of its directed graph does not in general imply causal nonseparability of the process, even if the QCM is faithful. Consider, for example, the quantum SWITCH with process operator $$ {\sigma }_{ABFP}^{\mathrm{SWITCH}}$$. Tracing out the system Fⁱⁿ, we obtain a reduced 3-node process that (relabelling C as P) is both faithful and Markov for the graph of Fig. 2b, having the form σ_ABP = ρ_A∣BPρ_B∣APρ_P. This process is causally separable, since it can be understood as describing a situation in which the order between A and B depends in an incoherent manner on the logical value of the control qubit prepared at the initial time. This process thus forms a faithful cyclic QCM and is a canonical example of a process with dynamical causal order (here between nodes A and B).

In fact, one and the same cyclic graph may appear in two distinct faithful QCMs, one involving a causally separable, the other a nonseparable process. An example of this can again be given using the quantum SWITCH. The latter is causally nonseparable and has the graph in Fig. 4 as causal structure, which however also is the causal structure of the classical SWITCH², which in contrast is causally separable (see subsequent discussion of classical processes). What this points at is a well-known fact, namely that causal separability cannot separate the distinction between cyclicity and acyclicity on one hand, and classical and quantum causal order on the other hand.

For the case of unitary processes things are, however, much simpler.

Theorem 4 A unitary process is causally nonseparable iff it has a cyclic causal structure.

Proof See Methods.

If a unitary process has a causal structure given by an acyclic graph, then it is a unitary comb⁵⁴. Hence a unitary process is either a comb or is causally nonseparable—intermediate possibilities, such as dynamical causal order, cannot arise. Note that there is no classical analogue of Theorem 4, i.e., a classical deterministic process is not necessarily causally nonseparable if it has a cyclic causal structure. The classical SWITCH² is again an example that establishes this claim. (See below for an introduction of classical deterministic processes).

Cyclicity and classical processes

If a process operator is diagonal in a basis that is a product of local bases for the input and output Hilbert spaces at each node, it is equivalent to a classical process^3,12,56, where each node X is associated with a pair of classical variables Xⁱⁿ and X^out. Following ref. ³⁵ we call such classical nodes classical split nodes. Classical processes are studied in detail in refs. ^12,35,56. (See also refs. ^11,22.) This section presents the main ideas, and defines (possibly cyclic) classical split-node causal models (CSM). For the most part the definitions are the obvious classical analogues of those for the quantum case. While cyclic classical causal models have sometimes been studied (see, e.g., refs. ^66,67), for example to encompass the possibility of classical feedback loops, they are not of the split-node variety described here, and are not equivalent.

A classical process, defined over classical split-nodes X₁, ..., X_n, corresponds to a map $$ {\kappa }_{X_1...X_n}:X_1^{\mathrm{in}}\times X_1^{\mathrm{out}}\times \cdots \times X_n^{\mathrm{in}}\times X_n^{\mathrm{out}}\to \left[0,1\right]$$, such that $$ {\sum }_{X_1^{\mathrm{in}},X_1^{\mathrm{out}},...,X_n^{\mathrm{in}},X_n^{\mathrm{out}}}\left({\kappa }_{X_1...X_n}{\prod }_{i}P\left(X_i^{\mathrm{out}}\mid X_i^{\mathrm{in}}\right)\right)=1$$, for any set of classical channels $$ \left\{P\left(X_i^{\mathrm{out}}\mid X_i^{\mathrm{in}}\right)\right\}$$. A local intervention at a node X, with outcome k_X, corresponds to a classical instrument P(k_X, X^out∣Xⁱⁿ). Given a local intervention at each node, the joint probability distribution over the outcomes is

A special case of a classical process is a deterministic process $$ {\kappa }_{X_1...X_n}^f$$, for which $$ P\left(X_1^{\mathrm{in}},...,X_n^{\mathrm{in}}\mid X_1^{\mathrm{out}},...,X_n^{\mathrm{out}}\right)=\delta \left(\left(X_1^{\mathrm{in}},...,X_n^{\mathrm{in}}\right),f\left(X_1^{\mathrm{out}},...,X_n^{\mathrm{out}}\right)\right)$$, where $$ f:X_1^{\mathrm{out}}\times ....\times X_n^{\mathrm{out}}\to X_1^{\mathrm{in}}\times ....\times X_n^{\mathrm{in}}$$ is a function. When f is bijective, we call such a process reversible. It was shown in ref. ¹² that the set of classical processes over nodes X₁, ..., X_n forms a polytope, and that the deterministic polytope, defined as all convex mixtures of deterministic processes, is in general a strict subset of it. While all classical processes on two nodes are causally separable³, on three or more nodes there exist classical processes, including deterministic classical processes, that are causally nonseparable—the AF process from ref. ⁵⁶, described above, is an example.

Definition 9 (CSM—generalized) A CSM is given by:

a causal structure represented by a directed graph G with vertices corresponding to classical split-nodes X₁, . . . , X_n,

for each X_i, a classical channel $$ P\left(X_i^{\mathrm{in}}\mid Pa{\left(X_i\right)}^{\mathrm{out}}\right)$$, where Pa(X_i) denotes the set of parents of X_i according to G, such that $$ {\kappa }_{X_1\cdots X_n}={\prod }_{i}P\left(X_i^{\mathrm{in}}\mid Pa{\left(X_i\right)}^{\mathrm{out}}\right)$$ is a classical process over X₁, . . . , X_n.

This definition generalizes that of ref. ³⁵ to include the case of cyclic graphs, and classical split nodes where the input and output variables have different cardinalities. Reference ³⁵ presents detailed discussion of the relationship between (acyclic) CSMs and standard classical causal models^47,48.

In the classical case, causal structure (defined for unitary processes in the quantum case) can be defined for deterministic processes.

Definition 10 (Causal structure of a deterministic classical process) Given a deterministic process $$ {\kappa }_{X_1...X_n}^f$$, the causal structure of the process is the directed graph with vertices X₁,...,X_n and an arrow X_i → X_j, whenever $$ X_j^{\mathrm{in}}$$ depends on $$ X_i^{\mathrm{out}}$$ through the function f.

Definition 11 (Classical Markov condition—generalized) A process $$ {\kappa }_{X_1...X_n}$$ is called Markov for a directed graph G with classical split-nodes X₁, …, X_n as its vertices iff it admits a factorization of the form $$ {\kappa }_{X_1...X_n}={\prod }_{i=1}^{n}P\left(X_i^{\mathrm{in}}\mid Pa{\left(X_i\right)}^{\mathrm{out}}\right)$$, where Pa(X_i) denotes the set of parents of X_i according to G.

The following is immediate.

Proposition 2 Every deterministic classical process is Markov for its causal structure.

In the case of general—i.e., not necessarily deterministic—classical processes, an account of their relationship to causal structure can be given that again mirrors the quantum case. Let us adopt the provisional approach that causal structure always inheres in deterministic reversible processes (where reversibility here may not be essential, but is assumed to provide a closer analogue to the quantum case in which unitarity is assumed). Then compatibility with a given directed graph can be defined in terms of extension to a reversible deterministic process with latent local noise variables.

Definition 12 (Reversible extendibility) A process $$ {\kappa }_{X_1...X_n}$$ is reversibly extendible iff there exists a reversible deterministic process $$ {\kappa }_{X_1\cdots X_{n}F\lambda }^f$$ with an additional leaf node F and root node λ, such that $$ {\kappa }_{X_1\cdots X_n}={\sum }_{F^{\mathrm{in}},{\lambda }^{\mathrm{out}}}\left[{\kappa }_{X_1\cdots X_{n}F\lambda }^{f}P\left({\lambda }^{\mathrm{out}}\right)\right]$$ for some P(λ^out).

Definition 13 (Compatibility with a directed graph) A process $$ {\kappa }_{X_1\cdots X_n}$$ is compatible with a directed graph G with nodes X₁,...,X_n, iff $$ {\kappa }_{X_1\cdots X_n}$$ is reversibly extendible to a deterministic process $$ {\kappa }_{X_1\cdots X_{n}F{\lambda }_1...{\lambda }_n}^f$$, with an additional leaf node F, root nodes λ_i, and a product distribution $$ {\prod }_{i}P\left({\lambda }_i^{\mathrm{out}}\right)$$, such that through f, $$ X_i^{\mathrm{in}}$$ depends neither on $$ {\lambda }_j^{\mathrm{out}}$$ for j ≠ i nor on $$ X_j^{\mathrm{out}}$$ for X_j ∉ Pa(X_i) (with Pa(X_i) referring to G).

With Proposition 2, the following analogue of Thm. 2 is straightforward.

Theorem 5 If a classical process $$ {\kappa }_{X_1\cdots X_n}$$ is compatible with a directed graph G, then it is also Markov for G.

As in the quantum case, we leave open whether the converse to Theorem 5 holds.

Hypothesis 2 If a process $$ {\kappa }_{X_1...X_n}$$ is Markov for a directed graph G, then it is compatible with G.

We remark only that Hypothesis 2 is not obviously implied by its quantum counterpart, Hypothesis 1. First, it is not known whether reversible extendibility implies unitary extendibility for a classical process when seen as a special case of a quantum process. Second, even if this is the case, it is still conceivable that while a classical process that is Markov for a given graph may admit unitary extensions with the required no-influence properties when viewed as a quantum process, no such extension may be equivalent to a deterministic classical process for the given preferred basis.

We conclude with the following observation.

Theorem 6 Given a set of classical split nodes X₁, ..., X_n, the set of reversibly extendible classical processes on X₁, ..., X_n coincides with the deterministic polytope.

Proof See Methods.

If Hypothesis 2 holds, then Theorem 6 implies in particular that the process defined by a CSM must always belong to the deterministic polytope. An example of a classical process $$ {\kappa }_{X_1\cdots X_n}$$ outside of the deterministic polytope is described in ref. ¹² (and denoted $$ {\widehat{E}}_{ex1}$$ therein). It is not too hard to show that this process is not Markov for any directed graph, hence cannot be the process defined by a CSM, in keeping with Hypothesis 2.

Characterisation of process operators

In order to state necessary and sufficient conditions for an operator to be a valid process operator, the following will be useful. Let $$ {\left\{{\eta }_X^l\right\}}_{l=0}^{d_X^2-1}$$ denote a Hilbert-Schmidt (HS) basis for $$ \mathcal{L}\left({\mathcal{H}}_X\right)$$, i.e., a set of operators such that they are orthonormal with respect to the HS inner product and, in addition, traceless for all $$ l=1,...,d_X^2-1$$, while $$ {\eta }_X^0=\left(1/d_X\right){\mathbb{1}}_X$$. Any $$ \sigma \in \mathcal{L}\left({\mathcal{H}}_{A^{\mathrm{in}}}\otimes {\mathcal{H}}_{A^{\mathrm{out}}}\otimes {\mathcal{H}}_{B^{\mathrm{in}}}\otimes {\mathcal{H}}_{B^{\mathrm{out}}}\right)$$ can be expanded in a HS basis as $$ \sigma ={\sum }_{l_1,l_2,l_3,l_4}{\alpha }_{l_1{l}_2{l}_3{l}_4}{\eta }_{A^{\mathrm{in}}}^{l_1}\otimes {\eta }_{A^{\mathrm{out}}}^{l_2}\otimes {\eta }_{B^{\mathrm{in}}}^{l_3}\otimes {\eta }_{B^{\mathrm{out}}}^{l_4}$$. A term of type Aⁱⁿ in the expansion is a summand with non-trivial action only on Aⁱⁿ, i.e., l₁ ≠ 0 and l₂ = l₃ = l₄ = 0. Similarly for types AⁱⁿB^out etc.

It was shown in ref. ³ that σ being a bipartite process operator is equivalent to σ ≥ 0, $$ \mathrm{Tr}\left[\sigma \right]=d_{A^{\mathrm{out}}}{d}_{B^{\mathrm{out}}}$$ and that in a HS basis expansion, in addition to a term, which is proportional to the identity operator on all four spaces, only the coefficients of terms of the types Aⁱⁿ, Bⁱⁿ, AⁱⁿBⁱⁿ, AⁱⁿB^out, A^outBⁱⁿ, AⁱⁿA^outBⁱⁿ and AⁱⁿBⁱⁿB^out, may be non-vanishing. These conditions were generalized to n numbers of nodes in ref. ⁷ and can easily be stated as (1) σ ≥ 0, (2) $$ \mathrm{Tr}\left[\sigma \right]={\prod }_{i=1}^n{d}_{A_i^{\mathrm{out}}}$$ and (3) that in a HS basis expansion the only non-vanishing terms, apart from an overall identity operator, are of a type such that there must be at least one node, say A_i, on whose out-space, $$ A_i^{\mathrm{out}}$$, the action is trivial, but on whose in-space, $$ A_i^{\mathrm{in}}$$, the action is non-trivial. Equivalent conditions were presented in ref. ⁶ where the projector onto the linear subspace of process operators was defined explicitly, giving a basis-independent characterization.

Proof of Proposition 1 Suppose a bipartite cyclic QCM is given by the (unique) cyclic graph G with two nodes A and B from Fig. 2a and a process σ_AB = ρ_A∣Bρ_B∣A, Markov for G. It follows that σ_AB = ρ_B∣A ⊗ ρ_A∣B, as both factors act on distinct Hilbert spaces. Now suppose that this is a faithful QCM, i.e., both channels ρ_A∣B and ρ_B∣A are signalling channels. One way to see that this contradicts the assumption that σ_AB is a valid process is by analyzing the non-vanishing types of terms in an expansion of σ_AB relative to a HS product basis (see above). If signalling from B^out to Aⁱⁿ is possible in ρ_A∣B, then an expansion of just ρ_A∣B has to contain a non-vanishing term of type AⁱⁿB^out. Similarly, if signalling from A^out to Bⁱⁿ is possible in ρ_B∣A, then an expansion of ρ_B∣A has to contain a non-vanishing term of type BⁱⁿA^out. Consequently, σ_AB has to contain a non-vanishing term of type AⁱⁿB^outBⁱⁿA^out, which is forbidden for a process operator³.

Product of commuting operators not necessarily a process operator

As established by Proposition 1, not all cyclic graphs support a faithful cyclic QCM. Here we show that, given a cyclic graph G that does support a faithful cyclic QCM, it is not true that any product of commuting operators $$ {\prod }_i{\rho }_{A_i\mid Pa\left(A_i\right)}$$, with parental sets as in G, constitutes a process operator. Consider for instance the graph G in Fig. 2b (and see the discussion below Definition 8 for an example of a faithful cyclic QCM over G). Letting the three nodes A, B and C be classical split nodes, with classical bits Aⁱⁿ, A^out, Bⁱⁿ, B^out, Cⁱⁿ and C^out, define classical channels as in Eqs. (29)–(30). It is easy to see that the signalling relations through the channels P(Aⁱⁿ∣B^out, C^out) and P(Bⁱⁿ∣A^out, C^out) are indeed as in Fig. 2b. At the same time, for any choice of probability distribution P(Cⁱⁿ), the product P(Aⁱⁿ∣B^out, C^out)P(Bⁱⁿ∣A^out, C^out)P(Cⁱⁿ) cannot be a classical process: consider an intervention at C which fixes C^out to be 0, then P(Aⁱⁿ∣B^out, 0)P(Bⁱⁿ∣A^out, 0) is still a product of two signalling classical channels, which (seeing them as special cases of quantum channels) was already established in the proof of Proposition 1 to be in contradiction with being a process. This establishes the claim.

Proof of Theorem 3

Suppose the bipartite quantum process operator σ_AB is unitarily extendible. Consider an arbitrary unitary extension of it, $$ {\sigma }_{ABFP}={\rho }_{ABF\mid ABP}^{\mathcal{U}}$$. From Eq. (14) it follows that the reduced process obtained by tracing out Fⁱⁿ has the form