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:2506.16250

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

Huang, Yuwen, Pascal O. Vontobel

Published Jun 19, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2506.16250

Related papers

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

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

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

Michael X. Cao, Pascal O. Vontobel

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.

arXiv:1706.00752•IEEE Information Theory Workshop (ITW)•Nov 1, 2017•8 citations

Complex-Valued-Matrix Permanents: SPA-based Approximations and Double-Cover Analysis

Junda Zhou, Pascal O. Vontobel

Approximating the permanent of a complex-valued matrix is a fundamental problem with applications in Boson sampling and probabilistic inference. In this paper, we extend factor-graph-based methods for approximating the permanent of non-negative-real-valued matrices that are based on running the sum-product algorithm (SPA) on standard normal factor graphs, to factor-graph-based methods for approximating the permanent of complex-valued matrices that are based on running the SPA on double-edge normal factor graphs. On the algorithmic side, we investigate the behavior of the SPA, in particular how the SPA fixed points change when transitioning from real-valued to complex-valued matrix ensembles. On the analytical side, we use graph covers to analyze the Bethe approximation of the permanent, i.e., the approximation of the permanent that is obtained with the help of the SPA. This combined algorithmic and analytical perspective provides new insight into the structure of Bethe approximations in complex-valued problems and clarifies when such approximations remain meaningful beyond the non-negative-real-valued settings.

cs.ITCross-listedarXiv:2601.18232•IEEE International Symposium on Information Theory (ISIT)•Jan 27, 2026•1 citation

Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function

Pascal O. Vontobel

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.

arXiv:1012.0065•IEEE Transactions on Information Theory•Jul 29, 2013•79 citations

On the relevance of graph covers and zeta functions for the analysis of SPA decoding of cycle codes

Henry D. Pfister, Pascal O. Vontobel

For an arbitrary binary cycle code, we show that sum-product algorithm (SPA) decoding after infinitely many iterations equals symbolwise graph-cover decoding. We do this by characterizing the Bethe free energy function of the underlying normal factor graph (NFG) and by stating a global convergence proof of the SPA. We also show that the set of log-likelihood ratio vectors for which the SPA converges to the all-zero codeword is given by the region of convergence of the edge zeta function associated with the underlying NFG. The results in this paper justify the use of graph-cover pseudo-codewords and edge zeta functions to characterize the behavior of SPA decoding of cycle codes. These results have also implications for the analysis of attenuated sum-product and max-product algorithm decoding of low-density parity-check (LDPC) codes beyond cycle codes.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•7 citations
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.
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.
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.
Approximating the permanent of a complex-valued matrix is a fundamental problem with applications in Boson sampling and probabilistic inference. In this paper, we extend factor-graph-based methods for approximating the permanent of non-negative-real-valued matrices that are based on running the sum-product algorithm (SPA) on standard normal factor graphs, to factor-graph-based methods for approximating the permanent of complex-valued matrices that are based on running the SPA on double-edge normal factor graphs. On the algorithmic side, we investigate the behavior of the SPA, in particular how the SPA fixed points change when transitioning from real-valued to complex-valued matrix ensembles. On the analytical side, we use graph covers to analyze the Bethe approximation of the permanent, i.e., the approximation of the permanent that is obtained with the help of the SPA. This combined algorithmic and analytical perspective provides new insight into the structure of Bethe approximations in complex-valued problems and clarifies when such approximations remain meaningful beyond the non-negative-real-valued settings.
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.
For an arbitrary binary cycle code, we show that sum-product algorithm (SPA) decoding after infinitely many iterations equals symbolwise graph-cover decoding. We do this by characterizing the Bethe free energy function of the underlying normal factor graph (NFG) and by stating a global convergence proof of the SPA. We also show that the set of log-likelihood ratio vectors for which the SPA converges to the all-zero codeword is given by the region of convergence of the edge zeta function associated with the underlying NFG. The results in this paper justify the use of graph-cover pseudo-codewords and edge zeta functions to characterize the behavior of SPA decoding of cycle codes. These results have also implications for the analysis of attenuated sum-product and max-product algorithm decoding of low-density parity-check (LDPC) codes beyond cycle codes.