Abstract Marginal problems naturally arise in a variety of different fields: basically, the question is whether some marginal/partial information is compatible with a joint probability distribution. To this aim, the characterization of marginal sets via quantifier elimination and polyhedral projection algorithms is of primal importance. In this work, before considering specific problems, we review polyhedral projection algorithms with focus on applications in information theory, and, alongside known algorithms, we also present a newly developed geometric algorithm which walks along the face lattice of the polyhedron in the projection space. One important application of this is in the field of quantum non-locality, where marginal problems arise in the computation of Bell inequalities. We apply the discussed algorithms to discover many tight entropic Bell inequalities of the tripartite Bell scenario as well as more complex networks arising in the field of causal inference. Finally, we analyze the usefulness of these inequalities as nonlocality witnesses by searching for violating quantum states.
Abstract Marginal problems naturally arise in a variety of different fields: basically, the question is whether some marginal/partial information is compatible with a joint probability distribution. To this aim, the characterization of marginal sets via quantifier elimination and polyhedral projection algorithms is of primal importance. In this work, before considering specific problems, we review polyhedral projection algorithms with focus on applications in information theory, and, alongside known algorithms, we also present a newly developed geometric algorithm which walks along the face lattice of the polyhedron in the projection space. One important application of this is in the field of quantum non-locality, where marginal problems arise in the computation of Bell inequalities. We apply the discussed algorithms to discover many tight entropic Bell inequalities of the tripartite Bell scenario as well as more complex networks arising in the field of causal inference. Finally, we analyze the usefulness of these inequalities as nonlocality witnesses by searching for violating quantum states.
Bell's theorem in physics, as well as causal discovery in machine learning, both face the problem of deciding whether observed data is compatible with a presumed causal relationship between the variables (for example, a local hidden variable model). Traditionally, Bell inequalities have been used to describe the restrictions imposed by causal structures on marginal distributions. However, some structures give rise to non-convex constraints on the accessible data, and it has recently been noted that linear inequalities on the observable entropies capture these situations more naturally. In this paper, we show the versatility of the entropic approach by greatly expanding the set of scenarios for which entropic constraints are known. For the first time, we treat Bell scenarios involving multiple parties and multiple observables per party. Going beyond the usual Bell setup, we exhibit inequalities for scenarios with extra conditional independence assumptions, as well as a limited amount of shared randomness between the parties. Many of our results are based on a geometric observation: Bell polytopes for two-outcome measurements can be naturally imbedded into the convex cone of attainable marginal entropies. Thus, any entropic inequality can be translated into one valid for probabilities. In some situations the converse also holds, which provides us with a rich source of candidate entropic inequalities.
Bell inequalities characterize the boundary of the local-realist correlation polytope -- the set of joint probability distributions achievable by classical hidden-variable models. Quantum mechanics exceeds this boundary through non-commutativity, reaching the Tsirelson bound 22 for CHSH. We show that this polytope structure is not specific to quantum foundations: it appears identically in the causal inference literature, where the instrumental inequality, the Balke--Pearl linear programming bounds, and the Tian--Pearl probabilities of causation all arise as facets of the same marginal compatibility polytope. Fine's theorem -- that CHSH inequalities hold if and only if a joint distribution exists -- is precisely the pivot: the instrumental variable model in causal inference is structurally equivalent to the Bell local hidden-variable model, with the instrument playing the role of the measurement setting and the latent confounder playing the role of the hidden variable λ. We develop this correspondence in detail, extending it to algorithmic (Kolmogorov complexity) and entropic formulations of Bell inequalities, the NPA semidefinite programming hierarchy, and the MIP∗=RE undecidability result. We further show that the Born-rule / Bayes-rule duality underlying quantum Bayesian computation exploits the same non-commutativity that enables Bell violation, providing polynomial speedups for posterior inference. The framework yields a concrete dictionary between quantum information theory, causal econometrics, and Bayesian computation, and suggests new directions including NPA-based quantum causal inference algorithms and quantum architectures for function approximation.
In this thesis, we present optimization tools for different problems in quantum information theory. First, we introduce an algorithm for quantum estate estimation. The algorithm consists of orthogonal projections on intersecting hyperplanes, which are determined by the probability distributions and the measurement operators. We show its performance, in both runtime and fidelity, considering realistic errors. Second, we present a technique for certifying quantum non-locality. Given a set of bipartite measurement frequencies, this technique finds a Bell inequality that maximizes the gap between the local hidden variable and the quantum value of a Bell inequality. Lastly, to study the quantum marginal problem, we introduce an operator and develop an algorithm, which takes as inputs a set of quantum marginals and eigenvalues, and outputs a density matrix, if exists, compatible with the prescribed data.
Consider the problem of deciding, for a particular multipartite quantum state, whether or not it is realizable in a quantum network with a particular causal structure. This is a fully quantum version of what causal inference researchers refer to as the problem of causal discovery. In this work, we introduce a fully quantum version of the inflation technique for causal inference, which leverages the quantum marginal problem. The primary example by which we illustrate the utility of this method is testing compatibility of tripartite quantum states with the quantum network known as the triangle scenario. We show, in particular, how the method yields a complete classification of pure three-qubit states into those that are and those that are not compatible with the triangle scenario. We also provide some illustrative examples involving mixed-states and some where one or more of the systems is higher dimensional. Furthermore, we examine the question of when the incompatibility of a multipartite quantum state with a causal structure can be inferred from the incompatibility of a joint probability distribution induced by implementing measurements on each subsystem. Finally, we present a family of networks, which includes the triangle scenario as a special case, for which causal compatibility constraints can be derived.
The information-theoretic approach to Bell's theorem is developed with use of the conditional q-entropies. The q-entropic measures fulfill many similar properties to the standard Shannon entropy. In general, both the locality and noncontextuality notions are usually treated with use of the so-called marginal scenarios. These hypotheses lead to the existence of a joint probability distribution, which marginalizes to all particular ones. Assuming the existence of such a joint probability distribution, we derive the family of inequalities of Bell's type in terms of conditional q-entropies for all q≥1. Quantum violations of the new inequalities are exemplified within the Clauser--Horne--Shimony--Holt (CHSH) and Klyachko--Can--Binicio\v{g}lu--Shumovsky (KCBS) scenarios. An extension to the case of n-cycle scenario is briefly mentioned. The new inequalities with conditional q-entropies allow to expand a class of probability distributions, for which the nonlocality or contextuality can be detected within entropic formulation. The q-entropic inequalities can also be useful in analyzing cases with detection inefficiencies. Using two models of such a kind, we consider some potential advantages of the q-entropic formulation.
As with entanglement, different forms of Bell nonlocality arise in the multipartite scenario. These can be defined in terms of relaxations of the causal assumptions in local hidden-variable theories. However, a characterisation of all the forms of multipartite nonlocality has until now been out of reach, mainly due to the complexity of generic multipartite causal models. Here, we employ the formalism of Bayesian networks to reveal connections among different causal structures that make a both practical and physically meaningful classification possible. Our framework holds for arbitrarily many parties. We apply it to study the tripartite scenario in detail, where we fully characterize all the nonlocality classes. Remarkably, we identify new highly nonlocal causal structures that cannot reproduce all quantum correlations. This shows, to our knowledge, the strongest form of quantum multipartite nonlocality known to date. Finally, as a by-product result, we derive a non-trivial Bell-type inequality with no quantum violation. Our findings constitute a significant step forward in the understanding of multipartite Bell nonlocality and open several venues for future research.