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

IEEE International Symposium on Information Theory (ISIT)

Quantum message-passing algorithm for optimal and efficient decoding

Christophe Piveteau, Joseph M. Renes

Published Jun 26, 2022• 3 citations
Publisher

Abstract

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 classical-quantum channel [1]. 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. 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 which causes quantum circuit realizations to be exponentially large in the code size. We remedy this problem by formulating a truly message-passing algorithm which approximates BPQM and has circuit complexity, ${\mathcal{O}}\left({{\text{ poly }}n{\text{, polylog }}\frac{1}{ \in }}\right)$, 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.

DOI
10.1109/isit50566.2022.9834749

Related papers

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 Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes

Avijit Mandal, Christophe Piveteau, Joseph M. Renes +1 more

Belief propagation with quantum messages (BPQM) is a quantum algorithm that decodes classical codes transmitted over classical--quantum channels. It realizes optimal decoding on tree factor graphs over pure-state classical-quantum channels. However, this tree-based analysis does not ensure vanishing block-error probability for LDPC Tanner graphs with cycles. In this work, we construct a two-stage BPQM decoder for random $q$-ary LDPC codes over symmetric $q$-ary pure-state channels, where $q$ is prime, and prove that its ensemble-average block-error probability vanishes as the blocklength $N$ tends to infinity. For regular ensembles with $d_v\geq3$, fidelity bounds yield double-exponential decay of the average symbol-error probability throughout the BPQM success region. We apply depth-$\ell$ BPQM to coordinates with tree neighbourhoods and treat the remaining coordinates as erasures. With a suitable $\ell=Θ(\log\log N)$, a noncommutative union bound controls the BPQM decoding errors, while the minimum-distance property guarantees erasure recovery. We also extend the analysis to finite-support irregular ensembles. These results are relevant to quantum algorithms based on Regev's reduction, where coherent decoding uncomputes a codeword register. Decoded quantum interferometry (DQI) uses a closely related Fourier-based framework that reduces sparse max-LINSAT optimization problems to LDPC decoding problems on pure-state channels. Our results justify the use of BPQM in the decoding step of DQI and of coding-theoretic algorithms based on Regev's reduction whenever the code is drawn from one of the random LDPC ensembles analyzed here and the induced memoryless symmetric pure-state channel lies in the BPQM success region. Curiously, our numerical results indicate that DQI+BPQM achieves a satisfaction ratio that closely matches that of simulated annealing.

quant-pharXiv:2609.05857•Sep 8, 2026•0 citations

Belief Propagation with Quantum Messages for Symmetric Classical-Quantum Channels

Sarah Brandsen, Avijit Mandal, Henry D. Pfister

Belief propagation (BP) is a classical algorithm that approximates the marginal distribution associated with a factor graph by passing messages between adjacent nodes in the graph. It gained popularity in the 1990’s as a powerful decoding algorithm for LDPC codes. In 2016, Renes introduced a belief propagation with quantum messages (BPQM) and described how it could be used to decode classical codes defined by tree factor graphs that are sent over the classical-quantum pure-state channel. In this work, we propose an extension of BPQM to general binary-input symmetric classical-quantum (BSCQ) channels based on the implementation of a symmetric "paired measurement". While this new paired-measurement BPQM (PMBPQM) approach is suboptimal in general, it provides a concrete BPQM decoder that can be implemented with local operations. Finally, we demonstrate that density evolution can be used to analyze the performance of PMBPQM on tree factor graphs. As an application, we compute noise thresholds of some LDPC codes with BPQM decoding for a class of BSCQ channels.

arXiv:2207.04984•IEEE Information Theory Workshop (ITW)•Nov 1, 2022•5 citations

Belief Propagation with Quantum Messages for Symmetric Q-ary Pure-State Channels

Avijit Mandal, Henry D. Pfister

Belief propagation with quantum messages (BPQM) provides a low-complexity alternative to collective measurements for communication over classical--quantum channels. Prior BPQM constructions and density-evolution (DE) analyses have focused on binary alphabets. Here, we generalize BPQM to symmetric q-ary pure-state channels (PSCs) whose output Gram matrix is circulant. For this class, we show that bit-node and check-node combining can be tracked efficiently via closed-form recursions on the Gram-matrix eigenvalues, independent of the particular physical realization of the output states. These recursions yield explicit BPQM unitaries and analytic bounds on the fidelities of the combined channels in terms of the input-channel fidelities. This provides a DE framework for symmetric q-ary PSCs that allows one to estimate BPQM decoding thresholds for LDPC codes and to construct polar codes on these channels.

cs.ITCross-listedarXiv:2601.21330•IEEE International Symposium on Information Theory (ISIT)•Jan 30, 2026•0 citations

Belief Propagation for Classical and Quantum Systems: Overview and Recent Results

Henry D. Pfister, Christophe Piveteau, Joseph M. Renes +1 more

This article reviews belief propagation (BP) for classical inference problems and describes its extension to quantum systems, which is known as BP with quantum messages (BPQM). Since BP plays a key role in many low-complexity decoders for error-correcting codes, BPQM enables the practical extension of these decoders to classical quantum channels, such as the pure state channel.

IEEE BITS the Information Theory Magazine•Dec 1, 2022•5 citations

Quantum Message Passing for Factor Graphs over Finite Abelian Groups

Avijit Mandal, Henry D. Pfister

We develop a quantum message-passing framework for factor graphs over finite abelian groups. Our starting point is the task of discriminating between a collection of quantum states indexed by the elements of a finite abelian group $\mathcal{G}$ whose overlaps respect the structure of a group-covariant pure-state channel (PSC). For such channels, we show that the Gram matrix constructed from the output states is diagonalized by the character basis of the dual group $\widehat{\mathcal{G}}$. Hence, the channel is characterized, up to isometric equivalence, by its character-indexed eigen list. Based on this representation, we analyze the induced classical-quantum channels associated with check, equality, homomorphism, marginalization, and automorphism factors. For each factor, we derive explicit update rules showing that if the incoming messages are heralded mixtures of group-covariant PSCs, then the outgoing message remains in the same class. This provides a closed quantum message-passing framework for tree-structured factor graphs assembled from these primitives. The framework applies directly to several standard code families over finite abelian groups, including polar codes, LDPC codes, and convolutional and turbo codes. It recovers the previously studied $q$-ary formulation as the special case $(\mathcal{G}=\mathbb{Z}_q)$, while extending the belief propagation with quantum messages (BPQM) framework introduced by Renes to non-cyclic alphabets and more general factor-graph constraints described by homomorphisms between products of abelian groups.

quant-pharXiv:2604.12186•Apr 15, 2026•0 citations
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 classical-quantum channel [1]. 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. 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 which causes quantum circuit realizations to be exponentially large in the code size. We remedy this problem by formulating a truly message-passing algorithm which approximates BPQM and has circuit complexity, O( poly n, polylog 1∈){\mathcal{O}}\left({{\text{ poly }}n{\text{, polylog }}\frac{1}{ \in }}\right)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.
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.
Belief propagation with quantum messages (BPQM) is a quantum algorithm that decodes classical codes transmitted over classical--quantum channels. It realizes optimal decoding on tree factor graphs over pure-state classical-quantum channels. However, this tree-based analysis does not ensure vanishing block-error probability for LDPC Tanner graphs with cycles. In this work, we construct a two-stage BPQM decoder for random qqq-ary LDPC codes over symmetric qqq-ary pure-state channels, where qqq is prime, and prove that its ensemble-average block-error probability vanishes as the blocklength NNN tends to infinity. For regular ensembles with dv≥3d_v\geq3dv​≥3, fidelity bounds yield double-exponential decay of the average symbol-error probability throughout the BPQM success region. We apply depth-ℓ\ellℓ BPQM to coordinates with tree neighbourhoods and treat the remaining coordinates as erasures. With a suitable ℓ=Θ(log⁡log⁡N)\ell=Θ(\log\log N)ℓ=Θ(loglogN), a noncommutative union bound controls the BPQM decoding errors, while the minimum-distance property guarantees erasure recovery. We also extend the analysis to finite-support irregular ensembles. These results are relevant to quantum algorithms based on Regev's reduction, where coherent decoding uncomputes a codeword register. Decoded quantum interferometry (DQI) uses a closely related Fourier-based framework that reduces sparse max-LINSAT optimization problems to LDPC decoding problems on pure-state channels. Our results justify the use of BPQM in the decoding step of DQI and of coding-theoretic algorithms based on Regev's reduction whenever the code is drawn from one of the random LDPC ensembles analyzed here and the induced memoryless symmetric pure-state channel lies in the BPQM success region. Curiously, our numerical results indicate that DQI+BPQM achieves a satisfaction ratio that closely matches that of simulated annealing.
Belief propagation (BP) is a classical algorithm that approximates the marginal distribution associated with a factor graph by passing messages between adjacent nodes in the graph. It gained popularity in the 1990’s as a powerful decoding algorithm for LDPC codes. In 2016, Renes introduced a belief propagation with quantum messages (BPQM) and described how it could be used to decode classical codes defined by tree factor graphs that are sent over the classical-quantum pure-state channel. In this work, we propose an extension of BPQM to general binary-input symmetric classical-quantum (BSCQ) channels based on the implementation of a symmetric "paired measurement". While this new paired-measurement BPQM (PMBPQM) approach is suboptimal in general, it provides a concrete BPQM decoder that can be implemented with local operations. Finally, we demonstrate that density evolution can be used to analyze the performance of PMBPQM on tree factor graphs. As an application, we compute noise thresholds of some LDPC codes with BPQM decoding for a class of BSCQ channels.
Belief propagation with quantum messages (BPQM) provides a low-complexity alternative to collective measurements for communication over classical--quantum channels. Prior BPQM constructions and density-evolution (DE) analyses have focused on binary alphabets. Here, we generalize BPQM to symmetric q-ary pure-state channels (PSCs) whose output Gram matrix is circulant. For this class, we show that bit-node and check-node combining can be tracked efficiently via closed-form recursions on the Gram-matrix eigenvalues, independent of the particular physical realization of the output states. These recursions yield explicit BPQM unitaries and analytic bounds on the fidelities of the combined channels in terms of the input-channel fidelities. This provides a DE framework for symmetric q-ary PSCs that allows one to estimate BPQM decoding thresholds for LDPC codes and to construct polar codes on these channels.
We develop a quantum message-passing framework for factor graphs over finite abelian groups. Our starting point is the task of discriminating between a collection of quantum states indexed by the elements of a finite abelian group G\mathcal{G}G whose overlaps respect the structure of a group-covariant pure-state channel (PSC). For such channels, we show that the Gram matrix constructed from the output states is diagonalized by the character basis of the dual group G^\widehat{\mathcal{G}}G​. Hence, the channel is characterized, up to isometric equivalence, by its character-indexed eigen list. Based on this representation, we analyze the induced classical-quantum channels associated with check, equality, homomorphism, marginalization, and automorphism factors. For each factor, we derive explicit update rules showing that if the incoming messages are heralded mixtures of group-covariant PSCs, then the outgoing message remains in the same class. This provides a closed quantum message-passing framework for tree-structured factor graphs assembled from these primitives. The framework applies directly to several standard code families over finite abelian groups, including polar codes, LDPC codes, and convolutional and turbo codes. It recovers the previously studied qqq-ary formulation as the special case (G=Zq)(\mathcal{G}=\mathbb{Z}_q)(G=Zq​), while extending the belief propagation with quantum messages (BPQM) framework introduced by Renes to non-cyclic alphabets and more general factor-graph constraints described by homomorphisms between products of abelian groups.