Analysing causal structures with entropy

(i) Outer approximation: the Shannon cone

The standard outer approximation to $\overline{{\mathit{\Gamma }}_n^{\ast }}$ is the polyhedral cone constrained by the Shannon inequalities listed in the following:

• — Monotonicity. For all X_T, X_S⊆Ω, H(X_S∖X_T)≤H(X_S).

• — Submodularity. For all X_S, X_T⊆Ω, H(X_S∩X_T)+H(X_S∪X_T)≤H(X_S)+H(X_T).

It is a matter of convention, whether H({})=0 is included as a Shannon inequality; we keep this implicit.

These inequalities are always obeyed by the entropies of a set of jointly distributed random variables. They may be concisely rewritten in terms of the following information measures: the conditional entropy of two jointly distributed random variables X and Y , H(X | Y):=H(XY)−H(Y), their mutual information, I(X:Y):=H(X)+H(Y)−H(XY), and the conditional mutual information between two jointly distributed random variables X and Y given a third, Z, defined by I(X:Y | Z):=H(XZ)+H(Y Z)−H(Z)−H(XY Z). Hence, the monotonicity constraints correspond to positivity of conditional entropy, H(X_S∩X_T | X_S∖X_T)≥0, and submodularity is equivalent to positivity of the conditional mutual information, I(X_S∖X_T:X_T∖X_S | X_S∩X_T)≥0. The monotonicity and submodularity constraints can all be generated from a minimal set of n+n(n−1)2ⁿ⁻³ inequalities [33]: for the monotonicity constraints it is sufficient to consider the n constraints with X_S=Ω and X_T=X_i for some X_i∈Ω; for the submodularity constraints it is sufficient to consider those with X_S∖X_T=X_i and X_T∖X_S=X_j with i<j and where X_U:=X_S∩X_T is any subset of Ω not containing X_i or X_j, i.e. submodularity constraints of the form I(X_i:X_j | X_U)≥0.

These n+n(n−1)2ⁿ⁻³ independent Shannon inequalities can be expressed in terms of a (n+n(n−1)2ⁿ⁻³)×(2ⁿ−1)-dimensional matrix, which we call $M_{\mathrm{SH}}^n$, such that, for any $v\in {\mathit{\Gamma }}_n^{\ast }$, the conditions $M_{\mathrm{SH}}^n\cdot v\ge 0$ hold (these are to be interpreted as the requirement that each component of $M_{\mathrm{SH}}^n\cdot v$ is non-negative). More generally, for $v\in {\mathbb{R}}_{\ge 0}^{2^n-1}$, a violation of $M_{\mathrm{SH}}^n\cdot v\ge 0$ certifies that there is no distribution $P\in {\mathcal{P}}_n$ such that v=H(P). It follows that the Shannon cone, ${\mathit{\Gamma }}_n:=\{v\in {\mathbb{R}}_{\ge 0}^{2^n-1}\mid M_{\mathrm{SH}}^n\cdot v\ge 0\}$, is an outer approximation of the set of achievable entropy vectors, ${\mathit{\Gamma }}_n^{\ast }$ [33].

Example 2.1.

The three-variable Shannon cone is ${\mathit{\Gamma }}_3=\{v\in {\mathbb{R}}_{\ge 0}^7\mid M_{\mathrm{SH}}^3\cdot v\ge 0\}$, where

The first three rows are monotonicity constraints; the remaining six ensure submodularity.

(ii) Beyond the Shannon cone

For two variables the Shannon cone coincides with the actual entropy cone, ${\mathit{\Gamma }}_2={\mathit{\Gamma }}_2^{\ast }$, while for three random variables this holds only for the closure of the entropic cone, i.e. ${\mathit{\Gamma }}_3=\overline{{\mathit{\Gamma }}_3^{\ast }}$ but ${\mathit{\Gamma }}_3\ne {\mathit{\Gamma }}_3^{\ast }$ [36,37]. For n≥4, further independent constraints on the set of entropy vectors are needed to fully characterize $\overline{{\mathit{\Gamma }}_n^{\ast }}$, the first of which was discovered in [38].

Proposition 2.2 (Zhang & Yeung).

For any four discrete random variables T, U, V and W the following inequality holds: $-H(T)-H(U)-\frac{1}{2}H(V)+\frac{3}{2}H(TU)+\frac{3}{2}H(TV)+\frac{1}{2}H(TW)+\frac{3}{2}H(UV)+\frac{1}{2}H(UW)-\frac{1}{2}H(VW)-2H(TUV)-\frac{1}{2}H(TUW)\ge 0$.

For n≥4, the convex cone $\overline{{\mathit{\Gamma }}_n^{\ast }}⊊{\mathit{\Gamma }}_n$ is not polyhedral, i.e. it cannot be characterized by finitely many linear inequalities [39]. Nonetheless, many linear entropic inequalities have been discovered [36,38,40,41]. Recently, systematic searches for new entropic inequalities for n=4 have been conducted [42,43], which recover most of the previously known inequalities; in particular, the inequality of proposition 2.2 is rederived and shown to be implied by tighter ones [43]. The systematic search in [43] is based on considering additional random variables that obey certain constraints and then deriving four-variable inequalities from the known identities for five or more random variables (see also [38,39]), an idea that is captured by a so-called copy lemma [38,43,44]. In the same article, several rules to generate families of inequalities have been suggested, in the style of techniques introduced by Matúš [39].

For more than four variables, a few additional inequalities are known [38,40]. Curiously, to our knowledge, all known relevant non-Shannon inequalities (i.e. the ones found in [38–43] that are not yet superseded by tighter ones) can be written as a positive linear combination of the Ingleton quantity, I(T:U | V)+I(T:U | W)+I(V :W)−I(T:U), and conditional mutual information terms (see also [43]).

(iii) Inner approximations

Inner approximations are constructed from a set of conditions that are sufficient for an entropy vector to be realized by a distribution. Such conditions can be stated in terms of so-called linear rank inequalities [45–48]. They can be useful for establishing tightness of outer approximations.

For the four-variable entropy cone, $\overline{{\mathit{\Gamma }}_4^{\ast }}$, an inner approximation is defined as the region constrained by the Shannon inequalities and the six permutations of the Ingleton inequality [45], I(T:U | V)+I(T:U | W)+I(V :W)−I(T:U)≥0, for random variables T, U, V and W. These inequalities can be concisely written as a matrix $M_I\in {\mathbb{R}}^6\times {\mathbb{R}}^{15}$. The constrained region is called the Ingleton cone, ${\mathit{\Gamma }}^{\mathrm{I}}:=\{v\in {\mathbb{R}}_{\ge 0}^{15}\mid M_{\mathrm{SH}}^4\cdot v\ge 0\text{ and }{M}_I\cdot v\ge 0\},$ and it has the property that v∈Γ^I implies v∈Γ*_n [46]. By contrast, there are entropy vectors that violate the Ingleton inequalities, as the following example shows.

Example 2.3.

Let T, U, V and W be four jointly distributed random variables. Let V and W be uniform random bits and let T=AND(¬V,¬W) and U=AND(V,W). This distribution [39] leads to the entropy vector v≈(0.81,0.81,1,1,1.50,1.50,1.50,1.50,1.50,2,2,2,2,2,2), for which I(T:U | V)+I(T:U | W)+I(V :W)−I(T:U)≈−0.12 in violation of the Ingleton inequality.

For five random variables an inner approximation in terms of Shannon, Ingleton and 24 additional inequalities and their permutations is known (including partial extensions to more variables) [47,48].

(i) Classical causal structures

In the classical case, the causal relations among a set of random variables can be explored by means of the theory of Bayesian networks (see, for instance, [1,2] for a complete presentation of this theory).

Definition 2.5.

A classical causal structure, C^C, is a causal structure in which each node of the DAG has an associated random variable.

It is common to use the same label for the node and its associated random variable. The DAG encodes which joint distributions of the involved variables are allowed in a causal structure C^C. To explain this, we need a little more terminology.

Definition 2.6.

Let X_S, X_T, X_U be three disjoint sets of jointly distributed random variables. Then X_S and X_T are said to be conditionally independent given X_U if and only if their joint distribution P_XSXTXU can be written as P_XSXTXU= P_XS | XUP_XT | XUP_XU. Conditional independence of X_S and X_T given X_U is denoted as X_S ⫫ X_T | X_U.

Two variables X_S and X_T are (unconditionally) independent if P_XSXT=P_XSP_XT, concisely written X_S ⫫ X_T. With reference to a DAG with a subset of nodes, X, we will use X^↓ to denote the ancestors of X and X^↑ to denote the descendants of X. The parents of X are represented by X^↓₁ and the non-descendants are X^⤉ .

Definition 2.7.

Let C^C be a classical causal structure with nodes {X₁,X₂,…,X_n}. A probability distribution $P_{X_1{X}_2\cdots X_n}\in {\mathcal{P}}_n$ is (Markov) compatible with C^C if it can be decomposed as $P_{X_1{X}_2\cdots X_n}=\prod _i{P}_{X_i\hspace{0.17em}|\hspace{0.17em}{X}_i^{{\downarrow }_1}}$.

The compatibility constraint encodes all conditional independences of the random variables in the causal structure C^C. Nonetheless, whether a particular set of variables is conditionally independent of another is more easily read from the DAG, as explained in the following.

Definition 2.8.

Let X, Y and Z be three pairwise disjoint sets of nodes in a DAG G. The sets X and Y are said to be d-separated by Z, if Z blocks any path from any node in X to any node in Y . A path is blocked by Z if the path contains one of the following: $i\to z\to j$ or $i\leftarrow z\to j$ for some nodes i, j and a node z∈Z in that path, or if the path contains $i\to k\leftarrow j$, where k∉Z.

The d-separation of the nodes in a causal structure is directly related to the conditional independence of its variables. The following proposition corresponds to theorem 1.2.5 from [1], previously introduced in [51,52]. It justifies the application of d-separation as a means to identify independent variables.

Proposition 2.9 (Verma & Pearl).

Let C^C be a classical causal structure and let X, Y and Z be pairwise disjoint subsets of nodes in C^C. If a probability distribution P is compatible with C^C, then the d-separation of X and Y by Z implies the conditional independence X ⫫ Y | Z. Conversely, if, for every distribution P compatible with C^C, the conditional independence X ⫫ Y | Z holds, then X is d-separated from Y by Z.

The compatibility of probability distributions with a classical causal structure is conveniently determined with the following proposition, which has also been called the parental or local Markov condition before (theorem 1.2.7 in [1]).

Proposition 2.10 (Pearl).

Let C^C be a classical causal structure. A probability distribution P is compatible with C^C if and only if every variable in C^C is independent of its non-descendants, conditioned on its parents.

Hence, to establish whether a probability distribution is compatible with a certain classical causal structure, it is enough to check that every variable X is independent of its non-descendants X^⤉ given its parents X^↓₁, concisely written as X ⫫ X^⤉ | X^↓₁, i.e. to check one constraint for each variable. In particular, it is not necessary to explicitly check for all possible sets of nodes whether they obey the independence relations implied by d-separation. Each such constraint can be conveniently expressed as

This follows because the relative entropy $D(P\hspace{0.17em}\parallel \hspace{0.17em}Q):=\sum _x{P}_X(x)\log (P_X(x)/Q_X(x))$ satisfies D(P ∥ Q)=0 ⇔ P=Q, and because I(X:X^⤉ | X^↓₁)=D(P_XX^⤉X^↓1 ∥ P_{X | X^↓1}P_{X^⤉ | X^↓1}P_X^↓1).

While the conditional independence relations capture some features of the causal structure, they are insufficient to completely capture the causal relations between variables, as illustrated in figure 2. In this case, the probability distributions themselves are unable to capture the difference between these causal structures: correlations are insufficient to determine causal links between random variables. External interventions allow for the exploration of causal links beyond the conditional independences [1]. However, we do not consider these here.

• Download figure
• Open in new tab
• Download PowerPoint

Let C^C be a classical causal structure involving n random variables {X₁,X₂,…,X_n}. The restricted set of distributions that are compatible with the causal structure C^C is $\mathcal{P}(C^{\mathrm{C}}):=\{P\in {\mathcal{P}}_n\mid P=\prod _{i=1}^n{P}_{X_i\hspace{0.17em}|\hspace{0.17em}{X}_i^{{\downarrow }_1}}\}$.

Example 2.11 (Allowed distributions in the instrumental scenario).

The classical instrumental scenario of figure 1a allows for any four-variable distribution in the set $\mathcal{P}({IC}^{\mathrm{C}})=\{P_{AXYZ}\in {\mathcal{P}}_4\mid P_{AXYZ}=P_{Y\hspace{0.17em}|\hspace{0.17em}AZ}{P}_{Z\hspace{0.17em}|\hspace{0.17em}AX}{P}_X{P}_A\}.$

The restrictions on the allowed distributions also restrict the corresponding entropy cones. Owing to proposition 2.10 there are at most n independent conditional independence equalities (2.1) in a causal structure C^C. Their coefficients can be concisely written in terms of a matrix M_CI(C^C), where CI stands for conditional independence. For a causal structure C^C, we define the two sets ${\mathit{\Gamma }}^{\ast }(C^{\mathrm{C}}):=\{v\in {\mathit{\Gamma }}_n^{\ast }\mid M_{\mathrm{CI}}(C^{\mathrm{C}})\cdot v=0\}$ and Γ(C^C):={v∈Γ_n|M_CI(C^C)⋅v=0}, where Γ*(C^C)⊆Γ(C^C). The following lemma justifies the notation we use for Γ*(C^C); it is the set of achievable entropy vectors in C^C.

Lemma 2.12.

For a causal structure C^C, ${\mathit{\Gamma }}^{\ast }(C^{\mathrm{C}})=\{v\in {\mathbb{R}}_{\ge 0}^{2^n-1}\mid \mathrm{\exists }P=\prod _{i=1}^n{P}_{X_i\hspace{0.17em}|\hspace{0.17em}{X}_i^{{\downarrow }_1}}\in {\mathcal{P}}_n\hspace{0.17em}\text{s.t.}\hspace{0.17em}v=\mathbf{\text{H}}(P)\}$. Furthermore, its topological closure, $\overline{{\mathit{\Gamma }}^{\ast }}(C^{\mathrm{C}})=\{v\in \overline{{\mathit{\Gamma }}_n^{\ast }}\mid M_{\mathrm{CI}}(C^{\mathrm{C}})\cdot v=0\},$ is a convex cone.

Proof.

For the causal structure C^C, let $E(C^{\mathrm{C}}):=\{v\in {\mathbb{R}}_{\ge 0}^{2^n-1}\mid \mathrm{\exists }P=\prod _{i=1}^n{P}_{X_i\hspace{0.17em}|\hspace{0.17em}{X}_i^{{\downarrow }_1}}\in {\mathcal{P}}_n\hspace{0.17em}\text{s.t.}\hspace{0.17em}v=\mathbf{\text{H}}(P)\}$ be the set of all entropy vectors. As (2.1) holds for each variable X_i if and only if $P=\prod _{i=1}^n{P}_{X_i\hspace{0.17em}|\hspace{0.17em}{X}_i^{{\downarrow }_1}}$ (cf. proposition 2.10), $E(C^{\mathrm{C}})=\{v\in {\mathit{\Gamma }}_n^{\ast }\hspace{0.17em}|\hspace{0.17em}\mathrm{\forall }\hspace{0.17em}i\in \{1,\dots ,n\},I(X_i:X_i^{⤉}\hspace{0.17em}|\hspace{0.17em}{X}_i^{{\downarrow }_1})=0\}$. Applying the definition of M_CI(C^C) yields E(C^C)=Γ*(C^C). Now, let us consider the set $F(C^{\mathrm{C}}):=\{v\in \overline{{\mathit{\Gamma }}_n^{\ast }}\mid M_{\mathrm{CI}}(C^{\mathrm{C}})\cdot v=0\}\subseteq {\mathbb{R}}^{2^n-1}$. This is a closed convex set, because $\overline{{\mathit{\Gamma }}_n^{\ast }}$ is known to be closed and convex [36] and because restricting the closed convex cone $\overline{{\mathit{\Gamma }}_n^{\ast }}$ with linear equality constraints retains these properties. More precisely, the set of solutions to the matrix equality M_CI(C^C)⋅v=0 is also closed and convex. Being the intersection of two closed convex sets, the set F(C^C) is also closed and convex. From this we conclude that $\overline{{\mathit{\Gamma }}^{\ast }}(C^{\mathrm{C}})$ is convex because $\overline{{\mathit{\Gamma }}^{\ast }}(C^{\mathrm{C}})=\overline{\{v\in {\mathit{\Gamma }}_n^{\ast }\hspace{0.17em}|\hspace{0.17em}{M}_{\mathrm{CI}}(C^{\mathrm{C}})\cdot v=0\}}$ equals F(C^C). (Because F(C^C) is closed, any element w∈F(C^C), in particular any element on its boundary, is the limit of a sequence of elements {w_k}_k for $k\to \mathrm{\infty }$, where the w_k lie in the interior of F(C^C) for all k. Hence $w\in \overline{{\mathit{\Gamma }}^{\ast }}(C^{\mathrm{C}})$.) □

The convexity of $\overline{{\mathit{\Gamma }}^{\ast }}(C^{\mathrm{C}})$ is crucial for the considerations of the following sections. Note that, in spite of the convexity of $\overline{{\mathit{\Gamma }}^{\ast }}(C^{\mathrm{C}})$, the set $\mathcal{P}(C^{\mathrm{C}})$ is generally not convex. This alludes to the fact that significant information about the achievable correlations among the random variables is lost via the mapping from $\mathcal{P}(C^{\mathrm{C}})$ to the corresponding entropic cone $\overline{{\mathit{\Gamma }}^{\ast }}(C^{\mathrm{C}})$.

Example 2.13 (Entropic outer approximation for the instrumental scenario).

The instrumental scenario has at most four independent conditional independence equalities (2.1). We find that there are only two, I(A:X)=0 and I(Y :X|AZ)=0. This yields $\overline{{\mathit{\Gamma }}^{\ast }}({IC}^{\mathrm{C}})=\{v\in \overline{{\mathit{\Gamma }}_4^{\ast }}\mid M_{\mathrm{CI}}({IC}^{\mathrm{C}})\cdot v=0\}$ with

where the coordinates are ordered as (H(A), H(X), H(Y), H(Z), H(AX), H(AY), H(AZ), H(XY), H(XZ), H(Y Z), H(AXY), H(AXZ), H(AY Z), H(XY Z), H(AXY Z)). An outer approximation is given by Γ(IC^C)={v∈Γ₄|M_CI(IC^C)⋅v=0}.

In general, the outer approximation to $\overline{{\mathit{\Gamma }}^{\ast }}(C^{\mathrm{C}})$ can be further tightened by taking non-Shannon inequalities into account. These have lead to the derivation of numerous new entropic inequalities for various causal structures [50] (see e.g. the triangle causal structure of figure 1c). For the instrumental scenario, however, such additional inequalities are irrelevant. This can, for instance, be seen by constructing the following inner approximation to the cone.

Example 2.14 (Entropic inner approximation for the instrumental scenario [50]).

] For the instrumental scenario an inner approximation is given in terms of the Ingleton cone and the conditional independence constraints from the previous example, Γ^I(IC^C)={v∈Γ^I|M_CI(IC^C)⋅v=0}. For this causal structure the Ingleton constraints are implied by the Shannon inequalities and the conditional independence constraints and, hence, inner and outer approximation coincide. Consequently, they also coincide with the actual entropy cone, i.e. ${\mathit{\Gamma }}^{\mathrm{I}}({IC}^{\mathrm{C}})=\mathit{\Gamma }({IC}^{\mathrm{C}})=\overline{{\mathit{\Gamma }}^{\ast }}({IC}^{\mathrm{C}})$. In particular, non-Shannon entropic inequalities cannot improve the outer approximation in this example.

Inner approximations have been considered in [50]. They are particularly useful in cases where identical inner and outer approximations are found, where they identify the actual boundary of the entropy cone. In other cases, they can allow parts of the actual boundary to be identified or give clues on how to find better outer approximations.

Arguably all interesting scenarios (such as the previous example) involve unobserved variables that are suspected to cause some of the correlations between the variables we observe. These unobserved variables may yield constraints on the possible joint distributions of the observed variables, a well-known example being a Bell inequality [30] (for a detailed discussion of the significance of Bell inequality violation on classical causal structures see [31]). More generally, we would like to infer constraints on the observed variables that follow from the presence of unobserved variables.

For a causal structure on n random variables {X₁,X₂,…,X_n}, the restriction to the set of observed variables is called its marginal scenario, denoted by $\mathcal{M}$. Here, we assume w.l.o.g. that the first k≤n variables are observed and the remaining n−k are not. We are thus interested in the correlations among the first k variables that can be obtained as the marginal of some distribution over all n variables. Without any causal restrictions the set of all probability distributions of the k observed variables is ${\mathcal{P}}_{\mathcal{M}}:=\{P\in {\mathcal{P}}_k\mid P=\sum _{X_{k+1},\dots ,X_n}{P}_{X_1{X}_2\cdots X_n}\},$ i.e. ${\mathcal{P}}_{\mathcal{M}}={\mathcal{P}}_k$. For a classical causal structure C^C on the set of variables {X₁,X₂,…,X_n}, marginalizing all distributions $P\in \mathcal{P}(C^{\mathrm{C}})$ over the n−k unobserved variables leads to the set ${\mathcal{P}}_{\mathcal{M}}(C^{\mathrm{C}}):=\{P\in {\mathcal{P}}_k\mid P=\sum _{X_{k+1},\dots ,X_n}\prod _{i=1}^n{P}_{X_i\hspace{0.17em}|\hspace{0.17em}{X}_i^{{\downarrow }_1}}\}$. In contrast with the unrestricted case, this set of distributions is, in general, not recovered by considering a causal structure that involves only k observed random variables, as can be seen in the following example.

Example 2.15 (Observed distributions in the instrumental scenario).

For the instrumental scenario, the observed variables are X, Y and Z and their joint distribution is of the form ${\mathcal{P}}_{\mathcal{M}}({IC}^{\mathrm{C}})=\{P_{XYZ}\in {\mathcal{P}}_3\mid P_{XYZ}=\sum _A{P}_{Y\hspace{0.17em}|\hspace{0.17em}AZ}{P}_{Z\hspace{0.17em}|\hspace{0.17em}AX}{P}_X{P}_A\}$.

The first entropic inequalities for a marginal scenario were derived in [12], where certificates for the existence of common ancestors of a subset of the observed random variables of at least a certain size were given. One such scenario is the triangle causal structure of figure 1c. The systematic entropy vector approach was devised for classical causal structures in [6,8,10]. An outer approximation to the entropic cones of a variety of causal structures was given in [11]. In the following we give the details of this approach.

In the entropic picture, marginalization is performed by eliminating the coordinates that represent entropies of sets of variables containing at least one unobserved variable from the vectors. This corresponds to a projection of a cone in ${\mathbb{R}}^{2^n-1}$ to its marginal cone in ${\mathbb{R}}^{2^k-1}$ [9]. We will denote this projection ${\pi }_{\mathcal{M}}:{\mathbb{R}}^{2^n-1}\to {\mathbb{R}}^{2^k-1}$. It gives all entropy vectors w of the observed sets of variables, i.e. of the marginal scenario $\mathcal{M}$, for which there exists at least one entropy vector v in the original scenario with matching entropies on the observed variables.

Starting from the set of all entropy vectors, Γ*(C^C), those relevant for the marginal scenario can be obtained by discarding the appropriate components. For a finitely generated cone such as Γ(C^C), its projection can be more efficiently determined from the projection of its extremal rays. In the dual description of the entropic cone in terms of its facets (i.e. its inequality description), the transition to the marginal scenario can be made computationally by eliminating all entropies of sets of variables not contained in $\mathcal{M}$ from the system of inequalities. The standard algorithm that achieves this is Fourier–Motzkin elimination [53], which has been used in this context in [6,8,9].

Without any causal restrictions, the entropy cone $\overline{{\mathit{\Gamma }}_n^{\ast }}$ is projected to the marginal cone $\overline{{\mathit{\Gamma }}_{\mathcal{M}}^{\ast }}:=\{w\in {\mathbb{R}}_{\ge 0}^{2^k-1}\mid \mathrm{\exists }v\in \overline{{\mathit{\Gamma }}_n^{\ast }}\text{ s.t. }w={\pi }_{\mathcal{M}}(v)\}$. Note that if we marginalize $\overline{{\mathit{\Gamma }}_n^{\ast }}$ over n−k variables, we recover the entropy cone for k random variables, i.e. $\overline{{\mathit{\Gamma }}_{\mathcal{M}}^{\ast }}=\overline{{\mathit{\Gamma }}_k^{\ast }}$. The same applies to the outer approximations: The n variable Shannon cone Γ_n is projected to the k variable Shannon cone with the mapping ${\pi }_{\mathcal{M}}$, i.e. ${\mathit{\Gamma }}_{\mathcal{M}}:=\{w\in {\mathbb{R}}_{\ge 0}^{2^k-1}\mid \mathrm{\exists }v\in {\mathit{\Gamma }}_n\text{ s.t. }w={\pi }_{\mathcal{M}}(v)\}={\mathit{\Gamma }}_k$. This follows because the n variable Shannon constraints contain the corresponding k variable constraints as a subset, and because any vector in Γ_k can be extended to a vector in Γ_n, for instance, by taking H(X_k+1)=H(X_k+2)=⋯=H(X_n)=0 and H(X_S∪X_T)=H(X_S) for any X_T⊆{X_k+1,X_k+2,…,X_n}.

For a classical causal structure C^C, we will be interested in the set $\overline{{\mathit{\Gamma }}_{\mathcal{M}}^{\ast }}(C^{\mathrm{C}}):=\{w\in {\mathbb{R}}_{\ge 0}^{2^k-1}\mid \mathrm{\exists }v\in \overline{{\mathit{\Gamma }}^{\ast }}(C^{\mathrm{C}})\hspace{0.17em}\mathrm{s}.\mathrm{t}.\hspace{0.17em}w={\pi }_{\mathcal{M}}(v)\}$, which is by construction a convex cone, because projection preserves convexity. The following lemma confirms that this is the entropy cone of the marginal scenario $\mathcal{M}$ and thus also formally justifies the method of projecting the sets directly.

Lemma 2.16.

$\overline{{\mathit{\Gamma }}_{\mathcal{M}}^{\ast }}(C^{\mathrm{C}})$ is equal to the set of entropy vectors compatible with the marginal scenario of the classical causal structure C^C, i.e. $\overline{{\mathit{\Gamma }}_{\mathcal{M}}^{\ast }}(C^{\mathrm{C}})=\overline{\{w\in {\mathbb{R}}_{\ge 0}^{2^k-1}\mid \mathrm{\exists }P\in {\mathcal{P}}_{\mathcal{M}}(C^{\mathrm{C}})\hspace{0.17em}\mathrm{s}.\mathrm{t}.\hspace{0.17em}w=\mathbf{\text{H}}(P)\}}$.

Proof.

Let $\mathcal{F}$ denote the set on the rhs of the statement in the lemma. Note that $w\in {\mathit{\Gamma }}_{\mathcal{M}}^{\ast }(C^{\mathrm{C}})$ implies that there exists v∈Γ*(C^C) s.t. $w={\pi }_{\mathcal{M}}(v)$. Using lemma 2.12, we have v=H(P) for some $P=\prod _i{P}_{X_i\hspace{0.17em}|\hspace{0.17em}{X}_i^{{\downarrow }_1}}$. If we take $P^{\prime }=\sum _{X_{k+1},\dots ,X_n}P,$ then w=H(P′) and hence $w\in \mathcal{F}$.

Conversely, $w\in \mathcal{F}$ implies that there exists $P^{\prime }\in {\mathcal{P}}_{\mathcal{M}}(C^{\mathrm{C}})$ s.t. w=H(P′) and, hence, there exists $P\in \mathcal{P}(C^{\mathrm{C}})$ such that $P^{\prime }=\sum _{X_{k+1},\dots ,X_n}P$. If we take v=H(P), then $w={\pi }_{\mathcal{M}}(v)$ and hence $w\in {\mathit{\Gamma }}_{\mathcal{M}}^{\ast }(C^{\mathrm{C}})$. Taking the topological closure of both sets concludes the proof. ▪

An outer approximation to $\overline{{\mathit{\Gamma }}_{\mathcal{M}}^{\ast }}(C^{\mathrm{C}})$ is ${\mathit{\Gamma }}_{\mathcal{M}}(C^{\mathrm{C}}):=\{w\in {\mathbb{R}}_{\ge 0}^{2^k-1}\mid \mathrm{\exists }v\in \mathit{\Gamma }(C^{\mathrm{C}})\hspace{0.17em}\mathrm{s}.\mathrm{t}.\hspace{0.17em}w={\pi }_{\mathcal{M}}(v)\}$, which can be written as ${\mathit{\Gamma }}_{\mathcal{M}}(C^{\mathrm{C}})=\{w\in {\mathit{\Gamma }}_{\mathcal{M}}\mid M_{\mathcal{M}}(C^{\mathrm{C}})\cdot w\ge 0\}$, where $M_{\mathcal{M}}(C^{\mathrm{C}})$ is the matrix obtained via Fourier-Motzkin elimination and encodes the set of inequalities on ${\mathbb{R}}_{\ge 0}^{2^k-1}$ that are implied by the fact that M_CI(C^C)⋅v=0 and Mⁿ_SH⋅v≥0 hold on ${\mathbb{R}}_{\ge 0}^{2^n-1}$ (except for the k-variable Shannon constraints which are already included in ${\mathit{\Gamma }}_{\mathcal{M}}$).

Example 2.17 (Entropic outer approximation for the marginal cone of the instrumental scenario [10,11]).

] For the instrumental scenario, the outer approximation to its marginal cone is found by projecting Γ(IC^C) to its three variable scenario and yields ${\mathit{\Gamma }}_{\mathcal{M}}({IC}^{\mathrm{C}})=\{w\in {\mathit{\Gamma }}_{\mathcal{M}}\mid M_{\mathcal{M}}({IC}^{\mathrm{C}})\cdot w\ge 0\}$, where $M_{\mathcal{M}}({IC}^{\mathrm{C}})=(-1\hspace{0.17em}0\hspace{0.17em}1\hspace{0.17em}0\hspace{0.17em}0\hspace{0.17em}-1\hspace{0.17em}1)$ corresponds to the inequality I(X:Y Z)≤H(Z) from [10,11]. As $\mathit{\Gamma }({IC}^{\mathrm{C}})=\overline{{\mathit{\Gamma }}^{\ast }}({IC}^{\mathrm{C}})$ holds, we also have ${\mathit{\Gamma }}_{\mathcal{M}}({IC}^{\mathrm{C}})=\overline{{\mathit{\Gamma }}_{\mathcal{M}}^{\ast }}({IC}^{\mathrm{C}})$.

As mentioned previously, non-Shannon inequalities cannot give any new entropic constraints for IC, as the Shannon approximation is already tight. However, in many causal structures they do. For instance in the triangle scenario of figure 1c, non-Shannon inequalities still lead to new entropic constraints, even after marginalization to the three observed variables [50].

(ii) Causal structures with unobserved quantum systems

A quantum causal structure differs from its classical counterpart in that unobserved systems correspond to shared quantum states.

Definition 2.18.

A quantum causal structure, C^Q, is a causal structure where each observed node has a corresponding random variable, and each unobserved node has an associated quantum system.

In a classical causal structure, the edges of the DAG represent the propagation of classical information, and, at a node with incoming edges, the random variable there can be generated by applying an arbitrary function to its parents. We are hence implicitly assuming that all the information about the parents is transmitted to its children (otherwise the set of allowed functions would be restricted). This does not pose a problem because classical information can be copied. In the quantum case, on the other hand, the no-cloning theorem means that the children of a node cannot (in general) all have access to the same information as is present at that node. Furthermore, the analogue of performing arbitrary functions in the classical case is replaced by arbitrary quantum operations. Such a quantum framework that allows for an analysis with entropy vectors was introduced in [13]. In the following we outline this approach. However, for unity of description, our account of quantum causal structures is based upon the viewpoint that is taken for generalized causal structures in [11], which we review in the next section. (The difference is as follows: In [13] nodes correspond to quantum systems. All outgoing edges of a node together define a completely positive trace-preserving (CPTP) map with output states corresponding to the joint state associated with its child nodes. Similarly, the CPTP map associated to the input edges of a node must map the states of the parent nodes to the node in question. In [11], on the other hand, edges correspond to states, whereas the transformations occur at the nodes.)

Let C^Q be a quantum causal structure. Nodes without input edges correspond to the preparation of a quantum state described by a density operator on a Hilbert space, e.g. ${\rho }_A\in \mathcal{S}({\mathcal{H}}_A)$ for a node A, where for observed nodes this state is required to be classical. By ($\mathcal{S}(\mathcal{H})$, we denote the set of all density operators on a Hilbert space $\mathcal{H}$.) For each directed edge in the graph there is a corresponding subsystem with Hilbert space labelled by the edge’s input and output nodes. For instance, if Y and Z are the only children of A, then there are associated spaces ${\mathcal{H}}_{A_Y}$ and ${\mathcal{H}}_{A_Z}$ such that ${\mathcal{H}}_A={\mathcal{H}}_{A_Y}\otimes {\mathcal{H}}_{A_Z}$ (in the classical case these subsystems may all be taken to be copies of the system itself). At an unobserved node, a CPTP map from the joint state of all its input edges to the joint state of its output edges is performed. A node is labelled by its output state. For an observed node the latter is classical. Hence, it corresponds to a random variable that represents the output statistics obtained in a measurement by applying a positive operator-valued measure (POVM) to the input states. (Note that preparation and measurement can also be seen as CPTP maps with classical input and output systems, respectively, thus allowing for a unified formulation.) If all input edges are classical, this can be interpreted as a stochastic map between random variables.

A distribution, P, over the observed nodes of a causal structure C^Q is compatible with C^Q if there exists a quantum state labelling each unobserved node (with subsystems for each unobserved edge) and transformations, i.e. preparations and CPTP maps for each unobserved node as well as POVMs for each observed node, that allow for the generation of P by means of the Born rule. We denote the set of all compatible distributions ${\mathcal{P}}_{\mathcal{M}}(C^{\mathrm{Q}})$.

Example 2.19 (Compatible distributions in the quantum instrumental scenario).

For the quantum instrumental scenario (figure 1a), ${\mathcal{P}}_{\mathcal{M}}({IC}^{\mathrm{Q}})=\{P_{XYZ}\in {\mathcal{P}}_3\mid P_{XYZ}=\mathrm{tr}((E_X^Z\otimes F_Z^Y){\rho }_A)P_X\}$ is the set of compatible distributions. A state ${\rho }_A\in \mathcal{S}({\mathcal{H}}_{A_Z}\otimes {\mathcal{H}}_{A_Y})$ is prepared. Depending on the random variable X, a POVM ${\{E_X^Z\}}_Z$ on ${\mathcal{H}}_{A_Z}$ is applied to generate the output distribution of the observed variable Z. Depending on the latter, another POVM ${\{F_Z^Y\}}_Y$ is applied to generate the distribution of Y .

The set of entropy vectors of compatible probability distributions over the observed nodes, ${\mathcal{P}}_{\mathcal{M}}(C^{\mathrm{Q}})$, is ${\mathit{\Gamma }}_{\mathcal{M}}^{\ast }(C^{\mathrm{Q}}):=\{w\in {\mathbb{R}}_{\ge 0}^{2^k-1}\mid \mathrm{\exists }P\in {\mathcal{P}}_{\mathcal{M}}(C^{\mathrm{Q}})\hspace{0.17em}\mathrm{s}.\mathrm{t}.\hspace{0.17em}w=\mathbf{\text{H}}(P)\}$. Outer approximations ${\mathit{\Gamma }}_{\mathcal{M}}(C^{\mathrm{Q}})$ were first derived in [13], a procedure that we outline in the following. For their construction, an entropy is associated to each random variable and to each subsystem of a quantum state (equivalently each edge originating at a quantum node), corresponding to the von Neumann entropy of the respective system. For convenience of exposition, edges and their associated systems share the same label. The von Neumann entropy of a density operator ${\rho }_X\in \mathcal{S}({\mathcal{H}}_X)$ is defined as

The quantum conditional entropy, mutual- and conditional mutual information are defined as in the classical case and with the von Neumann entropy replacing the Shannon entropy.

Because of the impossibility of cloning, the outcomes and the quantum systems that led to them do not exist simultaneously. Therefore, there is in general no joint multiparty quantum state for all subsystems and it does not make sense to talk about the joint entropy of the states and outcomes. More concretely, if a system A is measured to produce Z, then ρ_AZ is not defined and hence neither is H(AZ) (for attempts to circumvent this, see, for example, [54]).

Definition 2.20.

Two subsystems in a quantum causal structure C^Q coexist if neither of them is a quantum ancestor of the other. A set of subsystems that mutually coexist is termed coexisting.

A quantum causal structure may have several maximal coexisting subsets. Only within such subsets is there a well-defined joint quantum state and joint entropy.

Example 2.21 (Coexisting sets in the quantum instrumental scenario).

Consider the quantum version of the instrumental scenario, as illustrated in figure 1a. There are three observed variables as well as two edges originating at unobserved (quantum) nodes, hence 5 variables to consider. More precisely, the quantum node A has two associated subsystems A_Z and A_Y. The correlations seen at the two observed nodes Z and Y are formed by measurement on the respective subsystems A_Z and A_Y. The coexisting sets in this causal structure are {A_Y,A_Z,X}, {A_Y,X,Z} and {X,Y,Z} and their (non-empty) proper subsets.

Note that, without loss of generality, we can assume that any initial, i.e. parentless quantum states, such as ρ_A above, are pure. This is because any mixed state can be purified, and if the transformations and measurement operators are then taken to act trivially on the purifying systems, the same statistics are observed. In the causal structure of example 2.21, this implies that ρ_A can be considered to be pure and thus H(A_YA_Z)=0. The Schmidt decomposition then implies that H(A_Y)=H(A_Z). This is computationally useful as it reduces the number of free parameters in the entropic description of the scenario. Furthermore, by Stinespring’s theorem [55], whenever a CPTP map is applied at a node that has at least one quantum child, then one can instead consider an isometry to a larger output system. The additional system that is required for this can be taken to be part of the unobserved quantum output (or one of them in case of several quantum output nodes). Each such case allows for the reduction of the number of variables by one, because the joint entropy of all inputs to such a node must be equal to that of all its outputs.

Quantum states are known to obey submodularity [56] and also obey the following condition:

• — Weak monotonicity [56]: H(X_S∖X_T)+H(X_T∖X_S)≤H(X_S)+H(X_T), for all X_S, X_T⊆Ω (recall H({})=0).

This is the dual of submodularity in the sense that the two inequalities can be derived from each other by considering purifications of the corresponding quantum states [57].

Within the context of causal structures, these relations can always be applied between variables in the same coexisting set. In addition, whenever it is impossible for there to be entanglement between the subsystems X_S∩X_T and X_S∖X_T—for instance, if these subsystems are in a cq-state—the monotonicity constraint H(X_S∖X_T)≤H(X_S) holds. If it is also impossible for there to be entanglement between X_S∩X_T and X_T∖X_S, then the monotonicity relation H(X_T∖X_S)≤H(X_T) holds, rendering the weak monotonicity relation stated above redundant.

Altogether, these considerations lead to a set of basic inequalities containing some Shannon and some weak-monotonicity inequalities, which are conveniently expressed in a matrix M_B(C^Q). This way of approximating the entropic cone in the quantum case is inspired by work on the entropic cone for multiparty quantum states [34]. Note also that there are no further inequalities for the von Neumann entropy known to date (contrary to the classical case where a variety of non-Shannon inequalities is known), except under additional constraints [58–63].

The conditional independence constraints in C^Q cannot be identified by proposition 2.10, because variables do not coexist with any quantum parents and hence conditioning a variable on a quantum parent is not meaningful. Nonetheless, among the variables in a coexisting set the conditional independences that are valid for C^C also hold in C^Q. This can be seen as follows. First, the validity of any constraints that involve only observed variables (which are always part of a coexisting set) hold by proposition 2.27 below. Secondly, for unobserved systems only their classical ancestors and none of their descendants can be part of the same coexisting set. An unobserved system is hence independent of any subset of the same coexisting set with which it shares no ancestors. Note that each of the subsystems associated with a quantum node is considered to be a parent of all of the node’s children (see figure 1 for an example).

In addition, suppose that X_S and X_T are disjoint subsets of a coexisting set, Ξ, and that the unobserved system A is also in Ξ. Then I(A:X_S | X_T)=0 if X_T d-separates A from X_S (in the full graph including quantum nodes). This follows because any quantum states generated from the classical separating variables may be obtained by first producing random variables from the latter (for which the usual d-separation rules hold) and then using these to generate the quantum states in question (potentially after generating other variables in the network), hence retaining conditional independence. The same considerations can be made for sets of unobserved systems. These independence constraints may be assembled in a matrix M_QCI(C^Q).

Among the variables that do not coexist, some are obtained from others by means of quantum operations. These variables are thus related by data processing inequalities (DPIs) [64].

Proposition 2.22 (DPI).

Let ${\rho }_{X_S{X}_T}\in \mathcal{S}({\mathcal{H}}_{X_S}\otimes {\mathcal{H}}_{X_T})$ and $\mathcal{E}$ be a completely positive trace-preserving (CPTP) map on $\mathcal{S}({\mathcal{H}}_{X_T})$ leading to a state ρ′_XSXT. Then I(X_S:X_T)_ρ′XSXT≤I(X_S:X_T)_ρXSXT.

Remarks: (1) the map from a quantum state to the diagonal state with entries equal to the outcome probabilities of a measurement is a CPTP map and hence also obeys the DPI. (2) In general, $\mathcal{E}$ can be a map between operators on different Hilbert spaces, i.e. $\mathcal{E}:\mathcal{S}({\mathcal{H}}_{X_T}^{\prime })\to \mathcal{S}({\mathcal{H}}_{X_T}^{″})$. However, as we can consider these operators to act on the same larger Hilbert space, we can w.l.o.g. take $\mathcal{E}$ to be a map on this larger space, which we call $\mathcal{S}({\mathcal{H}}_{X_T})$; (3) There are also DPIs for conditional mutual information, e.g. I(A:B | C)_ρ′ABC≤I(A:B | C)_ρABC for ${\rho }_{ABC}^{\prime }=(\mathcal{I}\otimes \mathcal{E}\otimes \mathcal{I})({\rho }_{ABC})$, but these are implied by proposition 2.22, so they need not be treated separately here.

The DPI provide an additional set of entropic constraints, which can be expressed in terms of a matrix inequality M_DPI(C^Q)⋅v≥0. In general, there are a large number of variables for which DPI hold. It is thus beneficial to derive rules that specify which of the inequalities are needed. First, note that whenever a concatenation of two CPTP maps ${\mathcal{E}}_1$ and ${\mathcal{E}}_2$, $\mathcal{E}={\mathcal{E}}_2\circ {\mathcal{E}}_1$, is applied to a state, then any DPIs for inputs and outputs of $\mathcal{E}$ are implied by the DPIs for ${\mathcal{E}}_1$ and ${\mathcal{E}}_2$. This follows by deriving the DPIs for input and output states of ${\mathcal{E}}_1$ and ${\mathcal{E}}_2$, respectively, and combining the two. Hence, the DPIs for composed maps $\mathcal{E}$ never have to be considered as separate constraints.

Secondly, whenever a state ${\rho }_{X_S{X}_T{X}_R}\in \mathcal{S}({\mathcal{H}}_{X_S}\otimes {\mathcal{H}}_{X_T}\otimes {\mathcal{H}}_{X_R})$ can be decomposed as ρ_XSXTXR=ρ_XSXT⊗ρ_XR and a CPTP map $\mathcal{E}$ transforms the state on $\mathcal{S}({\mathcal{H}}_{X_S}),$ then any DPIs for ρ_XSXTXR are implied by the DPIs for ρ_XSXT. This follows from I(X_S:X_TX_R)=I(X_S:X_T), I(X_SX_R:X_T)=I(X_S:X_T) and I(X_SX_T:X_R)=0.

Furthermore, whenever a node has classical and quantum inputs, there is not only a CPTP map generating its output state, but this map also can be extended to a CPTP map that simultaneously retains the classical inputs, as is the content of the following lemma, which also shows that retaining a copy of the classical inputs leads to tighter entropic inequalities.

Lemma 2.23.

Let Y be a node with classical and quantum inputs X_C and X_Q and $\mathcal{E}$ be a CPTP map that acts at this node, i.e. $\mathcal{E}$ is a map from $\mathcal{S}({\mathcal{H}}_{X_C}\otimes {\mathcal{H}}_{X_Q})$ to $\mathcal{S}({\mathcal{H}}_Y)$. Then $\mathcal{E}$ can be extended to a map ${\mathcal{E}}^{\prime }:\mathcal{S}({\mathcal{H}}_{X_C}\otimes {\mathcal{H}}_{X_Q})\to \mathcal{S}({\mathcal{H}}_{X_C}\otimes {\mathcal{H}}_Y)$ such that ${\mathcal{E}}^{\prime }:{\rho }_{X_C{X}_Q}\mapsto {\rho }_{X_{C}Y}^{\prime }$ with the property that ρ′_XCY is classical on ${\mathcal{H}}_{X_C}$ and ρ′_XC=ρ_XC. Furthermore, the DPIs for ${\mathcal{E}}^{\prime }$ imply those for $\mathcal{E}$.

Proof.

The first part of the lemma follows because classical information can be copied, and hence ${\mathcal{E}}^{\prime }$ can be decomposed into first copying X_C, and then performing $\mathcal{E}$. (Alternatively, we can think of $\mathcal{E}$ as the concatenation of ${\mathcal{E}}^{\prime }$ with a partial trace; this allows us to use the same output state ρ′ for both maps in the argument below.)

Suppose $\mathcal{E}:{\rho }_{X_C{X}_Q}\mapsto {\rho }_Y^{\prime }$. The second part follows because if I(X_CX_QX_S:X_T)_ρ≥I(Y X_S:X_T)_ρ′ is a valid DPI for $\mathcal{E},$ then I(X_CX_QX_S:X_T)_ρ≥I(X_CY X_S:X_T)_ρ′ is valid for ${\mathcal{E}}^{\prime }$. The second of these implies the first by the submodularity relation I(X_CY X_S:X_T)_ρ′≥ I(Y X_S:X_T)_ρ′. ▪

All the above (in)equalities are necessary conditions for a vector to be an entropy vector compatible with the causal structure C^Q. They constrain a polyhedral cone in ${\mathbb{R}}_{\ge 0}^m$, where m is the total number of coexisting sets of C^Q,

Example 2.24 (Entropic constraints for the quantum instrumental scenario).

The cone $\mathit{\Gamma }({IC}^{\mathrm{Q}})=\{v\in {\mathbb{R}}_{\ge 0}^{15}\mid M_{\mathrm{B}}({IC}^{\mathrm{Q}})\cdot v\ge 0,M_{\mathrm{QCI}}({IC}^{\mathrm{Q}})\cdot v=0\text{ and }{M}_{\mathrm{DPI}}({IC}^{\mathrm{Q}})\cdot v\ge 0\}$ involves the matrix M_B(IC^Q) that features 29 (independent) inequalities (note that the only weak monotonicity relations that are not made redundant by other basic inequalities are H(A_Y|A_ZX)+H(A_Y)≥0, H(A_Z|A_YX)+H(A_Z)≥0, H(A_Y|A_Z)+H(A_Y|X)≥0 and H(A_Z|A_Y)+H(A_Z|X)≥0). In this case, a single independence constraint encodes that X is independent of A_YA_Z:

Two DPI are required (cf. lemma 2.23), I(A_ZX:A_Y)≥I(XZ:A_Y) and I(A_YZ:X)≥I(Y Z:X), which yield a matrix The above matrices are all expressed in terms of coefficients of (H(A_Y), H(A_Z), H(X), H(Y), H(Z), H(A_YA_Z), H(A_YX), H(A_YZ), H(A_ZX), H(XY), H(XZ), H(Y Z), H(A_YA_ZX), H(A_YXZ), H(XY Z)). Although the notation suppresses the different states, there is no ambiguity because e.g. the entropy of X is the same for all states with subsystem X. The full list of inequalities is provided in the electronic supplementary material.

From Γ(C^Q), an outer approximation to the set of compatible entropy vectors ${\mathit{\Gamma }}_{\mathcal{M}}^{\ast }(C^{\mathrm{Q}})$ of the observed scenario $\mathcal{M}$ of C^Q can be obtained using Fourier-Motzkin elimination. This leads to ${\mathit{\Gamma }}_{\mathcal{M}}(C^{\mathrm{Q}}):=\{w\in {\mathbb{R}}_{\ge 0}^{2^k-1}\mid \mathrm{\exists }v\in \mathit{\Gamma }(C^{\mathrm{Q}})\hspace{0.17em}\mathrm{s}.\mathrm{t}.\hspace{0.17em}w={\pi }_{\mathcal{M}}(v)\}$, which can be written as ${\mathit{\Gamma }}_{\mathcal{M}}(C^{\mathrm{Q}})=\{w\in {\mathit{\Gamma }}_{\mathcal{M}}\mid M_{\mathcal{M}}(C^{\mathrm{Q}})\cdot w\ge 0\}$. The matrix $M_{\mathcal{M}}(C^{\mathrm{Q}})$ encodes all (in)equalities on ${\mathbb{R}}_{\ge 0}^{2^k-1}$ implied by M_B(C^Q)⋅v≥0, M_QCI(C^Q)⋅v=0 and M_DPI(C^Q)⋅v≥0 (except for the Shannon inequalities, which are already included in ${\mathit{\Gamma }}_{\mathcal{M}}$). Note that ${\mathit{\Gamma }}_{\mathcal{M}}(C^{\mathrm{C}})\subseteq {\mathit{\Gamma }}_{\mathcal{M}}(C^{\mathrm{Q}})\subseteq {\mathit{\Gamma }}_{\mathcal{M}}$, where the first relation holds because all inequalities relevant for quantum states also hold in the classical case. (This can be seen by thinking of a classical source as made up of two or more (perfectly correlated) random variables as its subsystems, which are sent to its children and processed there. The Shannon inequalities hold among all of these variables (and also imply any weak monotonicity constraints). The classical independence relations include the quantum ones but may add constraints that involve conditioning on any of the variables’ ancestors. These (in)equalities are tighter than the DPIs, which are hence not explicitly considered in the classical case.)

Example 2.25 (Entropic outer approximation for the quantum instrumental scenario).

The projection of Γ(IC^Q) leads to the entropic cone ${\mathit{\Gamma }}_{\mathcal{M}}({IC}^{\mathrm{Q}})=\{w\in {\mathit{\Gamma }}_3\mid M_{\mathcal{M}}({IC}^{\mathrm{Q}})\cdot w\ge 0\}$, for which $M_{\mathcal{M}}({IC}^{\mathrm{Q}})$ equals $M_{\mathcal{M}}({IC}^{\mathrm{C}})$ from example 2.17, thus corresponding to the constraint I(X:Y Z)≤H(Z). Hence, $\overline{{\mathit{\Gamma }}_{\mathcal{M}}^{\ast }}({IC}^{\mathrm{Q}})$ coincides with $\overline{{\mathit{\Gamma }}_{\mathcal{M}}^{\ast }}({IC}^{\mathrm{C}})$ [50].

This method has been applied to find an outer approximation to the entropy cone of the triangle causal structure in the quantum case (cf. figure 1c) [13]. This approximation did not coincide with the outer approximation to the classical triangle scenario obtained from Shannon inequalities and independence constraints. Whether there are more as yet unknown inequalities in the quantum case remains an open question (as opposed to the classical case where even better outer approximations have already been found [50]). In [13], the method was furthermore combined with the approach reviewed in §3b, where it was applied to a scenario related to IC (cf. example 3.8 below).

(iii) Causal structures with unobserved systems in other non-signalling constraints

The concept of a generalized causal structure was introduced in [11], the idea being to have one framework in which classical, quantum and even more general systems, for instance non-local boxes [65,66], can be shared by unobserved nodes and where theory-independent features of networks and corresponding bounds on our observations may be identified.

Definition 2.26.

A generalized causal structure C^G is a causal structure which, for each observed node, has an associated random variable and, for each unobserved node, has a corresponding non-signalling resource allowed by a generalized probabilistic theory.

Classical and quantum causal structures can be viewed as special cases of generalized causal structures [11,67]. Generalized probabilistic theories may be conveniently described in the operational–probabilistic framework of [68]. Circuit elements correspond to so-called tests that are connected by wires, which represent propagating systems. In general, such a test has an input system, and two outputs: an output system and an outcome. In the case of a system with trivial input, this corresponds to a preparation test, and in the case of trivial output this is an observation test. In the causal structure framework, a test is associated to each node. However, each such test has only one output: for unobserved nodes this is a general resource state; for observed nodes it is a random variable. Furthermore, resource states do not allow for signalling from the future to the past, i.e. we are considering so-called causal operational–probabilistic theories. This is important for the interpretation of generalized causal structures.

A distribution P over the observed nodes of a generalized causal structure C^G is compatible with C^G if there exists a causal operational–probabilistic theory, a resource for each unobserved edge in that theory and transformations for each node that allow for the generation of P. We denote the set of all compatible distributions ${\mathcal{P}}_{\mathcal{M}}(C^{\mathrm{G}})$. As in the quantum case, there is no notion of a joint state of all nodes in the causal structure and of conditioning on an unobserved system. Even more, there is no consensus on the representation of states and their dynamics in general non-signalling theories. To circumvent this, the classical notion of d-separation has been reformulated [11], which enables the following proposition.

Proposition 2.27 (Henson, Lal & Pusey).

Let C^G be a generalized causal structure, and let X, Y and Z be pairwise disjoint subsets of observed nodes in C^G. If a probability distribution P is compatible with C^G, then the d-separation of X and Y by Z implies the conditional independence X ⫫ Y | Z. Conversely, if, for every distribution P compatible with C^G, the conditional independence X ⫫ Y | Z holds, then X is d-separated from Y by Z in C^G.

This allows for the derivation of conditional independence relations among observed variables that hold in any generalized probabilistic theory, which hence restrict a general entropic cone. Furthermore, it rigorously justifies retaining the independence constraints among the (observed) variables in coexisting sets in quantum causal structures (cf. §2bii), which can be seen as special cases of generalized causal structures.

In [11], sufficient conditions for identifying causal structures C for which, in the classical case, C^C, there are no restrictions on the distribution over observed variables other than those that follow from the d-separation of these variables were derived. As, by proposition 2.27, these conditions also hold in C^Q and C^G, this implies ${\mathcal{P}}_{\mathcal{M}}(C^{\mathrm{C}})={\mathcal{P}}_{\mathcal{M}}(C^{\mathrm{Q}})={\mathcal{P}}_{\mathcal{M}}(C^{\mathrm{G}})$. For causal structures with up to six nodes, there are 21 cases (and some that can be reduced to the these 21) where such equivalence does not hold and where further relations among the observed variables have to be taken into account [11,18].

Outer approximations to the entropic cones for causal structures, C^G, based on the observed variables and their independences only were derived in [11]. Moreover, a few additional constraints for certain generalized causal structures were derived there. For example, the entropic constraint I(X:Y)+I(X:Z)≤H(X) for the triangle causal structure of figure 1c (which had previously been established in the classical case [69]) was found. This constraint does not follow from the observed independences, but nonetheless holds for the triangle causal structure in generalized probabilistic theories.

In spite of this, a systematic entropic procedure, in which the unobserved variables are explicitly modelled and then eliminated from the description, is not available for generalized causal structures. The issue is that we are lacking a generalization of the Shannon and von Neumann entropy to generalized probabilistic theories that obeys submodularity and for which the conditional entropy can be written as the difference of unconditional entropies [70,71].

One possible generalized entropy is the measurement entropy, which is positive and obeys some of the submodularity constraints (those with X_S∩X_T={}) but not all [70,71]. Using this, [72] considered the set of possible entropy vectors for a bipartite state in box world, a generalized probabilistic theory that permits all bipartite correlations that are non-signalling [73]. They found no further constraints on the set of possible entropy vectors in this setting (hence, contrary to the quantum case, measurement entropy vectors of separable states in box world can violate monotonicity). Other generalized probabilistic theories and multiparty states have, to our knowledge, not been similarly analysed.

(iv) Other directions for exploring quantum and generalized causal structures

The approaches to quantum and generalized causal structures above are based on adaptations of the theory of Bayesian networks to the respective settings and on retaining the features that remain valid, for instance, the relation between d-separation and independence for observed variables [11] (cf. §2biii). Other approaches to generalize classical networks to the quantum realm have been pursued [54], where a definition of conditional quantum states analogous to conditional probability distributions was formulated.

Recent articles have proposed generalizations of Reichenbach’s principle [74] to the quantum realm [16,75,76]. In [16], a graph separation rule, q-separation, was introduced, whereas [75,76] rely on a formulation of quantum networks in terms of quantum channels and their Choi states.

An active area of research is the exploration of frameworks that allow for indefinite causal structures [77–79]. There are several approaches achieving this, such as the process matrix formalism [80], which has led to the derivation of so-called causal inequalities and the identification of signalling correlations that are achievable in this framework, however, not with any predefined causal structure [80,81]. Another framework that is able to describe such scenarios is the theory of quantum combs [82], illustrated by a quantum switch, a quantum bit controlling the circuit structure in a quantum computation. A recent framework with the aim to model cryptographic protocols is also available [83]. Some initial results on the analysis of indefinite causal structures with entropy have recently appeared [84].

In the classical, quantum and generalized causal structures considered above only the observed classical information can be transmitted via a link between two observed variables and, in particular, no additional unobserved system. This understanding of the causal links encodes a Markov condition. In other situations, it can be convenient for the links in the graph to represent a notion of future instead of direct causation, see e.g. [85,86].