Factor graphs and the sum-product algorithms form a powerful framework for expressing a great variety of algorithms in coding theory, signal processing, artificial intelligence, and other areas. Two different approaches to derive the sum-product algorithm are given by the so-called closing-the-box operation or by a variational approach known as Bethe free energy function minimization. In this paper we consider a generalization of factor graphs known as quantum factor graphs, along with a generalization of the sum-product algorithm known as the quantum sum-product algorithm. We explore the generalization of the closing-the-box operation and the Bethe free energy function from the classical to the quantum setup. Some expressions that hold exactly in the classical case hold only approximately in the quantum case; we give some analytical and numerical characterizations of these approximations.
Factor graphs and the sum-product algorithms form a powerful framework for expressing a great variety of algorithms in coding theory, signal processing, artificial intelligence, and other areas. Two different approaches to derive the sum-product algorithm are given by the so-called closing-the-box operation or by a variational approach known as Bethe free energy function minimization. In this paper we consider a generalization of factor graphs known as quantum factor graphs, along with a generalization of the sum-product algorithm known as the quantum sum-product algorithm. We explore the generalization of the closing-the-box operation and the Bethe free energy function from the classical to the quantum setup. Some expressions that hold exactly in the classical case hold only approximately in the quantum case; we give some analytical and numerical characterizations of these approximations.
The natural Hilbert Space of quantum particles can implement maximum-likelihood (ML) decoding of classical information. The 'Quantum Product Algorithm' (QPA) is computed on a Factor Graph, where function nodes are unitary matrix operations followed by appropriate quantum measurement. QPA is like the Sum-Product Algorithm (SPA), but without summary, giving optimal decode with exponentially finer detail than achievable using SPA. Graph cycles have no effect on QPA performance. QPA must be repeated a number of times before successful and the ML codeword is obtained only after repeated quantum 'experiments'. ML amplification improves decoding accuracy, and Distributed QPA facilitates successful evolution.
Low-density parity-check codes, turbo codes, and indeed most practically decodable capacity-approaching error correcting codes can all be understood as codes defined on graphs. Graphs not only describe the codes, but, more important, they structure the operation of the sum-product decoding algorithm (or one of many possible variations), which can be used for iterative decoding. Such coding schemes have the potential to approach channel capacity, while maintaining reasonable decoding complexity. In this tutorial article we review factor graphs, which can be used to describe codes and the joint probability distributions that must be dealt with in decoding. We also review the sum-product algorithm, and show how this algorithm leads to iterative decoding algorithms for codes defined on graphs.
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.
Some of the most interesting quantities associated with a factor graph are its marginals and its partition sum. For factor graphs without cycles and moderate message-update complexities, the sum-product algorithm (SPA) can be used to efficiently compute these quantities exactly. Moreover, for various classes of factor graphs with cycles, the SPA has been successfully applied to efficiently compute good approximations to these quantities. Note that in the case of factor graphs with cycles, the local functions are usually non-negative real-valued functions. In this paper we introduce a class of factor graphs, called double-edge factor graphs (DE-FGs), which allow local functions to be complex-valued and only require them, in some suitable sense, to be positive semi-definite kernel functions. We discuss various properties of the SPA when running it on DE-FGs and we show promising numerical results for various example DE-FGs, some of which have connections to quantum information processing.
We present a combinatorial characterization of the Bethe entropy function of a factor graph, such a characterization being in contrast to the original, analytical, definition of this function. We achieve this combinatorial characterization by counting valid configurations in finite graph covers of the factor graph. Analogously, we give a combinatorial characterization of the Bethe partition function, whose original definition was also of an analytical nature. As we point out, our approach has similarities to the replica method, but also stark differences. The above findings are a natural backdrop for introducing a decoder for graph-based codes that we will call symbolwise graph-cover decoding, a decoder that extends our earlier work on blockwise graph-cover decoding. Both graph-cover decoders are theoretical tools that help toward a better understanding of message-passing iterative decoding, namely blockwise graph-cover decoding links max-product (min-sum) algorithm decoding with linear programming decoding, and symbolwise graph-cover decoding links sum-product algorithm decoding with Bethe free energy function minimization at temperature one. In contrast to the Gibbs entropy function, which is a concave function, the Bethe entropy function is in general not concave everywhere. In particular, we show that every code picked from an ensemble of regular low-density parity-check codes with minimum Hamming distance growing (with high probability) linearly with the block length has a Bethe entropy function that is convex in certain regions of its domain.
[...] In this thesis, we are interested in generalizing factor graphs and the relevant methods toward describing quantum systems. Two generalizations of classical graphical models are investigated, namely double-edge factor graphs (DeFGs) and quantum factor graphs (QFGs). Conventionally, a factor in a factor graph represents a nonnegative real-valued local functions. Two different approaches to generalize factors in classical factor graphs yield DeFGs and QFGs, respectively. We proposed/re-proposed and analyzed generalized versions of belief-propagation algorithms for DeFGs/QFGs. As a particular application of the DeFGs, we investigate the information rate and their upper/lower bounds of classical communications over quantum channels with memory. In this study, we also propose a data-driven method for optimizing the upper/lower bounds on information rate.