Journal of Physics Conference Series

Mathematical structures of loopy belief propagation and cluster variation method

Kazuyuki Tanaka

Published Jan 7, 2009• 1 citation

Abstract

The mathematical structures of loopy belief propagation are reviewed for graphical models in probabilistic information processing in the stand point of cluster variation method. An extension of adaptive TAP approaches is given by introducing a generalized scheme of the cluster variation method. Moreover the practical message update rules in loopy belief propagation are summarized also for quantum systems. It is suggested that the loopy belief propagation can be reformulated for quantum electron systems by using density matrices of ideal quantum lattice gas system.

DOI: 10.1088/1742-6596/143/1/012023

Related papers

Review of Sublinear Modeling in Probabilistic Graphical Models by Statistical Mechanical Informatics and Statistical Machine Learning Theory

Kazuyuki Tanaka

Abstract We review sublinear modeling in probabilistic graphical models by statistical mechanical informatics and statistical machine learning theory. Our statistical mechanical informatics schemes are based on advanced mean-field methods including loopy belief propagations. This chapter explores how phase transitions appear in loopy belief propagations for prior probabilistic graphical models. The frameworks are mainly explained for loopy belief propagations in the Ising model which is one of the elementary versions of probabilistic graphical models. We also expand the schemes to quantum statistical machine learning theory. Our framework can provide us with sublinear modeling based on the momentum space renormalization group methods.

Springer eBooksOct 19, 20211 citation

Belief propagation for general graphical models with loops

Pedro Hack, Hitter, Jonas, Christian B. Mendl +1 more

There is an increasing interest in scaling tensor network methods through belief propagation (BP), as well as increasing the accuracy of BP through tensor network methods. We develop a unification framework that takes an arbitrary graphical model with loops and provides message passing update rules and inference equations. We show that recent state-of-the-art methods regarding tensors and BP, like block belief propagation and tensor network message passing, are special instances of our framework. From a practical perspective, we discuss how our framework can be useful to understand the benefits of scheduling in BP, and show how it can be used for decoding purposes in quantum error correction. We simulate the computation of marginals, internal energy, Shannon entropy and the partition function on synthetic topologies (Kagome lattice and lattices resembling quantum error-correcting codes) and a real world topology of a power grid. The results show orders of magnitude accuracy increases for modest computational overheads. For the marginals, for example, we show that our framework can achieve an accuracy improvement of more than six orders of magnitude over tensor network BP.

arXiv:2411.04957Nov 7, 20240 citations

Belief propagation algorithm for computing correlation functions in finite-temperature quantum many-body systems on loopy graphs

David Poulin, Ersen Bilgin

Belief propagation---a powerful heuristic method to solve inference problems involving a large number of random variables---was recently generalized to quantum theory. Like its classical counterpart, this algorithm is exact on trees when the appropriate independence conditions are met and is expected to provide reliable approximations when operated on loopy graphs. In this paper, we benchmark the performances of loopy quantum belief propagation (QBP) in the context of finite-temperature quantum many-body physics. Our results indicate that QBP provides reliable estimates of the high-temperature correlation function when the typical loop size in the graph is large. As such, it is suitable, e.g., for the study of quantum spin glasses on Bethe lattices and the decoding of sparse quantum error correction codes.

arXiv:0710.4304Physical Review AMay 16, 200824 citations

A Probabilistic Graphical Model of Quantum Systems

Chen‐Hsiang Yeang

Quantum systems are promising candidates of future computing and information processing devices. In a large system, information about the quantum states and processes may be incomplete and scattered. To integrate the distributed information we propose a quantum version of probabilistic graphical models. Variables in the model (quantum states and measurement outcomes) are linked by several types of operators (unitary, measurement, and merge/split operators). We propose algorithms for three machine learning tasks in quantum probabilistic graphical models: a belief propagation algorithm for inference of unknown states, an iterative algorithm for simultaneous estimation of parameter values and hidden states, and an active learning algorithm to select measurement operators based on observed evidence. We validate these algorithms on simulated data and point out future extensions toward a more comprehensive theory of quantum probabilistic graphical models.

International Conference on Machine Learning and ApplicationsDec 1, 20107 citations

Belief Propagation for Classical and Quantum Systems: Overview and Recent Results

Henry D. Pfister, Christophe Piveteau, Joseph M. Renes +1 more

This article reviews belief propagation (BP) for classical inference problems and describes its extension to quantum systems, which is known as BP with quantum messages (BPQM). Since BP plays a key role in many low-complexity decoders for error-correcting codes, BPQM enables the practical extension of these decoders to classical quantum channels, such as the pure state channel.

IEEE BITS the Information Theory MagazineDec 1, 20225 citations

Quantum graphical models and belief propagation

Matthew Leifer, David Poulin

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.

Jan 1, 200884 citations