Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

National Conference on Artificial Intelligence

Markov Entanglement Networks

Pierfrancesco La Mura, Lukasz Swiatczak

Published Jan 1, 2007• 3 citations
OpenAlex

Abstract

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.

Related papers

Markovian Entanglement Networks

Pierfrancesco La Mura, Lukasz Swiatczak

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.

arXiv:quant-ph/0702072•Feb 7, 2007•9 citations

Factorization of Quantum Density Matrices According to Bayesian and Markov Networks

Robert R. Tucci

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.

arXiv:quant-ph/0701201•Jan 28, 2007•11 citations

Probabilistic Graphical Models and Tensor Networks: A Hybrid Framework

Jacob Miller, Geoffrey Roeder, Tai-Danae Bradley

We investigate a correspondence between two formalisms for discrete probabilistic modeling: probabilistic graphical models (PGMs) and tensor networks (TNs), a powerful modeling framework for simulating complex quantum systems. The graphical calculus of PGMs and TNs exhibits many similarities, with discrete undirected graphical models (UGMs) being a special case of TNs. However, more general probabilistic TN models such as Born machines (BMs) employ complex-valued hidden states to produce novel forms of correlation among the probabilities. While representing a new modeling resource for capturing structure in discrete probability distributions, this behavior also renders the direct application of standard PGM tools impossible. We aim to bridge this gap by introducing a hybrid PGM-TN formalism that integrates quantum-like correlations into PGM models in a principled manner, using the physically-motivated concept of decoherence. We first prove that applying decoherence to the entirety of a BM model converts it into a discrete UGM, and conversely, that any subgraph of a discrete UGM can be represented as a decohered BM. This method allows a broad family of probabilistic TN models to be encoded as partially decohered BMs, a fact we leverage to combine the representational strengths of both model families. We experimentally verify the performance of such hybrid models in a sequential modeling task, and identify promising uses of our method within the context of existing applications of graphical models.

arXiv:2106.15666•Jun 29, 2021•11 citations

Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden Markov models to quantum machine learning

Ivan Glasser, Ryan Sweke, Nicola Pancotti +2 more

Tensor-network techniques have enjoyed outstanding success in physics, and have recently attracted attention in machine learning, both as a tool for the formulation of new learning algorithms and for enhancing the mathematical understanding of existing methods. Inspired by these developments, and the natural correspondence between tensor networks and probabilistic graphical models, we provide a rigorous analysis of the expressive power of various tensor-network factorizations of discrete multivariate probability distributions. These factorizations include non-negative tensor-trains/MPS, which are in correspondence with hidden Markov models, and Born machines, which are naturally related to local quantum circuits. When used to model probability distributions, they exhibit tractable likelihoods and admit efficient learning algorithms. Interestingly, we prove that there exist probability distributions for which there are unbounded separations between the resource requirements of some of these tensor-network factorizations. Particularly surprising is the fact that using complex instead of real tensors can lead to an arbitrarily large reduction in the number of parameters of the network. Additionally, we introduce locally purified states (LPS), a new factorization inspired by techniques for the simulation of quantum systems, with provably better expressive power than all other representations considered. The ramifications of this result are explored through numerical experiments. Our findings imply that LPS should be considered over hidden Markov models, and furthermore provide guidelines for the design of local quantum circuits for probabilistic modeling.

arXiv:1907.03741•Jul 8, 2019•43 citations

Quantum Enhanced Inference in Markov Logic Networks

Péter Wittek, Christian Gogolin

Markov logic networks (MLNs) reconcile two opposing schools in machine learning and artificial intelligence: causal networks, which account for uncertainty extremely well, and first-order logic, which allows for formal deduction. An MLN is essentially a first-order logic template to generate Markov networks. Inference in MLNs is probabilistic and it is often performed by approximate methods such as Markov chain Monte Carlo (MCMC) Gibbs sampling. An MLN has many regular, symmetric structures that can be exploited at both first-order level and in the generated Markov network. We analyze the graph structures that are produced by various lifting methods and investigate the extent to which quantum protocols can be used to speed up Gibbs sampling with state preparation and measurement schemes. We review different such approaches, discuss their advantages, theoretical limitations, and their appeal to implementations. We find that a straightforward application of a recent result yields exponential speedup compared to classical heuristics in approximate probabilistic inference, thereby demonstrating another example where advanced quantum resources can potentially prove useful in machine learning.

arXiv:1611.08104•Scientific Reports•Apr 19, 2017•28 citations

Quantum and Classical Markovian Graphical Causal Models and Their Identification

Barrett, Jonathan, Isaac Friend, Kissinger, Aleks

Markov categories allow formalization of probabilistic and causal reasoning in a general setting that applies uniformly to many different kinds of classical probabilistic processes. It has so far been challenging, however, to generalize these techniques to reasoning about quantum processes, as the quantum no-cloning theorem forbids "copy" maps of the sort that have been used to axiomatize conditional independence, and the related notions of complete common causes and Markovianity, in classical Bayesian networks. Here, we introduce a new categorical notion of Markovian causal model, according to which a distinguished subcategory of "common cause" maps plays a similar role to that of "copy" maps in the categorical formulation of Bayesian networks. Moreover, defining causal models as second-order processes yields a clean and flexible formulation of interventions. Our formalism is both rich enough to handle "complete common cause" assumptions and general enough to encompass not only standard classical causal identification scenarios, but also quantum causal scenarios and new kinds of classical causal identification based on imperfect observations. Furthermore, we show that one can reason uniformly across all of these cases using string-diagrammatic techniques.

Leibniz international proceedings in informatics•Jan 1, 2025•4 citations
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.
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.
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 investigate a correspondence between two formalisms for discrete probabilistic modeling: probabilistic graphical models (PGMs) and tensor networks (TNs), a powerful modeling framework for simulating complex quantum systems. The graphical calculus of PGMs and TNs exhibits many similarities, with discrete undirected graphical models (UGMs) being a special case of TNs. However, more general probabilistic TN models such as Born machines (BMs) employ complex-valued hidden states to produce novel forms of correlation among the probabilities. While representing a new modeling resource for capturing structure in discrete probability distributions, this behavior also renders the direct application of standard PGM tools impossible. We aim to bridge this gap by introducing a hybrid PGM-TN formalism that integrates quantum-like correlations into PGM models in a principled manner, using the physically-motivated concept of decoherence. We first prove that applying decoherence to the entirety of a BM model converts it into a discrete UGM, and conversely, that any subgraph of a discrete UGM can be represented as a decohered BM. This method allows a broad family of probabilistic TN models to be encoded as partially decohered BMs, a fact we leverage to combine the representational strengths of both model families. We experimentally verify the performance of such hybrid models in a sequential modeling task, and identify promising uses of our method within the context of existing applications of graphical models.
Tensor-network techniques have enjoyed outstanding success in physics, and have recently attracted attention in machine learning, both as a tool for the formulation of new learning algorithms and for enhancing the mathematical understanding of existing methods. Inspired by these developments, and the natural correspondence between tensor networks and probabilistic graphical models, we provide a rigorous analysis of the expressive power of various tensor-network factorizations of discrete multivariate probability distributions. These factorizations include non-negative tensor-trains/MPS, which are in correspondence with hidden Markov models, and Born machines, which are naturally related to local quantum circuits. When used to model probability distributions, they exhibit tractable likelihoods and admit efficient learning algorithms. Interestingly, we prove that there exist probability distributions for which there are unbounded separations between the resource requirements of some of these tensor-network factorizations. Particularly surprising is the fact that using complex instead of real tensors can lead to an arbitrarily large reduction in the number of parameters of the network. Additionally, we introduce locally purified states (LPS), a new factorization inspired by techniques for the simulation of quantum systems, with provably better expressive power than all other representations considered. The ramifications of this result are explored through numerical experiments. Our findings imply that LPS should be considered over hidden Markov models, and furthermore provide guidelines for the design of local quantum circuits for probabilistic modeling.
Markov logic networks (MLNs) reconcile two opposing schools in machine learning and artificial intelligence: causal networks, which account for uncertainty extremely well, and first-order logic, which allows for formal deduction. An MLN is essentially a first-order logic template to generate Markov networks. Inference in MLNs is probabilistic and it is often performed by approximate methods such as Markov chain Monte Carlo (MCMC) Gibbs sampling. An MLN has many regular, symmetric structures that can be exploited at both first-order level and in the generated Markov network. We analyze the graph structures that are produced by various lifting methods and investigate the extent to which quantum protocols can be used to speed up Gibbs sampling with state preparation and measurement schemes. We review different such approaches, discuss their advantages, theoretical limitations, and their appeal to implementations. We find that a straightforward application of a recent result yields exponential speedup compared to classical heuristics in approximate probabilistic inference, thereby demonstrating another example where advanced quantum resources can potentially prove useful in machine learning.
Markov categories allow formalization of probabilistic and causal reasoning in a general setting that applies uniformly to many different kinds of classical probabilistic processes. It has so far been challenging, however, to generalize these techniques to reasoning about quantum processes, as the quantum no-cloning theorem forbids "copy" maps of the sort that have been used to axiomatize conditional independence, and the related notions of complete common causes and Markovianity, in classical Bayesian networks. Here, we introduce a new categorical notion of Markovian causal model, according to which a distinguished subcategory of "common cause" maps plays a similar role to that of "copy" maps in the categorical formulation of Bayesian networks. Moreover, defining causal models as second-order processes yields a clean and flexible formulation of interventions. Our formalism is both rich enough to handle "complete common cause" assumptions and general enough to encompass not only standard classical causal identification scenarios, but also quantum causal scenarios and new kinds of classical causal identification based on imperfect observations. Furthermore, we show that one can reason uniformly across all of these cases using string-diagrammatic techniques.