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 propose a generalization of the cavity method to quantum spin glasses on fixed connectivity lattices. Our work is motivated by the recent refinements of the classical technique and its potential application to quantum computational problems. We numerically solve for the phase structure of a connectivity @math transverse field Ising model on a Bethe lattice with @math couplings and investigate the distribution of various classical and quantum observables. It is shown that if Ф is a finite range interaction of a quantum spin system, τ t Ф the associated group of time translations, τ x the group of space translations, and A, B local observables, then @math (1) whenever v is sufficiently large (ν > V Ф ,) where μ(ν) > 0. The physical content of the statement is that information can propagate in the system only with a finite group velocity. We present an accurate numerical algorithm, called quantum belief propagation, for simulation of one-dimensional quantum systems at nonzero temperature. The algorithm exploits the fact that quantum effects are short-range in these systems at nonzero temperature, decaying on a length scale inversely proportional to the temperature. We compare to exact results on a spin- @math Heisenberg chain. Even a very modest calculation, requiring diagonalizing only ten-by-ten matrices, reproduces the peak susceptibility with a relative error of less than @math , while more elaborate calculations further reduce the error.