We show that any quantum density matrix can be represented by a Bayesian network (a directed acyclic graph), and also by a Markov network (an undirected graph). We show that any Bayesian or Markov net that represents a density matrix, is logically equivalent to a set of conditional independencies (symmetries) satisfied by the density matrix. We show that the d-separation theorems of classical Bayesian and Markov networks generalize in a simple and natural way to quantum physics. The quantum d-separation theorems are shown to be closely connected to quantum entanglement. We show that the graphical rules for d-separation can be used to detect pairs of nodes (or of node sets) in a graph that are unentangled. CMI entanglement (a.k.a. squashed entanglement), a measure of entanglement originally discovered by analyzing Bayesian networks, is an important part of the theory of this paper.
We show that any quantum density matrix can be represented by a Bayesian network (a directed acyclic graph), and also by a Markov network (an undirected graph). We show that any Bayesian or Markov net that represents a density matrix, is logically equivalent to a set of conditional independencies (symmetries) satisfied by the density matrix. We show that the d-separation theorems of classical Bayesian and Markov networks generalize in a simple and natural way to quantum physics. The quantum d-separation theorems are shown to be closely connected to quantum entanglement. We show that the graphical rules for d-separation can be used to detect pairs of nodes (or of node sets) in a graph that are unentangled. CMI entanglement (a.k.a. squashed entanglement), a measure of entanglement originally discovered by analyzing Bayesian networks, is an important part of the theory of this paper.
Belief Propagation algorithms acting on Graphical Models of classical probability distributions, such as Markov Networks, Factor Graphs and Bayesian Networks, are amongst the most powerful known methods for deriving probabilistic inferences amongst large numbers of random variables. This paper presents a generalization of these concepts and methods to the quantum case, based on the idea that quantum theory can be thought of as a noncommutative, operator-valued, generalization of classical probability theory. Some novel characterizations of quantum conditional independence are derived, and definitions of Quantum n-Bifactor Networks, Markov Networks, Factor Graphs and Bayesian Networks are proposed. The structure of Quantum Markov Networks is investigated and some partial characterization results are obtained, along the lines of the Hammersely-Clifford theorem. A Quantum Belief Propagation algorithm is presented and is shown to converge on 1-Bifactor Networks and Markov Networks when the underlying graph is a tree. The use of Quantum Belief Propagation as a heuristic algorithm in cases where it is not known to converge is discussed. Applications to decoding quantum error correcting codes and to the simulation of many-body quantum systems are described.
We study quantum analogues of Bayesian networks on a directed acyclic graph (DAG), distinguishing two constructions for positive definite density operators on finite-dimensional tensor-product Hilbert spaces. The intrinsic construction starts from a joint state and its conditional-independence properties. The extrinsic construction assembles a state sequentially from prescribed local quantum kernels, following an ordering compatible with the arrows of the DAG. For the intrinsic construction, we prove the equivalence of the ordered, local, and global directed Markov properties, together with entropy, recursive-factorization, and logarithmic characterizations. The extrinsic construction always gives a normalized state and recovers each kernel as a conditional on all preceding systems. The same kernel, however, need not be recovered from the marginal on the vertex and its parents; a three-qubit example exhibits this obstruction. We prove that independence of the chosen topological ordering is sufficient exactly for transitive DAGs: every order-invariant kernel family then yields an intrinsically directed Markov state. Finally, we associate a logarithmic candidate with every positive definite state and DAG, prove that it is subnormalized, and show that the trace-one candidate is a directed Markov state. Both the candidate and the excess global information are invariant under DAG Markov equivalence.
Graphical models of probabilistic dependencies have been extensively investigated in the context of classical uncer-tainty. However, in some domains (most notably, in compu-tational physics and quantum computing) the nature of the relevant uncertainty is non-classical, and the laws of clas-sical probability theory are superseded by those of quan-tum mechanics. In this paper we introduce Markov Entan-glement Networks (MEN), a novel class of graphical repre-sentations of quantum-mechanical dependencies in the con-text of such non-classical systems. MEN are the quantum-mechanical analogue of Markovian Networks, a family of undirected graphical representations which, in the classical domain, exploit a notion of conditional independence among subsystems. After defining a notion of conditional independence appropri-ate to our domain (conditional separability), we prove that the conditional separabilities induced by a quantum-mechanical wave function are effectively reflected in the graphical struc-ture of MEN. Specifically, we show that for any wave func-tion there exists a MEN which is a perfect map of its condi-tional separabilities. Next, we show how the graphical struc-ture of MEN can be used to effectively classify the pure states of three-qubit systems. We also demonstrate that, in large systems, exploiting conditional independencies may dramat-ically reduce the computational burden of various inference tasks. In principle, the graph-theoretic representation of con-ditional independencies afforded by MEN may not only fa-cilitate the classical simulation of quantum systems, but also provide a guide to the efficient design and complexity analy-sis of quantum algorithms and circuits.
We give some quantum circuits for calculating the probability P(G∣D) of a graph G given data D. G together with a transition probability matrix for each node of the graph, constitutes a Classical Bayesian Network, or CB net for short. Bayesian methods for calculating P(G∣D) have been given before (the so called structural modular and ordered modular models), but these earlier methods were designed to work on a classical computer. The goal of this paper is to "quantum computerize" those earlier methods.
Graphical models of probabilistic dependencies have been extensively investigated in the context of classical uncertainty. However, in some domains (most notably, in computational physics and quantum computing) the nature of the relevant uncertainty is non-classical, and the laws of classical probability theory are superseded by those of quantum mechanics. In this paper we introduce Markovian Entanglement Networks (MEN), a novel class of graphical representations of quantum-mechanical dependencies in the context of such non-classical systems. MEN are the quantum-mechanical analogue of Markovian Networks, a family of undirected graphical representations which, in the classical domain, exploit a notion of conditional independence among subsystems. After defining a notion of conditional independence appropriate to our domain (conditional separability), we prove that the conditional separabilities induced by a quantum-mechanical wave function are effectively reflected in the graphical structure of MEN. Specifically, we show that for any wave function there exists a MEN which is a perfect map of its conditional separabilities. Next, we show how the graphical structure of MEN can be used to effectively classify the pure states of three-qubit systems. We also demonstrate that, in large systems, exploiting conditional independencies may dramatically reduce the computational burden of various inference tasks. In principle, the graph-theoretic representation of conditional independencies afforded by MEN may not only facilitate the classical simulation of quantum systems, but also provide a guide to the efficient design and complexity analysis of quantum algorithms and circuits.