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

Towards Scalable Quaternary Message-Passing Decoding for Quantum Error Correction

Boqing Zhang, Henry D. Pfister, Hanwen Yao, Siyuan Niu

quant-phcs.ITSubmitted May 22, 2026• Announced May 26, 2026• 0 citations
arXivHTMLPDF

Abstract

The scalability and interpretability of message-passing (MP) decoding, such as (quaternary) Belief Propagation, remain open challenges in quantum error correction. Even for surface codes, arguably the first testbed for decoding methods, studies of improved MP decoders have mostly been restricted to small distances ($d \lesssim 19$). Moreover, the mismatch with established message-passing theory limits the decoder's interpretability, making it unclear whether MP decoding can sustain its effectiveness at large system sizes. This work takes a step toward a more principled and interpretable MP decoding framework, with the goal of making MP-based decoding more reliable and bridging theory and practice. We introduce a dilution method, which allows a quaternary Min-Sum (MS) decoder to exhibit an apparent depolarizing threshold of $16\%$ up to distance $20$, outperforming Minimum-Weight Perfect Matching in finite-length regimes. Notably, for $X$-noise, the standard MS decoder under dilution has worst-case complexity $O(N \log^2 d)$ and outperforms BP-OSD at $d=65$. The observed $\sim 9\%$ threshold may correspond to a true asymptotic threshold. Finally, we give a graph-dilution argument that interprets the success of the dilution method and offers insight into when MP algorithms can genuinely scale. Taken together, these results provide encouraging progress toward scalable and interpretable MP decoding in quantum error correction.

Related papers

Achieving Thresholds via Standalone Belief Propagation on Surface Codes

Pedro Hack, Luca Menti, Francisco Lazaro +1 more

The standard approach to Belief Propagation (BP) decoding passes messages on the Tanner graph of the quantum error-correcting (QEC) code, and is known to lack a threshold for the surface code. We propose novel BP decoders that exchange messages on the decoding graph and obtain thresholds (both for code capacity and circuit-level noise) via standalone BP for the surface code under depolarizing noise. Our approach, similarly to the minimum weight perfect matching (MWPM) decoder, is applicable to any graphlike QEC code. The thresholds observed with our decoders are close to those obtained by MWPM. This result opens the path towards scalable hardware-accelerated implementations of MWPM-compatible decoders.

quant-pharXiv:2603.05381•Mar 6, 2026•0 citations

Quaternary-Binary Message-Passing Decoder for Quantum LDPC Codes

Dimitris Chytas, Nithin Raveendran, Asit Kumar Pradhan +1 more

We introduce a low-complexity message-passing quantum error correction algorithm for decoding Quantum Low-Density Parity-Check (QLDPC) stabilizer codes. The proposed decoder operates on the quaternary stabilizer graph but only exchanges binary messages. This leads to a significantly reduced complexity compared to other quaternary belief propagation (BP) algorithms that pass floating-point messages. The efficacy of the proposed decoder is evaluated by providing decoding examples, performance metrics using Monte-Carlo simulations, and complexity analysis. Despite its reduced complexity, the performance loss of the proposed decoder is modest compared to floating-point parallel quaternary decoders for a Calderbank-Shor-Steane (CSS) code family. In particular, experiments obtained over the [[1054, 140, 20]] lifted product (LP) Tanner code demonstrated that for low error rates (< 0.01), the proposed quaternary-binary message-passing decoder approaches the performance of quaternary BP by converging in almost the same number of iterations while requiring less complex operations. Additionally, for non-CSS codes, our decoder performs similarly as quaternary floating-point decoders despite its lower complexity.

Globecom•Dec 4, 2023•0 citations

Multi-path Summation for Decoding 2D Topological Codes

Ben Criger, Imran Ashraf

Fault tolerance is a prerequisite for scalable quantum computing. Architectures based on 2D topological codes are effective for near-term implementations of fault tolerance. To obtain high performance with these architectures, we require a decoder which can adapt to the wide variety of error models present in experiments. The typical approach to the problem of decoding the surface code is to reduce it to minimum-weight perfect matching in a way that provides a suboptimal threshold error rate, and is specialized to correct a specific error model. Recently, optimal threshold error rates for a variety of error models have been obtained by methods which do not use minimum-weight perfect matching, showing that such thresholds can be achieved in polynomial time. It is an open question whether these results can also be achieved by minimum-weight perfect matching. In this work, we use belief propagation and a novel algorithm for producing edge weights to increase the utility of minimum-weight perfect matching for decoding surface codes. This allows us to correct depolarizing errors using the rotated surface code, obtaining a threshold of 17.76 ± 0.02 % . This is larger than the threshold achieved by previous matching-based decoders ( 14.88 ± 0.02 % ), though still below the known upper bound of ∼ 18.9 % .

arXiv:1709.02154•Quantum•Oct 19, 2018•46 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 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.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•3 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

Decoding the surface code using graph neural networks

Moritz Lange

Quantum error correction is essential to achieve fault-tolerant quantum computation in the presence of noisy qubits. Among the most promising approaches to quantum error correction is the surface code, thanks to a scalable two-dimensional architecture, only nearest-neighbor interactions, and a high error threshold. Decoding the surface code, i.e. finding the most likely error chain given a syndrome measurement outcome is a computationally complex task. Traditional decoders rely on classical algorithms, which, especially for larger systems, can be slow and may not always converge to the optimal solution. This thesis presents a novel approach to decoding the surface code using graph neural networks. By mapping the syndrome measurements to a graph and performing graph classification, we find that the graph neural networks can predict the most likely error configuration with high accuracy. Our results show that the GNN-based decoder outperforms the classic minimum weight perfect matching (MWPM) decoder in terms of accuracy. With a phenomenological noise model with depolarizing noise and perfect syndrome measurements, our networks beat MWPM up to code-size 15 across all relevant error rates. Furthermore, the GNN is capable of surpassing MWPM under circuit-level noise up to code size 7. We also show that training the network on repetition code data from a recent experiment [Google Quantum AI, Nature 614, 676 (2023)] produces per-step error rates comparable to those achieved with a matching decoder specifically adapted to the error rates of the physical qubits. This indicates that graph neural network decoders are capable of learning the underlying error distribution on the qubits. Our findings advance the field of quantum error correction and provide a promising new direction for the development of efficient decoding algorithms.

•Oct 17, 2023•0 citations
The scalability and interpretability of message-passing (MP) decoding, such as (quaternary) Belief Propagation, remain open challenges in quantum error correction. Even for surface codes, arguably the first testbed for decoding methods, studies of improved MP decoders have mostly been restricted to small distances (d≲19d \lesssim 19d≲19). Moreover, the mismatch with established message-passing theory limits the decoder's interpretability, making it unclear whether MP decoding can sustain its effectiveness at large system sizes. This work takes a step toward a more principled and interpretable MP decoding framework, with the goal of making MP-based decoding more reliable and bridging theory and practice. We introduce a dilution method, which allows a quaternary Min-Sum (MS) decoder to exhibit an apparent depolarizing threshold of 16%16\%16% up to distance 202020, outperforming Minimum-Weight Perfect Matching in finite-length regimes. Notably, for XXX-noise, the standard MS decoder under dilution has worst-case complexity O(Nlog⁡2d)O(N \log^2 d)O(Nlog2d) and outperforms BP-OSD at d=65d=65d=65. The observed ∼9%\sim 9\%∼9% threshold may correspond to a true asymptotic threshold. Finally, we give a graph-dilution argument that interprets the success of the dilution method and offers insight into when MP algorithms can genuinely scale. Taken together, these results provide encouraging progress toward scalable and interpretable MP decoding in quantum error correction.
The standard approach to Belief Propagation (BP) decoding passes messages on the Tanner graph of the quantum error-correcting (QEC) code, and is known to lack a threshold for the surface code. We propose novel BP decoders that exchange messages on the decoding graph and obtain thresholds (both for code capacity and circuit-level noise) via standalone BP for the surface code under depolarizing noise. Our approach, similarly to the minimum weight perfect matching (MWPM) decoder, is applicable to any graphlike QEC code. The thresholds observed with our decoders are close to those obtained by MWPM. This result opens the path towards scalable hardware-accelerated implementations of MWPM-compatible decoders.
We introduce a low-complexity message-passing quantum error correction algorithm for decoding Quantum Low-Density Parity-Check (QLDPC) stabilizer codes. The proposed decoder operates on the quaternary stabilizer graph but only exchanges binary messages. This leads to a significantly reduced complexity compared to other quaternary belief propagation (BP) algorithms that pass floating-point messages. The efficacy of the proposed decoder is evaluated by providing decoding examples, performance metrics using Monte-Carlo simulations, and complexity analysis. Despite its reduced complexity, the performance loss of the proposed decoder is modest compared to floating-point parallel quaternary decoders for a Calderbank-Shor-Steane (CSS) code family. In particular, experiments obtained over the [[1054, 140, 20]] lifted product (LP) Tanner code demonstrated that for low error rates (< 0.01), the proposed quaternary-binary message-passing decoder approaches the performance of quaternary BP by converging in almost the same number of iterations while requiring less complex operations. Additionally, for non-CSS codes, our decoder performs similarly as quaternary floating-point decoders despite its lower complexity.
Fault tolerance is a prerequisite for scalable quantum computing. Architectures based on 2D topological codes are effective for near-term implementations of fault tolerance. To obtain high performance with these architectures, we require a decoder which can adapt to the wide variety of error models present in experiments. The typical approach to the problem of decoding the surface code is to reduce it to minimum-weight perfect matching in a way that provides a suboptimal threshold error rate, and is specialized to correct a specific error model. Recently, optimal threshold error rates for a variety of error models have been obtained by methods which do not use minimum-weight perfect matching, showing that such thresholds can be achieved in polynomial time. It is an open question whether these results can also be achieved by minimum-weight perfect matching. In this work, we use belief propagation and a novel algorithm for producing edge weights to increase the utility of minimum-weight perfect matching for decoding surface codes. This allows us to correct depolarizing errors using the rotated surface code, obtaining a threshold of 17.76 ± 0.02 % . This is larger than the threshold achieved by previous matching-based decoders ( 14.88 ± 0.02 % ), though still below the known upper bound of ∼ 18.9 % .
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.
Quantum error correction is essential to achieve fault-tolerant quantum computation in the presence of noisy qubits. Among the most promising approaches to quantum error correction is the surface code, thanks to a scalable two-dimensional architecture, only nearest-neighbor interactions, and a high error threshold. Decoding the surface code, i.e. finding the most likely error chain given a syndrome measurement outcome is a computationally complex task. Traditional decoders rely on classical algorithms, which, especially for larger systems, can be slow and may not always converge to the optimal solution. This thesis presents a novel approach to decoding the surface code using graph neural networks. By mapping the syndrome measurements to a graph and performing graph classification, we find that the graph neural networks can predict the most likely error configuration with high accuracy. Our results show that the GNN-based decoder outperforms the classic minimum weight perfect matching (MWPM) decoder in terms of accuracy. With a phenomenological noise model with depolarizing noise and perfect syndrome measurements, our networks beat MWPM up to code-size 15 across all relevant error rates. Furthermore, the GNN is capable of surpassing MWPM under circuit-level noise up to code size 7. We also show that training the network on repetition code data from a recent experiment [Google Quantum AI, Nature 614, 676 (2023)] produces per-step error rates comparable to those achieved with a matching decoder specifically adapted to the error rates of the physical qubits. This indicates that graph neural network decoders are capable of learning the underlying error distribution on the qubits. Our findings advance the field of quantum error correction and provide a promising new direction for the development of efficient decoding algorithms.