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:quant-ph/0010043

Quantum Factor Graphs

Matthew Geoffrey Parker

Published Oct 11, 2000• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0010043

Related papers

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

Pseudocodeword-based Decoding of Quantum Stabilizer Codes

July X. Li, Pascal O. Vontobel

It has been shown that graph-cover pseudocodewords can be used to characterize the behavior of sum-product algorithm (SPA) decoding of classical codes. In this paper, we leverage and adapt these results to analyze SPA decoding of quantum stabilizer codes. We use the obtained insights to formulate modifications to the SPA that overcome some of its weaknesses.

arXiv:1903.01202•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•7 citations

Message-Passing Algorithm

Bane Vasic, Erozan M. Kurtas

A growing interest in the theory and application of iterative decoding algorithms was ignited by the impressive bit-error rate performance of the turbo-decoding algorithm demonstrated by Berrou et al. [3]. In the last several years, the turbo decoding algorithm has been generalized and mathematically formulated using a graph-theoretic approach. Such iterative decoding algorithms operate by “messagepassing” in graphs associated with codes and hence, they are referred to as the message-passing algorithms. The theory of codes on graphs has helped to improve the error performance of low-complexity decoding schemes. Also, it has opened new research avenues for investigating alternative suboptimal decoding schemes. One of the key results in the theory of codes on graphs comes from Kschischang et al. [8,9]. They generalized the concept of codes on graphs by introducing the idea of general functions on graphs. They derived a general distributed marginalization algorithm for function described by factor graphs. The theory of factor graphs and the sum-product algorithm generalizes a variety of algorithms developed in computer science and engineering. The belief propagation algorithm, developed by Pearl [14], operating on Bayesian networks is an instance of the sum-product algorithm operating on an appropriate factor graph.

CRC Press eBooks•Nov 9, 2004•2 citations

Survey of Stochastic Computation on Factor Graphs

Saeed Sharifi Tehrani, Shie Mannor, Warren J. Gross

Stochastic computation is a new alternative approach for iterative computation on factor graphs. In this approach, the information is represented by the statistics of the bit stream which results in simple high-speed hardware implementation of graph-based algorithms. Despite the first purpose of its invention (i.e., low-precision digital circuits), the stochastic representation has recently been shown to be able to provide near-optimal decoding performance for practical Low-Density Parity- Check (LDPC) codes, with respect to Sum-Product Algorithm (SPA). This paper provides a survey of stochastic methods for graph-based iterative decoding, the state-of-the-art and, their possible new applications.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2007•29 citations

Quantum message-passing algorithm for optimal and efficient decoding

Christophe Piveteau, Joseph M. Renes

Recently, Renes proposed a quantum algorithm called belief propagation with quantum messages (BPQM) for decoding classical data encoded using a binary linear code with tree Tanner graph that is transmitted over a pure-state CQ channel \cite{renes_2017}, i.e., a channel with classical input and pure-state quantum output. The algorithm presents a genuine quantum counterpart to decoding based on the classical belief propagation algorithm, which has found wide success in classical coding theory when used in conjunction with LDPC or Turbo codes. More recently Rengaswamy et al. \cite{rengaswamy_2020} observed that BPQM implements the optimal decoder on a small example code, in that it implements the optimal measurement that distinguishes the quantum output states for the set of input codewords with highest achievable probability. Here we significantly expand the understanding, formalism, and applicability of the BPQM algorithm with the following contributions. First, we prove analytically that BPQM realizes optimal decoding for any binary linear code with tree Tanner graph. We also provide the first formal description of the BPQM algorithm in full detail and without any ambiguity. In so doing, we identify a key flaw overlooked in the original algorithm and subsequent works which implies quantum circuit realizations will be exponentially large in the code dimension. Although BPQM passes quantum messages, other information required by the algorithm is processed globally. We remedy this problem by formulating a truly message-passing algorithm which approximates BPQM and has quantum circuit complexity O(poly n,polylog 1ϵ) , where n is the code length and ϵ is the approximation error. Finally, we also propose a novel method for extending BPQM to factor graphs containing cycles by making use of approximate cloning. We show some promising numerical results that indicate that BPQM on factor graphs with cycles can significantly outperform the best possible classical decoder.

arXiv:2109.08170•Quantum•Aug 23, 2022•11 citations

Quantum Graph-Based Machine Learning Framework

Jincheng Zhang

Quantum Graph-Based Machine Learning Framework introduces a novel approach to machine learning utilizing quantum graphs as a foundation. This framework employs automated graph generation and optimization techniques, enabling efficient execution of complex machine learning tasks. The core mechanism centers on leveraging the unique properties of quantum graphs – superposition, entanglement, and interference – to improve the performance of algorithms. This paper explores the design and implementation of this framework, detailing its architecture, functionalities, and potential applications within the field of machine learning.

•Sep 4, 2026•0 citations
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.
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.
A growing interest in the theory and application of iterative decoding algorithms was ignited by the impressive bit-error rate performance of the turbo-decoding algorithm demonstrated by Berrou et al. [3]. In the last several years, the turbo decoding algorithm has been generalized and mathematically formulated using a graph-theoretic approach. Such iterative decoding algorithms operate by “messagepassing” in graphs associated with codes and hence, they are referred to as the message-passing algorithms. The theory of codes on graphs has helped to improve the error performance of low-complexity decoding schemes. Also, it has opened new research avenues for investigating alternative suboptimal decoding schemes. One of the key results in the theory of codes on graphs comes from Kschischang et al. [8,9]. They generalized the concept of codes on graphs by introducing the idea of general functions on graphs. They derived a general distributed marginalization algorithm for function described by factor graphs. The theory of factor graphs and the sum-product algorithm generalizes a variety of algorithms developed in computer science and engineering. The belief propagation algorithm, developed by Pearl [14], operating on Bayesian networks is an instance of the sum-product algorithm operating on an appropriate factor graph.
Stochastic computation is a new alternative approach for iterative computation on factor graphs. In this approach, the information is represented by the statistics of the bit stream which results in simple high-speed hardware implementation of graph-based algorithms. Despite the first purpose of its invention (i.e., low-precision digital circuits), the stochastic representation has recently been shown to be able to provide near-optimal decoding performance for practical Low-Density Parity- Check (LDPC) codes, with respect to Sum-Product Algorithm (SPA). This paper provides a survey of stochastic methods for graph-based iterative decoding, the state-of-the-art and, their possible new applications.
Recently, Renes proposed a quantum algorithm called belief propagation with quantum messages (BPQM) for decoding classical data encoded using a binary linear code with tree Tanner graph that is transmitted over a pure-state CQ channel \cite{renes_2017}, i.e., a channel with classical input and pure-state quantum output. The algorithm presents a genuine quantum counterpart to decoding based on the classical belief propagation algorithm, which has found wide success in classical coding theory when used in conjunction with LDPC or Turbo codes. More recently Rengaswamy et al. \cite{rengaswamy_2020} observed that BPQM implements the optimal decoder on a small example code, in that it implements the optimal measurement that distinguishes the quantum output states for the set of input codewords with highest achievable probability. Here we significantly expand the understanding, formalism, and applicability of the BPQM algorithm with the following contributions. First, we prove analytically that BPQM realizes optimal decoding for any binary linear code with tree Tanner graph. We also provide the first formal description of the BPQM algorithm in full detail and without any ambiguity. In so doing, we identify a key flaw overlooked in the original algorithm and subsequent works which implies quantum circuit realizations will be exponentially large in the code dimension. Although BPQM passes quantum messages, other information required by the algorithm is processed globally. We remedy this problem by formulating a truly message-passing algorithm which approximates BPQM and has quantum circuit complexity O(poly n,polylog 1ϵ) , where n is the code length and ϵ is the approximation error. Finally, we also propose a novel method for extending BPQM to factor graphs containing cycles by making use of approximate cloning. We show some promising numerical results that indicate that BPQM on factor graphs with cycles can significantly outperform the best possible classical decoder.
Quantum Graph-Based Machine Learning Framework introduces a novel approach to machine learning utilizing quantum graphs as a foundation. This framework employs automated graph generation and optimization techniques, enabling efficient execution of complex machine learning tasks. The core mechanism centers on leveraging the unique properties of quantum graphs – superposition, entanglement, and interference – to improve the performance of algorithms. This paper explores the design and implementation of this framework, detailing its architecture, functionalities, and potential applications within the field of machine learning.