# Cyclic functional causal models beyond unique solvability with a graph separation theorem

Carla Ferradini, Victor Gitton, V. Vilasini

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

## To cite this version:

Carla Ferradini, Victor Gitton, V. Vilasini. Cyclic functional causal models beyond unique solvability with a graph separation theorem. 2025. hal-04934079

HAL Id: hal-04934079

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

Preprint submitted on 7 Feb 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Cyclic functional causal models beyond unique solvability with a graph separation theorem

Carla Ferradini¹, Victor Gitton¹, and V. Vilasini¹,²

¹Institute for Theoretical Physics, ETH Zurich, 8093 Zürich, Switzerland

²Université Grenoble Alpes, Inria, 38000 Grenoble, France

Functional causal models (fCMs) specify functional dependencies between random variables associated to the vertices of a graph. In directed acyclic graphs (DAGs), fCMs are well-understood: a unique probability distribution on the random variables can be easily specified, and a crucial graph-separation result called the *d*-separation theorem allows one to characterize conditional independences between the variables. However, fCMs on cyclic graphs pose challenges due to the absence of a systematic way to assign a unique probability distribution to the fCM's variables, the failure of the *d*-separation theorem, and lack of a generalization of this theorem that is applicable to all consistent cyclic fCMs. In this work, we develop a causal modeling framework applicable to all cyclic fCMs involving finite-cardinality variables, except inconsistent ones admitting no solutions. Our probability rule assigns a unique distribution even to non-uniquely solvable cyclic fCMs and reduces to the known rule for uniquely solvable fCMs. We identify a class of fCMs, called averagely uniquely solvable, that we show to be the largest class where the probabilities admit a Markov factorization. Furthermore, we introduce a new graph-separation property, *p*-separation, and prove this to be sound and complete for all consistent finite-cardinality cyclic fCMs while recovering the *d*-separation theorem for DAGs. These results are obtained by considering classical post-selected teleportation protocols inspired by analogous protocols in quantum information theory. We discuss further avenues for exploration, linking in particular problems in cyclic fCMs and in quantum causality.
# Contents

<table><tr><td>1</td><td>Introduction</td><td>3</td></tr><tr><td>2</td><td>Functional causal models</td><td>5</td></tr><tr><td>3</td><td>Mapping cyclic to acyclic functional models with post-selection</td><td>8</td></tr><tr><td>3.1</td><td>Classical post-selected teleportation</td><td>8</td></tr><tr><td>3.2</td><td>Family of acyclic functional models from a cyclic functional model</td><td>11</td></tr><tr><td>3.3</td><td>General probability rule for cyclic functional causal models</td><td>13</td></tr><tr><td>3.4</td><td>Examples of cyclic functional causal models</td><td>14</td></tr><tr><td>4</td><td>A sound and complete graph-separation property for cyclic functional models</td><td>17</td></tr><tr><td>4.1</td><td>Review of d-separation</td><td>18</td></tr><tr><td>4.2</td><td>Failure of d-separation in cyclic graphs</td><td>19</td></tr><tr><td>4.3</td><td>Introducing p-separation</td><td>21</td></tr><tr><td>4.4</td><td>Examples: p-separation in acyclic and cyclic graphs</td><td>22</td></tr><tr><td>4.5</td><td>Links to σ-separation</td><td>24</td></tr><tr><td>5</td><td>Solvability and related properties of cyclic functional models</td><td>26</td></tr><tr><td>5.1</td><td>Number of solutions and consistency</td><td>26</td></tr><tr><td>5.2</td><td>Examples on solvability</td><td>27</td></tr><tr><td>5.3</td><td>Linking Markov factorization and average unique solvability</td><td>28</td></tr><tr><td>6</td><td>Discussion and outlook</td><td>30</td></tr><tr><td>A</td><td>Proofs of section 3</td><td>37</td></tr><tr><td>B</td><td>Proofs of section 4</td><td>41</td></tr><tr><td>C</td><td>Proofs of section 5</td><td>48</td></tr></table>
# 1 Introduction

Providing causal explanations for observable correlations and understanding how causal relations constrain possible observations are fundamental across scientific disciplines. To achieve this goal, the framework of causal models was formulated for rigorously connecting cause-effect relations and observable data between random variables. Originating in the context of classical statistics, this formalism has found diverse applications in data-driven fields such as machine learning, economics, biological systems and medical trials [RCLH21, KH11, Pea09, Spi05, PL14, AHK20, LKK21].

Classical causal modeling frameworks involve a representation through directed graphs, whose vertices are associated with random variables and edges with causal relations, and incorporate causal mechanisms, such as functional dependencies between variables. More specifically, these are called *functional causal models* (fCMs), as well as *structural equation/causal models*.<fnref n="1" /> The majority of the causal modeling literature focuses on *acyclic* graphs, where there exists a well-defined probability rule to evaluate correlations over observed variables for all causal mechanisms and crucial graph-theoretic properties, such as the *d*-separation theorem [VP90, GVP90, Pea09], hold. This theorem is a cornerstone for causal discovery and inference methods as it allows to tightly relate observed conditional independences to the connectivity of the causal graph.

However, these results no longer hold for classical causal models on *cyclic* graphs, which are important to consider to effectively describe physical processes involving feedback [PD96, FM17, BFPM21] and to study informational models for exotic solutions of general relativity involving causal loops [Sto38, G49, MM67, Deu91, LMGP$^{+11a}$, LMGP$^{+11b}$]. Existing cyclic causal modeling frameworks consider the probability distribution associated with a causal model to be well defined only for a restricted class of models where the functional dependences admit unique solutions (uniquely solvable models). Moreover, it is known that for cyclic graphs, even when restricting to the class of uniquely solvable models involving finite-cardinality variables, the *d*-separation theorem fails [Nea00].

Studying the limits of *d*-separation and identifying alternative graph-separation properties that hold in the cyclic case has emerged as an active research area in classical causal modeling and there has been significant progress in understanding this from different (stronger) unique solvability properties [FM17, BFPM21]. Notably, the concept of *σ*-separation was introduced in [FM17] and shown to be sound and complete in a subclass of uniquely solvable models known as modular structural equation models, which have no constraint on the cardinality or discreteness of the variables involved. However, to our knowledge, a general graph-separation property that applies to all (including non-unique solvable) consistent causal models is lacking, even in the case of finite-cardinality variables. This is complicated by the fact that existing methods do not uniquely fix the probability distribution of a classical causal model in non-unique solvable models.

In this work, we address both the problems of fixing the observed probability distribution and of identifying a graph-separation property for all consistent classical cyclic causal models involving finite-cardinality variables. Our approach reveals connections between problems in classical functional causal models and various results in the quantum information community, which we hope will serve as an invitation for collaboration between the communities. We summarize the main contributions below.

<footnote n="1">¹We refer to these as classical causal modeling frameworks to distinguish them from quantum causal modeling frameworks (e.g., [HLP14, CS16, BLO20]) where causal mechanisms are linked to quantum channels on quantum systems. This paper will focus on classical causal models, while our accompanying paper [FGV25] develops a similar framework for the quantum case.</footnote>
1. **Framework for cyclic classical models:** We develop a framework for classical cyclic causal models (cyclic fCMs) analogous to, yet independent of, a framework for quantum cyclic causal models introduced in our companion paper [FGV25]. This framework encompasses all classical causal models definable on discrete variables of finite cardinality, excluding only the most pathological ones where the functional dependencies admit no solutions.

2. **Probability rule:** We construct a method for uniquely fixing the probability distribution for all causal models in our framework, which recovers the previously known probability rule for uniquely solvable models. In [VC22b] a method for computing the probability distribution was suggested for one specific non-unique solvable cyclic causal model involved in demonstrating that the relativistic principle of no superluminal communication does not forbid causal loops in (1+1)-Minkowski space-time. Our probability rule also recovers this case and provides a generalization of the method suggested in [VC22b].

3. **A graph-separation property for cyclic fCMs inspired by quantum teleportation:** We introduce a novel graph-separation property for cyclic fCMs, called *p*-separation. We prove that *p*-separation is sound and complete for all fCMs in our framework, and reduces to *d*-separation in the acyclic case. To our knowledge, this is the first sound and complete graph-separation property known for non-unique solvable fCMs over finite-cardinality variables. This is achieved by mapping any cyclic fCM on finite-cardinality variables to an acyclic causal model involving post-selection. This mapping introduces the concept of a classical post-selected teleportation protocol, inspired by the quantum teleportation protocol [BBC$^{+93}$] that is a key concept in the quantum information community.

4. **On correlation gaps between graph-separation properties and finite vs infinite cardinality variables:** We compare *p*-separation introduced here with *σ*-separation [FM17], and propose a new direction for future research on characterizing correlation gaps between graph-separation properties: for a given graph *G*, and two graph-separation properties that imply distinct sets of conditional independences on correlations, is it possible to witness this gap through a class of causal models on *G*? In particular, our results indicate that there exists a graph within which no gap between *d* and *σ* separation can be witnessed for any causal model in our framework. This suggests that infinite-cardinality or continuous variables would be necessary to witness the gap, and indeed there exist such examples of continuous variable models on this graph [FM17, FM18]. More generally, this motivates exploration of correlation gaps between finite vs infinite cardinality fCMs on a given cyclic causal structure, analogous to the highly studied problem of certifying correlation gaps between classical and quantum correlations in an acyclic causal structure (of which the fundamental Bell's theorem [Bel64] of quantum mechanics is an instance).

5. **Solvability properties:** We analyze solvability properties of cyclic fCMs, linking the number and existence of solutions to conditions on post-selection success probability. We identify a class of models satisfying a property called average unique solvability — a strict superset of uniquely solvable models — and show that this property is necessary and sufficient for recovering the usual probability rule based on Markov factorization. Our findings connect cyclic functional causal models, studied in the statistics community, with classical processes without definite causal order
[BW16b], originating in the quantum information community. We note striking similarities between the solvability properties of these models and results [BW16a] on the fixed points of classical processes.

For a brief overview of our framework and probability rule, as well as an introduction to our new graph-separation property, p-separation, we recommend referring to the example in section 3.4 and section 4.3, respectively.

**Notation.** We denote with $G = (V, E)$ a directed graph where each edge $e = (v_1, v_2) \in E$ is an ordered pair of two vertices $v_1, v_2 \in V$. We shall always assume, for convenience, that the set of vertices $V$ is equipped with a preferred order, such that we can write $V = \{v_1, \dots, v_n\}$ where $n = |V|$. The incoming and outgoing edges to a vertex $v \in V$ are denoted

$$ \mathrm{In}(v) = \{e \in E \mid \exists v' \in V : e = (v', v)\}, \quad (1a) $$

$$ \mathrm{Out}(v) = \{e \in E \mid \exists v' \in V : e = (v, v')\}, \quad (1b) $$

while the parents and children of a vertex $v \in V$ are denoted

$$ \mathrm{Pa}(v) = \{v' \in V \mid (v', v) \in E\}, \quad (2a) $$

$$ \mathrm{Ch}(v) = \{v' \in V \mid (v, v') \in E\}. \quad (2b) $$

Given a graph $G = (V, E)$, we say that a vertex $v \in V$ is exogenous if the set $\mathrm{Pa}(v)$ is empty. Otherwise, $v$ is said to be endogenous. We define the sets

$$ V_{\mathrm{ex}} = \{v \in V : \mathrm{Pa}(v) = \emptyset\} \quad \text{and} \quad V_{\mathrm{end}} = V \setminus V_{\mathrm{ex}}, \quad (3) $$

of exogenous and endogenous vertices of a graph. We represent directed graphs using diagrams where vertices are denoted as rectangles $v$ and edges as directed arrows $\rightarrow$.

## 2 Functional causal models

Here we review functional causal models, which are also referred to as structural causal models. While functional causal models are generally defined for variables taking values from a continuous set, here we restrict our definition to functional models over finite-cardinality variables as this is the relevant case for our results. For brevity, we will refer to this subclass of functional models as functional models instead of finite functional models, and denote them as fCm.

**Definition 1 (Finite functional causal model).** Given a directed graph $G = (V, E)$, a finite functional model (fCm$_G$) is given by associating the following specifications to each vertex $v \in V$:

1. A random variable $X_v$ taking values $x_v$ from a non-empty finite set $X_v$. We will use a notation where if $V' \subseteq V$ is a non-empty subset of vertices,

$$ \mathcal{X}_{V'} = \prod_{v \in V'} \mathcal{X}_v \quad (4) $$

where $\prod$ here denotes the Cartesian product.

2. An error random variable $U_v$ taking values $u_v$ from a finite set $U_v$, distributed as $p^v : U_v \mapsto [0, 1]$.
### 3. A function $f^v : \mathcal{X}_{Pa(v)} \times \mathcal{U}_v \to \mathcal{X}_v$.

One can think of functional models as assigning to each vertex $v \in V$ a value from the set $\mathcal{X}_v$. The value assignment on a vertex, $v \in V$, depends stochastically on the value assignments of its parents through the functional dependency associated to it, $f^v$. The stochastic character of such dependency is given by error variables associated to each vertex. In other words, the value $x_v \in \mathcal{X}_v$ that we associate to the vertex $v$, depends deterministically on the values $x_{Pa(v)} = \{x_{v'} \in \mathcal{X}_{v'}\}_{v' \in Pa(v)}$ and $u_v \in \mathcal{U}_v$ through $x_v = f^v(x_{Pa(v)}, u_v)$, by averaging on $u_v \in \mathcal{U}_v$ we obtain the stochastic dependency on $x_{Pa(v)}$ only.

Given a functional model on a graph, a well-defined probability distribution over the values of the vertices has to be defined. In the special case of functional models on acyclic graphs, the probability rule is given as follows. Note that this definition is standard in the literature [Pea09, Spi05]$^2$.

**Definition 2** (Probability distribution of an acyclic functional model). Consider a functional model $f\mathfrak{C}m_G$ on an acyclic graph $G = (V, E)$ and a global observed event $x := \{x_v \in \mathcal{X}_v\}_{v \in V}$. The probability $\text{Pr}_{acyc}(x)_G \in [0, 1]$ is defined as

$$ \text{Pr}_{acyc}(x)_G = \sum_u \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(x_{Pa(v)}, u_v)}, \quad (5) $$

where the sum $\sum_u$ runs over $u = \{u_v \in \mathcal{U}_v\}_{v \in V}$.

If some vertices are unobserved, the probability distribution over the remaining ones is obtained though marginalising the distribution in definition 2 over the unobserved variables.

Notice that the above probability rule can be equivalently expressed as

$$ \text{Pr}_{acyc}(x)_G = \prod_{v \in V} \text{Pr}^{(v)}(x_v | \text{Pa}(x_v))_G, \quad (6) $$

where $\text{Pr}^{(v)}(x_v|\text{Pa}(x_v))_G = \sum_{u_v} p^v(u_v) \delta_{x_v, f^v(x_{Pa(v)}, u_v)}$ is the conditional probability distribution of the variable $X^v$ conditioned on its parent variables $\text{Pa}(X^v)$ in $f\mathfrak{C}m_G$.

**Remark.** Definition 1 associates to each vertex an error random variable to account for stochastic dependencies. In many of the examples treated below, we consider deterministic dependencies, which amount to associating functions that do not depend on the error variable. In this case, we omit the error variables from the definition of the functional model and in the probability rule. In addition, for an exogenous vertex in $G$, $v \in V_{ex}$, such that $\mathcal{X}_v = \mathcal{U}_v$ and $f^v(u_v) = u_v$, the variable associated to $v$, $X^v$, is distributed as the error variable $U_v$.

Thus, in the special case where all endogenous vertices depend deterministically on their parents and all associations to exogenous vertices satisfy $\mathcal{X}_v = \mathcal{U}_v$ and $f^v(u_v) = u_v$, the probability rule can be written as

$$ \text{Pr}_{acyc}(x)_G = \prod_{v \in V_{\text{ex}}} p^v(x_v) \prod_{w \in V_{\text{end}}} \delta_{x_w, f^w(x_{Pa(w)})}. \quad (7) $$

<footnote>$^2$This probability rule for acyclic functional models is well-defined also in the infinite-cardinality or continuous variable case.</footnote>
distribution $\mathcal{P}$ on $A$ and $B$ such that $\mathcal{P}(a = b) = 1$, i.e., the two variables are equal with certainty. This corresponds to a distribution of the form $\mathcal{P}(a, b) = p(a)\delta_{a,b}$, for an arbitrary distribution $\{p(a)\}_{a \in \mathcal{X}}$. Thus, in the non-uniquely solvable case, the distribution is not uniquely defined.

Our first goal for the next sections is to solve this ambiguity and give a method to define a unique probability distribution over the vertices of discrete functional models on any cyclic graph. Based on this, we will develop our new graph-separation property, *p*-separation.

# 3 Mapping cyclic to acyclic functional models with post-selection

In order to define probabilities for functional models on arbitrary cyclic graphs, we construct a mapping from cyclic models to acyclic ones with post-selection. The mapping is inspired by a quantum protocol which is well-known in quantum mechanics and information theory, namely the *quantum teleportation protocol* [BBC$^{+}$93]. This protocol allows a party to transmit an arbitrary quantum state to another party using only quantum correlations and classical communication. If we introduce post-selection, classical communication is no longer necessary, and in this case, we call the protocol *post-selected teleportation* [LMGP$^{+}$11a, LMGP$^{+}$11b].

Here, we construct a classical analogue of the (post-selected) teleportation protocol and define the desired mapping. The mapping and probability rule follow the same ideas of [FGV25], where we defined the probability rule for *quantum* cyclic causal models exploiting post-selected teleportation.

## 3.1 Classical post-selected teleportation

Consider two binary random variables, $A$ and $C$, taking values from the same alphabet $\{0,1\} = \mathcal{X}_A = \mathcal{X}_C$, and let $p^A$ be an arbitrary distribution on $A$. Our goal is to construct a protocol which, for any distribution $p^A$, allows us to obtain the same distribution on $C$ as though there was an identity channel between the variables $A$ and $C$ that “teleports” $A$'s distribution to $C$. Let us consider the following: take $C$ to be uniformly distributed and measure whether $A$ and $C$ are equal, if not apply a bit flip correction to $C$. For clarity let us denote with $C'$ the variable $C$ after the correction (which is trivial if $A$ and $C$ are equal) is applied. We can achieve this as follows. First we represent this protocol using the graph$^4$

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

and associate $p^A$ to $A$, $p^C(c) = 1/2$ to $C$, the function $f^T(a, c) = \delta_{a,c}$ to $T$ and the function $f^{C'}(c, t) = c \oplus t \oplus 1$ to $C'$, for all $a, c \in \mathcal{X}$ and $t \in \{0,1\}$. In this example, we consider the error variables as described in the remark of section 2. The distribution of $C'$ and $T$ can

<footnote>$^4$This graph mimics the structure of the quantum teleportation protocol [BBC$^{+}$93].</footnote>
be evaluated using definition 2 and the fact that $\delta_{t,\delta_{a,c}} = \delta_{t,a \oplus c \oplus 1}$:

$$ \begin{aligned} \mathrm{Pr}_{\mathrm{acyc}}(c', t) &= \sum_{a,c} p^A(a)p^C(c)\delta_{t,a \oplus c \oplus 1}\delta_{c',c \oplus t \oplus 1} \\ &= \frac{1}{2}\sum_a p^A(a)\delta_{a,c'}\sum_c \delta_{c' \oplus t,c} \\ &= \frac{1}{2}\sum_a p^A(a)\delta_{a,c'} = \frac{1}{2}p^A(c'). \end{aligned} \quad (14) $$

Hence, independently of $t$ the distribution on $C'$ equals the initial and unknown distribution on $A$ up to a constant factor. In particular, if we only consider the instances where $A$ and $C$ take equal values, i.e., $t = 1$, no correction on $C$ is needed and the function from $C$ to $C'$ acts as an identity channel, $c' = f^{C'}(c, t = 1) = c$ for all $c$. Thus, if we post-select on $t = 1$, the vertex $C'$ is not necessary and we can represent the post-selected protocol as

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

where we denoted with $\mathcal{L}$ the post-selected vertex. In this case, we have $\mathrm{Pr}_{\mathrm{acyc}}(c|t = 1) = p^A(c)$ as desired. Since this holds for any distribution on $p^A$, we can identify this structure with an identity channel:

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

where the equivalence has to be understood at the level of conditional probabilities, conditioned on the event $t = 1$. Motivated by such example, we define in more generality a classical post-selected teleportation protocol.

**Definition 3** (Classical post-selected teleportation protocol). Let $\mathcal{X}_A = \mathcal{X}_C$ and $\mathcal{X}_B$ be finite sets. A classical post-selected teleportation protocol consists of a triple $(f, \mathcal{P}_B, \mathcal{P}_C)$ where $f: \mathcal{X}_A \times \mathcal{X}_B \times \mathcal{X}_C \to \{0,1\}$ is a function and $\mathcal{P}_i: \mathcal{X}_i \to [0,1]$ for $i = B, C$ are probability distributions, such that for all probability distribution $p^A: \mathcal{X}_A \to [0,1]$, it holds that

$$ \sum_{\substack{a \in \mathcal{X}_A \\ b \in \mathcal{X}_B}} p^A(a) \delta_{f(a,b,c),1} \mathcal{P}_B(b) \mathcal{P}_C(c) = p_{TP} p^A(c) \quad (17) $$

for all $c \in \mathcal{X}_C$, where $p_{TP} \in (0,1]$ is the success probability of the post-selected teleportation protocol.

In contrast to the example presented above, general classical post-selected teleportation protocols can be implemented using a non-deterministic function on $A$ and $C$ to post-select (where $B$ plays the role of an error variable for the post-selection vertex $T$). The following results are proven in appendix A.

**Lemma 4.** The success probability of a classical teleportation protocol, $p_{TP}$, of definition 3 is independent of the probability distribution $p^A$ being teleported.

**Lemma 5.** Consider a classical teleportation protocol defined by the pair $(f, \mathcal{P}_B, \mathcal{P}_C)$. Then, it holds:

$$ \sum_{b \in \mathcal{X}_B} \delta_{f(a,b,c),1} \mathcal{P}_B(b) \mathcal{P}_C(c) = p_{TP} \delta_{a,c}. \quad (18) $$
## 3.2 Family of acyclic functional models from a cyclic functional model

Using classical post-selected teleportation protocols, we construct a family of acyclic functional models from a given cyclic functional model. First, we define the family of acyclic graphs underlying these functional models. The proofs of the results in this section are provided in appendix A.

**Definition 7** (Family of acyclic classical teleportation graphs $G_{TP}(G)$). Given a directed graph $G = (V, E)$, we define an associated family $G_{TP}(G)$ of acyclic graphs, where each element $G_{TP} \in G_{TP}(G)$ is obtained from the graph $G$ as follows.

1. Choose any subset of vertices $V_S(G_{TP}) \subseteq V$, such that the subgraph $G' = (V', E')$ of $G$ with $V' = V$ and $E' = E \setminus (\cup_{v \in V_S(G_{TP})} \text{Out}(v))$ is acyclic. We refer to $V_S(G_{TP})$ as the split vertices of $G_{TP}$.

2. The vertices $V_{TP}$ of $G_{TP}$ consist of the vertices $V$ of the original graph $G$ together with new vertices $R_v, T_v$ for each split vertex $v \in V_S(G_{TP})$, i.e.,

$$V_{TP} = V \cup \{R_v\}_{v \in V_S(G_{TP})} \cup \{T_v\}_{v \in V_S(G_{TP})}. \quad (24)$$

3. The edges $E_{TP}$ of $G_{TP}$ consist of the edges $E'$ of the subgraph $G'$ together with the following new edges:

$$E_{TP} = E' \cup \{(v, T_v)\}_{v \in V_S(G_{TP})} \cup \{(R_v, T_v)\}_{v \in V_S(G_{TP})} \\ \cup \{(R_v, v')\}_{v \in V_S(G_{TP}), v' \in \text{Ch}(v)_G}, \quad (25)$$

where $\text{Ch}(v)_G$ refers to the children vertices of $v$ in the graph $G$.

For each $v \in V_S(G_{TP})$, we refer to the vertices $R_v$ and $T_v$ as pre- and post-selection vertices respectively and depict them with distinct vertex styles $T_v$ and $R_v$, as these will play a special role in our framework. This construction makes $G_{TP}$ identical to $G$ up to replacing all vertices $v \in V_S(G_{TP})$ with the following structure

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

Each element of the family $G_{TP} \in G_{TP}(G)$ is called a classical teleportation graph. The set of all pre- and post-selection vertices in $G_{TP}$ are denoted as $V_{\text{pre}} = \{R_v\}_{v \in V_S(G_{TP})}$ and $V_{\text{post}} = \{T_v\}_{v \in V_S(G_{TP})}$.

The following lemma, proven in appendix A, shows that classical teleportation graphs constructed as above are indeed acyclic.

**Lemma 8** (Acyclicity of classical teleportation graphs). Given a directed graph $G$, each classical teleportation graph $G_{TP} \in G_{TP}(G)$ is acyclic.

The next step of the mapping of cyclic functional models to acyclic functional models with post-selection involves defining functional models on classical teleportation graphs.
**Definition 9** (Family of functional models on acyclic classical teleportation graphs). Given a functional model on a directed graph $G = (V, E)$, $f\mathbf{C}m_G$, we can construct a family of functional models by defining a functional causal model, $f\mathbf{C}m_{G_{TP}}$, on each acyclic classical teleportation graph $G_{TP} \in \mathbb{G}_{TP}(G)$ (definition 7), as follows:

1. Using the same notation as in definition 7, for each split vertex $v \in V_S(G_{TP})$ of $G_{TP}$ the functional model $f\mathbf{C}m_{G_{TP}}$, has the following specifications:

(a) To the post-selection vertex $T_v$, we associate a random variable taking values from $\mathcal{X}_{T_v} = \{0, 1\}$, an error variable $U_{T_v}$ with distribution $p^{T_v}$ and a function $f^{T_v}$.

(b) To the pre-selection vertex $R_v$, we associate a random variable taking values from $\mathcal{X}_{R_v} = \mathcal{X}_v$, an error variable $U_{R_v}$ with distribution $p^{R_v}$ and a function $f^{R_v}(u_{R_v}) = u_{R_v}^6$.

(c) The probability distributions $p^{R_v}$, $p^{T_v}$ together with the function $f^{T_v}$ form a classical teleportation protocol (definition 3).

2. For each vertex present in both $G$ and $G_{TP}$, i.e., each vertex except the pre- and post-selection vertices, the assigned finite sets, error variables and functional dependencies are the same in $f\mathbf{C}m_{G_{TP}}$ and $f\mathbf{C}m_G$, where for all $v \in V_S(G_{TP})$ the corresponding preselection vertex $R_v$ plays the role of the original vertex $v$ in the inputs of the relevant functions, i.e., $f^{v'}$ for $v' \in \text{Ch}(v)_G$.

We will refer to functional models in this family as classical teleportation functional models.

Any classical teleportation model $f\mathbf{C}m_{G_{TP}}$ constructed according to definition 9 is defined over an acyclic graph, thus, we can compute its probabilities using the acyclic probability rule of definition 2. Denoting $V_{\text{post}}$ and $V_{\text{pre}}$ as the set of all pre- and post-selection vertices of $G_{TP}$, its total set of vertices is $V \cup V_{\text{pre}} \cup V_{\text{post}}$. Therefore, by applying the acyclic probability rule of definition 2 to $f\mathbf{C}m_{G_{TP}}$, we can compute

$$ \mathrm{Pr}_{\mathrm{acyc}}(x, r, \{t_T = 1\}_{T \in V_{\mathrm{post}}})_{G_{\mathrm{TP}}}, \qquad (27) $$

where $x = \{x_v\}_{v \in V}$ and $r = \{r_R\}_{R \in V_{\text{pre}}}$. From this probability we can define the probability of successful post-selection.

**Definition 10** (Post-selection success probability.). Consider a functional model on a directed graph $G$ and a functional model of the family in definition 9 with associated graph $G_{TP}$. We define the probability of successful post-selection of the classical teleportation functional model as

$$ p_s := \mathrm{Pr}_{\mathrm{acyc}}(\{t_T = 1\}_{T \in V_{\mathrm{post}}})_{G_{\mathrm{TP}}} = \sum_{x,r} \mathrm{Pr}_{\mathrm{acyc}}(x, r, \{t_T = 1\}_{T \in V_{\mathrm{post}}})_{G_{\mathrm{TP}}}, \qquad (28) $$

where the summation is performed over $x = \{x_v \in \mathcal{X}_v\}_{v \in V}$ and $r = \{r_R \in \mathcal{X}_R\}_{R \in V_{\text{pre}}}$.

Since the preselection vertices act as copies of the split vertices, we marginalize over them to obtain

$$ \mathrm{Pr}_{\mathrm{acyc}}(x, \{t_T = 1\}_{T \in V_{\mathrm{post}}} )_{G_{\mathrm{TP}}} = \sum_{r} \mathrm{Pr}_{\mathrm{acyc}}(x, r, \{t_T = 1\}_{T \in V_{\mathrm{post}}} )_{G_{\mathrm{TP}}}, \qquad (29) $$

<footnote n="6">⁶As discussed in the remark of section 2, this is equivalent to directly considering the variable $R_v$ as having distribution $p^{R_v}$.</footnote>
and focus on the conditional probability

$$ \mathrm{Pr}_{\mathrm{acyc}}(x|\{t_T = 1\}_{T \in V_{\mathrm{post}}})_{G_{\mathrm{TP}}} = \frac{\mathrm{Pr}_{\mathrm{acyc}}(x, \{t_T = 1\}_{T \in V_{\mathrm{post}}})_{G_{\mathrm{TP}}}}{p_s} \quad (30) $$

which will be the probability of interest in our framework. The following proposition shows that this is independent of the choice of teleportation graph $G_{TP} \in \mathbb{G}_{TP}(G)$.

**Proposition 11** (Equivalent probabilities from different classical teleportation graphs). Let $f\mathbf{Cm}_G$ be a functional model on a directed graph $G$. Consider any $G_1, G_2 \in \mathbb{G}_{TP}(G)$, and for $i \in \{1, 2\}$, let $f\mathbf{Cm}_{G_i}$ be a causal model on the teleportation graph $G_i$ constructed according to definition 9. Denoting the set of all post-selection vertices of $G_1, G_2$ as $V_{\mathrm{post}}^1$ and $V_{\mathrm{post}}^2$ respectively, we have

$$ \mathrm{Pr}_{\mathrm{acyc}}(x|\{t_T = 1\}_{T \in V_{\mathrm{post}}^1})_{G_1} = \mathrm{Pr}_{\mathrm{acyc}}(x|\{t_T = 1\}_{T \in V_{\mathrm{post}}^2})_{G_2}, \quad (31) $$

for all joint observed events $x = \{x_v \in \mathcal{X}_v\}_{v \in V}$.

The above proposition is proven in appendix A.

### 3.3 General probability rule for cyclic functional causal models

In section 3.2, we have constructed a family of acyclic functional models associated with a given, potentially cyclic, functional model (definition 9). We have proven that the acyclic distribution conditioned on successful post-selection is independent of which functional model we choose in this family. Here, we use these results to define a probability rule for the cyclic functional model underlying the family. The proofs of the results presented in this section can be found in appendix A.

**Definition 12** (Probability of a cyclic functional models). Consider a functional model on a graph $G$. Let $G_{TP} \in \mathbb{G}_{TP}(G)$ be a classical teleportation graph with associated functional model $f\mathbf{Cm}_{G_{TP}}$ derived from $f\mathbf{Cm}_G$ according to definition 9 and let $p_s$ be the probability of successful post-selection as in definition 10. If $p_s > 0$, the probability of the joint observed event $x = \{x_v \in \mathcal{X}_v\}_{v \in V}$ in $f\mathbf{Cm}_G$ is defined as

$$ \mathrm{Pr}(x)_G := \mathrm{Pr}_{\mathrm{acyc}}(x|\{t_T = 1\}_{T \in V_{\mathrm{post}}} )_{G_{\mathrm{TP}}} = \frac{\mathrm{Pr}_{\mathrm{acyc}}(x, \{t_T = 1\}_{T \in V_{\mathrm{post}}} )_{G_{\mathrm{TP}}}}{p_s}. \quad (32) $$

If $p_s = 0$, we say that the model is inconsistent and the probabilities $\mathrm{Pr}(x)_G$ are undefined.

In the above definition of $\mathrm{Pr}$, there are two choices involved. One first needs to choose a teleportation graph $G_{TP} \in \mathbb{G}_{TP}(G)$, and secondly, once $G_{TP}$ is fixed, there is still freedom in choosing a specific implementation of classical post-selected teleportation protocol for each pair of pre- and post-selection vertices in $G_{TP}$. We have already shown in proposition 11 that the definition above is independent of the first choice. In the following, we show that it is also independent of the second choice.

**Proposition 13** (Alternative formulation of the probability rule). Consider a functional model $f\mathbf{Cm}_G$ on a directed graph $G = (V, E)$. If the model is not inconsistent, an alternative expression for the probability rule in definition 2 is given by

$$ \mathrm{Pr}(x)_G = \frac{\sum_u \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(x_{\mathrm{Pa}(v)}, u_v)}}{\sum_y \sum_u \prod_{v \in V} p^v(u_v) \delta_{y_v, f^v(y_{\mathrm{Pa}(v)}, u_v)}} \quad (33) $$

where we have defined the global event $x = \{x_v \in \mathcal{X}_v\}_{v \in V}$, the sum $\sum_y$ runs over all $y = \{y_v \in \mathcal{X}_v\}_{v \in V}$ and $\sum_u$ over $u = \{u_v \in \mathcal{U}_v\}_{v \in V}$.
The proof of the above proposition is given in appendix A. Observing that by definition the success probability of a post-selected teleportation protocol is strictly greater than zero, the following corollary immediately follows from proposition 13.

**Corollary 14 (Equivalent probabilities from different implementations).** Consider a functional model $f\mathbf{Cm}_G$ on a directed graph $G$ and any classical teleportation model in the family of classical teleportation functional models derived from $f\mathbf{Cm}_G$ according to definition 9. It holds that whether or not the probabilities $\text{Pr}(x)_G$ of $f\mathbf{Cm}_G$ (given by definition 12) are defined and the values they take (if they are defined) do not depend on the choices of the post-selected teleportation protocols (definition 3) one makes in the construction of $f\mathbf{Cm}_{G_{TP}}$ from $f\mathbf{Cm}_G$ (definition 9).

Proposition 13 highlights the way our method picks a unique probability rule even for non-uniquely solvable models. For instance, consider the model introduced in section 2 on the graph

$$ G = \boxed{A} \quad \boxed{B}, \qquad (34) $$

where $\mathcal{X} = \mathcal{X}_A = \mathcal{X}_B$, $f^A(b) = b$ and $f^B(a) = a$ for all $a, b \in \mathcal{X}$. These functional dependencies are deterministic, thus it is not necessary to specify error variables (see the remark of section 2 for more details). As we showed in section 2, this functional model is not uniquely solvable (unless the set $\mathcal{X}$ has trivial cardinality) and in literature any distribution $\mathcal{P}$ such that $\mathcal{P}(A = B) = 1$ is considered valid. The probability rule definition 12 evaluated using proposition 13 gives

$$ \text{Pr}(a, b)_G = \frac{\delta_{a,b}\delta_{b,a}}{\sum_{a',b'} \delta_{a',b'}\delta_{b',a'}} = \frac{\delta_{a,b}}{|\mathcal{X}|}. \qquad (35) $$

Notice that the probability rule of definition 12 associates a uniform distribution to all allowed solutions of the functional model in this example. This is not a consequence of using as classical teleportation protocol the uniform prior one (definition 6), as we have shown that the probability rule does not depend on which classical teleportation protocol one chooses (corollary 14). In principle, other classical teleportation protocols which are associated with a non-uniform prior on the pre-selection vertices could be considered, which would yield the same probability.

## 3.4 Examples of cyclic functional causal models

**Detailed example illustrating our framework and probability rule.** Here, we illustrate through an example how to perform the mapping of a cyclic functional model to an acyclic one with post-selection, and evaluate the corresponding probability distribution in our framework. Consider the following cyclic graph:

$$ G = \boxed{v_3} \rightarrow \boxed{v_1} \rightarrow \boxed{v_2} \rightarrow \boxed{v_4}. \qquad (36) $$

A functional model on this graph is defined by associating finite sets $\mathcal{X}_i$ and error variables $U_i \in \mathcal{U}_i$ with distribution $p^i$ to each vertex $v_i$ for $i = 1, 2, 3, 4$, and functions $f^1(x_2, x_3, u_1)$ to $v_1$, $f^2(x_1, x_4, u_2)$ to $v_2$, $f^3(u_3)$ to $v_3$ and $f^4(u_4)$ to $v_4$ for all $x_i \in \mathcal{X}_i$ and $i = 1, 2, 3, 4$.
For simplicity, let the functions associated to endogenous nodes, $f^1$ and $f^2$, be independent on the error variables and $f^3(u_3) = u_3$, $f^4(u_4) = u_4$. In this case, we can simplify the probability rule as explained in the remark of section 2.

This functional model is mapped to an acyclic functional model with post-selection, where we can evaluate probabilities using the acyclic rule in definition 2. The probabilities of the acyclic model (conditioned on successful post-selection) are used to define the desired distribution of the cyclic functional model. Explicitly, the procedure is given by the following steps for this example:

1. Consider a subset of vertices $V_S(G_{TP})$ such that the subgraph $G'$ obtained from $G$ through removing all outgoing edges of vertices in $V_S(G_{TP})$ is acyclic, e.g., considering $V_S(G_{TP}) = \{v_2\}$ we have

$$G' = \vcenter{\hbox{\includegraphics[height=1.5cm]{graph.png}}} \qquad (37)$$

2. Construct a classical teleportation graph $G_{TP}$ by adding for each vertex $v \in V_S(G_{TP})$ the pre- and post-selection vertices of a classical post-selected teleportation protocol (definition 3 and definition 7), i.e.,

$$G_{TP} = \vcenter{\hbox{\includegraphics[height=3cm]{graph.png}}} \qquad (38)$$

3. Define a functional model on $G_{TP}$ by keeping the same associations of the original functional model to all vertices and edges that are preserved from $G$ to $G_{TP}$ and associating a teleportation protocol to the added vertices, e.g., to $R$ associate the set $\mathcal{X}_2$ and a uniform probability distribution $p^R(r) = 1/|\mathcal{X}_2|$ for all $r \in \mathcal{X}_2$ and to $T$ associate the set $\{0, 1\}$ and function $f^T(x_2, r) = \delta_{x_2, r}$ for all $x_2, r \in \mathcal{X}_2$.

4. Evaluate the probability of the functional model on the acyclic graph $G_{TP}$

$$\mathrm{Pr}_{\mathrm{acyc}}(\{x_i\}_{i=1}^4, r, t=1)_{G_{\mathrm{TP}}} = \frac{p^3(x_3)p^4(x_4)\delta_{x_1, f^1(r, x_3)}\delta_{x_2, f^2(x_1, x_4)}\delta_{x_2, r}}{|\mathcal{X}_2|}, \qquad (39)$$

consider $r$ unobserved, i.e., marginalize $r$,

$$\mathrm{Pr}_{\mathrm{acyc}}(\{x_i\}_{i=1}^4, t=1)_{G_{\mathrm{TP}}} = \frac{p^3(x_3)p^4(x_4)\delta_{x_1, f^1(x_2, x_3)}\delta_{x_2, f^2(x_1, x_4)}}{|\mathcal{X}_2|} \qquad (40)$$

and post-select on $t=1$

$$\mathrm{Pr}_{\mathrm{acyc}}(\{x_i\}_{i=1}^4|t=1)_{G_{\mathrm{TP}}} = \frac{\mathrm{Pr}_{\mathrm{acyc}}(\{x_i\}_{i=1}^4, t=1)_{G_{\mathrm{TP}}}}{\mathrm{Pr}_{\mathrm{acyc}}(t=1)_{G_{\mathrm{TP}}}} \qquad (41)$$
$$= \frac{p^3(x_3)p^4(x_4)\delta_{x_1,f^1(x_2,x_3)}\delta_{x_2,f^2(x_1,x_4)}}{\sum_{y_i} p^3(y_3)p^4(y_4)\delta_{y_1,f^1(y_2,y_3)}\delta_{y_2,f^2(y_1,y_4)}} \quad (42)$$

5. If $p_s = \mathrm{Pr}_{\mathrm{acyc}}(t = 1)_{G_{\mathrm{TP}}} > 0$, define the probability distribution in the functional model on the cyclic graph $G$ as the conditional probability in equation (41), i.e.,

$$\mathrm{Pr}(x_1, x_2, x_3, x_4)_G := \mathrm{Pr}_{\mathrm{acyc}}(\{x_i\}_{i=1}^4 | t = 1)_{G_{\mathrm{TP}}}. \quad (43)$$

If $p_s = 0$, we say that the model is inconsistent and the probabilities are undefined.

Now we give a specific functional model on $G$ (equation (36)) and evaluate the probability as above. Let us consider binary variables, i.e., $\mathcal{X}_i = \{0,1\}$, let $f^1(x_2, x_3) = x_3 \oplus x_2$ and $f^2(x_1, x_4) = x_1 \oplus x_4$, and consider arbitrary distributions $p^3$ and $p^4$. This model is not uniquely solvable (see section 5). Indeed, if $x_3 \neq x_4$ the model has no solutions, while if $x_3 = x_4$ it has 2 solutions each satisfying $x_2 = x_1 \oplus x_3$. From the joint distribution,

$$\mathrm{Pr}(x_1, x_2, x_3, x_4)_G = \frac{p^3(x_3)p^4(x_4)\delta_{x_1,x_2 \oplus x_3}\delta_{x_2,x_1 \oplus x_4}}{\mathcal{N}} = \frac{p^3(x_3)p^4(x_4)\delta_{x_1,x_2 \oplus x_3}\delta_{x_3,x_4}}{\mathcal{N}}, \quad (44)$$

where

$$\begin{aligned} \mathcal{N} &= \sum_{y_1, y_2, y_3, y_4} p^3(y_3)p^4(y_4)\delta_{y_1, y_2 \oplus y_3}\delta_{y_3, y_4} \\ &= \sum_{y_1, y_2} p^3(0)p^4(0)\delta_{y_1, y_2} + p^3(1)p^4(1)\delta_{y_1, y_2 \oplus 1} = 2(p^3(0)p^4(0) + p^3(1)p^4(1)), \end{aligned} \quad (45)$$

we can evaluate the conditional probability for the case were $x_3 = x_4 = 0$. Previous methods would suggest that any distributions with $x_1 = x_2$ and arbitrary weights on their value being 0 or 1 are allowed. Contrary to that, our method uniquely fixes the probability distribution to

$$\mathrm{Pr}(x_1, x_2|0, 0)_G = \frac{p^3(0)p^4(0)\delta_{x_1, x_2}}{p^3(0)p^4(0)\sum_{y_1, y_2} \delta_{y_1, y_2}} = \frac{\delta_{x_1, x_2}}{2}. \quad (46)$$

This is not a consequence of the specific teleportation protocol (definition 6) we chose, as any other protocol yields the same result (corollary 14).

**Example of [VC22b].** We now consider a particular functional model introduced in [VC22b] which does not admit unique solutions. The model was introduced to illustrate a result regarding the relativistic principles of no causal loops and no superluminal signalling in Minkowski space-time. Here, we are only interested in the properties and probability distribution of the underlying functional model and show that these are recovered in our framework. Consider the graph

$$G = \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.7, every node/.style={scale=0.7}] 
% Vertices
\node[circle, fill, inner sep=1.5pt] (A) at (0,0) {};
\node[circle, fill, inner sep=1.5pt] (B) at (2,0) {};
\node[circle, fill, inner sep=1.5pt] (C) at (0,2) {};
\node[circle, fill, inner sep=1.5pt] (D) at (0,0.5) {};
\node[circle, fill, inner sep=1.5pt] (E) at (2,0.5) {};
\node[circle, fill, inner sep=1.5pt] (F) at (2,2) {};

% Edges
\draw[->] (A) -- (B) node[left] {$\Lambda$};
\draw[->] (B) -- (C) node[right] {$C$};
\draw[->] (C) -- (D) node[right] {$\Lambda$};
\draw[->] (D) -- (E) node[left] {$A$};
\draw[->] (E) -- (F) node[right] {$B$};

% Labels
\node[above] at (A) {$A$};
\node[above] at (B) {$B$};
\node[above] at (C) {$C$};
\node[above] at (D) {$D$};
\node[above] at (E) {$E$};
\node[above] at (F) {$F$};

% Edges
\draw[->] (A) -- (D) node[left] {$\Lambda$};
\draw[->] (B) -- (E) node[right] {$\Lambda$};
\draw[->] (C) -- (F) node[right] {$\Lambda$};
\draw[->] (D) -- (F) node[right] {$\Lambda$};
\draw[->] (E) -- (F) node[right] {$\Lambda$};

\end{tikzpicture}, \quad (47)$$

where all variables are binary and the following deterministic functions are associated to the vertices: $a = f^A(\lambda) := \lambda$, $b = f^B(a, c) := a \oplus c$ and $c = f^C(\lambda, b) := \lambda \oplus b$ for all $a, b, c, \lambda \in \{0,1\}$, and let $p^A$ be the distribution of the exogenous vertex $\Lambda$ (here we have
embed finite-cardinality fCMs. Here, we present an alternative formulation of *p*-separation that is independent of the quantum formalism, and defined in terms of the classical causal modeling framework we have developed in this paper (section 3). The key difference lies in the mapping of cyclic to acyclic causal models with post-selection, which differs in the classical (here) vs the quantum framework ([FGV25]) as classical variables can be perfectly copied while arbitrary quantum states cannot, by virtue of the no-cloning theorem [WZ82, Die82]. However, in appendix C of [FGV25], we prove the equivalence between the two definitions for *p*-separation.

We begin in section 4.1 by reviewing the definition of *d*-separation (which is defined on acyclic and cyclic graphs) and the *d*-separation theorem in acyclic graphs. We then demonstrate in section 4.2 the failure of *d*-separation in cyclic scenarios. We introduce *p*-separation in section 4.3, using the framework of section 3, proving the soundness and completeness of *p*-separation and discussing its properties. We describe examples of applications of *p*-separation in section 4.4. Finally, we describe the relations between *p*-separation and *σ*-separation in section 4.5.

## 4.1 Review of *d*-separation

The concept of *d*-separation [Pea09, Spi05] is a graph-theoretic property defined for any directed graph by looking at the structure of paths between sets of vertices. Let us motivate *d*-separation by considering the following graphs:

Chain: $A \to C \to B$, (51)

Fork: $A \to C \to B$, (52)

Collider: $A \to C \to B$, (53)

For causal models on the chain and the fork, we would generally expect *A* and *B* to get correlated, through the (indirect) causal influence of *A* on *B* in the first case and through the common cause *C* in the second case. However, we would expect that *A* and *B* would become independent conditioned on *C* as *C* mediates the correlations between *A* and *B* in both cases. In the chain and fork, we would say *A* is *d*-connected to *B*, denoted $A \perp^d B$ while *A* is *d*-separated from *B* given *C*, denoted $A \perp^d B|C$. For the collider on the other hand, *A* and *B* have no prior causes and we would expect them to be uncorrelated and we would say $A \perp^d B$. However, conditioning on their common child *C* amounts to post-selection and can correlate *A* and *B*, i.e., they become *d*-connected conditioned on *C*, $A \perp^d B|C$. Further, if in the case of the collider, we had $C \to D$ as shown below, then we would also expect *A* and *B* to get correlated given *D* (as it is in the future of both), and expect $A \perp^d B|D$ also for descendants *D* of a collider *C*.

Collider with descendant: (54)

Although this intuition comes from thinking of the correlations, the following definitions are purely graph-theoretic. A subsequent theorem links this definition of *d*-separation to conditional independences in a causal model, which recovers the above intuition for these simple examples.

**Definition 15 (Blocked paths).** Let *G* be a directed graph in which $V_1$, $V_2$ and $V_3$ are disjoint sets of vertices, with $V_1$ and $V_2$ being non-empty. A path (not necessarily directed)
from $V_1$ to $V_2$ is said to be blocked by $V_3$ if it contains, for some vertices A and B in the path, either $A \to W \to B$ with $W \in V_3$, $A \leftarrow W \to B$ with $W \in V_3$ or $A \to W \leftarrow B$ such that neither the vertex W nor any descendant of W belongs to $V_3$.

**Definition 16 (d-separation).** Let G be a directed graph in which $V_1$, $V_2$ and $V_3$ are disjoint sets of vertices with $V_1$ and $V_2$ non-empty. $V_1$ and $V_2$ are d-separated by $V_3$ in G, denoted $(V_1 \perp^d V_2|V_3)_G$, if for every pair of vertices in $V_1$ and $V_2$ there is no path between them, or if every path from a vertex in $V_1$ to a vertex in $V_2$ is blocked by $V_3$. Otherwise, $V_1$ is said to be d-connected with $V_2$ given $V_3$, denoted as $(V_1 \not\perp^d V_2|V_3)_G$.

The concept of d-separation only involves graph properties and is independent on whether a functional model is defined on the graph. However, the d-separation theorem relates the graph property to conditional independencies of the probability distribution of a functional model on the graph. For a proof and further details on the theorems see [VP90, GVP90, Pea09].

**Definition 17 (Conditional independence).** Let V be a non-empty finite set, and let $\mathcal{P}(x)$ be a joint probability distribution over a set $X = \{X_v\}_{v \in V}$ of finite-cardinality random variables, whose values are denoted $x = \{x_v\}_{v \in V}$. Let $V_1$, $V_2$ and $V_3$ be three disjoint subsets of V, with $V_1$ and $V_2$ being non-empty. We denote the corresponding sets of random variables as $X_i = \{X_v\}_{v \in V_i}$ and the corresponding values as $x_i = \{x_v\}_{v \in V_i}$ for $i \in \{1, 2, 3\}$. We say that $X_1$ is conditionally independent of $X_2$ given $X_3$ and denote it as $(X_1 \perp X_2|X_3)_\mathcal{P}$ if, for all $x_1, x_2, x_3$, it holds that $\mathcal{P}(x_1|x_3)\mathcal{P}(x_2|x_3) = \mathcal{P}(x_1|x_3)$.

**Theorem 18 (d-separation theorem for acyclic graphs).** Consider a directed acyclic graph G and let $V_1$, $V_2$ and $V_3$ be any three disjoint sets of the vertices of G with $V_1$ and $V_2$ being non-empty. Then, the following holds:

(Soundness) For any functional model $f\mathfrak{Cm}_G$ on G, we have that d-separation between the vertex sets $V_i$ implies conditional independence for the corresponding sets of random variables $X_i := \{X_v\}_{v \in V_i}$ where $i \in \{1, 2, 3\}$, i.e.,

$$ (V_1 \perp^d V_2|V_3)_G \implies (X_1 \perp X_2|X_3)_{\mathrm{Pr}_{\mathrm{acycG}}}. \qquad (55) $$

(Completeness) If the d-connection $(V_1 \not\perp^d V_2|V_3)_G$ holds in G, then there exists a functional causal model $f\mathfrak{Cm}_G$ such that $(X_1 \not\perp X_2|X_3)_{\mathrm{Pr}_{\mathrm{acycG}}}$.

The above conditional (in)dependence statements are relative to the marginal $\mathrm{Pr}_{\mathrm{acyc}}(x_1, x_2, x_3)_G$ on $X_1 \cup X_2 \cup X_3$, where $x_i = \{x_v \in \mathcal{X}_v\}_{v \in V_i}$, of the observed distribution $\mathrm{Pr}_{\mathrm{acyc}}(x)_G$, where $x = \{x_v\}_{v \in V}$, in the functional model $f\mathfrak{Cm}_G$.

## 4.2 Failure of d-separation in cyclic graphs

The d-separation theorem (theorem 18) and, in particular, the soundness of d-separation are known to fail for functional models on cyclic graphs [Pea09, Nea00]. For instance, consider the following cyclic graph and augmented version:

$$ G = \begin{tikzpicture}[baseline={([yshift=-0.5em]current bounding box.center)}] 
    \node[circle, fill, inner sep=1.5pt] (v1) at (0,0) {};
    \node[circle, fill, inner sep=1.5pt] (v2) at (1,0) {};
    \node[circle, fill, inner sep=1.5pt] (v3) at (0.5,0.866) {};
    \node[circle, fill, inner sep=1.5pt] (v4) at (0.5,-0.866) {};
    \draw[->] (v1) -- (v2) node[left] {$v_1$};
    \draw[->] (v2) -- (v3) node[right] {$v_2$};
    \draw[->] (v3) -- (v4) node[right] {$v_3$};
    \draw[->] (v4) -- (v1) node[left] {$v_4$};
    \end{tikzpicture}. \qquad (56) $$

We have $(v_3 \perp^d v_4)_G$, thus, if the soundness of d-separation held true for cyclic models we would conclude that for any functional model on it, we must have the independence
$(X_3 \perp X_4)_{\mathrm{Pr}_G}$, where $X_i$ is the random variable associated to $v_i$. However, it is possible to construct a simple functional model where $x_3$ and $x_4$ must necessarily be correlated (and hence not independent).

For instance, consider the example in section 3.4. There we assumed that $\mathcal{X}_{v_i} = \{0, 1\}$ for all $i = 1, 2, 3, 4$, i.e., all vertices are associated to binary variables, and considered the following deterministic functional dependencies $x_1 = f^{v_1}(x_2, x_3) := x_2 \oplus x_3$ and $x_2 = f^{v_2}(x_1, x_4) := x_1 \oplus x_4$, i.e., both $x_1$ and $x_2$ are given by the sum modulo 2 of their parents. In addition, consider error variables $U_3$ and $U_4$ distributed as $p^3$ and $p^4$ and functions $f^3(u_3) = u_3$ and $f^4(u_4) = u_4$ associated respectively to $v_3$ and $v_4$. The probability distribution can be evaluated using proposition 13 and we obtain

$$ \mathrm{Pr}(x_3, x_4)_G = \mathcal{N}^{-1} \sum_{x_1, x_2} p^{v_3}(x_3) p^{v_4}(x_4) \delta_{x_1, x_2 \oplus x_3} \delta_{x_2, x_1 \oplus x_4} \quad (57) $$

$$ = \mathcal{N}^{-1} p^{v_3}(x_3) p^{v_4}(x_4) \delta_{x_3, x_4}, \quad (58) $$

where we defined $\mathcal{N} = \sum_{x_3, x_4} p^{v_3}(x_3) p^{v_4}(x_4) \delta_{x_3, x_4}$ for short (we assume here that $p^{v_3}$ and $p^{v_4}$ are such that $\mathcal{N} \neq 0$, in particular this would be the case if both correspond to the uniform distribution). Thus, $x_3$ and $x_4$ are perfectly correlated, since $\mathrm{Pr}(x_3, x_4)_G = 0$ whenever $x_3 \neq x_4$.

This example shows that $x_3$ and $x_4$ are correlated in the given fCM even though their associated vertices are $d$-separated in the graph. The reason for this lies on the fact that the loop between $v_1$ and $v_2$ effectively acts as a collider for $v_3$ and $v_4$. Conditioning on a collider can $d$-connect two variables which were $d$-separated before the conditioning. Here the collider is not explicitly conditioned upon in the original cyclic graph, however, the logical consistency of the model imposes an effective post-selection on the values in the loop variables. In the next section, we introduce the notion of $p$-separation which generalizes $d$-separation through making the effective conditioning explicit.

In this example, $x_3 = u_3$ and $x_4 = u_4$, thus whenever $u_3 \neq u_4$ also $x_3 \neq x_4$ (as these are binary, we have $x_4 = x_3 \oplus 1$). Then, the two functional dependencies of the model reduce to $x_1 = x_2$ and $x_2 = x_1 \oplus 1$, and there are zero solutions $(x_1, x_2)$ satisfying these for any values of $u_3 \neq u_4$. Whenever $u_3 \neq u_4$ also $x_3 = x_4$, and both the functional dependencies reduce to $x_1 = x_2$, which admits the two solutions $(x_1 = 0, x_2 = 0)$ and $(x_1 = 1, x_2 = 1)$ for any values of $u_3 = u_4$. This model is therefore not uniquely solvable (see section 5 for more precise and general definitions of solvability conditions).

**Failure of $d$-separation in uniquely solvable models.** There also exist uniquely solvable models where the soundness of $d$-separation fails: [Nea00] constructs such an example (albeit on a more complicated graph), which we review below. Consider the
graph

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

Consider a functional model $f\mathbf{Cm}_{G^{\text{Neal}}}$ which involves only binary variables i.e., $\mathcal{X}_{v_i} = \{0, 1\}$ for all $i = 1, 2, 3, 4, 5, 6, 7$. The exogenous vertices $v_1, v_4$ and $v_5$ are given corresponding errors $U_1, U_4$ and $U_5$ uniformly distributed and the functional dependences relating the values of each vertex to those of its parents are deterministic and we therefore need not consider their error variables (see the remark in section 2):

$$
\begin{align}
x_1 &= u_1, \notag \\
x_2 &= x_1 \oplus x_3, \notag \\
x_3 &= x_1 \oplus x_2, \notag \\
x_4 &= u_4, \tag{60} \\
x_5 &= u_5, \notag \\
x_6 &= (x_2 \oplus x_4 \oplus x_5) \cdot (x_7 \oplus 1), \notag \\
x_7 &= (x_2 \oplus x_4 \oplus x_5) \cdot x_6. \notag
\end{align}
$$

To see that the model is uniquely solvable, note that consistency for the functional de-
pendences of $x_6$ and $x_7$ forces $x_2 \oplus x_4 \oplus x_5 = 0$, in which case $x_6 = x_7 = 0$. Moreover,
$x_2 \oplus x_4 \oplus x_5 = 0$ implies $x_2 = x_4 \oplus x_5$ and together with the functional dependence of $x_3$
above gives $x_3 = x_1 \oplus x_4 \oplus x_5$. Therefore, given any valuation of the error variables $u_1$,
$u_4$ and $u_5$, there is a unique consistent valuation for the variables assigned to all the ver-
tices: the given values $u_1$, $u_4$ and $u_5$ fix the valuations of the exogenous vertices $x_1 = u_1$,
$x_4 = u_4$ and $x_5 = u_5$, which in turn uniquely determine $x_2$, $x_3$, $x_6$ and $x_7$ as explained
above. Furthermore, we can see that the *d*-separation $(v_4 \perp^d v_5|v_2)_{G^{\text{Neal}}}$ holds here, al-
though $(X_4 \not\perp X_5|X_2)_{\text{Pr}_{G^{\text{Neal}}}}$ in the constructed model as $x_2 \oplus x_4 \oplus x_5 = 0$ implies that
$x_4 = x_5$ whenever $x_2 = 0$. In other words, the soundness of *d*-separation fails in this
uniquely solvable functional model.

4.3 Introducing *p*-separation

In the previous section, we have seen that *d*-separation does not correctly capture corre-
lations in cyclic models. Its failure suggested that cycles induce correlations in a way that
could be captured through post-selection. Indeed, in section 3 we provided a mapping for
all finite cyclic fCMs into acyclic fCMs with post-selection. Based on this, we define a new
graph-separation property *p*-separation for cyclic graphs, where *p* stands for post-selection.

**Definition 19 (p-separation).** Let $G$ be a directed graph and $V_1, V_2$ and $V_3$ denote any three disjoint subsets of the vertices of $G$ with $V_1$ and $V_2$ being non-empty. Then, we say
that $V_1$ is p-separated from $V_2$ given $V_3$ in $G$, denoted $(V_1 \perp^p V_2|V_3)_G$, if and only if there exists $G_{TP} \in \mathbb{G}_{TP}(G)$ (definition 7) such that $(V_1 \perp^d V_2|V_3 \cup V_{post})_{G_{TP}}$, where $\perp^d$ denotes d-separation and $V_{post}$ denotes the set of all post-selection vertices in the teleportation graph $G_{TP} \in \mathbb{G}_{TP}(G)$. Otherwise, we say that $V_1$ is p-connected to $V_2$ given $V_3$ in $G$, and we denote it $(V_1 \not\perp^p V_2|V_3)_G$. To summarize,

$$ \textit{p-separation:} \quad (V_1 \perp^p V_2|V_3)_G \iff \exists G_{TP} \in \mathbb{G}_{TP}(G) : (V_1 \perp^d V_2|V_3 \cup V_{post})_{G_{TP}}, \quad (61) $$

$$ \textit{p-connection:} \quad (V_1 \not\perp^p V_2|V_3)_G \iff \forall G_{TP} \in \mathbb{G}_{TP}(G) : (V_1 \not\perp^d V_2|V_3 \cup V_{post})_{G_{TP}}. $$

The following theorems, whose proofs can be found in appendix B, establish soundness and completeness of p-separation. These results prove that p-separation correctly captures conditional independences in finite-cardinality cyclic functional models.

**Theorem 20 (p-separation theorem).** Consider a directed graph $G$ and let $V_1, V_2$ and $V_3$ be any three disjoint sets of the vertices of $G$ with $V_1$ and $V_2$ being non-empty. Then, the following holds:

(Soundness) For any functional model $f\mathbb{C}m_G$ on $G$, we have that p-separation between the vertex sets $V_i$ implies conditional independence for the corresponding sets of random variables $X_i := \{X_v\}_{v \in V_i}$ where $i \in \{1, 2, 3\}$, i.e.,

$$ (V_1 \perp^p V_2|V_3)_G \implies (X_1 \perp X_2|X_3)_{\mathrm{Pr}_G}. \quad (62) $$

(Completeness) If the p-connection $(V_1 \not\perp^p V_2|V_3)_G$ holds in $G$, then there exists a functional causal model $f\mathbb{C}m_G$ such that $(X_1 \not\perp X_2|X_3)_{\mathrm{Pr}_G}$.

The above conditional (in)dependence statements are relative to the marginal $\mathrm{Pr}(x_1, x_2, x_3)_G$ on $X_1 \cup X_2 \cup X_3$, where $x_i = \{x_v \mid x_v\}_{v \in V_i}$ of the observed distribution $\mathrm{Pr}(x)_G$, where $x = \{x_v\}_{v \in V}$, in the functional model $f\mathbb{C}m_G$.

The proof of theorem 20 is given in appendix B.

## 4.4 Examples: p-separation in acyclic and cyclic graphs

**Recovering d-separation in acyclic graphs.** Notice that our definition of p-separation reduces to d-separation whenever the graph $G$ is acyclic. This is because in this case the graph is a representative of its own acyclic family, $G \in \mathbb{G}_{TP}(G)$ with an empty set of post-selection vertices $V_{post} = \emptyset$, and for p-separation, it is sufficient to have one graph from this family where d-separation conditioned on $V_{post}$ holds. Thus we immediately have that d-separation of $V_1$ from $V_2$ given $V_3$ implies p-separation of $V_1$ from $V_2$ given $V_3$ in any directed acyclic graph $G$, according to definition 19. The other direction, namely that p-separation implies d-separation is also true, as can be seen from the contrapositive that d-connection implies p-connection. Indeed, it is easy to see, from the definition of the graph family (definition 7) that if $V_1$ and $V_2$ are d-connected conditioned on $V_3$ in a graph $G$, the same d-connection will hold in all teleportation graphs $G_{TP} \in \mathbb{G}_{TP}(G)$ once we additionally condition on the post-selection vertices (as these can only act as conditioned colliders). Thus, $V_1$ and $V_2$ are p-connected conditioned on $V_3$.

We now highlight the significance in definition 19 of requiring that a p-separation relation holds if there exists a teleportation graph $G_{TP} \in \mathbb{G}_{TP}(G)$ in which a corresponding d-separation relation holds, as opposed to requiring that the p-separation relation holds
if a corresponding d-separation relation holds for all teleportation graphs $G_{TP} \in \mathbb{G}_{TP}(G)$. For this, consider the following simple directed acyclic graph $G$:

$$G = \begin{tikzpicture}[baseline={([yshift=-0.5em]current bounding box.center)}]
% Vertices
\node[circle, fill=blue!20, inner sep=1.2pt] (A) at (0,0) {};
\node[circle, fill=blue!20, inner sep=1.2pt] (B) at (0,2) {};
\node[circle, fill=blue!20, inner sep=1.2pt] (C) at (0,4) {};
\node[circle, fill=blue!20, inner sep=1.2pt] (D) at (0,6) {};

% Edges
\draw[->, blue!50!black] (A) -- (C) node[left] {$A$};
\draw[->, blue!50!black] (A) -- (D) node[left] {$D$};
\draw[->, blue!50!black] (B) -- (C) node[right] {$B$};
\draw[->, blue!50!black] (B) -- (D) node[right] {$R$};

% Labels
\node[above] at (A) {$A$};
\node[above] at (B) {$B$};
\node[above] at (C) {$C$};
\node[above] at (D) {$D$};
\node[below] at (A) {$A$};
\node[below] at (B) {$B$};
\node[below] at (C) {$C$};
\node[below] at (D) {$D$};
\end{tikzpicture} \quad (63)$$

Consider the following teleportation graph $G_{TP} \in \mathbb{G}_{TP}(G)$ in its acyclic family (definition 7) obtained by choosing $V_S(G_{TP}) = \{C\}$:

$$G_{TP} = \begin{tikzpicture}[baseline={([yshift=-0.5em]current bounding box.center)}]
% Vertices
\node[circle, fill=blue!20, inner sep=1.2pt] (A) at (0,0) {};
\node[circle, fill=blue!20, inner sep=1.2pt] (B) at (0,2) {};
\node[circle, fill=blue!20, inner sep=1.2pt] (C) at (0,4) {};
\node[circle, fill=blue!20, inner sep=1.2pt] (D) at (0,6) {};

% Edges
\draw[->, blue!50!black] (A) -- (C) node[left] {$A$};
\draw[->, blue!50!black] (A) -- (D) node[left] {$D$};
\draw[->, blue!50!black] (B) -- (C) node[right] {$B$};
\draw[->, blue!50!black] (B) -- (D) node[right] {$R$};

% Labels
\node[above] at (A) {$A$};
\node[above] at (B) {$B$};
\node[above] at (C) {$C$};
\node[above] at (D) {$D$};
\node[below] at (A) {$A$};
\node[below] at (B) {$B$};
\node[below] at (C) {$C$};
\node[below] at (D) {$D$};
\end{tikzpicture} \quad (64)$$

Let $V_{post} = \{T\}$ be the set of post-selection vertices in this graph. Notice that $G'_{TP} := G$, being acyclic, is also a member of its acyclic family $\mathbb{G}_{TP}(G)$, and we denote with $V'_{post} = \emptyset$ the (trivial) set of post-selection vertices in this case.

It holds that $(A \not\perp^d B | V_{post})_{G_{TP}}$ but $(A \perp^d B | V'_{post})_{G'_{TP}}$, since the latter is equivalent to $(A \perp^d B)_G$. However $(A \not\perp^d B | V_{post})_{G_{TP}}$ does not imply $p$-connection as there exists an acyclic graph (in this case $G'_{TP} := G$) in the family having the relevant $d$-separation conditioned on the post-selection vertices. Thus, we have $(A \perp^p B)_G$ in this example, which coincides with $d$-separation.

In other words, our definition only implies a $p$-connection in $G$ when that connection is reflected in all the graphs of the graph family $\mathbb{G}_{TP}(G)$. Indeed, we have shown (see proposition 11 and definition 12) that the observed probabilities for the causal model are independent of the representative of $\mathbb{G}_{TP}(G)$ chosen in computing them. It follows from these results that for any functional causal model on $G_{TP}$ induced by a functional model on $G$, the outcomes $a$ and $b$ of the vertices $A$ and $B$ will be conditionally independent even when conditioned on the collider $V_{post} := \{T\}$ in equation (64). This is because the post-selection on the unblocking collider $T$ is fine-tuned in our definition of the induced model (it has to correspond to a post-selected teleportation protocol)$^7$. Thus, our definition of $p$-separation serves to avoid such fine-tuning and enables us to construct a sound and complete graph separation property for general directed graphs that reduces to $d$-separation in the acyclic case.

**$p$-separation in action.** Going back to the example in section 4.2, we can see that although $d$-separation failed to detect the possibility of correlation between certain vertices, $p$-separation does. In particular, for the cyclic graph in equation (56), consider the following member of $\mathbb{G}_{TP}(G)$ obtained by choosing $V_S(G_{TP}) := \{v_1\}$.

<footnote>$^7$Specifically, the post-selection here serves to simulate a directed edge from $C$ to $D$ through an identity channel (without post-selecting a particular outcome value on $C$ or $D$), which is why it does not correlate the outcomes of $A$ and $B$.</footnote>
<figure><img src="image_8.png" /></figure>

We can see that $(v_3 \not\perp^d v_4 | V_{\text{post}})_{G_{\text{TP}}}$ as $V_{\text{post}} := \{T_1\}$ acts as an unblocking collider. It is easy to see that every member of $G_{\text{TP}}(G)$ will have this $d$-connection relative to its $V_{\text{post}}$, as each such member will necessarily include at least one of the loop vertices $v_1, v_2$ in $V_S(G_{\text{TP}})$ and hence always introduce at least one unblocking collider between $v_3$ and $v_4$. Therefore, by definition 19, we have that $(v_3 \not\perp^p v_4)_{G}$. This $p$-connection explains the correlation between the outcomes of $v_3$ and $v_4$ that was observed in the functional model constructed in section 4.2.

Moreover, note that the same cyclic graph $G$ also has a non-trivial $p$-separation. In particular notice that $(v_3 \perp^d v_4 | v_1, v_2)_{G}$. It is straightforward to see by applying definition 19 to the graph $G_{\text{TP}} \in G_{\text{TP}}(G)$ that we also have $(v_3 \perp^p v_4 | v_1, v_2)_{G}$, since conditioning additionally on $v_1$ and $v_2$ blocks all paths between the remaining vertices and the post-selection vertex $T_1$. The soundness of $p$-separation then implies that the conditional independence $(X_3 \perp X_4 | X_1, X_2)_{\text{Pr}_G}$ will hold for all valid functional causal models one can define on $G$ within our framework.

Finally, applying similar arguments to the cyclic graph $G^{\text{Neal}}$ (equation (59)) underlying the example of [Nea00], where we had the $d$-separation $(v_4 \perp^d v_5 | v_2)_{G^{\text{Neal}}}$, we can see that we would have the $p$-connection $(v_4 \not\perp^p v_5 | v_2)_{G^{\text{Neal}}}$. This is because, just as in the simpler example above, any member of $G_{\text{TP}}(G^{\text{Neal}})$ will necessarily involve at least one post-selection vertex within the loop between $v_6$ and $v_7$ and conditioning on this, the exogenous vertices $v_4$ and $v_5$ influencing the loop, will become $d$-connected (and stay that way also when conditioning on $v_2$), i.e., $(v_4 \not\perp^d v_5 | \{v_2\} \cup V_{\text{post}})_{G^{\text{Neal}}}$ will hold for every $G^{\text{Neal}} \in G_{\text{TP}}(G^{\text{Neal}})$. This implies the $p$-connection $(v_4 \not\perp^p v_5 | v_2)_{G^{\text{Neal}}}$, which can explain the correlations seen between the outcomes $x_4$ and $x_5$ conditioned on $x_2$ in the uniquely solvable functional model $f\text{Cm}_{G^{\text{Neal}}}$ of that example (reviewed in section 4.2).

## 4.5 Links to $\sigma$-separation

In light of the failure of the $d$-separation theorem in cyclic causal models, another generalization of $d$-separation for cyclic graphs, known as $\sigma$-separation, was developed in [FM17]. This property, $\sigma$-separation was proven to be sound and complete for a class of functional causal models (fCMs) known as modular fCMs or mfCMs [FM17]$^8$. Modular fCMs correspond to fCMs defined generally on discrete and continuous variables, where the functional dependences possess a stronger version of the unique solvability property. Although mfCMs are a well-behaved and important subclass of classical causal models with many desirable properties, there do exist well-defined and consistent functional models outside this class for which the $\sigma$-separation theorem (i.e., the soundness and completeness of the property) no longer applies, and cannot account for the correlations there. In contrast, the $p$-separation theorem proven here applies to all consistent functional causal models, but with the restriction to finite-cardinality variables. More generally, as shown in the companion paper [FGV25], the theorem also extends to all consistent cyclic quantum causal

<footnote>$^8$These are referred to as modular structural equation models, (mSEM), in [FM17]</footnote>
models involving finite-dimensional Hilbert spaces. Thus the domains of validity of the σ- and p-separation theorems are quite distinct, neither being a subset of the other (non- uniquely solvable and quantum models are excluded in the former while functional models involving infinite-cardinality discrete variables as well as continuous variables are excluded in the latter).

Despite the different approaches backing σ and p-separation, some interesting points of comparison can be made, which suggest new research directions. We do not discuss the definition of σ-separation here (for that we refer to [FM17]), but we consider a particular example often used in the previous literature. Consider the following cyclic graph:

$$
G = \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.7, every node/.style={scale=0.7}]
\node (v1) at (0,0) {$v_1$};
\node (v2) at (1,0) {$v_2$};
\node (v3) at (0,1) {$v_3$};
\node (v4) at (1,1) {$v_4$};
\draw[->] (v1) -- (v2) node left {$v_2 \perp^d v_3 | v_2, v_4)_G$};
\draw[->] (v1) -- (v3) node left {$v_1 \perp^d v_4 | v_1, v_3)_G$};
\draw[->] (v2) -- (v4) node left {$v_4 \perp^d v_3 | v_2, v_4)_G$};
\draw[->] (v2) -- (v1) node left {$v_1 \perp^d v_3 | v_2, v_4)_G$};
\draw[->] (v3) -- (v4) node left {$v_3 \perp^d v_4 | v_1, v_3)_G$};
\node (v5) at (0.5,0.5) {$v_5$};
\draw[->] (v5) -- (v1) node left {$v_1 \perp^d v_5 | v_2, v_4)_G$};
\draw[->] (v5) -- (v2) node left {$v_2 \perp^d v_5 | v_1, v_3)_G$};
\draw[->] (v5) -- (v3) node left {$v_3 \perp^d v_5 | v_1, v_2)_G$};
\draw[->] (v5) -- (v4) node left {$v_4 \perp^d v_5 | v_2, v_3)_G$};
\node (v6) at (0.5,1.5) {$v_6$};
\draw[->] (v6) -- (v1) node left {$v_1 \perp^d v_6 | v_2, v_4)_G$};
\draw[->] (v6) -- (v2) node left {$v_2 \perp^d v_6 | v_1, v_3)_G$};
\draw[->] (v6) -- (v3) node left {$v_3 \perp^d v_6 | v_1, v_2)_G$};
\draw[->] (v6) -- (v4) node left {$v_4 \perp^d v_6 | v_2, v_3)_G$};
\end{tikzpicture} \qquad (66)
$$

Applying the definition of *d*-separation, it is easy to confirm that $(v_1 \perp^d v_3 | v_2, v_4)_G$ and $(v_2 \perp^d v_4 | v_1, v_3)_G$ hold in this graph. Nevertheless [FM17, FM18] shows that there exist functional causal models on this graph, where the variables associated with the vertices are continuous (take real values, $\mathbb{R}$) which can generate correlations between the variables associated with $v_1$ and $v_3$ even when conditioned on the variables of $v_2$ and $v_4$. On the other hand, relative to $\sigma$-separation, denoted as $\perp^\sigma$, $(v_1 \perp^\sigma v_3 | v_2, v_4)_G$ and $(v_2 \perp^\sigma v_4 | v_1, v_3)_G$ which can explain the correlations in this case (where *d*-separation fails to do so). In other words, observing such correlations in this graph would certify a correlation gap between *d* and $\sigma$ separation.

Interestingly, *p*-separation in this case agrees with *d*-separation rather than *σ*-separation, and we can check that we have the *p*-separations $(v_1 \perp^p v_3 | v_2, v_4)_G$ and $(v_2 \perp^p v_4 | v_1, v_3)_G$. This is because, even when introducing post-selection vertices for any number of edges and conditioning on them, the conditioning on the vertices $v_2$ and $v_4$ or $v_1$ and $v_3$ blocks all the paths between the remaining vertices under consideration. As a consequence of theorem 20 about the soundness of *p*-separation, it follows that for every causal model on the above graph where the vertices have non-trivial outcome sets, we will have the conditional independencies $(X_1 \perp X_3 | X_2, X_4)_{\text{Pr}_G}$ and $(X_2 \perp X_4 | X_1, X_3)_{\text{Pr}_G}$. In other words, this implies that a gap between *d* and $\sigma$ separation cannot be certified in the above graph using correlations arising in any classical causal model that can be described within our framework. Using the results of [FGV25], even allowing for quantum causal models on finite dimensional Hilbert spaces would not allow to certify this gap, as the soundness of *p*-separation extends to the quantum case.

A crucial point to note here is that our framework assumes only finite-cardinality random variables. The previously found distinguishing example between *d*- and *σ*-separation involves continuous variables, which are not covered by our formalism. This observation also highlights that the intuition given by *p*-separation may not immediately generalize to continuous models. Indeed, our method for computing probabilities in cyclic causal models relies on post-selecting on the precise values of certain variables. In the case of continuous variables, this post-selection event is of measure zero, and the associated probability of success would tend to zero<fnref n="9" />. In section 6, we further discuss possible directions for future

<footnote n="9">⁹In the quantum case, this discussion is related to the difficulty in defining an analogue of a maximally entangled state between infinite-dimensional Hilbert spaces while ensuring a bounded norm for that state.</footnote>
research based on such comparisons between graph-separation properties and associated correlations.

# 5 Solvability and related properties of cyclic functional models

An interesting question arising in the literature is whether the functional dependencies of a given causal models can be jointly satisfied for a choice of value assignment over error vertices. Explicitly, given a valuation {$u_v \in \mathcal{X}_v$}$_{v \in V}$ over the error variables, one considers whether there exists a set {$x_v \in \mathcal{X}_v$}$_{v \in V}$ of values on the vertices such that

$$x_v = f^v(x_{Pa(v)}, u_v) \quad \text{for all } v \in V \qquad (67)$$

holds (then the values entail a consistent solution), and, eventually, whether this set is unique (this entails a unique solution). For functional models on arbitrary cyclic graphs, the existence of a consistent solution is not guaranteed. However, if we restrict to functional models on acyclic graphs, for all valuations of the error variables, a consistent solution that satisfies all functional dependencies always exists and is unique [Pea09]. In this section, we aim to characterize the existence and number of solutions of a given finite functional causal model, and discuss how this relates to other properties of the model, such as Markovianity.

## 5.1 Number of solutions and consistency

We begin by formally defining the number of solutions of a functional causal model over finite-cardinality variables on an arbitrary graph. Then, we review the notion of unique solvability and introduce a new notion of average unique solvability, proving links to other properties. The proofs relative to results of this section are given in appendix C.

**Definition 21 (Number of solutions).** Consider a functional model on a directed graph $G = (V, E)$, $f\mathfrak{C}m_G$, and a set of value assignments on error variables, $u = \{u_v \in \mathcal{U}_v\}_{v \in V}$. The number of solutions of the model, for the given value assignment on exogenous vertices, is defined as

$$N_{f\mathfrak{C}m}(u) = \sum_x \prod_{v \in V} \delta_{f^v(x_{Pa(v)}, u_v), x_v}, \qquad (68)$$

where we used the same notation of definition 1 and the sum is over the value assignments, $x = \{x_v \in \mathcal{X}_v\}_{v \in V}$.

Notice that the number of solutions of a model is defined independently of the prior distributions $p^v$ associated to error variables $u_v$ for $v \in V$ in that model. Thus, we introduce the notion of average number of solutions of a functional model which takes into account these distributions.

**Definition 22 (Average number of solutions).** Consider a functional model on a directed graph $G = (V, E)$, $f\mathfrak{C}m_G$, the average number of solutions of the model is defined as

$$\bar{N}_{f\mathfrak{C}m} = \sum_u N_{f\mathfrak{C}m}(u) \prod_{v \in V} p^v(u_v), \qquad (69)$$

where the sum runs over $u = \{u_v \in \mathcal{U}_v\}_{v \in V}$.

The following proposition connects the probability of successful post-selection (definition 10) of a teleportation causal model in $\mathbb{G}_{\text{TP}}(G)$ to the average number of solutions of the underlying causal model $f\mathfrak{C}m_G$.
**Proposition 23** (Average number of solutions and success probability). Consider a functional causal model over a directed graph $G = (V, E)$, $f\mathbf{C}m_G$. Let $G_{TP} \in \mathbb{G}_{TP}(G)$ be a teleportation graph and $f\mathbf{C}m_{G_{TP}}$ the corresponding teleportation causal model constructed from $f\mathbf{C}m_G$. The post-selection success probability $p_s$ (definition 10) of $f\mathbf{C}m_{G_{TP}}$ satisfies

$$p_s = \left( \prod_{v \in V_s(G_{TP})} p_{TP}^{(v)} \right) \bar{N}_{f\mathbf{C}m}, \qquad (70)$$

where $V_s(G_{TP})$ is the set of split vertices of $G_{TP}$ and $p_{TP}^{(v)}$ is the teleportation probability associated to the classical post-selected teleportation protocol implemented for the split vertex $v \in V_s(G_{TP})$.

The previous proposition allows us to characterize inconsistent functional models, i.e., models where $p_s = 0$, in terms of the average number of solutions. This follows immediately from proposition 23 and from the fact that $p_{TP} > 0$ by definition of teleportation protocol.

**Corollary 24** (Characterization of inconsistent models). A functional causal model on a directed graph $G$, $f\mathbf{C}m_G$, is inconsistent (definition 12) if and only if $\bar{N}_{f\mathbf{C}m} = 0$.

An interesting subset of functional models is the set of so-called uniquely solvable functional models (see also [FM17, BFPM21]).

**Definition 25** (Uniquely solvable functional models). A functional model $f\mathbf{C}m_G$ on a directed graph $G = (V, E)$ is uniquely solvable if for all value assignments on error variables, $u = \{u_v \in \mathcal{U}_v\}_{v \in V}$, it holds that

$$N_{f\mathbf{C}m}(u) = 1. \qquad (71)$$

In analogy to uniquely solvable models, we can define averagely uniquely solvable models as follows.

**Definition 26** (Averagely uniquely solvable models). A functional model $f\mathbf{C}m_G$ on a directed graph $G = (V, E)$ as in definition 1 is averagely uniquely solvable if it holds

$$\bar{N}_{f\mathbf{C}m} = 1. \qquad (72)$$

Clearly, every uniquely solvable model is also averagely uniquely solvable. This is proven in the following proposition.

**Proposition 27** (Unique solvability implies average unique solvability). A uniquely solvable functional model is also averagely uniquely solvable.

The converse, however, is not true. The examples of the next section show that there are functional models that are only averagely uniquely solvable.

## 5.2 Examples on solvability

In this section, we first consider acyclic models, then discuss two examples of cyclic functional models and their solvability.

**Acyclic functional models.** It is easy to see that acyclic models are uniquely solvable, indeed, given definition 2 we have

$$N_{f\mathbf{C}m}(u) = \sum_{x} \mathrm{Pr}_{\mathrm{acyc}}(x|u) = 1, \qquad (73)$$

where $u = \{u_v \in \mathcal{U}_v\}_{v \in V}$ and the sum runs over $x = \{x_v \in \mathcal{X}_v\}_{v \in V}$.
**Definition 28** (Markov property in functional causal models). Consider a functional causal model $f\mathbf{Cm}_G$ over a directed graph $G = (V, E)$. If the joint distribution over observed events $x = \{x_v \in \mathcal{X}_v\}_{v \in V}$ factorizes as in equation (6) i.e.,

$$ \mathrm{Pr}(x)_G = \prod_{v \in V} \mathrm{Pr}^{(v)}(x_v | \mathrm{Pa}(x_v))_G, \qquad (82) $$

where $\mathrm{Pr}^{(v)}$ is the conditional probability distribution specified by $f\mathbf{Cm}_G$ for all $v \in V$, then we say that the model satisfies the Markov property or is probabilistically Markovian.

With this definition, it is immediate to see that all acyclic functional causal models satisfy this Markov property by definition 2 of their probabilities. Moreover as the probability rule for uniquely solvable models is identical to the acyclic case,<fnref n="10" /> they also respect this property [FM17, BFPM21]. However, generic functional models on cyclic graphs are not necessarily Markovian, as there exist examples of non-unique solvable models [VC22a] whose distribution does not factorize as in definition 28. Using our framework, we are able to characterize the set of functional models which satisfy the Markov property. The following propositions shows that in the finite cardinality case, Markovianity is satisfied in a strictly larger set of models than the uniquely solvable ones, namely, it is satisfied for all average unique solvable models. Furthermore, this is the largest set of models satisfying Markovianity.

**Corollary 29.** Given a functional causal model on a directed graph $G$, $f\mathbf{Cm}_G$, the following statements are equivalent:

1. $f\mathbf{Cm}_G$ is probabilistically Markovian;

2. $f\mathbf{Cm}_G$ is averagely uniquely solvable, $\overline{\mathbf{N}}_{f\mathbf{Cm}} = 1$;

3. for every choice of $G_{TP} \in \mathbb{G}_{TP}(G)$ used in the definition of $p_s$ (definition 10), the post-selection success probability is

$$ p_s = \left( \prod_{v \in V_s(G_{TP})} p_{TP}^{(v)} \right), \qquad (83) $$

where $V_s(G_{TP})$ is the set of split vertices of $G_{TP}$ and $p_{TP}^{(v)}$ is the teleportation probability associated to the classical post-selected teleportation protocol implemented for the split vertex $v \in V_s(G_{TP})$.

The above corollary follows directly from propositions 13 and 23. Indeed, it holds that

$$ \mathrm{Pr}(x) = \frac{\sum_u \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(x_{Pa(v)}, u_v)}}{\sum_y \sum_u \prod_{v \in V} p^v(u_v) \delta_{y_v, f^v(y_{Pa(v)}, u_v)}} \\ = \frac{\sum_u \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(x_{Pa(v)}, u_v)}}{\overline{\mathbf{N}}_{f\mathbf{Cm}}}, \qquad (84) $$

where the sum runs over $u = \{u_v \in \mathcal{U}_v\}_{v \in V}$. The numerator of the above equality yields the Markov property if and only if the constant denominator, $\overline{\mathbf{N}}_{f\mathbf{Cm}}$, is equal to 1, i.e., if the model is averagely uniquely solvable.

<footnote n="10">¹⁰One can see this explicitly in the upcoming equation (84).</footnote>
**Links between d-separation and Markovianity.** In acyclic functional causal models, the probability distribution is given by definition 2, which trivially satisfies the Markov property of definition 28. For these models we also know that d-separation is sound and complete (theorem 18). This is not a coincidence, as it is known that in directed acyclic graphs d-separation and Markovianity are equivalent to each other, and to another property (called the local Markov property) which states that the variable at each vertex is conditionally independent of its non-descendants given the parents [LDLL90, GP90]. However, in cyclic models this is no longer the case [VP22]. Firstly, while we have shown that Markovianity in the sense of definition 28 holds for all averagely uniquely solvable models, d-separation soundness fails in this set as shown by the example of the uniquely solvable model given in [Nea00] (reviewed in section 4.2).

Furthermore, consider the graph

$$G = \begin{tikzpicture}[baseline={([yshift=-0.5em]current bounding box.center)}]
    \node (v1) at (0,0) {$v_1$};
    \node (v2) at (1,0) {$v_2$};
    \node (v3) at (0.5,0.5) {$v_3$};
    \node (v4) at (1.5,0.5) {$v_4$};

    \draw[->] (v1) -- (v2);
    \draw[->] (v1) -- (v3);
    \draw[->] (v2) -- (v4);

    \node at (0.25,0.25) {$\perp$};
    \node at (0.25,0.35) {$\perp$};
    \node at (0.25,0.45) {$\perp$};

    \node at (0.25,0.5) {$\perp$};

    \node at (0.5,0.25) {$\perp$};
    \node at (0.5,0.35) {$\perp$};
    \node at (0.5,0.45) {$\perp$};
    \node at (0.5,0.5) {$\perp$};

    \node at (0.25,0.25) {$\perp$};
    \node at (0.25,0.35) {$\perp$};
    \node at (0.25,0.45) {$\perp$};
    \node at (0.25,0.5) {$\perp$};

    \node at (0.5,0.25) {$\perp$};
    \node at (0.5,0.35) {$\perp$};
    \node at (0.5,0.45) {$\perp$};
    \node at (0.5,0.5) {$\perp$};

    \node at (0.5,0.25) {$\perp$};
    \node at (0.5,0.35) {$\perp$};
    \node at (0.5,0.45) {$\perp$};
    \node at (0.5,0.5) {$\perp$};

    \node at (0.25,0.25) {$v_1$};
    \node at (0.25,0.35) {$v_2$};
    \node at (0.25,0.45) {$v_3$};
    \node at (0.25,0.5) {$v_4$};
\end{tikzpicture}. \qquad (85)$$

The local Markov property implies that $v_2$ is independent of $v_3$ (which is the only non-descendent which is not a parent of $v_2$), conditioned on $Pa(v_2) = \{v_1, v_4\}$, that is $(X_2 \perp X_3|X_1, X_4)_G$, where $X_i$ is the random variable associated to the vertex $v_i$. However, it holds that $(v_2 \perp^d v_3|v_1, v_4)_G$, since the path $v_2 \to v_1 \leftarrow v_3$ is a collider, hence conditioning on $v_1$ d-connects $v_2$ and $v_3$ allowing the associated variables to be conditionally dependent in a general functional model on this graph. This highlights that in cyclic graphs, d-separation, Markovianity (as in definition 28) and the local Markov property are not equivalent.

# 6 Discussion and outlook

We have developed a general framework applicable to all consistent cyclic functional causal models defined on finite-cardinality variables. The formalism includes both uniquely and non- uniquely solvable models and only excludes pathological models which admit no solutions for all possible valuations of the exogenous vertices<fnref n="11" />. We applied this framework to solve two open problems, for all (possibly cyclic) causal models describable within this formalism: (1) providing a general and robust method to uniquely fix the probability distribution, while recovering the known probability rule in the uniquely-solvable (and hence acyclic) case, and (2) introducing a new sound and complete graph-separation property, called p-separation, for cyclic models, which is equivalent to d-separation in the acyclic case. This was achieved by introducing the concept of a classical post-selected teleportation protocol (inspired by an analogous quantum information protocol), which enabled us to map cyclic functional causal models to acyclic ones with post-selection. Moreover, we defined a new class of models, averagely uniquely solvable functional causal models, finding this to be a strict superset of uniquely solvable ones, and the largest set where the previously known probability rule based on Markov factorization relative to the underlying graph is recovered.

There are several interesting avenues for future investigations and we discuss some of them below.

<footnote n="11">¹¹In case the graph contains no exogenous vertices, these would be models admitting no solutions.</footnote>
1. **Causal discovery algorithms:** These algorithms aim to ascertain the underlying causal structure (graph) from observable data, or a set of possible graphs compatible with the data. In acyclic graphs, the *d*-separation theorem plays a crucial role in such algorithms (see [SZ16]). Causal discovery algorithms in the cyclic case have been proposed for different subsets of models, e.g., for modular functional causal models based on *σ*-separation theorem [MC20]. As we discussed in section 4, in the finite-cardinality case, our framework and the *p*-separation theorem apply to more general models which include non-uniquely solvable ones. A natural next step would be to study whether robust causal discovery algorithms based on *p*-separation can be developed, as this would be applicable to all consistent finite-cardinality (possibly cyclic) functional causal models.

2. **Causal compatibility problems:** This involves determining whether a given distribution could arise from any classical causal model (here, a functional causal model) on a given causal structure. Again, as this involves relating the causal structure and observable distributions, it is also intimately linked to the *d*-separation theorem. This problem has applications for classical causal inference on the one hand, because focussing on classical causal explanations, incompatibility with a graph would allow to rule out that graph as an explanation [Pea09]. On the other hand, if a distribution generated by a quantum causal model on the same graph<fnref n="12" /> is classically incompatible as above, this would certify a quantum-classical gap in that causal structure. Bell's seminal theorem [Bel64] provides the first instance of an acyclic graph with such a gap, which is verifiable experimentally and has lead to several quantum information processing applications (see [BCP+14] for a review on Bell nonlocality, including relevant experiments and applications). Our contributions enable to extend such studies to cyclic graphs. In particular, since our framework maps cyclic causal modeling problems to acyclic causal modeling with post-selection, it is likely that existing techniques developed for solving acyclic causal compatibility problems can be ported to cyclic causal compatibility problems. For instance, it would be interesting to consider if the inflation technique for causal compatibility [WSF19] would generalize to cyclic causal models, using these ideas.

3. **Correlation gaps between *d*-, *σ*- and *p*-separation and unfaithful models:** In section 4, we demonstrated that in the graph of equation (66), there exists a *d*-separation relation that aligns with *p*-separation but not with *σ*-separation. Combined with our *p*-separation theorem, this implies that for all functional causal models within our framework, the resulting correlations would be unfaithful or fine-tuned relative to *σ*-separation (as conditional independence holds, yet there is *σ*-connection).<fnref n="13" /> This finding further suggests that within this graph, a correlation gap between *d*- and *σ*-separation cannot be established using functional models in our framework. However, there do exist continuous variable models, not captured within our framework, that are *σ*-faithful for this graph and certify such a gap [FM17, FM18]. Consequently, our results, together with these prior examples, also point to a correlation gap between finite-cardinality and infinite-cardinality or continuous functional causal models for

<footnote n="12">¹²That is, using quantum states and measurements wired together as suggested by the graph. See [FGV25] for details.</footnote>

<footnote n="13">¹³A causal model is unfaithful (or fine-tuned) relative to a graph-separation property if the model entails a conditional independence between three sets of variables whose vertices are connected in the graph according to the property. If this is never the case, the model is faithful relative to the given graph-separation property.</footnote>
the graph in equation (66)<fnref n="14" />.

Similarly, we identified another situation—the graph in equation (56)—where the vertices $v_3$ and $v_4$ are both *d*- and *σ*-separated but not *p*-separated. The soundness of *σ*-separation in all modular functional causal models [FM17] implies that such models will be unfaithful relative to *p*-separation. Furthermore, it indicates that a correlation gap between *d*- and *p*-separation may not be certifiable through such models for this particular graph.

Whether these curious observations generalize to arbitrary directed graphs remains an open question. This opens new directions for future exploration into correlation gaps between constraints imposed by different graph separation properties and among various classes of causal models on a given directed graph. Additionally, in the acyclic case, it is well-established that the set of unfaithful causal models on a graph (i.e., where there is *d*-connection and yet conditional independence) forms a measure-zero set [Pea09, Spi05]. The above discussion sheds light on the open problem regarding the generalization of this result for cyclic graphs, for (un)faithfulness defined relative to the distinct properties of *σ*- or *p*-separation (both of which reduce to *d*-separation in the acyclic case).

4. **Links between graph separation properties and Markovianity:** As discussed in section 5.3, the notion of Markovianity and the soundness of *d*-separation are equivalent for functional models on acyclic graphs. However, this equivalence no longer holds for models on cyclic graphs. It would be interesting to characterize the class of cyclic models in our framework for which the equivalence is recovered. In particular, although we found that the Markov factorization is recovered for all averagely uniquely solvable models, the example of [Nea00] (a uniquely solvable model) demonstrates that the *d*-separation theorem cannot be recovered for all such models. Therefore, tighter conditions would be required for the equivalence, and it would also be fruitful to consider other types of Markov properties such as the local Markov property, corresponding to conditional independence between a vertex and its non-descendants given its parents (which is also equivalent to *d*-separation properties in the acyclic case). In addition, relations between Markov properties and *p*-separation are yet to be explored as well as possible uses of *p*-separation in extending previous studies on Markov equivalence classes [Ric97, CM23].

5. **Characterising classical processes with “indefinite causal order”:** We note a striking similarity between our results of section 5.3 (regarding average unique solvability) and those in the literature on so-called indefinite causal order or higher-order processes [OCB12, CDPV13, BW16b] studied in the quantum information community. Specifically, classical processes in such formalisms are higher-order transformations from functions to functions, where the set of input functions could be composed together in a manner where one cannot identify a definite acyclic ordering between them [BW16b]. It was shown in [BW16a] that valid classical processes are characterized by having exactly one fixed point, and, by allowing probabilistic mixtures of such processes, the requirement becomes that of having one fixed point of average. There as well, one generally considers functions on finite alphabets, as in our functional causal modeling framework.

It is not difficult to see that each such classical process together with the input

<footnote n="14">¹⁴In conjunction with the results of [FGV25], this also highlights a gap between all finite-dimensional quantum causal models and continuous variable functional causal models in the graph of equation (66).</footnote>
functions on which it acts specifies a (possibly cyclic) functional causal model that
is valid in our framework<fnref n="15" />. This highlights a general link between average uniquely
solvable functional causal models defined here and the class of classical higher-order
processes. Thus, it indicates future avenues to investigate open problems on the
characterization of higher-order processes by linking them to problems regarding
solvability and Markov properties of cyclic functional models, and to study these in
mutual synergy within a common formalism.

6. **Incorporating interventions:** We have focussed on properties of correlations obtainable through passive observation in cyclic fCMs. Another natural extension of this work would be to incorporate active interventions within this framework and study the consistency and solvability properties of fCMs under interventions. The class of allowed interventions is also expected to play a role. Commonly, do-interventions are considered which fix a variable to a certain value independently of its parents [Pea09, Spi05]. The above-mentioned links to higher-order processes also suggests more general interventions where the functional dependences may be replaced without “cutting off” a vertex from its parents.

7. **Generalization to infinite-cardinality random variables:** Our framework is applicable to functional causal models associated with finite-cardinality random variables. The generalization to infinite-cardinality models (including both discrete and continuous random variables) is not immediate because it would require post-selecting on a measure-zero event. Therefore, the question on whether and how the probability rule and *p*-separation can be generalized to (possibly non-uniquely solvable) infinite-cardinality models remains open. Whether the discrete with infinite-cardinality vs continuous case impacts this generalization is also open. In particular, the discussions comparing *p* and *σ* separation [FM17] above and in section 4 suggest that for *p*-separation as defined here, soundness could fail in continuous variable functional causal models. It would be interesting to investigate possible extensions of the classical post-selected teleportation protocol introduced here to the infinite-cardinality case, to explore modifications to *p*-separation that may arise in that case.

**Acknowledgements.** We are grateful to Elie Wolfe for valuable feedback on our framework and its relation to results in classical cyclic causal models. We are thankful to Yílé Yīng for suggesting the name *p*-separation for the new graph separation property that we propose here. VV’s research has been supported by an ETH Postdoctoral Fellowship. VV acknowledges support from ETH Zurich Quantum Center, the Swiss National Science Foundation via project No. 200021_188541 and the QuantERA programme via project No. 20QT21_187724. VG and CF acknowledge support from NCCR SwissMAP, the ETH Zurich Quantum Center and the Swiss National Science Foundation via project No. 20QU-1_225171. CF acknowledges support from the ETH Foundation.

<footnote n="15">¹⁵This is also implied by the our results in the accompanying paper [FGV25] for general quantum processes.</footnote>
References

[AHK20] S. Arti, I. Hidayah, S. S. Kusumawardani, "Research trend of causal ma-
chine learning method: a literature review", *IJID (International Journal on
Informatics for Development)*, 9(2):111–118, doi:10.14421/ijid.2020.09208,
2020.

[BBC<sup>+</sup>93] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, W. K. Wootters, “Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels”, *Physical Review Letters*, 70:1895–1899, doi:10.1103/PhysRevLett.70.1895, 1993.

[BCP<sup>+</sup>14] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, S. Wehner, “Bell nonlocality”, *Reviews of Modern Physics*, 86:419–478, doi:10.1103/RevModPhys.86.419, 2014.

[Bel64] J. S. Bell, "On the Einstein Podolsky Rosen paradox", *Physics Physique Fizika*, 1:195-200, doi:10.1103/PhysicsPhysiqueFizika.1.195, 1964.

[BFPM21] S. Bongers, P. Forré, J. Peters, J. M. Mooij, “Foundations of structural causal models with cycles and latent variables”, *The Annals of Statistics*, 49(5):2885–2915, doi:10.1214/21-AOS2064, 2021.

[BLO20] J. Barrett, R. Lorenz, O. Oreshkov, “Quantum causal models”, *arXiv:1906.10726 [quant-ph]*, doi:10.48550/arXiv.1906.10726, 2020.

[BW16a] Ä. Baumeler, S. Wolf, “Device-independent test of causal order and relations to fixed-points”, *New Journal of Physics*, 18(3):035014, doi:10.1088/1367-2630/18/3/035014, 2016.

[BW16b] Ä. Baumeler, S. Wolf, “The space of logically consistent classical pro-
cesses without causal order”, *New Journal of Physics*, 18(1):013036,
doi:10.1088/1367-2630/18/1/013036, 2016.

[CDPV13] G. Chiribella, G. M. D’Ariano, P. Perinotti, B. Valiron, “Quantum computations without definite causal structure”, *Physical Review A*, 88(2), doi:10.1103/PhysRevA.88.022318, 2013.

[CM23] T. Claassen, J. M. Mooij, “Establishing Markov equivalence in cyclic directed graphs”, in R. J. Evans, I. Shpitser, editors, *Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence*, volume 216 of *Proceedings of Machine Learning Research*, 433–442, PMLR, URL https://proceedings.mlr.press/v216/claassen23a.html, 2023.

[CS16] F. Costa, S. Shrapnel, “Quantum causal modelling”, *New Journal of Physics*, 18(6):063032, doi:10.1088/1367-2630/18/6/063032, 2016.

[Deu91] D. Deutsch, “Quantum mechanics near closed timelike lines”, *Physical Review D*, 44:3197–3217, doi:10.1103/PhysRevD.44.3197, 1991.

[Die82] D. Dieks, “Communication by EPR devices”, *Physics Letters A*, 92(6):271–272, doi:10.1016/0375-9601(82)90084-6, 1982.

[FGV25] C. Ferradini, V. Gitton, V. Vilasini, “Cyclic quantum causal modelling with a graph separation theorem”, (Submitted to arXiv simultaneously with the present paper), 2025.

[FM17] P. Forré, J. M. Mooij, “Markov properties for graphical mod-
els with cycles and latent variables”, *arXiv:1710.08775 [math.ST]*,
doi:10.48550/arXiv.1710.08775, 2017.
[FM18] P. Forré, J. M. Mooij, “Constraint-based causal discovery for non-linear structural causal models with cycles and latent confounders”, in *Proceedings of the 34th Annual Conference on Uncertainty in Artificial Intelligence*, 269–278, doi:10.48550/arXiv.1807.03024, 2018.

[G49] K. Gödel, “An example of a new type of cosmological solutions of Einstein’s field equations of gravitation”, *Reviews of Modern Physics*, 21:447–450, doi:10.1103/RevModPhys.21.447, 1949.

[GP90] D. Geiger, J. Pearl, “On the logic of causal models”, in *Uncertainty in Artificial Intelligence*, volume 9 of *Machine Intelligence and Pattern Recognition*, 3–14, North-Holland, doi:10.1016/B978-0-444-88650-7.50006-8, 1990.

[GVP90] D. Geiger, T. Verma, J. Pearl, “Identifying independence in bayesian networks”, *Networks*, 20(5):507–534, doi:10.1002/net.3230200504, 1990.

[HLP14] J. Henson, R. Lal, M. F. Pusey, “Theory-independent limits on correlations from generalized bayesian networks”, *New Journal of Physics*, 16(11):113043, doi:10.1088/1367-2630/16/11/113043, 2014.

[KH11] S. Kleinberg, G. Hripcsak, “A review of causal inference for biomedical informatics”, *Journal of biomedical informatics*, 44:1102–12, doi:10.1016/j.jbi.2011.07.001, 2011.

[LDLL90] S. L. Lauritzen, A. P. Dawid, B. N. Larsen, H.-G. Leimer, “Independence properties of directed markov fields”, *Networks*, 20(5):491–505, doi:10.1002/net.3230200503, 1990.

[LKK21] T. Liu, P. V. Kulkarni, K. P. Kording, “Quantifying causality in data science with quasi-experiments”, *Nature Computational Science*, 1:24 – 32, doi:10.1038/s43588-020-00005-8, 2021.

[LMGP+11a] S. Lloyd, L. Maccone, R. Garcia-Patron, V. Giovannetti, Y. Shikano, S. Pirandola, L. A. Rozema, A. Darabi, Y. Soudagar, L. K. Shalm, A. M. Steinberg, “Closed timelike curves via postselection: Theory and experimental test of consistency”, *Physical Review Letters*, 106(4), doi:10.1103/PhysRevLett.106.040403, 2011.

[LMGP+11b] S. Lloyd, L. Maccone, R. Garcia-Patron, V. Giovannetti, Y. Shikano, S. Pirandola, L. A. Rozema, A. Darabi, Y. Soudagar, L. K. Shalm, A. M. Steinberg, “Closed timelike curves via postselection: Theory and experimental test of consistency”, *Physical Review Letters*, 106(4), doi:10.1103/PhysRevLett.106.040403, 2011.

[MC20] J. M. Mooij, T. Claassen, “Constraint-based causal discovery using partial ancestral graphs in the presence of cycles”, in *Conference on Uncertainty in Artificial Intelligence*, 1159–1168, URL https://proceedings.mlr.press/v124/m-mooij20a/m-mooij20a.pdf, 2020.

[MM67] R. A. Matzner, C. W. Misner, “Gravitational field equations for sources with axial symmetry and angular momentum”, *Physical Review*, 154:1229–1232, doi:10.1103/PhysRev.154.1229, 1967.

[Nea00] R. M. Neal, “On deducing conditional independence from d-separation in causal graphs with feedback (research note)”, *Journal of Artificial Intelligence Research*, 12:87–91, doi:10.1613/jair.689, 2000.

[OCB12] O. Oreshkov, F. Costa, v. Brukner, “Quantum correlations with no causal order”, *Nature Communications*, 3(1), doi:10.1038/ncomms2076, 2012.
[PD96] J. Pearl, R. Dechter, "Identifying independencies in causal graphs with feedback", in *Proceedings of the Twelfth International Conference on Uncertainty in Artificial Intelligence*, UAI'96, 420-426, Morgan Kaufmann Publishers Inc., doi:10.48550/arXiv.1302.3595, 1996.

[Pea09] J. Pearl, *Causality*, Cambridge University Press, 2nd edition, doi:10.1017/CBO9780511803161, 2009.

[PL14] M. Petersen, M. Laan, "Causal models and learning from data integrating causal modeling and statistical estimation", *Epidemiology (Cambridge, Mass.)*, 25:418-26, doi:10.1097/EDE.0000000000000078, 2014.

[RCLH21] Y. Raita, C. A. Camargo, L. Liang, K. Hasegawa, "Big data, data science, and causal inference: a primer for clinicians", *Frontiers in Medicine*, 8, doi:10.3389/fmed.2021.678047, 2021.

[Ric97] T. Richardson, "A characterization of Markov equivalence for directed cyclic graphs", *International Journal of Approximate Reasoning*, 17(2):107-162, doi:10.1016/S0888-613X(97)00020-0, uncertainty in AI (UAI'96) Conference, 1997.

[Spi05] P. Spirtes, "Graphical models, causal inference, and econometric models", *Journal of Economic Methodology*, 12:3-34, doi:10.1080/1350178042000330887, 2005.

[Sto38] W. J. van Stockum, "IX.-the gravitational field of a distribution of particles rotating about an axis of symmetry", *Proceedings of the Royal Society of Edinburgh*, 57:135-154, doi:10.1017/S0370164600013699, 1938.

[SZ16] P. Spirtes, K. Zhang, "Causal discovery and inference: concepts and recent methodological advances", *Applied Informatics*, 3(1):3, doi:10.1186/s40535-016-0018-x, 2016.

[VC22a] V. Vilasini, R. Colbeck, "General framework for cyclic and fine-tuned causal models and their compatibility with space-time", *Physical Review A*, 106(3), doi:10.1103/PhysRevA.106.032204, 2022.

[VC22b] V. Vilasini, R. Colbeck, "Impossibility of superluminal signaling in Minkowski spacetime does not rule out causal loops", *Physical Review Letters*, 129(11), doi:10.1103/PhysRevLett.129.110401, 2022.

[VP90] T. Verma, J. Pearl, "Causal networks: semantics and expressiveness", in R. D. Shachter, T. S. Levitt, L. N. Kanal, J. F. Lemmer, editors, *Machine Intelligence and Pattern Recognition*, volume 9, 69-76, North-Holland, ISBN 9780444886507, doi:10.1016/B978-0-444-88650-7.50011-1, 1990.

[VP22] T. Verma, J. Pearl, *Equivalence and Synthesis of Causal Models*, 221-236, Association for Computing Machinery, New York, NY, USA, 1 edition, ISBN 9781450395861, doi:10.1145/3501714.3501732, 2022.

[WSF19] E. Wolfe, R. W. Spekkens, T. Fritz, "The inflation technique for causal inference with latent variables", *Journal of Causal Inference*, 7(2), doi:10.1515/jci-2017-0020, 2019.

[WZ82] W. K. Wootters, W. H. Zurek, "A single quantum cannot be cloned", *Nature*, 299(5886):802-803, doi:10.1038/299802a0, 1982.
# A Proofs of section 3

In this section, we provide proofs of the results in section 3.

**Lemma 4.** The success probability of a classical teleportation protocol, $p_{TP}$, of definition 3 is independent of the probability distribution $p^A$ being teleported.

*Proof.* Assume that $p_{TP}$ depends on the probability being teleported, i.e., $p_{TP} = p_{TP}(p^A)$, and for all $c \in \mathcal{X}_C$,

$$ \sum_{\substack{a \in \mathcal{X}_A \\ b \in \mathcal{X}_B}} p^A(a) \delta_{f(a,b,c),1} \mathcal{P}_B(b) \mathcal{P}_C(c) = p_{TP}(p^A) p^A(c), \quad (86) $$

and assume that there exist two distinct probabilities $p^A$ and $p'^A$ such that $p_{TP}(p^A) \neq p_{TP}(p'^A)$. Consider a mixture of the two, i.e., $\lambda p^A + (1 - \lambda)p'^A$ for some $\lambda \in [0, 1]$, and teleport it:

$$ \begin{aligned} & \sum_{a,b} [\lambda p^A(a) + (1-\lambda)p'^A(a)] \delta_{f(a,b,c),1} \mathcal{P}_B(b) \mathcal{P}_C(c) && (87) \\ & = p_{TP} (\lambda p^A + (1-\lambda)p'^A) [\lambda p^A(c) + (1-\lambda)p'^A(c)]. && (88) \end{aligned} $$

By linearity on the left-hand side of the equation, we have

$$ \begin{aligned} & \sum_{a,b} [\lambda p^A(a) + (1-\lambda)p'^A(a)] \delta_{f(a,b,c),1} \mathcal{P}_B(b) \mathcal{P}_C(c) \\ & = \lambda \sum_{a,b} p^A(a) \delta_{f(a,b,c),1} \mathcal{P}_B(b) \mathcal{P}_C(c) + (1-\lambda) \sum_{a,b} p'^A(a) \delta_{f(a,b,c),1} \mathcal{P}_B(b) \mathcal{P}_C(c) \\ & = \lambda p_{TP}(p^A) p^A(c) + (1-\lambda) p_{TP}(p'^A) p'^A(c). \end{aligned} \quad (89) $$

Combining equations (88) and (89) we have

$$ \begin{aligned} & \lambda p_{TP}(p^A) p^A(c) + (1-\lambda)p_{TP}(p'^A) p'^A(c) \\ & = p_{TP} (\lambda p^A + (1-\lambda)p'^A) [\lambda p^A(c) + (1-\lambda)p'^A(c)], \end{aligned} \quad (90) $$

and marginalising over $c$,

$$ \lambda p_{TP}(p^A) + (1-\lambda)p_{TP}(p'^A) = p_{TP} (\lambda p^A + (1-\lambda)p'^A). \quad (91) $$

Inserting the last equation in equation (90), we get a quadratic expression in $\lambda$ which has to hold for all $\lambda \in [0, 1]$:

$$ (p_{TP}(p^A) - p_{TP}(p'^A)) (p^A(c) - p'^A(c)) \lambda^2 + (\dots) \lambda + (\dots) = 0. \quad (92) $$

This implies that the term before $\lambda^2$ should vanish for all $c \in \mathcal{X}_C$. This contradicts our assumption that $p^A \neq p'^A$ and $p_{TP}(p^A) \neq p_{TP}(p'^A)$. $\square$

**Lemma 5.** Consider a classical teleportation protocol defined by the pair $(f, \mathcal{P}_B, \mathcal{P}_C)$. Then, it holds:

$$ \sum_{b \in \mathcal{X}_B} \delta_{f(a,b,c),1} \mathcal{P}_B(b) \mathcal{P}_C(c) = p_{TP} \delta_{a,c}. \quad (18) $$
Proof. Consider a deterministic distribution $p^A(a) = \delta_{a,\bar{a}}$, we have

$$p_{TP} \delta_{\bar{a},c} = \sum_{\substack{a \in \mathcal{X}_A \\ b \in \mathcal{X}_B}} \delta_{a,\bar{a}} \delta_{f(a,b,c),1} \mathcal{P}_B(b) \mathcal{P}_C(c) = \sum_{b} \delta_{f(\bar{a},b,c),1} \mathcal{P}_B(b) \mathcal{P}_C(c), \quad (93)$$

which gives the result up changing the name of $\bar{a}$ to $a$. □

**Lemma 30.** The uniform prior post-selected teleportation protocol (definition 6) is a valid classical post-selected teleportation protocol with $p_{TP} = 1/|\mathcal{X}_A|$.

Proof. We have, for all distribution $p^A$ over $\mathcal{X}_A$,

$$\sum_{a \in \mathcal{X}_A} p^A(a) \delta_{\delta_{a,c},1} \frac{1}{|\mathcal{X}_A|} = \sum_{a \in \mathcal{X}_A} p^A(a) \delta_{a,c} \frac{1}{|\mathcal{X}_A|} = \frac{p^A(c)}{|\mathcal{X}_A|}. \quad (94)$$

**Lemma 8** (Acyclicity of classical teleportation graphs). Given a directed graph $G$, each classical teleportation graph $G_{TP} \in \mathbb{G}_{TP}(G)$ is acyclic.

Proof. In the first step of definition 7, the graph $G'$ is acyclic by definition. The second step introduces pre- and post-selection vertices, $R_v$ and $T_v$ for each $v \in V_S(G_{TP})$, and associated edges according to equation (26). To show that this step preserves acyclicity, notice that a directed graph is acyclic if and only if it can be drawn on a page with all directed edges oriented from bottom to top of the page<fnref n="16" />. Since $G'$ is acyclic, we can represent it on a page through such a diagram. We now add the pre- and post-selection vertices to this diagram by drawing all the $R_v$ at the bottom of the page, below all other vertices, and all the $T_v$ at the top of the page, above all the other vertices. Since all preselection vertices $R_v$ only have outgoing edges and all post-selection vertices $T_v$ only have incoming arrows, both of which will be oriented from bottom to top in our diagram, it follows that $G_{TP}$ is acyclic. □

**Proposition 11** (Equivalent probabilities from different classical teleportation graphs). Let $f \mathbb{C}m_G$ be a functional model on a directed graph $G$. Consider any $G_1, G_2 \in \mathbb{G}_{TP}(G)$, and for $i \in \{1, 2\}$, let $f \mathbb{C}m_{G_i}$ be a causal model on the teleportation graph $G_i$ constructed according to definition 9. Denoting the set of all post-selection vertices of $G_1, G_2$ as $V_{\text{post}}^1$ and $V_{\text{post}}^2$ respectively, we have

$$\mathrm{Pr}_{\mathrm{acyc}}(x | \{t_T = 1\}_{T \in V_{\mathrm{post}}^1})_{G_1} = \mathrm{Pr}_{\mathrm{acyc}}(x | \{t_T = 1\}_{T \in V_{\mathrm{post}}^2})_{G_2}, \quad (31)$$

for all joint observed events $x = \{x_v \in \mathcal{X}_v\}_{v \in V}$.

Proof. In what follows we will use the following result: given a functional model (definition 1) on an acyclic graph $\tilde{G} = (\tilde{V}, \tilde{E})$ and a global observed event $x = \{x_v \in \mathcal{X}_v\}_{v \in \tilde{V}}$, the acyclic probability rule definition 2 can be factorized as follows for $x_0 \in x$ associated with the vertex $v_0 \in \tilde{V}$:

$$\mathrm{Pr}_{\mathrm{acyc}}(x)_{\tilde{G}} = \sum_{u} p(u, \bar{x}) \prod_{v' \in \mathrm{Ch}(v_0)} \delta_{f^v(x_{\mathrm{Pa}(v)}, u_v), x_v} p^v(u_v) \quad (95)$$

<footnote n="16">¹⁶This representation is equivalent to a Hasse diagram for partially ordered sets, recognising the fact that every directed acyclic graph induces a partial order and vice versa.</footnote>
where we denoted $\bar{x} := \{x_v\}_{v \in \tilde{V} \setminus \text{Ch}(v_0)}$ and defined

$$p(u, \bar{x}) = \prod_{\substack{v \in \tilde{V} \\ v \notin \text{Ch}(v_0)}} p^v(x_v) \delta_{f^v(x_{\text{Pa}(v)}, u_v), x_v}. \qquad (96)$$

Notice that $\sum_u p(u, \bar{x})$ is just the marginal $\text{Pr}_{\text{acyc}}(\bar{x})_{\tilde{G}}$ where $\bar{x} = \{x_v\}_{v \in \tilde{V} \setminus \text{Ch}(v_0)}$. With this in mind, we first proceed with proving the result in a special case.

**Proof in a special case.** Consider the special case where $G_1$ and $G_2$ were constructed by choosing

$$V_S(G_2) = V_S(G_1) \cup \{v_0\}, \qquad (97)$$

i.e., the vertices which are split in $G_2$ include all vertices that are split in $G_1$ plus the vertex $v_0$. Let $V_{\text{post}}^1$ denote the set of post-selection vertices of $G_1$ and $t = \{t_T \in \{0, 1\}\}_{T \in V_{\text{post}}^1}$ the set of outcomes associated to them. Then, taking $t_0$ to be the outcome of the post-selection vertex associated to the vertex $v_0$, we have $t \cup t_0 := \{t_T \in \{0, 1\}\}_{T \in V_{\text{post}}^2}$ as outcomes associated to the post-selection vertices of $G_2$.

Denoting with $(x = \{x_v \in \mathcal{X}_v\}_{v \in V}, t)$ an event on $G_1$, consider the probability $\text{Pr}_{\text{acyc}}(x, t)_{G_1}$ associated to the causal model $\text{fCm}_{G_1}$. As this is an acyclic causal model by construction, the probability is immediately given by applying the acyclic probability rule of definition 2 to this functional model. As argued above, this can be factorized<fnref n="17" /> as

$$\text{Pr}_{\text{acyc}}(x, t)_{G_1} = \sum_{u} p(u, \bar{x}, t) \prod_{v \in \text{Ch}(v_0)} \delta_{f^v(x_{\text{Pa}(v)}, u_v), x_v} p^v(u_v) \qquad (98)$$

where $p(u, \bar{x}, t)$ was defined as prescribed in equation (96)<fnref n="18" />. Let $(f, \mathcal{P}_B, \mathcal{P}_C)$ be the classical post-selected teleportation protocol which implements the splitting of $v_0$ in the functional model $\text{fCm}_{G_2}$, with associated pre- and post-selection vertices $R_0$ and $T_0$, and teleportation probability $p_{\text{TP}} \in (0, 1]$. For all, $a, c \in \mathcal{X}_{v_0}$, it holds that (lemma 5)

$$\sum_{b \in \mathcal{X}_B} \delta_{f(a,b,c),1} \mathcal{P}_B(b) \mathcal{P}_C(c) = p_{\text{TP}} \delta_{a,c}. \qquad (99)$$

<footnote n="17">¹⁷This factorization corresponds to considering the product of all probabilities and delta functions of the functional model $\text{fCm}_{G_1}$ but leaving the multiplication along the split vertex $v_0$ as the last step.</footnote>

<footnote n="18">¹⁸Note that for $G_1$, the joint observed event includes the post-selections, i.e., it is $x \cup t$. Since $v_0$ is not split in $G_1$, $T \notin \text{Ch}(G_1)$ for all $T \in T$.</footnote>
Using this equality, we can rewrite

$$
\begin{align}
\mathrm{Pr}_{\mathrm{acyc}}(x,t)_{G_1} &= \sum_u p(u, \bar{x}, t) \prod_{v \in \mathrm{Ch}(v_0)} \delta_{f^v(x_{\mathrm{Pa}(v)}, u_v), x_v} p^v(u_v) \nonumber \\
&= \sum_u p(u, \bar{x}, t) \prod_{v \in \mathrm{Ch}(v_0)} \delta_{f^v(x_{\mathrm{Pa}(v) \setminus v_0}, x_0, u_v), x_v} p^v(u_v) \sum_{r_0 \in \mathcal{X}_{v_0}} \delta_{x_0, r_0} \nonumber \\
&= \sum_u p(u, \bar{x}, t) \prod_{v \in \mathrm{Ch}(v_0)} p^v(u_v) \sum_{r_0} \delta_{f^v(x_{\mathrm{Pa}(v) \setminus v_0}, r_0, u_v), x_v} \delta_{x_0, r_0} \tag{100} \\
&= \frac{1}{p_{\mathrm{TP}}} \sum_u p(u, \bar{x}, t) \prod_{v \in \mathrm{Ch}(v_0)} p^v(u_v) \nonumber \\
&\qquad \sum_{r_0, b} \delta_{f^v(x_{\mathrm{Pa}(v) \setminus v_0}, r_0, u_v), x_v} \delta_{f(x_0, b, r_0), 1} \mathcal{P}_B(b) \mathcal{P}_C(r_0) \nonumber \\
&= \frac{1}{p_{\mathrm{TP}}} \mathrm{Pr}_{\mathrm{acyc}}(x, t, t_0 = 1)_{G_2}, \nonumber
\end{align}
$$

where in $f^v$ we separated the dependency on the parent node $v_0$ as $f^v(x_{\mathrm{Pa}(v)\setminus v_0}, x_0, u_v)$.
In the above steps, we have used that dividing by $p_{\mathrm{TP}}$ is allowed as $p_{\mathrm{TP}} > 0$ by definition and lemma 5 between the third to fourth step above. In the last equation, we used that $\mathrm{fCm}_{G_1}$ and $\mathrm{fCm}_{G_2}$ can be chosen to have the same associated $p(u, \bar{x}, t)$ (to see this, one may restrict all the post-selected teleportation protocols to be implemented as in definition 6 — if the equality holds in this case, the general result follows from corollary 14).

We can now relate the success probabilities $p_s^{(1)}$ and $p_s^{(2)}$ respectively of the functional model $\mathrm{fCm}_{G_1}$ on the classical teleportation graph $G_1$ and on $\mathrm{fCm}_{G_2}$ on $G_2$. By definition 10 and using that $p_{\mathrm{TP}} > 0$, we have

$$ p_s^{(1)} = \sum_x \mathrm{Pr}_{\mathrm{acyc}}(x, t=1)_{G_1} \quad (101) $$

$$ = \frac{1}{p_{\mathrm{TP}}} \sum_x \mathrm{Pr}_{\mathrm{acyc}}(x, t=1, t_0=1)_{G_2} \quad (102) $$

$$ = \frac{1}{p_{\mathrm{TP}}} p_s^{(2)}, \quad (103) $$

where we denoted with $t=1$ the event $\{t_T = 1\}_{T \in V_{\mathrm{post}}^1}$, and the sum $\sum_x$ runs over all $x = \{x_v \in \mathcal{X}_v\}_{v \in V}$.

We see that the two success probabilities differ by a multiplicative constant (the success probability $p_{\mathrm{TP}}$ of the post-selected teleportation protocol defined by $\mathrm{fCm}_{G_1}$ for the split vertex $v_0$), and hence, $p_s^{(1)}$ is zero if and only if $p_s^{(2)}$ is zero. Thus, the probabilities $\mathrm{Pr}_{\mathrm{acyc}}(x|t=1)_{G_1}$ are defined if and only if the probabilities $\mathrm{Pr}_{\mathrm{acyc}}(x|t=1, t_0=1)_{G_2}$ are defined. In this case, we can relate them as follows:

$$
\begin{align}
\mathrm{Pr}_{\mathrm{acyc}}(x|t=1)_{G_1} &= \frac{\mathrm{Pr}_{\mathrm{acyc}}(x, t=1)_{G_1}}{p_s^{(1)}} \nonumber \\
&= \frac{p_{\mathrm{TP}} \mathrm{Pr}_{\mathrm{acyc}}(x, t=1, t_0=1)_{G_2}}{p_{\mathrm{TP}} p_s^{(2)}} \tag{104} \\
&= \mathrm{Pr}_{\mathrm{acyc}}(x|t=1, t_0=1)_{G_2}, \nonumber
\end{align}
$$

which completes the proof in this case.
**Proof in the general case.** Consider two general elements $G_1, G_2$ of $\mathbb{G}_{\text{TP}}(G)$. We can prove the general statement by first noticing that the repeated application of the above argument can be used to prove that the probabilities of both $G_1$ and $G_2$ are equivalent to those of $G_0$, where the latter corresponds to the graph where all the vertices have been split (i.e., $V_S(G_0) = V$, where $G = (V, E)$). The result follows by transitivity. □

**Proposition 13** (Alternative formulation of the probability rule). Consider a functional model $\mathfrak{fCm}_G$ on a directed graph $G = (V, E)$. If the model is not inconsistent, an alternative expression for the probability rule in definition 2 is given by

$$ \mathrm{Pr}(x)_G = \frac{\sum_u \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(x_{\mathrm{Pa}(v)}, u_v)}}{\sum_y \sum_u \prod_{v \in V} p^v(u_v) \delta_{y_v, f^v(y_{\mathrm{Pa}(v)}, u_v)}} \quad (33) $$

where we have defined the global event $x = \{x_v \in \mathcal{X}_v\}_{v \in V}$, the sum $\sum_y$ runs over all $y = \{y_v \in \mathcal{X}_v\}_{v \in V}$ and $\sum_u$ over $u = \{u_v \in \mathcal{U}_v\}_{v \in V}$.

**Proof.** We have shown that the probability rule is independent on the set of split vertices $V_S(G_{\text{TP}})$, hence we can consider the element $G_0 = (V_0, E_0)$ of $\mathbb{G}_{\text{TP}}(G)$ where $V_S(G_{\text{TP}}) = V$, i.e., all vertices are split and associated with pre- and post-selection vertices and edges. Therefore, the set of vertices of $G_0$ is $V_0 = V \cup \{R_v, T_v\}_{v \in V}$, i.e., for each vertex in $G$ there is a pre- and post-selection pair of vertices in $G_0$. For $v \in V$ we denote with $(f^v, \mathcal{P}_B^v, \mathcal{P}_C^v)$ the post-selected teleportation protocol associated to the corresponding pre- and post-selection pair.

Denoting with $t_v \in \{0, 1\}$ the outcome associated to $T_v$ and with $r := \{r_v \in \mathcal{X}_v\}_{v \in V}$ the outcomes associated to the preselection vertices $\{R_v\}_{v \in V}$, we have (definition 2)

$$ \begin{aligned} \mathrm{Pr}_{\mathrm{acyc}}(x, \{t_v = 1\}_{v \in V})_{G_0} &= \sum_r \mathrm{Pr}_{\mathrm{acyc}}(x, r, \{t_v = 1\}_{v \in V})_{G_0} \\ &= \sum_{r,b,u} \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(r_{\mathrm{Pa}(v)}, u_v)} \delta_{f^v(x_v, b_v, r_v), 1} \mathcal{P}_B^v(b_v) \mathcal{P}_C^v(r_v) \\ &\stackrel{\text{lem. 5}}{=} \sum_{r,u} \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(r_{\mathrm{Pa}(v)}, u_v)} p_{\text{TP}}^{(v)} \delta_{x_v, r_v} \\ &= p_{\text{TP}}^{\text{tot}} \sum_u \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(x_{\mathrm{Pa}(v)}, u_v)} \end{aligned} \quad (105) $$

where $p_{\text{TP}}^{\text{tot}} = \prod_{v \in V} p_{\text{TP}}^{(v)}$ and $p_{\text{TP}}^{(v)}$ is the probability of successful post-selection of the implementation chosen for the vertex $v$. Therefore,

$$ \begin{aligned} \mathrm{Pr}(x)_G &= \frac{\mathrm{Pr}_{\mathrm{acyc}}(x, \{t_v = 1\}_{v \in V})_{G_0}}{\sum_y \mathrm{Pr}_{\mathrm{acyc}}(y, \{t_v = 1\}_{v \in V})_{G_0}} \\ &= \frac{p_{\mathrm{TP}}^{\mathrm{tot}} \sum_u \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(x_{\mathrm{Pa}(v)}, u_v)}}{p_{\mathrm{TP}}^{\mathrm{tot}} \sum_{y,u} \prod_{v \in V} p^v(u_v) \delta_{y_v, f^v(y_{\mathrm{Pa}(v)}, u_v)}} \\ &= \frac{\sum_u \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(x_{\mathrm{Pa}(v)}, u_v)}}{\sum_{y,u} \prod_{v \in V} p^v(u_v) \delta_{y_v, f^v(y_{\mathrm{Pa}(v)}, u_v)}}. \end{aligned} \quad \square $$

## B Proofs of section 4

We provide the proof of theorem 20.
**Theorem 20 (p-separation theorem).** Consider a directed graph G and let $V_1, V_2$ and $V_3$ be any three disjoint sets of the vertices of G with $V_1$ and $V_2$ being non-empty. Then, the following holds:

(Soundness) For any functional model $f\mathbf{Cm}_G$ on G, we have that p-separation between the vertex sets $V_i$ implies conditional independence for the corresponding sets of random variables $X_i := \{X_v\}_{v \in V_i}$ where $i \in \{1, 2, 3\}$, i.e.,

$$ (V_1 \perp^p V_2 | V_3)_G \implies (X_1 \perp X_2 | X_3)_{\mathrm{Pr}_G}. \qquad (62) $$

(Completeness) If the p-connection $(V_1 \perp^p V_2 | V_3)_G$ holds in G, then there exists a functional causal model $f\mathbf{Cm}_G$ such that $(X_1 \perp X_2 | X_3)_{\mathrm{Pr}_G}$.

The above conditional (in)dependence statements are relative to the marginal $\mathrm{Pr}(x_1, x_2, x_3)_G$ on $X_1 \cup X_2 \cup X_3$, where $x_i = \{x_v\}_{v \in V_i}$ of the observed distribution $\mathrm{Pr}(x)_G$, where $x = \{x_v\}_{v \in V}$, in the functional model $f\mathbf{Cm}_G$.

**Proof.** (Soundness) From definition 19, we have $(V_1 \perp^p V_2 | V_3)_G \iff \exists G_{\mathrm{TP}} \in \mathbb{G}_{\mathrm{TP}}(G)$ such that $(V_1 \perp^d V_2 | V_3 \cup V_{\mathrm{post}})_{G_{\mathrm{TP}}}$, where $V_{\mathrm{post}}$ is the set of all post-selection vertices in the chosen classical teleportation graph $G_{\mathrm{TP}}$. From theorem 18, it then follows that the conditional independence $(X_1 \perp X_2 | X_3 \cup V_{\mathrm{post}})_{(\mathrm{Pr}_{\mathrm{acyc}})_{G_{\mathrm{TP}}}}$ holds since $G_{\mathrm{TP}}$ is a directed acyclic graph (lemma 8). Finally, by definition 12, the probability distribution associated with a functional model on the possibly cyclic graph G is given by the corresponding probability computed in any representative teleportation graph $G_{\mathrm{TP}} \in \mathbb{G}_{\mathrm{TP}}(G)$ with an additional conditioning on the associated post-selection vertices $V_{\mathrm{post}}$. Recall from proposition 11 that this distribution is the same, independently of which representative $G_{\mathrm{TP}} \in \mathbb{G}_{\mathrm{TP}}(G)$ is chosen. Therefore, using definition 12, we know that $(X_1 \perp X_2 | X_3 \cup V_{\mathrm{post}})_{(\mathrm{Pr}_{\mathrm{acyc}})_{G_{\mathrm{TP}}}}$ is equivalent to $(X_1 \perp X_2 | X_3)_{\mathrm{Pr}_G}$ by definition 19, which completes the proof.

(Completeness) We begin by making an important observation.

*Observation 1:* Consider a directed graph $G := (V, E)$ and an arbitrary subgraph $G' := (V', E')$ of $G$ with $V' \subseteq V$ and $E' \subseteq E$. Then any functional causal model $f\mathbf{Cm}_{G'}$ (definition 1) on the subgraph trivially induces a functional causal model $f\mathbf{Cm}_G$ on the original graph $G$ where both models assign the same probabilities to the values $x' := \{x_v\}_{v \in V'}$ of variables associated to $V'$, i.e., $\mathrm{Pr}_{G'}(x') = \mathrm{Pr}_G(x')$. Explicitly, $f\mathbf{Cm}_G$ is constructed from the given $f\mathbf{Cm}_{G'}$ by including the same error distribution $p^v(u_v)$ and same function $f^v$ to each $v \in V'$ in both models, in $G$, these functions ignore any dependencies on parents of $v$ associated with edges in $E \setminus E'$. For all remaining vertices, $v \in V \setminus V'$, the error distributions $p^v(u_v)$ can be arbitrary and the functions set $x_v = u_v$. As the models $f\mathbf{Cm}_G$ and $f\mathbf{Cm}_{G'}$ are exactly the same for the common vertices $V'$, it is immediate that the probabilities for $x'$ are identical.

Now suppose we have a p-connection $(V_1 \perp^p V_2 | V_3)_G$, and consider two cases based on whether or not the corresponding d-connection holds. We will establish the existence of a causal model with the corresponding conditional dependence separately in each case.

**Proof when d- and p-connections coincide,** i.e., $(V_1 \perp^d V_2 | V_3)_G$:

By definition 16 of d-separation, this d-connection implies the existence of a path between $V_1$ and $V_2$ that is not blocked by $V_3$. Since $V_1$ and $V_2$ are disjoint, such a path (all the vertices and edges included in the path) define an acyclic<fnref n="19" /> subgraph

<footnote n="19">¹⁹This is the case because by definition a path involves distinct vertices.</footnote>
G' of G, formed by all the vertices of G but only the edges that contribute to the d-connecting path. The completeness of d-separation for classical acyclic causal models that is well-known (theorem 18) then implies that there must exist a causal model on G' where $(X_1 \perp X_2|X_3)_{\text{Pr}_{acycG'}}$. Since G' is a subgraph of G, this also constitutes a causal model on G by Observation 1,<fnref n="20" /> which gives the required conclusion for the outcome sets of interest, $(X_1 \perp X_2|X_3)_{\text{Pr}_G}$.

**Proof when d- and p-connections do not coincide**, i.e., $(V_1 \perp^d V_2|V_3)_G$:

Here we have the d-separation $(V_1 \perp^d V_2|V_3)_G$ but the p-connection $(V_1 \not\perp^p V_2|V_3)_G$. The former d-separation implies the same in all teleportation graphs $G_{TP} \in \mathbb{G}_{TP}(G)$ of G, i.e., $(V_1 \perp^d V_2|V_3)_{G_{TP}}$. This is because teleportation graphs are constructed by removing edges and adding colliders (from $V_{post}$). Since these are not conditioned on in this d-separation, they cannot convert the given d-separation into a d-connection by definition 16. The p-connection $(V_1 \not\perp^p V_2|V_3)_G$ is equivalent, by definition 19, to d-connection in some teleportation graph $G_{TP} \in \mathbb{G}_{TP}(G)$ of G, including additional conditioning on the set $V_{post}$ of post-selection vertices in $G_{TP}$. That is, we have the following two conditions satisfied in this case:

$$ \begin{aligned} & (V_1 \perp^d V_2|V_3)_{G_{TP}} \\ & (V_1 \not\perp^d V_2|V_3 \cup V_{post})_{G_{TP}}. \end{aligned} \qquad (106) $$

This is equivalent to saying that there exist $v_1 \in V_1$ and $v_2 \in V_2$ such that

$$ \begin{aligned} & (v_1 \perp^d v_2|V_3)_{G_{TP}} \\ & (v_1 \not\perp^d v_2|V_3 \cup V_{post})_{G_{TP}}. \end{aligned} \qquad (107) $$

Again, as in the previous case, we can use the existence of a path which d-connects $v_1$ and $v_2$ conditioned on $V_3$ and $V_{post}$ to construct an acyclic subgraph $G'_{TP}$ of $G_{TP}$, but introduce a slight modification to handle post-selection vertices. Here we consider any choice of d-connecting (or unblocking) path which entails the d-connection of equation (107) and the subgraph $G'_{TP}$ is formed by all the vertices of $G_{TP}$ but only keeping the edges which contribute to this d-connecting path, along with the edges $(v, T_v)$ and $(R_v, T_v)$ for each $v \in V_S(G_{TP})$ which are present in $G_{TP}$. Therefore by construction equation (107) also holds for $G'_{TP}$, i.e.,

$$ \begin{aligned} & (v_1 \perp^d v_2|V_3)_{G'_{TP}} \\ & (v_1 \not\perp^d v_2|V_3 \cup V_{post})_{G'_{TP}}. \end{aligned} \qquad (108) $$

This tells us that all paths between $v_1$ and $v_2$ in $G'_{TP}$ are blocked by $V_3$, but there exists at least one such path that becomes unblocked when additionally conditioning on $V_{post}$. Thus, $V_{post}$ (being composed of childless vertices) act as colliders. This implies that in the subgraph $G'_{TP}$, there must be an unblocked path from $v_1$ to some $T \in V_{post}$ as well as an unblocked path from $v_2$ to some $T' \in V_{post}$ (not necessarily

<footnote n="20">²⁰This causal model can potentially be fine-tuned relative to other d-separations i.e., there can be d-connections between other sets of vertices in G that are not accompanied by the corresponding conditional dependence in this causal model. The completeness statement here only requires the model to reproduce the conditional dependence for the given d-connection $(V_1 \not\perp^d V_2|V_3)_G$.</footnote>
the same as $T$), and an unblocked path between $T$ and $T'$. That is $\exists T, T' \in V_{\text{post}}$ such that

$$ (v_1 \not\perp^d T|V_3)_{G'_{\text{TP}}} \\ (v_2 \not\perp^d T'|V_3)_{G'_{\text{TP}}} \\ (T \not\perp^d T'|V_3)_{G'_{\text{TP}}}. \qquad (109) $$

We now construct a functional model $f\mathfrak{C}m_{G'_{\text{TP}}}$ on $G'_{\text{TP}}$ (an acyclic graph) and use the $d$-connections of equation (109) to argue that the random variable $\bar{X}_1$ of $v_1 \in V_1$, with values $\bar{x}_1 = x_{v_1}$, and the random variable $\bar{X}_2$ of $v_2 \in V_2$, with values $\bar{x}_2 = x_{v_2}$, will become correlated given the outcomes of $V_3$ and $T, T' \in V_{\text{post}}$ in this functional model. Using Observation 1, this will induce a functional causal model on the teleportation graph $G_{\text{TP}}$ with the same distribution on the shared vertices. Through the connection between cyclic functional models on $G$ and acyclic functional models on $G_{\text{TP}}$ with post-selection on $V_{\text{post}}$ established in section 3, we will show that this model on $G_{\text{TP}}$ implies a functional causal model $f\mathfrak{C}m_G$ on the original (possibly cyclic) $G$ and imply the necessary conditional independence $(X_1 \not\perp X_2|X_3)_{\text{Pr}_G}$ between the outcomes of $V_1, V_2$ and $V_3$ in $f\mathfrak{C}m_G$.

Before defining the functional model $f\mathfrak{C}m_{G'_{\text{TP}}}$, we make another important observation.

**Observation 2:** Recall that $G'_{\text{TP}}$ is a subgraph of $G_{\text{TP}} \in \mathbb{G}_{\text{TP}}(G)$ which is a classical teleportation graph of $G$ (definition 7). Thus, the post-selection vertices, $T$, occurring in the subgraph $G'_{\text{TP}}$ only occur in the following structure where $v$ and $u$ are vertices belonging to the original graph $G$ as well as $G'_{\text{TP}}$.

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

Indeed, we chose $G'_{\text{TP}}$ to only have the edges present in a $d$-connecting (or unblocked) path associated with the $d$-connection $(X \not\perp^d Y|V_3 \cup V_{\text{post}})_{G'_{\text{TP}}}$. We now define a generic functional model applicable to any graph as follows.

**Definition 31** (A functional model on an arbitrary graph). Associate a binary outcome $x_v \in \mathcal{X}_v := \{0, 1\}$ to each vertex $v$ of the given graph. Every exogenous vertex $v \in V_{\text{ex}}$ is associated with a uniform distribution $p^v(x_v = 0) = p^v(x_v = 1) = \frac{1}{2}$ and every endogenous vertex $v \in V_{\text{end}}$ is associated with a function $x_v = f^v(x_{\text{Pa}(v)}) := \bigoplus_{u \in \text{Pa}(v)} x_u$. Here, we have chosen a functional model where the functions deterministically relate each variable to its parental variables in the graph, and have thus applied the simplification allowed by the remark of section 2.

This fully specifies the functional model (definition 1). In particular, applying the above definition to the acyclic graph $G'_{\text{TP}}$ we will denote the resulting functional model as $f\mathfrak{C}m_{G'_{\text{TP}}}$, and the induced model (by Observation 1) on $G_{\text{TP}}$, of which $G'_{\text{TP}}$ is a subgraph, as $f\mathfrak{C}m_{G'_{\text{TP}}}^{21}$.

The functional dependences in the above model encode that the outcome value for each vertex $v$ is given by the sum modulo 2 (denoted by $\bigoplus$) of all the outcomes

<footnote>$^{21}$ Observation 1 here implies that, in case the parent set of a vertex does not coincide between $G_{\text{TP}}$ and $G'_{\text{TP}}$, the association of $x_v = f^v(x_{\text{Pa}(v)}) := \bigoplus_{u \in \text{Pa}(v)} x_u$ refers to the parent set of $G'_{\text{TP}}$.</footnote>
associated with the parent vertices of $v$. In particular, note that if $u$ has exactly one parent $v$, this causal model imposes $x_u = x_v$.

We now argue for the relevant conditional independence using this functional model. We first consider a simple example of a graph $G'_{\text{TP}}$ where equation (107) and hence equation (109) are satisfied. We carry out the proof for this simple case and then argue how the general argument can be reduced to this case.

**Proof for a simple case:** We consider a specific way, using the following three paths, to implement the three $d$-connections of equation (109) respectively:

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

for some vertices $\{\tilde{v}_i\}_{i=1}^k$, none of which belong to $V_3$,

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

for some vertices $\{\tilde{u}_j\}_{j=1}^l$, none of which belong to $V_3$,

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

for some $C \in V_3$. Let $G'_{\text{TP}}$ be defined to be formed by these three unblocked paths (i.e. all vertices and edges featuring in equation (111), equation (112), equation (113) included) and the remaining vertices of the original graph $G_{\text{TP}}$ included without any of their associated edges.

Since all the vertices in $\{\tilde{v}_i\}_{i=1}^k$ and $\{\tilde{u}_j\}_{j=1}^l$ have exactly one parent in this $G'_{\text{TP}}$, one can immediately see that the functional model $fCm_{G'_{\text{TP}}}$ for this case imposes $x_{\tilde{v}_k} = x_{v_1}$ and $x_{\tilde{u}_l} = x_{v_2}$. $T$ has two parents, $\tilde{v}_k$ and $R$, with the outcomes related as $x_T = x_{\tilde{v}_k} \oplus x_R$ and similarly $T'$ has two parents, $R'$ and $\tilde{u}_l$, with the outcomes related as $x_{T'} = x_{R'} \oplus x_{\tilde{u}_l}$. Finally, we also have $x_C = x_R \oplus x_{R'}$.

If we condition on $x_C = 0$, then we have $x_R = x_{R'}$. Then notice that $x_T = x_{v_1} \oplus x_R$ and $x_{T'} = x_{v_2} \oplus x_R$, i.e., given that $x_C = 0$, we have $x_T \oplus x_{v_1} = x_{T'} \oplus x_{v_2}$. This implies that conditioned on $x_C = x_{T'} = x_T = 0$, we have perfect correlations $x_{v_1} = x_{v_2}$ between the outcomes of $v_1$ and $v_2$. We can visualize this as follows. Our causal model ensures that when we condition on $x_C = 0$, for the purpose of correlations in the model, we can equivalently reason using the following simplified graph<fnref n="22" />

<footnote n="22">²²Even though this does not have the structure of a teleportation graph, the relevant point is that $T$ and $T'$ share effectively a common cause $R$ when conditioned on $x_C = 0$.</footnote>
<figure><img src="image_13.png" /></figure>

Explicitly, recalling that $G'_{\text{TP}}$ is a directed acyclic graph we can directly compute the joint probability distribution of $f\mathbf{Cm}_{G'_{\text{TP}}}$ (definition 2). Then, the functional dependence $x_T \oplus x_{v_1} = x_{T'} \oplus x_{v_2}$, which holds when $x_C = 0$, translates to the conditional dependence

$$ (\bar{X}_1 \perp \bar{X}_2 | T=0, T'=0, C=0)_{\text{Pr}_{\text{acyc}G'_{\text{TP}}}} \quad (115) $$

where $\bar{X}_i$ denotes the random variable associated to the vertex $v_i$ for $i \in \{1, 2\}$. Note that the remaining vertices are causally disconnected in $G_{\text{TP}}$ (in the sense that are not involved in any functional dependencies, except trivially on their error variable), by construction of the way the causal model on the subgraph $G'_{\text{TP}}$ is extended to a causal model on $G_{\text{TP}}$ in Observation 1, and conditioning on the outcomes of such vertices cannot uncorrelate the remaining outcomes in an acyclic functional model. Using this, we see that equation (115) implies that $(\bar{X}_1 \perp X_2 | V_3 \cup \{T=0\}_{T \in V_{\text{post}}})_{\text{Pr}_{\text{acyc}G_{\text{TP}}}}$ also holds using definition 17, where we recall that $X_i$ is the set of variables associated to the vertex set $V_i$ for $i \in \{1, 2\}$. This trivially implies, by inclusion, that $(X_1 \perp X_2 | V_3 \cup \{T=0\}_{T \in V_{\text{post}}})_{\text{Pr}_{\text{acyc}G_{\text{TP}}}}$ holds.

Finally, to link the constructed model $f\mathbf{Cm}_{G_{\text{TP}}}$ on the teleportation graph $G_{\text{TP}} \in \mathbb{G}_{\text{TP}}(G)$ of $G$ to a causal model $f\mathbf{Cm}_G$ on the original (possibly cyclic) graph $G$, it is important to note that our mapping from cyclic functional models to acyclic functional models with post-selection relies on a particular form of post-selection at the post-selection vertices $V_{\text{post}}$. The post-selections must form a post-selected teleportation protocol (definition 3) for each pair of pre and post-selection vertices in equation (110).

Notice that the graph $G$ differs from $G_{\text{TP}}$ specifically by replacing each structure of the form equation (110) with a directed edge $v \to u$ and thus, $G$ contains no pre and post-selection vertices, only observed vertices $v$. By post-selecting on $\{t_T = 0\}_{T \in V_{\text{post}}}$ (i.e., 0 outcome on all post-selection vertices) in the causal model $f\mathbf{Cm}_{G_{\text{TP}}}$ defined on $G_{\text{TP}}$, we induce a causal model $f\mathbf{Cm}_G$ on $G$ where one replaces $r_R$ (outcome of a pre-selection vertex) appearing in any functional dependence with the outcome $x_v$ for the corresponding vertex $v$ (which has an edge to the same $T$ as $R$, as in equation (110)). This way all functional dependences are expressed only in terms of the vertices of $G$, and $f\mathbf{Cm}_G$ is a fully specified functional model on $G$.

This establishes that the constructed causal model $f\mathbf{Cm}_{G_{\text{TP}}}$ on the acyclic teleportation graph $G_{\text{TP}}$ of $G$ induces a functional model $f\mathbf{Cm}_G$ on the possibly cyclic graph $G$ where $\text{Pr}(x)_G = \text{Pr}_{\text{acyc}}(x|\{t_T = 0\}_{T \in V_{\text{post}}})_{G_{\text{TP}}}$. Here the $t_T = 0$ post-selection plays the same role as the post-selection on $x_T = 1$ in definition 12 and $x = \{x_v\}_{v \in V}$ is the set of all observed outcomes of the graph.

Therefore the conditional dependence $(X_1 \perp X_2 | X_3 \cup \{T=0\}_{T \in V_{\text{post}}})_{\text{Pr}_{\text{acyc}G_{\text{TP}}}}$ established above for the acyclic model on the teleportation graph $G_{\text{TP}}$ implies $(X_1 \perp X_2 | X_3)_{\text{Pr}_G}$, as required.
**Proof for the general case:** We now consider the case of more general paths that can ensure the *d*-connections in equation (109), as compared to the paths in equation (111), equation (112), equation (113). Consider the first *d*-connection $(v_1 \not\perp^d T|V_3)_{G'_{\text{TP}}}$ of equation (109). In the simple case of equation (111), we argued that for the correlations between outcomes in our functional model, we could equivalently consider $v_1$ as a direct cause of $T$ as in equation (114). This used the fact that the *d*-connecting path between $v_1$ and $T$ in equation (111) ensures equal outcomes for all intervening vertices in the path that are not in the conditioning set $V_3$. It is easy to see that this property holds generically for our causal model, independently of the particular *d*-connecting path equation (111), if we condition on $x_v = 0$ for every $v$ that features in this *d*-connecting path where $v$ or a descendant of it belongs to $V_3$.

We argue this through examples for simplicity, but the argument generalizes in a straightforward manner. Consider the direct cause graph $v_1 \to \tilde{v}$, and the common cause graph $v_1 \leftarrow \tilde{u} \to v$ where $\tilde{u}$ in the latter case does not belong to $V_3$ (otherwise, $v_1$ and $\tilde{v}$ would be *d*-separated by conditioning on $V_3$). In both these cases, the causal model from definition 31 ensures $x_{v_1} = x_{\tilde{v}}$ ($= x_{\tilde{u}}$). Now consider the collider graph $v_1 \to \tilde{u} \to \tilde{v}$ where $\tilde{u} \in V_3$ (so that $v_1$ and $\tilde{v}$ are *d*-connected given $V_3$). Our causal model ensures that $x_{\tilde{u}} = x_{v_1} \oplus x_{\tilde{v}}$ i.e., if we post-select on $x_{\tilde{u}} = 0$, we have equality $x_{v_1} = x_{\tilde{v}}$. Even if $\tilde{u} \notin V_3$ but $\tilde{u}$ is a descendant of $u' \in V_3$, this means we have a directed path from $\tilde{u}$ to $u'$ and conditioning on $x_{u'} = 0$ would give $x_{\tilde{u}} = 0$ and thereby $x_{v_1} = x_{\tilde{v}}$. Note that as we apply the functional model defined in definition 31 to the subgraph $G'_{\text{TP}}$ comprised only of edges in a relevant *d*-connecting path, any such colliders $\tilde{u}$ will only have at most two children (two children if it is itself a collider and one child if it is a descendant of a collider) in $G'_{\text{TP}}$ even if this vertex has more parents in $G_{\text{TP}}$.

In a similar manner, we can consider the second *d*-connection $(v_2 \not\perp^d T'|V_3)_{G'_{\text{TP}}}$ of equation (109) and obtain that for the purpose of our arguments, we can equivalently consider $v_2$ as a direct cause of $T'$ as in equation (114).

Finally for the third *d*-connection $(T \not\perp^d T'|V_3)_{G'_{\text{TP}}}$ of equation (109), we can apply a similar argument as well. In equation (113), the central observed vertex $C$ acts as a collider. We may also have a situation where it acts as part of a chain.

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

In this case, for this to be the *d*-connecting path for the third condition of equation (109), we must have $C \notin V_3$. The causal model of definition 31 for this case entails $x_C = x_R$, i.e., this is again equivalent to $T$ and $T'$ sharing the same common cause $R$ as in equation (114).

Another case is where $C$ is a common cause of $T$ and $T'$ (then $C \notin V_3$), here we already have the structure of equation (114) (it does not matter for our arguments whether the common cause is $C$ or $R$, the causal model behaves in
the same way). More generally, $T$ and $T'$ could be $d$-connected through paths that have additional intervening vertices $T'' \in V_{\text{post}}$ which are conditioned on. These arguments straightforwardly generalize to that case, post-selecting on the 0 value of all such vertices again reduces our arguments to a situation of the form of equation (114).

Therefore all the steps following equation (114) also apply to the general case, allowing us to establish the required conditional independence $(X_1 \perp X_2 | X_3)_{\text{Pr}_G}$.

This completes the proof.

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

## C Proofs of section 5

**Proposition 23** (Average number of solutions and success probability). Consider a functional causal model over a directed graph $G = (V, E)$, $f\mathbf{C}m_G$. Let $G_{\text{TP}} \in \mathbb{G}_{\text{TP}}(G)$ be a teleportation graph and $f\mathbf{C}m_{G_{\text{TP}}}$ the corresponding teleportation causal model constructed from $f\mathbf{C}m_G$. The post-selection success probability $p_s$ (definition 10) of $f\mathbf{C}m_{G_{\text{TP}}}$ satisfies

$$p_s = \left( \prod_{v \in V_s(G_{\text{TP}})} p_{\text{TP}}^{(v)} \right) \bar{N}_{f\mathbf{C}m}, \qquad (70)$$

where $V_s(G_{\text{TP}})$ is the set of split vertices of $G_{\text{TP}}$ and $p_{\text{TP}}^{(v)}$ is the teleportation probability associated to the classical post-selected teleportation protocol implemented for the split vertex $v \in V_s(G_{\text{TP}})$.

*Proof.* Let us denote with

$$p_s^{G_{\text{TP}}} = \mathrm{Pr}_{\mathrm{acyc}} (\{t_T = 1\}_{T \in V_{\text{post}}} )_{G_{\text{TP}}}, \qquad (117)$$

the success probability relative to $G_{\text{TP}} \in \mathbb{G}_{\text{TP}}(G)$, with post-selection set $V_{\text{post}}$. We first prove the statement for a specific teleportation graph.

Consider the teleportation graph $G_0 \in \mathbb{G}_{\text{TP}}(G)$ where $V_s(G_0) = V$, i.e., all vertices are split and associated with pre- and post-selection vertices and edges as in definition 9. Therefore, the set of vertices of $G_0$ is $V_0 = V \cup \{R_v, T_v\}_{v \in V}$. For each $v \in V$ we denote with $(f^v, \mathcal{P}_B^v, \mathcal{P}_C^v)$ the augmented post-selected teleportation protocol associated to the corresponding pre and post-selection pair.

Since all vertices are split, for each vertex $v \in V$ the variable associated to $v$, $x_v$ is the value associated to such vertex, obtained through $f^v$, and the variable associated to the reconsigning pre-selection vertex $R_v$, $r_v$, acts as input of the functions $f^{v'}$ where $v' \in \text{Ch}(v)$. Thus, denoting with $t_v \in \{0, 1\}$ the values associated to $T_v$ and with $r := \{r_v \in \mathcal{X}_v\}_{v \in V}$ the values associated to the preselection vertices $\{R_v\}_{v \in V}$, we have (definition 2)

$$
\begin{align*}
\mathrm{Pr}_{\mathrm{acyc}}(\{t_v = 1\}_{v \in V})_{G_0} &= \sum_{r,x} \mathrm{Pr}_{\mathrm{acyc}}(x, r, \{t_v = 1\}_{v \in V})_{G_0} \\
&= \sum_{r,b,x,u} \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(r_{\mathrm{Pa}(v)}, u_v)} \delta_{f^v(x_v, b_v, r_v), 1} \mathcal{P}_B^v(b_v) \mathcal{P}_C^v(r_v) \\
\stackrel{\text{lem. 5}}{=} & \sum_{r,x,u} \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(r_{\mathrm{Pa}(v)}, u_v)} p_{\text{TP}}^{(v)} \delta_{x_v, r_v} \\
& = p_{\text{TP}}^{\text{tot}} \sum_{x,u} \prod_{v \in V} p^v(u_v) \delta_{x_v, f^v(x_{\mathrm{Pa}(v)}, u_v)}
\end{align*}
$$
$$ 
\begin{aligned}
&= p_{\text{TP}}^{\text{tot}} \sum_{u} \prod_{v \in V} p^{v}(u_{v}) N_{\text{fCm}}(u) \\
&= p_{\text{TP}}^{\text{tot}} \bar{N}_{\text{fCm}},
\end{aligned} 
\qquad (118) $$

where $p_{\text{TP}}^{\text{tot}} = \prod_{v \in V} p_{\text{TP}}^{(v)}$ and $p_{\text{TP}}^{(v)}$ is the probability of successful post-selection of the implementation chosen for the vertex $v$.

Consider an arbitrary teleportation graph $G_{\text{TP}} \in \mathcal{G}_{\text{TP}}(G)$ with $V_{\text{S}}(G_{\text{TP}}) \subseteq V$. In the proof of proposition 11 we related the success probabilities of two teleportation graphs. By applying recursively equation (101) we get

$$ p_{\text{S}}^{(G_{\text{TP}})} = \left( \frac{p_{\text{TP}}^{\text{tot}}}{\prod_{v \notin V_{\text{S}}(G_{\text{TP}})} p_{\text{TP}}^{(v)}} \right) \bar{N}_{\text{fCm}} = \left( \prod_{v \in V_{\text{S}}(G_{\text{TP}})} p_{\text{TP}}^{(v)} \right) \bar{N}_{\text{fCm}}, \qquad (119) $$

which completes the proof. $\square$

**Proposition 27** (Unique solvability implies average unique solvability). A uniquely solvable functional model is also averagely uniquely solvable.

*Proof.* Consider a uniquely solvable functional model: it holds that

$$ \bar{N}_{\text{fCm}} = \sum_{x} \prod_{v \in V} p^{v}(u_{v}) N_{\text{fCm}}(u) = \sum_{x} \prod_{v \in V} p^{v}(u_{v}) = 1, \qquad (120) $$

where the sum runs over $x = \{x_v \in \mathcal{X}_v\}_{v \in V}$. $\square$