{'fraction_non_alphanumeric': 0.04618426966292135, 'fraction_numerical': 0.015712359550561796, 'mean_word_length': 4.1856064137223825, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 30, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A unifying framework for relaxations of the causal assumptions in Bell's theorem

Bell's Theorem shows that quantum mechanical correlations can violate the constraints that the causal structure of certain experiments impose on any classical explanation. It is thus natural to ask to which degree the causal assumptions -- e.g. locality or measurement independence -- have to be relaxed in order to allow for a classical description of such experiments. Here, we develop a conceptual and computational framework for treating this problem. We employ the language of Bayesian networks to systematically construct alternative causal structures and bound the degree of relaxation using quantitative measures that originate from the mathematical theory of causality. The main technical insight is that the resulting problems can often be expressed as computationally tractable linear programs. We demonstrate the versatility of the framework by applying it to a variety of scenarios, ranging from relaxations of the measurement independence, locality and bilocality assumptions, to a novel causal interpretation of CHSH inequality violations.

Bell's Theorem shows that quantum mechanical correlations can violate the constraints that the causal structure of certain experiments impose on any classical explanation. It is thus natural to ask to which degree the causal assumptions -e.g. "locality" or "measurement independence" -have to be relaxed in order to allow for a classical description of such experiments. Here, we develop a conceptual and computational framework for treating this problem. We employ the language of Bayesian networks to systematically construct alternative causal structures and bound the degree of relaxation using quantitative measures that originate from the mathematical theory of causality. The main technical insight is that the resulting problems can often be expressed as computationally tractable linear programs. We demonstrate the versatility of the framework by applying it to a variety of scenarios, ranging from relaxations of the measurement independence, locality and bilocality assumptions, to a novel causal interpretation of CHSH inequality violations.
The paradigmatic Bell experiment [1] involves two distant observers, each with the capability to perform one of two possible experiments on their shares of a joint system. Bell observed that even absent of any detailed information about the physical processes involved, the causal structure of the setup alone implies strong constraints on the correlations that can arise from any classical description [2]. The physically wellmotivated causal assumptions are: (i) measurement independence: experimenters can choose which property of a system to measure, independently of how the system has been prepared; (ii) locality: the results obtained by one observer cannot be influenced by any action of the other (ideally space-like separated) experimenter. The resulting constraints are Bell's inequalities [1]. Quantum mechanical processes subject to the same causal structure can violate these constraints -a prediction that has been abundantly verified experimentally [3][4][5][6][7]. This effect is commonly referred to as quantum nonlocality.
It is now natural to ask how stable the effect of quantum non-locality is with respect to relaxations of the causal assumptions. Which "degree of measurement dependence", e.g., is required to reconcile empirically observed correlations with a classical and local model? Such questions are not only, we feel, of great relevance to foundational questions -they are also of interest to practical applications of non-locality, e.g. in cryptographic protocols. Indeed, eavesdroppers can (and do [8]) exploit the failure of a given cryptographic device to be constrained by the presumed causal structure to compromise its security. At the same time, it will often be difficult to ascertain that causal assumptions hold exactly -which makes it important to develop a systematic quantitative theory.
Several variants of this question have recently at-tracted considerable attention [9][10][11][12][13][14][15][16][17][18][19][20]. For example, measurement dependence has been found to be a very strong resource: If no restrictions are imposed on possible correlations between the measurement choices and the source producing the particles to be measured, any nonlocal distribution can be reproduced [21]. What is more, only about about 1/15 of a bit of correlation between the source and measurements is sufficient to reproduce all correlations obtained by projective measurements on a singlet state [10,12,13]. In turn, considering relaxations of the locality assumption, Toner and Bacon showed that one bit of communication between the distant parties is again sufficient to simulate the correlations of singlet states [9]. In this paper we provide a unifying framework for treating relaxations of the measurement independence and locality assumptions in Bell's theorem. To achieve this, we borrow several concepts from the mathematical theory of causality, a relatively young subfield of probability theory and statistics [22,23]. With the aim of describing the causal relations (rather than mere correlations) between variables that can be extracted from empirical observations, this community has developed a systematic and rigorous theory of causal structures and quantitative measures of causal influence.
Our framework rests on three observations (details are provided below): (i) Alternative causal structures can systematically be represented using the graphical notation of Bayesian networks [22]. There, variables are associated with nodes in a graph, and directed edges represent functional dependencies. (ii) These edges can be weighted by quantitative measures of causal influence [22,24]. (iii) Determining the minimum degree of influence required for a classical explanation of observable distributions can frequently be cast as a computationally tractable linear program.

arXiv:1411.4648v1 [quant-ph] 17 Nov 2014
The versatility of the framework is demonstrated in a variety of applications. We give an operational meaning to the violation of the CHSH inequality [25] as the minimum amount of direct causal influence between the parties required to reproduce the observed correlations. Considering the Collins-Gisin scenario [26], we show that quantum correlations are incompatible with a classical description, even if we allow one of the parties to communicate its outcomes. We also show that the results in [10,13] regarding measurement-independence relaxations can be improved by considering different Bell scenarios. Finally, we study the bilocality assumption [27,28] and show that although it defines a nonconvex set, its relaxation can also be cast as a linear program, naturally quantifying the degree of nonbilocality.
Bayesian networks and measures for the relaxation of causal assumptions-The causal relationships between n jointly distributed discrete random variables (X 1 , . . . , X n ) are specified by means of a directed acyclic graph (DAG). To this end, each variable is associated with one of the nodes of the graph. One then says that the X i 's form a Bayesian network with respect to the graph, if every variable can be expressed as a deterministic function X i = f i (PA i , N i ) of its graph-theoretic parents PA i and an unobserved noise term N i , such that the N i 's are jointly independent [29]. This is the case if and only if the probability p(x) = p(x 1 , . . . , x n ) is of the form This identity encodes the causal relationships implied by the DAG [22]. As a paradigmatic example of a DAG, consider a bipartite Bell scenario (Fig. 1a). In this scenario, two separated observers, Alice and Bob, each perform measurements according to some inputs, here represented by random variables X and Y respectively, and obtain outcomes, represented by A and B. The causal model involves an explicit shared hidden variable Λ which mediates the correlations between A and B. From (1) it follows that p(x, y, λ) = p(x)p(y)p(λ) -which reflects the measurement independence assumption. It also follows that a = f A (x, λ, n A ), b = f B (y, λ, n B ). We incur no loss of generality by absorbing the local noise terms N A , N B into Λ and will thus assume from now on that This encodes the locality assumption. Together, these relations imply the well-known local hidden variable (LHV) model of Bell's theorem: p(a, b|x, y) = ∑ λ p(a|x, λ)p(b|y, λ)p(λ).
(2) Causal mechanisms relaxing locality ( Fig. 1b-d) and measurement independence (Fig. 1e) can be easily expressed using Bayesian networks. The networks themselves, however, do not directly quantify the degree of relaxation. Thus, one needs to devise ways of checking and quantifying such causal dependencies. To define a sensible measure of causal influence we introduce a core concept from the causality literature -interventions [22].
An intervention is the act of forcing a variable, say X i , to take on some given value x i and is denoted by do(x i ). The effect is to erase the original mechanism f i (pa i , n i ) and place X i under the influence of a new mechanism that sets it to the value x i while keeping all other functions f j for j = i unperturbed. The intervention do(x i ) amounts to a change in the decomposition (1), given by [30] Considering locality relaxations, we can now define a measure C A→B for the direct causal influence of A into B for the model in Fig. 1b: (4) It is the maximum shift (averaged over the unobservable Λ) in the probability of B caused by interventions in A. Similarly, one can define C X→B for the DAG in Fig. 1c and in other situations. To highlight the relevance of this measure, we note that a variation of it, known as average causal effect, can be used to quantify the effect of a drug in remedying a given symptom [22]. We are also interested in relaxations of measurement independence. Considering the case of a bipartite scenario (illustrated in Fig. 1e and that can be easily extended to multipartite versions), we can define the measure This can be understood as a measure of how much the inputs are correlated with the source, i.e. how much the underlying causal model fails to comply with measurement independence.
The linear programing framework-Given some observed probabilities and a particular measure of relaxation, our aim is to compute the minimum value of the measure compatible with the observations. As sketched below, this leads to a tractable linear program as long as there is only one unobserved variable Λ. (However, even in case of several hidden variables, variants of these ideas can still be used). Details are given in the Appendix.
For simplicity we consider the usual Bell scenario of Fig. 1a. The most general observable quantity is the joint distribution p(a, b, x, y) = p(a, b|x, y)p(x)p(y). Since we control the "inputs" X and Y, their distribution carries no information and we may thus restrict attention to p(a, b|x, y). This conditional probability is, in turn, a linear function of the distribution of Λ. To make this explicit, represent p(a, b|x, y) as a vector p with components p j labeld by the multi-index j = (a, b, x, y). Similarly, identify the distribution of Λ with a vector with components q λ = p(Λ = λ). Then from the discussion above, we have that p = Tq where T is a matrix with elements T j,λ = δ a, f A (x,λ) δ b, f B (y,λ) . Conditional expectations that include the application of a dooperation are obtained via a modified T matrix. E.g., q j = p(a, b|x, y, do(a )) = T q for T j,λ = δ a,a δ b, f B (y,λ) . The measures C and M are easily seen to be convex functions of the conditional probabilities p(a, b|x, y) and their variants arising from the application of do's -and thus convex functions of q. Hence their minimization subject to the linear constraint Tq = p for an empirically observed distribution p is a convex optimization problem. This remains true if only some linear function Vp = VTq (e.g. a Bell inequality) of the distribution p is constrained. The problem is not manifestly a (computationally tractable) linear program (LP), since neither objective function is linear in q. However, we establish in the appendix that it can be cast as such: Theorem 1. The constrained minimization of the measures C and M over hidden variables reproducing any observed probability distribution can be reformulated as a primal linear program (LP). Its solution is equivalent to where the {v i } K i=1 are the vertices of the LP's dual feasible region.
This result highlights another nice aspect of our framework. Unlike the results in [11][12][13][14][15][16][17], (6) is a closed form-expression valid for any distribution (or observation derived from it by a linear function Vp), not just the value of a specific Bell inequality. This allows for a much more detailed description.
In the following sections, we apply our framework to a variety of applications. We focus on the results while the more technical proofs are given in the Appendices.
Novel interpretation of the CHSH inequality-As a first application, we show that a violation of the CHSH inequality can be interpreted as the minimal direct causal influence between the parties required to simulate the observed correlations.
Intuitively, the more nonlocal a given distribution is, the more direct causal influence between Alice and Bob should be required to simulate it. We make this intuition precise by considering the models in Fig. 1b-c and the CHSH scenario (two inputs, two outputs for both Alice and Bob). For any observed distribution p(a, b|x, y), we establish in the Appendix that where the maximum should be taken over all the eight symmetries under relabelling of inputs, outputs, and parties of the CHSH quantity [25] where the last two terms represent the marginals for Alice and Bob respectively. The CHSH inequality stipulates that for any LHV model, CHSH ≤ 0. Eq. (7) shows that, regardless of the particular distribution, the minimum direct causal influence is exactly quantified by the CHSH inequality violation. Inspired by the communication scenario of Toner and Bacon [9] (Fig. 1d), we can also quantify the relaxation of the locality assumption as the minimum amount of communication required to simulate a given distribution. We measure the communication by the Shannon entropy H(m) of the message m which is sent. For a binary message, we can use our framework to prove, in complete analogy with (7), that if CHSH > 0 and 0 otherwise, where is the binary entropy. We note that for maximal quantum violation CHSH = 1/ √ 2 − 1/2, as produced by a single state, a message with H(m) ≈ 0.736 bits is required. This is less than the 1 bit of communication required by the protocol of Toner and Bacon [9] for reproducing arbitrary correlations of a singlet.
Quantum nonlocality is incompatible with some locality relaxations-Given that violation of CHSH can be directly related to relaxation of locality, one can ask whether similar interpretations exists for other scenarios. For example, we can consider a setting with three inputs and two outputs for Alice and Bob, and consider the causal model in Fig. 1b. Similar to the usual LHV model (2), the correlations compatible with this model form a polytope. One facet of this polytope is where E xy = A x B y = ∑ a,b (−1) a+b p(a, b|x, y). This inequality can be violated by any quantum state |ψ = √ |00 + (1 − )|11 with = 0, 1. Consequently, any pure entangled state -no matter how close to separable -generates correlations that cannot be explained even if we allow for a relaxation of the locality assumption, where one of the parties communicates its measurement outcomes to the other.
How much measurement dependence is required to causally explain nonlocal correlations?-The results in Refs. [10,12,13] show that measurement dependence is a very strong resource for simulating nonlocal correlations. In fact, a mutual information as small as I(X, Y : λ) ≈ 0.0663 is already sufficient to simulate all correlations obtained by (any number of) projective measurements on a single state [12,13]. Given the fundamental implication and practical relevance of increasing these requirements, we aim to find larger values for I(X, Y : λ) by means of our framework. The result of [12,13] leaves us with three options, regarding the quantum states: either non-maximally entangled states of two qubits, two-qudit states, or states with more than two parties.
Regarding non-maximally entangled two-qubit states, we were unable to improve the minimal mutual information. Regarding qudits, we have considered relaxations in the CGLMP scenario [31] -a bipartite scenario, where Alice and Bob each have two inputs and d outcomes. The CGLMP inequality is of the form I d ≤ 2. Assuming that a particular I d -value is observed in the setting of Fig. 1e, we numerically obtain the very simple relation up to d = 8. Via the Pinsker inequality [32,33], (11) provides a lower bound on the minimum mutual information I(X, Y : λ) ≥ M 2 log 2 e. This bound implies that for any I d ≥ 3.214, the mutual information required exceeds the 0.0663 obtained in Ref. [13]. Using the results in Ref. [34] for the scaling of the optimal quantum violation with d, one sees that this requires d ≥ 16. However, we note that the bounds provided by the Pinsker inequality are usually far from tight, leaving a lot of room for improvement. Moreover -as detailed in the Appendix -a corresponding upper bound (obtained via the solution to the minimization of M) is larger than the values obtained in [12,13] as soon as d ≥ 5. Though this upper bound is not necessarily tight, we highlight the fact that for d = 2 it gives exactly I(X, Y : λ) = 0.0463, the value analytically obtained in [12,13].
Regarding multipartite scenarios, we have considered GHZ correlations [35] in a tri-partite scenario where each party has two inputs and two outputs. We numerically obtain 0.090 ≤ I(X, Y, Z : λ) ≤ 0.207. This implies that increasing the number of parties can considerably increase the measurement dependence requirements for reproducing quantum correlations.
Bilocality scenario-To illustrate how the formalism can also be used in generalized Bell scenarios [27,28,36,37], we briefly explore the entanglement swapping scenario [38] of Fig. 1f (a more detailed discussion is given in the Appendix). As can be seen from the DAG, the hidden variables in this scenario are independent p(λ 1 , λ 2 ) = p(λ 1 )p(λ 2 ), the so-called bilocality assumption [27,28].
As in Ref. [27,28], we take the inputs x, z and the outputs a, c to be dichotomic while b takes four values which we decompose in two bits as b = (b 0 , b 1 ). The distribution of hidden variables can be organized in a 64-dimensional vector q with components q α 0 ,α 1 ,β 0 ,β 1 ,γ 0 ,γ 1 , where α x specifies the value of a for a given x (and analogously for γ, c and z) and β i specifies the value of b i . Thus together the indices label all the deterministic functions for A, B, C given their parents. As shown in [27,28], the bilocality assumption is equivalent to demanding q ac α 0 ,α 1 ,γ 0 ,γ 1 = q a α 0 ,α 1 q c γ 0 ,γ 1 , where q ac α 0 ,α 1 ,γ 0 ,γ 1 = ∑ β 0 ,β 1 q α 0 ,α 1 ,β 0 ,β 1 ,γ 0 ,γ 1 is the marginal for AC etc. Similar to (5) a natural measure M BL of non-bilocality quantifies by how much the underlying hidden variable distribution fails to comply with this constraint: Clearly M BL = 0, if and only if the bilocality constraint is fulfilled. However, demanding bilocality imposes a quadratic constraint on the hidden variables. This results in a non-convex set which is extremely difficult characterize [27,28,36,37]. Nevertheless, our framework is still useful, as using the marginals for a given observed distribution to constrain the problem further, the minimization of M BL can be cast in terms of a linear program with a single free parameter, which is then further minimised over (see Appendix).
As an illustration we consider the non-bilocal distribution found in Refs. [27,28]. It can be obtained by projective measurements on a pair of identical twoqubit entangled states . This distribution violates the bilocality inequality B = |I| + |J| ≤ 1 giving a value B = √ 2v. Using our framework we find M BL = max(2v 2 − 1, 0). Thus, for this specific distribution, M BL = B 2 − 1, so there is a one-to-one correspondence between the violation of the bilocality inequality and the minimum relaxation of the bilocality constraint required to reproduce the correlations. This assigns an operational meaning to B.
Conclusion-In this work we have revisited nonlocality from a causal inference perspective and provided a linear programming framework for relaxing the measurement independence and locality assumptions in Bell's theorem. Using the framework, we have given a novel causal interpretation of violations of the CHSH inequality, and we have shown that quantum correlations are still incompatible with classical causal models even if one allows for the communication of measurement outcomes. This implies that quantum nonlocality is even stronger than previously thought. Considering a variety of scenarios, we also have shown that the results in Refs. [10,12,13] regarding the minimal measurement dependence required to simulated nonlocal correlations can be extended. Finally we explained how the relaxation of the bilocality assumption naturally quantifies the degree of non-bilocality in an entanglement swapping experiment.
In addition to these results, we believe the generality of our framework motivates and -more importantlyprovides a basic tool for future research. For instance, it would be interesting to understand how our framework can be generalized in order to derive useful inequalities in the context of randomness expansion, following the ideas in [14]. Another natural possibility, inspired by [39,40], would be to look for a good measure of genuine multipartite nonlocality, by considering specific underlying signalling models. Finally, it would be interesting to understand how our treatment of the bilocality problem could be generalized and applied to the characterization of the non-convex compatibility regions of more complex quantum networks [36,[41][42][43][44].
We thank R. Luce and D. Cavalcanti for useful dis-

APPENDIX
For the sake of being as self-contained as possible, we start the appendix with reviewing basic concepts in convex optimization. We then use these concepts to establish Theorem 1 -our main technical result. As detailed below, the measures of direct causal influence (4) and measurement dependence (5), respectively, can be recast as vector norms. Their minimization, subject to the specific constraints of each of the causal models in Fig. 1 is then explored in detail.

REVIEW OF LINEAR PROGRAMMING
Linear Programming (LP) is a very powerful and widely used tool for dealing -both practically and theoretically -with certain families of convex optimization problems. We refer to [45,46] and references therein for an overview. From now on we assume that vectors x ∈ R n are represented in the standard basis In this representation, the two vectors 0 n := (0, . . . , 0) T (the "zero"-vector) and 1 n := (1, . . . , 1) T (the "all-ones" vector) will be of particular importance. Furthermore, we are frequently going to concatenate vectors x ∈ R n and y ∈ R m via shall denote the standard inner product of finite dimensional real vector spaces. There are many equivalent ways of defining the standard form of primal/dual LP's. Here we adopt the formalism of [47]. A convex optimization problem fits the framework of linear programming, if it can be reformulated as where c ∈ R n as well as b ∈ R m are vectors and Φ : R n → R m corresponds to an arbitrary real m × nmatrix. The inequality signs here denote generalized inequalities on R n and R m , respectively. To be concrete, two vectors x, y ∈ R n obey y ≥ x if and only if y i ≥ x i holds for all i = 1, . . . , n.
It is very useful to consider linear programming problems in pairs. An optimization of the form (13) is called a primal problem in standard form and is accompanied by its dual problem (in standard form): subject to Φ T ζ ≤ c Here, Φ T : R m → R n denotes the transpose of Φ (with respect to the standard basis Theorem 2 (Weak+Strong Duality). Any primal feasible ξ and any dual feasible ζ obey Furthermore, if a given LP is either primal or dual feasible, problems (13) and (14) are equivalent, i.e.
Strong duality is a very powerful tool, as it allows one to switch between solving primal and dual problems at will. Moreover, the general framework of linear programming is surprsingly versatile, because many nonlinear convex optimization problems can be converted into a corresponding LP. Here, we content ourselves with two examples which will turn out to be important for our analysis.
Example 4 ( ∞ -norm calculation, [45] p. 293). Let x ∈ R n be an arbitrary vector. Then Note that the constraint −v1 n ≤ x is redundant if the vector of interest obeys x ≥ 0 n . Also, (20) implicitly assures v ≥ 0.
The primal LPs in examples 3 and 4 are not yet in standard form (13). However, they can be converted into it by applying some straightforward reformulations -we will come back to this later.
Another useful feature of LPs is that different minimization procedures of the above kind can be combined in order to yield an LP for a more complicated optimization problem. An instance of such a combination is the following result which will turn out to be crucial for our analysis.
which is a primal LP, albeit not yet in standard form. Also, the constraints implicitly assure t 1 , . . . , t L ≥ 0 n and v ≥ 0.
Proof. We introduce the non-negative auxiliary vector then follows from the definition of the ∞ -norm. Replacing this ∞ -norm calculation by the corresponding LP (example 4 for non-negative vectors) and including L unconstrained 1 -norm calculations -one for each component of u -as "subroutines" (example 3) yields the desired statement.
Finally it is worthwhile to mention that constrained norm-minimization, e.g.
can also be reformulated as a LP, because the constraint is linear. To this end, simply include the additional linear constraint in the LP for calculating x 1 : Clearly, this is a LP. Pushing this further, one can also handle certain types of non-linear constraints, e.g.

USEFUL RESULTS REGARDING LP'S
We can now use these concepts and techniques to obtain a linear programming formalism for a particular family of convex optimization problems that is relevant for our analysis. As detailed in the following two sections, the measures of direct causal influence (4) and of measurement dependence (5) can be cast as a ∞norm and 1 -norm, respectively. This in turn allows us to state the associated equivalent dual problem for the minimization of each of these two measures, which is the scope of the following theorems.
ily of L real valued k × n-matrices and let p ∈ R m be an arbitrary vector. Then, the convex optimization problem can be reformulated as a primal LP. Its associated dual problem is given by Proof. Combining Lemma 5 -for x i = M i q ∈ R k for i = 1, . . . , L -with the constrained minimization argument from (21) shows that the convex optimization problem (22) is equivalent to solving minimize t 1 ,...,t L ∈R k ,q∈R n v∈R v (22) subject to Aq = p which is clearly a LP. Note that the remaining optimization variables v ∈ R and t i ∈ R k are also implicitly constrained to be non-negative. So, in order to convert (22) into a primal LP in standard form (13), we define Counting the dimensions of the resulting vector spaces reveals ξ, c ∈ R 1+Lk+n and b ∈ R L+2Lk+2m+2 . Also, the (implicit and explicit) non-negativity constraints on v, t 1 , . . . , t L and q guarantee ξ ≥ 0 1+Lk+n . Due to our choice of b, we can incorporate all relevant constraints of (22) in the compact expression in the (extended) standard bases of the spaces R 1+Lk+n and R L+2Lk+2m+2 . Our definitions of ξ, c, b and Φ now indeed convert (22) into primal standard form (13). Its dual then simply corresponds to (14) which can be further simplified. The structure of b suggests decompos- with w i , u , u ∈ R, y i , y i ∈ R k and z , z ∈ R m . Using this decomposition of ζ, we obtain the following constraints from Φ T ζ ≤ c: Also, due to ζ ≥ 0 L+2Lk+2l+2 , all the optimization variables are non-negative. The objective function corresponds to The particular form of objective function and constraints suggests to replace the non-negative variables z , z ∈ R m and u , u ∈ R by z := z − z and u := u − u which are not constrained to be non-negative anymore. Also, y i + y i ≤ w i 1 k together with y i , y i ≥ 0 implies the equivalent constraint for all 1 ≤ i ≤ L. This motivates to define y i := y i − y i which is bounded by the above inequality chain, but also not constrained to be non-negative. Putting everything together yields the desired statement be a family of real valued k × n-matrices, N a real valued l × n-matrix and let p ∈ R m as well as c ∈ R be arbitrary.
The convex optimization problem can be converted into a primal LP. Its associated dual LP corresponds to Proof. Proceeding along similar lines as in the previous proof one can show that (24) is equivalent to solving minimize t 1 ,...,t L ∈R k ,q∈R n v,ṽ∈Rṽ which is again clearly a primal LP. Moreover, it strongly resembles the linear program (22). Indeed, defining and extending ξ, b, as well as Φ from the proof of Theorem 6 toξ converts (26) into primal standard form. Going to the dual and simplifying it in a similar way as shown in the previous proof -decomposeζ into where ζ was defined in (23) -yields the desired statement upon noticing that 1 l , x + x ≤ 1 together with x , x ≥ 0 l is equivalent to demanding that x := x − x obeys x 1 ≤ 1, but is not constrained to be nonnegative anymore. subject to A T z + u1 n ≤ N T x x 1 ≤ 1.
If the normalization condition 1 n , q = 1 is dropped as well, the optimization parameter u assumes 0 and need not be considered in the dual optimization.
Proof. Omitting the 1 -norm constraint is equivalent to letting the constraint c go to infinity. Since (−cv) is part of the dual's objective function (25), this limit enforces v = 0. This in turn demands w i = 0 and consequently y i = 0 k for all i = 1, . . . , L. As a result, we obtain the first desired statement. The second simplification requires a closer look at the proof of Theorem 7. Doing so reveals that the constraint 1 n , q = 1 results in the additional dual optimization parameter u. Omitting this constraint in the primal therefore implies that u has to be dropped accordingly.
Finally we are going to present the derivation of the second part of Theorem 1, namely that solving an arbitrary feasible primal LP (in standard form), is equivalent to maximizing the dual problem over finitely many points -the vertices of the dual feasible set. Proposition 9. Consider a primal feasible LP whose optimal value γ is bounded from below. Then this optimum is attained at one vertex d i of the dual feasible region D := ζ ∈ R m : Φ T ζ ≤ c, ζ ≥ 0 m : Possible unbounded directions (rays) of D can be safely ignored.
Note that all the measures we consider -(4), (5) and (12) in the main text -are non-negative by construction. Consequently, any reformulation of calculating (or optimizing over) these measures as a primal LP results in a bounded optimal value γ ≥ 0. Hence, Proposition 9 is applicable, provided there is at least one hidden variable that reproduces the observed distribution, thus establishing that the LP is primal feasible.
Proposition 9 establishes that the relevant part of the dual feasible region is bounded. It can be deduced from duality -Theorem 2 -and is standard. In order to be self-contained, we provide a slightly different proof that exploits the geometry of linear programs more explicitly.
Proof of Proposition 9. The fact that the primal LP is feasible and bounded assures that there is at least one dual feasible point via strong duality -Theorem 2. The dual feasible region D is defined by n + m linear inequalities and therefore has the structure of a convex polyhedron. We have just established that this polyhedron is nonempty, but it is not necessarily bounded. To see this, suppose for now that c ≥ 0 n holds (this is not necessary, but will simplify our argument). If Φ T has a nontrivial kernel, then each elementζ ∈ ker Φ T ∩ R m + is not affected by the linear inequalities, becausē ζ ≥ 0 m and Φ Tζ = 0 n ≤ c.
Consequently, D contains the convex cone C := ker Φ T ∩ R m + . Conversely, it is easy to show that the unbounded part of D is fully contained in C. This allows us to make a Minkowski decomposition where C is the unbounded conic part and P denotes the polyhedron's remaining part. We now aim to show that elementsζ ∈ C do not contribute to the actual optimization procedure and can therefore safely be ignored.
To this end, we combine the primal problem's (13) constraint Φξ − b ≥ 0 m with the dual constraint ζ ≥ 0 m to obtain ζ, b ≤ ζ, Φξ for any primal feasible ξ ∈ R n . Such a ξ is guaranteed to exist due to Theorem 2 and in particular implies for anyζ ∈ C: Here, the last equality is due toζ ∈ ker Φ T . Therefore elements of C manifestly do not contribute to the maximization and we can focus on the remaining set P. By construction, P is a bounded polyhedron and thus a polytope which can be characterized as the convex hull conv(d 1 , . . . , d K ) of its extremal points (Weyl-Minkowski Theorem [46,Corollary 4.3]). However, it is a well known fact that the maximum of a linear (or more generally: any concave) function over a convex polytope is attained at one of its extreme pointes, i.e. vertices.

RELAXATION OF LOCALITY
In this section we will analyze the relaxation of the locality assumption, as exemplified by the DAGs depicted in Fig. 1b-d. In particular, we will show that evaluating the minimal direct causal influence -see equation (4) in the main text -that is required to simulate a given non-local distribution can be recast as a LP. Consequently, it can be determined efficiently for any observed probability distribution.
We begin analyzing in details the scenario depicted in Fig. 1c. There, the input X of Alice has a direct causal influence over the outcome B of Bob. We consider the general, finite case where Alice has m x inputs and o a outputs, that is, x = 0, . . . , m x − 1 and a = 0, . . . , o a − 1 (and analogously for Bob). Variations of this signalling model can be easily constructed and will be briefly discussed at the end of this section.
The signalling model in Fig. 1c requires a hidden variable λ assuming n = o m x a o m x m y b possible values. The causal structure assures a = f A (x, λ) which resembles the LHV model (Fig. 1a). This is not the case for b, which can depend on x,y and λ -i.e. b = f B (x, y, λ).
Given such a signalling model and some observed constraints, our task is to find the minimum value of C X→B . Similarly to (4), this quantity can be defined as (29) which quantifies the amount of signalling required to explain the observation. Moving on, we note that where we have identified p(λ) with the n-dimensional vector q via e i , q = p(λ i ). The vector v = v(x, x , y, b) only consists of 1's and 0's and fully characterizes the action of the Kronecker-symbols in (30). By doing so, the measure of causal influence (29) can be recast as Here, the index i parametrizes one of the L possible instances of (x, x , y, b) with x = x and v i = v(x, x , y, b) denotes the vector corresponding to that instance. The last equality in (31) then follows from introducing C := ∑ L i=1 |e i v i | and the definition of the ∞ -norm. Consequently, minimizing C X→B over all hidden variables that are compatible with our observations is equivalent to solving minimize q∈R n Cq ∞ (32) subject to VTq = Vp Corollary 8 assures that this optimization problem can be translated into a LP in standard form. As already mentioned in the main text, Vp denotes the vector representing the correlations under consideration -the probability distribution itself (V = 1) or a function of it, e.g., a Bell inequality ( V = |e 1 b| for some b ∈ R m ) -and the matrix VT maps the underlying hidden variable states to the actually observed vector Vp . Given any observed distribution Vp of interest, one can easily implement this linear program and solve it efficiently. However, we are also interested in deriving an analytical solution which is valid for any vector p encoding the full probability distribution p(a, b|x, y). Subjecting to the full probability distribution p in particular guarantees that the normalization constraint (33) is already assured by Tq = p. This allows for dropping this constraint without loss of generality. Proposition 9 serves precisely the purpose of obtaining such an analytical expression, as it -in combination with Corollary 8 -assures that solving (32) is equivalent to evaluating denotes the vertices of the dual feasible region in (27). Standard algorithms like PORTA [48] allow for evaluating these extremal points. We have performed such an analysis for the particular case of the CHSH scenario (m x = m y = o a = o b = 2). We list all the 13 vertices of the LP's dual feasible region in Table I. Nicely, we see that all the extremal points can be divided into three types: i) the trivial vector 0 m , ii) the symmetries of the CHSH inequality vector, for example and iii) the non-signalling conditions, for instance Here, we have used the short hand notation p AB ab|xy = p(a, b|x, y) and similarly for the marginals.
For any non-signalling distribution, the conditions of the third type vanish and the corresponding vertices need not be considered. Therefore we arrive at the result stated in the main text, namely where the maximum is taken over all the eight symmetries of the CHSH inequality.
Having such a causal interpretation of the CHSH inequality at hand, one can wonder the same holds true for other Bell inequalities, for instance the (I 3322 ≤ 0)inequality [26] (three inputs for Alice and Bob with two outcomes each). Dwelling on the model in Fig. 1c we show that the I 3322 inequality only provides a lower bound to the actual value of C X→B required to simulate a given nonlocal distribution. This is illustrated in Fig. 2. To be more concrete, we consider the particular full probability distribution where  (36) is taken into account. The red curve is obtained by minimizing C X→B for a given value of I 3322 subject to non-signalling and normalization constraints.
of simulating any nonlocal distributions in the CHSH scenario.
Interestingly, things change drastically if we move on to the I 3322 scenario. It is worthwhile to point out that model (37) restricts the hidden variables to a region characterized by finitely many inequalities. Therefore, analogously to the usual LHV model (2), the feasible region is a polytope. Using the software PORTA we found different classes of non-trivial inequalities that define the compatibility region of this model. As shown in the main text -equation (10) -one of these inequalities corresponds to where E xy = A x B y = ∑ a,b (−1) a+b p(a, b|x, y). We now show that this inequality can be violated by any quantum state |ψ = √ |00 + (1 − )|11 with = 0, 1. To arrive at such a statement, it suffices to consider that Alice and Bob perform projective measurements on the X-Z plane of the Bloch sphere. More concretely, Alice measures observables of the form O A x = cos(θ A x )Z + sin(θ A x )X and so does Bob whose observables we denote by O B x . Here, X and Z refer to the Pauli matrices. For such particular measurements, the correlators E xy = A x B y simply correspond to Choosing the angles such that θ A 0 = 0, θ A 1 = π, θ A 2 = π/2, θ B 0 = 0 and θ B 2 = −π we obtain . This expression exceeds 4 for any = 0, 1, provided that we choose θ B 1 sufficiently small compared to 2 (1 − ). This result shows that even relaxing some of assumptions in Bell's theorem -in this particular case, the fact that Alice outcomes cannot have a direct causal influence over Bob outcomes -may not be enough to causally explain quantum correlations.
A similar analysis can be performed for the communication model of Fig. 1d. Such a model implies the following decomposition of the distribution observed: Such an expression suggests to decompose the hidden variable into λ = (λ α , λ β , λ m ). By doing so, one can perform an analysis similar to the one above and define a measure of causal influence similar to (4). However, inspired by the communication model of Toner and Bacon [9], we directly proceed to analyzing the amount of communication between Alice and Bob required to classically reproduce the distribution observed. We quantify the information content of a binary message m sent from Alice to Bob via its Shannon entropy H(m). Due to the highly non-linear character of entropies, the optimizations involving H(m) are quite hard in general. Fortunately in the particular case of binary messages, minimizing H(m) is equivalent to minimizing Here, we have once more identified p(λ) with the vector q and the components of v correspond to v i = ∑ a p(m = 0|x, a, λ i )p(a|x, λ i ). Also, we have without loss of generality considered a uniform distribution of Alice's inputs -i.e. p(x) = 1/m x -in the second line. Consequently, the constrained minimization of p(m = 0) (and thus H(m)) simply corresponds to minimize q∈R n v, q subject to Tq = p 1 n , q = 1 q ≥ 0 n , which is clearly a primal LP. Computing the extremal points of the dual problem allows us to infer a novel relation between the degree of nonlocality and the minimum communication required to simulate it. Namely, Here, h denotes the binary entropy given by These results on the relaxation of the locality assumption, in addition to fundamental implications and relevance in nonlocal protocols, can also be used to compute the minimum causal influences/communication required to causally explain the nonlocal correlations observed in experimental realizations of Bell's tests where the space-like separation is not achieved [6,7].

MEASUREMENT DEPENDENCE MODELS
In this section we focus on the measure M X,Y:λ -see equation (5) in the main text -which quantifies the degree of measurement dependence in a given causal model. Similar to the previous section, we are going to show that determining the minimal degree of measurement dependence required to reproduce a given nonlocal distribution can be done via solving a LP.
To illustrate this, we consider the simplest scenario of measurement dependence in detail. Such a model is displayed in Fig. 1e and involves a bipartite Bell scenario, where the measurement inputs X of Alice and Y of Bob, respectively, can be correlated with the source Λ producing the particles to be measured.
Without loss of generality, we model such correlations by introducing an additional hidden variable µ which serves as a common ancestor for x, y and λ. This suggests to decompose this common ancestor into µ = (µ x , µ y , µ λ ). We can assume x = µ x , y = µ y and λ = µ λ without loss of generality (x, y and λ are deterministic functions of their common ancestor µ). If Alice's apparatus has m x inputs (i.e. x = 0, . . . , m x − 1) and o a outputs (i.e. a = 0, . . . , o a − 1), and similarly for Bob, n = m x m y o m x a o m y a different instances of µ suffice to fully characterize the common ancestor's influence. Similar to the previous section, we can use this discrete nature of µ to identify any probability distribution p(µ) : Ξ → [0, 1] uniquely with a non-negative, real vector q via Likewise, we can rewrite the observed probability distribution p(a, b|x, y) as p(a, b|x, y) The usefulness of such vectorial identifications becomes apparent when taking a closer look at the measure of correlation (5). Indeed, where M denotes the real k × n matrix M = ∑ k j=1 |e j v(x, y, λ)|. Note that this matrix implicitly depends on p(x, y). However, p(x, y) is an observable quantity and thus available. Moreover, one is typically interested in the case, where said distribution for the inputs is uniformly distributed -i.e. p(x, y) = 1/(m x m y ).
It is worthwhile to point out that different measures of measurement dependence have been considered in the literature. For instance, in Ref. [12] the following measure of correlation has been proposed: Similarly to (41), we can rewrite this measure as a 1norm, namely The constrained minimization of both M and M Hall consequently corresponds to the following optimiza-tion: minimize q∈R n max i=1,...,L M i q 1 (42) subject to Vq =p 1 n , q = 1 q ≥ 0 n , Theorem 6 assures that such an optimization can be recast as a primal LP in standard form.
In this work we have opted to focus on the measure defined in (41). The reason for that is two-fold. Firstly, such a choice assures L = 1 and numerically solving the corresponding LP is substantially faster. The second reason stems from the fact that (41) is proportional to the variational distance between the distributions p(x, y, λ) and p(x, y)p(λ). Knowledge of the total variational distance allows to lower-bound the mutual information between (X, Y) and Λ via the Pinsker inequality [32,33]: A converse bound on I(X, Y : Λ) is obtained by noting that the (linear program) solution to the minimization of M returns a specific hidden variable model, for which we can readily compute the mutual information.
Using measure (41), we have considered many different Bell scenarios. This was already mentioned in the main text. In particular we refer to Fig. 3 where we consider the CGLMP scenario [31] -a bipartite model, where Alice and Bob measure one out of two observables each of them having d possible outcomes. The corresponding CGLMP inequality is of the form I d ≤ 2, where the local bound of 2 and the maximal violation of 4 are independent of the number of possible outcomes d. Imposing the value of the I d inequality ad imposing non-signalling and the normalization constraints we numerically obtain a very simple relation up to d = 8, namely Conversely, we have also considered specific quantum realizations. For d = 2, 5, 7 we have numerically optimized over quantum states and projective measurements maximizing the corresponding I d inequality. With the resulting quantum probability distribution at hand, we computed M and inferred lower and upper bounds for I(X, Y : Λ) in turn. These results are depicted in Fig. 3 and we refer to the corresponding section in the main text for further insights concerning measurement dependence.

BILOCALITY SCENARIO
In LHV models for multipartite Bell scenarios, it is usually assumed that the same hidden variable is shared among all the parties. That is, a Bell inequality violation rules out any shared LHV. However, in quantum information protocols it is often the case that different parties receive particles produced by independent sources, e.g. in quantum networks [36,[41][42][43][44]. It is then natural to focus on LHV models which reproduce the independence structure of the sources. That is, each hidden variable can only be shared between parties receiving particles from the same source. Such models are weaker than general LHV models, i.e. they form a subset of all the models where the hidden variables can be shared arbitrarily among the parties.
A particular case is an entanglement swapping scenario [38] involving three parties A, B and C which receive entangled states from two independent sources. The DAG of Fig. 1f shows an LHV model with independent variables for this scenario. The assumption that the sources are independent, p(λ 1 , λ 2 ) = p(λ 1 )p(λ 2 ), is known as bilocality [27,28]. With this assumption, in analogy with the usual LHV decomposition (2), the correlations for this scenario must fulfil p(a|x, λ 1 )p(b|λ 1 , λ 2 )p(c|z, λ 2 ).
Note that the set of bilocal correlations is non-convex because of the nonlinearity of the bilocality assumption. This makes the set extremely difficult characterize [27,28,36,37,49,50]. In the following, we introduce a measure of relaxation of bilocality, and we show that, despite the non-convex nature of the measure, it can nevertheless be computed by means of a linear program. For fixed numbers m x , m z and o a , o b , o c of the input x, z and output a, b, c values, there is a finite number n = o m x a o b o m z c of deterministic strategies. We can label the deterministic strategies for a by symbols α = α 0 , . . . , α m x where α x is the value of a when the input is x. Similarly, we label the functions for b by β and for c byγ = γ 0 , . . . , γ m z . Thus, the distribution over the deterministic strategies can be identified with an n-dimensional vector q, analogous to the case in the main text for usual LHV models. The vector q then has components qᾱ ,β,γ . Defining the marginals q ac the bilocality assumption is equivalent to the requirement In analogy with the measure (5) of measurement dependence, the degree of non-bilocality can be measured by how much the distribution over the LHVs fail to comply with this criterion. We define the measure of nonbilocality as Clearly M BL = 0 if and only if the bilocality constraint is fulfilled. The non-bilocality measure is quadratic in the distribution over the the deterministic strategies. Thus, it is not obvious that linear programming will be helpful in computing M BL or that the computation can be made efficient. However, we notice that, for given observed correlations, there are restrictions on the marginals q ā α and q cγ imposed by the observed distribution p(a, b, c|x, z) because of the constraint (43) that the LHV must reproduce the observations. This constraint can be written Depending on the observed distribution, there may be no or just a few free parameters ν which determine q ā α = fᾱ(ν). We can then rewrite M BL as For fixed ν the measure M BL (ν) is linear and its minimum can be found via a linear program, as we now show. As previously, the first step is to write M BL (ν) as an 1 -norm. For a given value of ν, we can write where M ν is a matrix of dimension l × n, with l = o m x a o m z c and entries M ν αγ,ᾱ β γ = δᾱ ,ᾱ δγ ,γ − fᾱ(ν)δγ ,γ (where δᾱ ,ᾱ = δ α 0 ,α 0 · · · δ α ox ,α ox etc.). Minimisation of M BL (ν) for given, observed correlations p(a, b, c|x, z) is then equivalent to minimize q∈R n M ν q 1 subject to Aq = p where p is the k-dimensionsal vector representing the observed correlations, with k = o a o b o c m x m z , and A is a k × n matrix which encodes the constraint (47) that the LHV must reproduce the observations. The entries of A are A abcxz,ᾱβγ = δ a,α x δ b,β δ c,γ z . From Theorem 6, the minimisation (52) is equivalent to the linear program minimize t∈R l 1 l , t subject to − t ≤ M ν q ≤ t, Aq = p, Thus, minimising M BL (ν) for fixed ν is indeed a linear program. To find the minimum of the measure M BL we must minimise also over ν and hence we have an optimisation over a linear program. In order to verify non-bilocality of a given distribution we need to check that the minimum over ν is non-zero, or equivalently that the minimum of M BL (ν) is non-zero for all values of ν in the allowed range. On the other hand, if we find a value of ν such that M BL (ν) = 0 this is sufficient to show that the distribution is bilocal (and as a byproduct we get an explicit bilocal decomposition).

Bilocality with binary inputs
To illustrate our framework, and to compare with previous results, we now consider the case where the (Z + X) and A 1 = , while Bob measures in the Bell basis assigning b 0 b 1 = 00, 01, 10, 11 to |Φ + , |Φ − , |Ψ + and |Ψ − . As shown in [27,28] this distribution is non-bilocal. Taking the marginal of (47) gives p(a|x) = ∑ᾱ δ a,α x qᾱ, explicitly for the distribution (54) p(a = 0|x = 0) = q a 0,0 + q a 0,1 = 1 2 p(a = 0|x = 1) = q a 0,0 + q a 1,0 = 1 2 p(a = 1|x = 0) = q a 1,0 + q a 1,1 = 1 2 p(a = 1|x = 1) = q a 0,1 + q a 1,1 = This implies that q a 0,0 = q a 1,1 and q a 1,0 = q a 0,1 = 1/2 − q a 0,0 and thus we have a single free parameter ν = q a 0,0 . The parameter is further constrained by the full distribution p(a, b, c|x, z). To determine its range we run the following two linear programs minimize c, q subject to Aq = p, and maximize c, q subject to Aq = p, where c, q = q a 0,0 . These two linear programs define a range ν min ≤ ν ≤ ν max . In some particular cases ν max = ν min , in which case the minimisation over ν is superfluous and the minimum of M BL is directly given by a linear program and is thus analytical. However, in general these bounds are different. For the distribution (54) with v = 1, we have ν max = ν min = 1/4, while for v = 0.8 we have ν min = 0.16 and ν = 0.34. In general what we observe is that for any v, the minimum M BL (ν) occurs at ν = 1/4. This is illustrated Fig. 4.
In Fig. 5 we show how the minimum of M BL depends on the visibility. We also show the value of the bilocality quantity B = |I| + |J| given in [27,28], where and A x B y C z = ∑ a,b 0 ,b 1 ,c (−1) a+b y +c p(a, b 0 , b 1 , c|x, z). (60) In [27,28] it was shown that bilocality implies B ≤ 1.
For the distribution (54) on the other hand, I = J = 1 2 v 2 and therefore B = √ 2v. From the numerical results in Fig. 5 one can easily fit the data and find min M BL = B 2 − 1. Thus the violation of the bilocality corresponds exactly to how much bilocality must be relaxed to reproduce the observed distribution.

Bilocality with ternary inputs
To sketch how the linear framework could be used in more general bilocality scenarios we consider the case where Alice and Charlie can perform three different measurements. We again consider the case of trivial marginals p(a|x) = 1/2. This imposes the following FIG. 5. Minimum of the non-bilocality measure M BL vs. visibility v (blue). We also show the bilocality quantity B (red). Our measure can be understood as the amount of correlation between the sources required to simulate the observed correlations.
This means that we now have four free parameters ν = (q a 000 , q a 001 , q a 010 , q a 100 ) . To linearize M BL in this case, we need to optimize over these four variables.
In practice, given a certain distribution p(a, b, c|x, z), we first fix a certain value for q a 000 = c 0 in the range q min 000 ≤ q a 000 ≤ q max 000 . We then solve a linear program to find the bounds for the next free parameter q min 001 ≤ q a 001 ≤ q max 001 but now imposing also the constraint that q a 000 = c 0 . Fixed q a 000 = c 0 and q a 001 = c 1 we look for the bounds of the next free parameter q min 010 ≤ q a 010 ≤ q max 010 . We now run the linear program for the remaining free parameter in the range q min 100 ≤ q a 100 ≤ q max 100 determined by the probability distribution and the constraints q a 000 = c 0 , q a 001 = c 1 , q a 010 = c 2 .
For a sufficiently good discretization of these continuous free parameters, we can be quite confident about the non-bilocality of the distribution if we find no values for which M BL = 0. On the other hand, if we find any values for the free parameters such that M BL = 0, then we can immediately conclude that the distribution is bilocal. To illustrate this we have tested the distribution obtained with two maximally entangled states |Ψ − when Alice and Charlie measure the three observables X, Y, Z while Bob measures in the Bell basis. It is possible to show that this distribution is bilocal by setting q a 000 = 0 and q a 001 = q a 010 = q a 100 = 1/4.