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

arXiv:1706.00752 · IEEE Information Theory Workshop (ITW)

Double-edge factor graphs: Definition, properties, and examples

Michael X. Cao, Pascal O. Vontobel

Published Nov 1, 2017• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/itw.2017.8277985

Related papers

Graph-Cover-based Characterization of the Bethe Partition Function of Double-Edge Factor Graphs

Huang, Yuwen, Pascal O. Vontobel

For standard factor graphs (S-FGs) with non-negative real-valued local functions, Vontobel provided a combinatorial characterization of the Bethe approximation of the partition function, also known as the Bethe partition function, using finite graph covers. The proof of this characterization, i.e., the graph-cover theorem for S-FGs, heavily relied on the method of types. In this paper, we study double-edge factor graphs (DE-FGs), a class of factor graphs where each local function takes complex values and satisfies some positive semi-definiteness constraints. DE-FGs and their partition functions are particularly relevant for quantum information processing. Approximating the partition function of a DE-FG is more difficult than for an S-FG, as it involves summing complex values instead of non-negative real values. We develop the sum-product algorithm (SPA) fixed-point-based Bethe approximation of the partition function. However, one cannot directly apply the method of types to prove a similar combinatorial characterization as in the case of S-FGs. We provide a combinatorial characterization of the Bethe partition function in terms of finite graph covers for a class of DE-FGs that satisfy a specific, easily checkable condition. Towards proving this characterization, we apply a suitable loop-calculus transform (LCT) to these graphs. Originally, the LCT was introduced by Chertkov and Chernyak as a special linear transform for S-FGs and later extended by Mori. Our proposed LCT is applicable for both DE-FGs and S-FGs and generalizes prior versions by handling zero-valued SPA fixed-point message components, which are common in DE-FGs. Supported by numerical results, we conjecture that this combinatorial characterization of the Bethe partition function in terms of finite graph covers holds more broadly for DE-FGs.

arXiv:2506.16250•Jun 19, 2025•0 citations

Characterizing the Bethe Partition Function of Double-Edge Factor Graphs via Graph Covers

Yuwen Huang, Pascal O. Vontobel

For standard factor graphs (S-FGs), i.e., factor graphs with local functions taking on non-negative real values, Vontobel gave a characterization of the Bethe approximation to the partition function in terms of the partition function of finite graph covers. The proof of that statement heavily relied on the method of types. In this paper we give a similar characterization for so-called double-edge factor graphs (DE-FGs), which are a class of factor graphs where local functions take on complex values and have to satisfy some positive semi-definiteness constraints. Such factor graphs are of interest in quantum information processing. In general, approximating the partition function of DE-FGs is more challenging than for S-FGs because the partition function is a sum of complex values and not just a sum of non-negative real values. In particular, for proving the above-mentioned characterization of the Bethe approximation in terms of finite graph covers, one cannot use the method of types anymore. We overcome this challenge by applying the loop-calculus transform by Chertkov and Chernyak, along with using the symmetricsubspace transform, a novel technique for factor graphs that should be of interest beyond proving the main result of this paper. Currently, the characterization of the Bethe approximation of the partition function of DE-FGs is for DE-FGs satisfying an (easily checkable) condition. However, based on numerical results, we suspect that the characterization holds more broadly.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•1 citation

A note on a decoding algorithm of codes on graphs with small loops

N. Kobayashi, Tomoko K. MATSUSHIMA, Shigeichi Hirasawa

The best-known algorithm for the decoding of low-density parity-check (LDPC) codes is the sum-product algorithm (SPA). The SPA is a message-passing algorithm on a graphical model called a factor graph (FG). The performance of the SPA depends on a structure of loops in a FG. Pearl showed that loops in a graphical model could be erased by the clustering method. This method clusters plural nodes into a single node. In this paper, we show several examples about a decoding on a FG to which the clustering method is applied. And we propose an efficient decoding algorithm for it. For a binary erasure channel (BEC), the performance with this method goes up clearly.

IEEE Information Theory Workshop (ITW)•Jan 1, 2005•1 citation

Finite-Graph-Cover-Based Analysis of Factor Graphs in Classical and Quantum Information Processing Systems

Huang, Yuwen

In this thesis, we leverage finite graph covers to analyze the SPA and the Bethe partition function for both S-FGs and DE-FGs. There are two main contributions in this thesis. The first main contribution concerns a special class of S-FGs where the partition function of each S-FG equals the permanent of a nonnegative square matrix. The Bethe partition function for such an S-FG is called the Bethe permanent. A combinatorial characterization of the Bethe permanent is given by the degree-$M$ Bethe permanent, which is defined based on the degree-$M$ graph covers of the underlying S-FG. In this thesis, we prove a degree-$M$-Bethe-permanent-based lower bound on the permanent of a non-negative square matrix, resolving a conjecture proposed by Vontobel in [IEEE Trans. Inf. Theory, Mar. 2013]. We also prove a degree-$M$-Bethe-permanent-based upper bound on the permanent of a non-negative matrix. In the limit $M \to \infty$, these lower and upper bounds yield known Bethe-permanent-based lower and upper bounds on the permanent of a non-negative square matrix. The second main contribution is giving a combinatorial characterization of the Bethe partition function for DE-FGs in terms of finite graph covers. In general, approximating the partition function of a DE-FG is more challenging than for an S-FG because the partition function of the DE-FG is a sum of complex values and not just a sum of non-negative real values. Moreover, one cannot apply the method of types for proving the combinatorial characterization as in the case of S-FGs. We overcome this challenge by applying a suitable loop-calculus transform (LCT) for both S-FGs and DE-FGs. Currently, we provide a combinatorial characterization of the Bethe partition function in terms of finite graph covers for a class of DE-FGs satisfying an (easily checkable) condition.

arXiv:2412.05942•Dec 8, 2024•0 citations

Quantum Factor Graphs

Matthew Geoffrey Parker

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.

arXiv:quant-ph/0010043•Oct 11, 2000•0 citations

Quantum factor graphs: Closing-the-box operation and variational approaches

Michael X. Cao, Pascal O. Vontobel

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.

International Symposium on Information Theory and its Applications•Oct 1, 2016•2 citations
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.
For standard factor graphs (S-FGs) with non-negative real-valued local functions, Vontobel provided a combinatorial characterization of the Bethe approximation of the partition function, also known as the Bethe partition function, using finite graph covers. The proof of this characterization, i.e., the graph-cover theorem for S-FGs, heavily relied on the method of types. In this paper, we study double-edge factor graphs (DE-FGs), a class of factor graphs where each local function takes complex values and satisfies some positive semi-definiteness constraints. DE-FGs and their partition functions are particularly relevant for quantum information processing. Approximating the partition function of a DE-FG is more difficult than for an S-FG, as it involves summing complex values instead of non-negative real values. We develop the sum-product algorithm (SPA) fixed-point-based Bethe approximation of the partition function. However, one cannot directly apply the method of types to prove a similar combinatorial characterization as in the case of S-FGs. We provide a combinatorial characterization of the Bethe partition function in terms of finite graph covers for a class of DE-FGs that satisfy a specific, easily checkable condition. Towards proving this characterization, we apply a suitable loop-calculus transform (LCT) to these graphs. Originally, the LCT was introduced by Chertkov and Chernyak as a special linear transform for S-FGs and later extended by Mori. Our proposed LCT is applicable for both DE-FGs and S-FGs and generalizes prior versions by handling zero-valued SPA fixed-point message components, which are common in DE-FGs. Supported by numerical results, we conjecture that this combinatorial characterization of the Bethe partition function in terms of finite graph covers holds more broadly for DE-FGs.
For standard factor graphs (S-FGs), i.e., factor graphs with local functions taking on non-negative real values, Vontobel gave a characterization of the Bethe approximation to the partition function in terms of the partition function of finite graph covers. The proof of that statement heavily relied on the method of types. In this paper we give a similar characterization for so-called double-edge factor graphs (DE-FGs), which are a class of factor graphs where local functions take on complex values and have to satisfy some positive semi-definiteness constraints. Such factor graphs are of interest in quantum information processing. In general, approximating the partition function of DE-FGs is more challenging than for S-FGs because the partition function is a sum of complex values and not just a sum of non-negative real values. In particular, for proving the above-mentioned characterization of the Bethe approximation in terms of finite graph covers, one cannot use the method of types anymore. We overcome this challenge by applying the loop-calculus transform by Chertkov and Chernyak, along with using the symmetricsubspace transform, a novel technique for factor graphs that should be of interest beyond proving the main result of this paper. Currently, the characterization of the Bethe approximation of the partition function of DE-FGs is for DE-FGs satisfying an (easily checkable) condition. However, based on numerical results, we suspect that the characterization holds more broadly.
The best-known algorithm for the decoding of low-density parity-check (LDPC) codes is the sum-product algorithm (SPA). The SPA is a message-passing algorithm on a graphical model called a factor graph (FG). The performance of the SPA depends on a structure of loops in a FG. Pearl showed that loops in a graphical model could be erased by the clustering method. This method clusters plural nodes into a single node. In this paper, we show several examples about a decoding on a FG to which the clustering method is applied. And we propose an efficient decoding algorithm for it. For a binary erasure channel (BEC), the performance with this method goes up clearly.
In this thesis, we leverage finite graph covers to analyze the SPA and the Bethe partition function for both S-FGs and DE-FGs. There are two main contributions in this thesis. The first main contribution concerns a special class of S-FGs where the partition function of each S-FG equals the permanent of a nonnegative square matrix. The Bethe partition function for such an S-FG is called the Bethe permanent. A combinatorial characterization of the Bethe permanent is given by the degree-MMM Bethe permanent, which is defined based on the degree-MMM graph covers of the underlying S-FG. In this thesis, we prove a degree-MMM-Bethe-permanent-based lower bound on the permanent of a non-negative square matrix, resolving a conjecture proposed by Vontobel in [IEEE Trans. Inf. Theory, Mar. 2013]. We also prove a degree-MMM-Bethe-permanent-based upper bound on the permanent of a non-negative matrix. In the limit M→∞M \to \inftyM→∞, these lower and upper bounds yield known Bethe-permanent-based lower and upper bounds on the permanent of a non-negative square matrix. The second main contribution is giving a combinatorial characterization of the Bethe partition function for DE-FGs in terms of finite graph covers. In general, approximating the partition function of a DE-FG is more challenging than for an S-FG because the partition function of the DE-FG is a sum of complex values and not just a sum of non-negative real values. Moreover, one cannot apply the method of types for proving the combinatorial characterization as in the case of S-FGs. We overcome this challenge by applying a suitable loop-calculus transform (LCT) for both S-FGs and DE-FGs. Currently, we provide a combinatorial characterization of the Bethe partition function in terms of finite graph covers for a class of DE-FGs satisfying an (easily checkable) condition.
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.
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.