Causal Inference & Quantum Foundations Workshop

"Imsets, introduced by Studený (see Studený, 2005 for details), are an algebraic method for representing conditional independence models. They have many attractive properties when applied to such models, and they are particularly nice when applied to directed acyclic graph (DAG) models. In particular, the standard imset for a DAG is in one-to-one correspondence with the independence model it induces, and hence is a label for its Markov equivalence class. We present a proposed extension to standard imsets for maximal ancestral graph (MAG) models, which have directed and bidirected edges, using the parameterizing set representation of Hu and Evans (2020). By construction, our imset also represents the Markov equivalence class of the MAG. We show that for many such graphs our proposed imset defines the model, though there is a subclass of graphs for which the representation does not. We prove that it does work for MAGs that include models with no adjacent bidirected edges, as well as for a large class of purely bidirected models. If there is time, we will also discuss applications of imsets to structure learning in MAGs. This is joint work with Zhongyi Hu (Oxford). References Z. Hu and R.J. Evans, Faster algorithms for Markov equivalence, In Proceedings for the 36th Conference on Uncertainty in Artificial Intelligence (UAI-2020), 2020. M. Studený, Probabilistic Conditional Independence Structures, Springer-Verlag, 2005."

Quantum measurements have been a central topic of research in quantum theory for many years. In the context of causal structures and communication over networks, we are often particularly interested in local measurements of subsystems of a multi-partite system and classical processing of their inputs and outcomes. Formally, this processing can often be described by means of maps that are known as wirings. These wirings are furthermore interesting for the analysis of generalized probabilistic theories, as they are shared by all of them. In this work, we explicitly characterise all possible mulitpartite measurements in the generalised probabilistic theory box-world for various numbers of parties n with systems characterised by n_i fiducial measurements (which can be thought of as inputs here) and n_o outcomes, for small n, n_i, n_o. This includes all n-party n_i-input, n_o-outcome wirings. For n > 2, we further classify these measurements into three classes: wirings, deterministic non-wiring type and non-deterministic non-wiring type measurements. We explore advantages of these different types of measurements over previous protocols in the context of non-locality distillation and state-distingishability. We further find examples of non-locality without entanglement (contrary to previous claims) and a relation of these measurements to classical process matrices.

"If one only performs experiments involving passive observations, in general there are multiple causal structures that can explain the same set of distributions over the observed variables. In this case, we say that these causal structures are observationally equivalent. In this work, we explore all the known techniques for proving observational equivalence or inequivalence, as well as some original ones. Even if the existing rules are not enough to achieve the full classification of the causal structures with four observed variables, our results get close to such classification and show that admitting inequality constraints is a generic feature among structures with four observed variables."

When some variables in a directed acyclic graph (DAG) are hidden, a notoriously complicated set of constraints on the distribution of observed variables is implied. In this talk, we present inequality constraints implied by graphical criteria in hidden variable DAGs. The constraints can intuitively be understood to follow from the fact that the capacity of variables along a causal pathway to convey information is restricted by their entropy. For DAGs that exhibit e-separation relations, we present entropic inequality constraints and we show how they can be used to learn about the true causal model from an observed data distribution (arXiv:2107.07087).

"Quantum computing requires the ability to manipulate large nonclassical quantum systems. As we are far from any useful quantum computing advantage, certifying this ability is an important benchmark to assess progress toward this goal. This can be done using the nonlocal nature of quantum correlations, which allows to certify a non-trusted experimental apparatus from its input/output behaviour in a device independent way. It first requires to introduce the concept of Genuine Multipartite Nonlocality (GMNL) of size n, which designate systems which nonlocality cannot be understood an obtained from many states composed of n − 1 (or less) constituents. The first historical definition of GMNL, proposed by Svetlichny, is ill-defined when used to assess the large nonclassical nature of quantum systems, as it predicts that maximal GMNL states can be obtain from bipartite sources only. A more appropriate re-definition of that concept, called LOSR-GMNL, was proposed recently [arXiv:2105.09381]. However, it is not satisfactory in all experimental situations, as it cannot (by design) capture potential communications between the systems which could occur in some realistic experimental systems (e.g., many-body systems) – which Svetlichny definition captures in a naïve way. In this talk, I will propose a new alternative re-definition solving this issue, called Communication-Genuine Multipartite Nonlocality of length t (C-GMNL). It is based on a model inspired from synchronous distributed computing, that involves t communications steps along a graph. I will show that (i) the GHZ state is maximally nonlocal according to this C-GMNL definition, (ii) the cluster state is trivial in this C-GMNL definition but that (iii) the cluster state is maximally difficult in the LOSR-GMNL definition. Hence, some complicated LOSR-GMNL states become trivial when a small amount of communication is allowed. Based on a joint work in preparation with Xavier Coiteux-Roy, Owidiusz Makuta, Fionnuala Curran, Remigiusz Augusiak."

Quantum nonlocal correlations are generated by implementation of local quantum measurements on spatially separated quantum subsystems. Depending on the underlying mathematical model and the dimension of the underlying Hilbert spaces, various notions of sets of quantum correlations can be defined. This talk is devoted to the separations of some of these sets via simple ideas in quantum information theory, namely self-testing and entanglement embezzlement.

I will sketch the current state of play with classifying causal scenarios (aka DAGs with latent variables). Some are interesting: the classical correlations are constrained by non-trivial inequalities such as Bell’s. Some are boring: the classical correlations are constrained only by observable conditional independencies. Some we still don’t know. Along the way I will mention joint work with Joe Henson, Ray Lal, Shashaank Khanna, Marina Ansanelli and Elie Wolfe, and disjoint work by Robin Evans.

Distinguishing causation from correlation from observational data requires assumptions. We consider the setting where the unobserved confounder between two observed variables is simple in an information-theoretic sense, captured by its entropy. When the observed dependence is not due to causation, there exists a small-entropy variable that can make the observed variables conditionally independent. The smallest such entropy is known as common entropy in information theory. We extend this notion to Renyi common entropy by minimizing the Renyi entropy of the latent variable. We establish identifiability results with Renyi-0 common entropy, and a special case of (binary) Renyi-1 common entropy. To efficiently compute common entropy, we propose an iterative algorithm that can be used to discover the trade-off between the entropy of the latent variable and the conditional mutual information of the observed variables. We show that our algorithm can be used to distinguish causation from correlation in such simple two-variable systems. Additionally, we show that common entropy can be used to improve constraint-based methods such as the PC algorithm in the small-sample regime, where such methods are known to struggle. We propose modifying these constraint-based methods to assess if a separating set found by these algorithms is valid using common entropy. We finally evaluate our algorithms on synthetic and real data to establish their performance.