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:2212.03214 · Quantum

Generalized Belief Propagation Algorithms for Decoding of Surface Codes

Josias Old, Manuel Rispler

Published Jun 7, 2023• 19 citations
arXivHTMLPDF

Abstract

Belief propagation (BP) is well-known as a low complexity decoding algorithm with a strong performance for important classes of quantum error correcting codes, e.g. notably for the quantum low-density parity check (LDPC) code class of random expander codes. However, it is also well-known that the performance of BP breaks down when facing topological codes such as the surface code, where naive BP fails entirely to reach a below-threshold regime, i.e. the regime where error correction becomes useful. Previous works have shown, that this can be remedied by resorting to post-processing decoders outside the framework of BP. In this work, we present a generalized belief propagation method with an outer re-initialization loop that successfully decodes surface codes, i.e. opposed to naive BP it recovers the sub-threshold regime known from decoders tailored to the surface code and from statistical-mechanical mappings. We report a threshold of 17% under independent bit-and phase-flip data noise (to be compared to the ideal threshold of 20.6% ) and a threshold value of 14% under depolarizing data noise (compared to the ideal threshold of 18.9% ), which are on par with thresholds achieved by non-BP post-processing methods.

DOI
10.22331/q-2023-06-07-1037

Related papers

Neural Network Belief Propagation and Ordered Statistics Decoding for Quantum Error Correction Codes

Gong, Christina Susan

In the quest for fault-tolerant quantum computation, the delicate nature of qubits demands the need for robust quantum error correction. Quantum error correcting codes, the quantum counterpart to classical error correcting codes in information theory, have been developed to address the unique challenges quantum bits face against the noise of their environment in storing information. These codes include but are not limited to the Kitaev surface code, toric code, rotated surface code, generalized bicycle code, and bivariate bicycle code. Fast and reliable decoders for these quantum error correcting codes are needed to correct errors and achieve fault tolerance on these qubits. The belief propagation algorithm, which is a efficient and reliable heuristic for decoding classical low-density parity check codes, has been generalized to different types of quantum error correction codes. Paired with the ordered statistics decoding algorithm as a post-processing step from the soft outputs of the belief propagation decoder, belief propagation and ordered statistics decoding has been one of the most promising avenues of efficient quantum error correction. This thesis combines the state-of-the-art belief propagation and ordered statistics decoding algorithms with the exploration of the neural belief propagation algorithm to leverage classical deep learning machines to learn message passing patterns in decoding the newest quantum codes, the rotated surface code and bivariate bicycle code. The neural network exploits the local lattice structure of these codes to adjust the trainable weights and biases to more learn message update patterns more efficiently than the vanilla belief propagation algorithm. In this thesis, we prove a new threshold for the physical error rate on the rotated surface code using a neural belief propagation algorithm and ordered statistics decoding that consistently outperforms the threshold established by the vanilla belief propagation algorithm with ordered statistics decoding. We additionally show the results for similar efforts on the bivariate bicycle codes, and discuss the difficulties in achieving a threshold using the current neural belief propagation algorithms.

•Jan 1, 2025•0 citations

Improved Belief Propagation Decoding Algorithms for Surface Codes

Jiahan Chen, Zhengzhong Yi, Zhipeng Liang +1 more

Quantum error correction is crucial for universal fault-tolerant quantum computing. Highly accurate and low-time-complexity decoding algorithms play an indispensable role in ensuring quantum error correction works effectively. Among existing decoding algorithms, belief propagation (BP) is notable for its nearly linear time complexity and general applicability to stabilizer codes. However, BP's decoding accuracy without post-processing is unsatisfactory in most situations. This article focuses on improving the decoding accuracy of BP over GF(4) for surface codes. Inspired by machine learning optimization techniques, we first propose Momentum-BP and AdaGrad-BP to reduce oscillations in message updating, breaking the trapping sets of surface codes. We further propose EWAInit-BP, which adaptively updates initial probabilities and provides a 1 to 3 orders of magnitude improvement over traditional BP for planar surface code, toric code, and XZZX surface code without any post-processing method, showing high decoding accuracy even under parallel scheduling. The theoretical$O(1)$time complexity under parallel implementation and high accuracy of EWAInit-BP make it a promising candidate for high-precision real-time decoders.

arXiv:2407.11523•IEEE Transactions on Quantum Engineering•Jan 1, 2025•10 citations

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

A High-Performance List Decoding Algorithm for Surface Codes with Erroneous Syndrome

Jifan Liang, Qianfan Wang, Lvzhou Li +1 more

Quantum error-correcting codes (QECCs) are necessary for fault-tolerant quantum computation. Surface codes are a class of topological QECCs that have attracted significant attention due to their exceptional error-correcting capabilities and easy implementation. In the decoding process of surface codes, the syndromes are crucial for error correction, however, they are not always correctly measured. Most of the existing decoding algorithms for surface codes need extra measurements to correct syndromes with errors, which implies a potential increase in inference complexity and decoding latency. In this paper, we propose a high-performance list decoding algorithm for surface codes with erroneous syndromes, where syndrome soft information is incorporated in the decoding, allowing qubits and syndrome to be recovered without needing extra measurements. Precisely, we first use belief propagation (BP) decoding for pre-processing with syndrome soft information, followed by ordered statistics decoding (OSD) for post-processing to list and recover both qubits and syndromes. Numerical results demonstrate that our proposed algorithm efficiently recovers erroneous syndromes and significantly improves the decoding performance of surface codes with erroneous syndromes compared to minimum-weight perfect matching (MWPM), BP and original BP-OSD algorithms.

arXiv:2409.06979•Sep 11, 2024•0 citations

Topological blocking decoder for surface codes

Hyun-Woo Jung, Jeongseok Ha

Surface codes have gained widespread popularity as quantum error-correction codes due to their unique structural feature that encoders and decoders can be implemented by leveraging interactions between physically neighboring qubits. The implementational advantage of surface codes has driven extensive research into decoding algorithms for surface codes, aimed at improving error-rate performance and/or reducing decoding complexity. In this paper, we propose a low-complexity postprocessing algorithm that effectively resolves failures of a syndrome-based belief-propagation (SB-BP) decoder for surface codes. In particular, we carefully analyze the topological structure of surface codes and present a method for selecting reliable qubits, enabling efficient recovery operator identification through a simple syndrome matching technique with a lookup table. Furthermore, we present an efficient way to construct lookup tables tailored to the proposed postprocessing algorithm. Numerical results demonstrate that the proposed postprocessing algorithm requires substantially reduced complexity as compared to that of a competing postprocessing algorithm, the ordered statistics decoding in the depolarizing error model, while providing the same logical error-rate (LER) performance. It is also demonstrated that the combination of SB-BP decoding and the proposed postprocessing algorithm outperforms minimum weight perfect matching, a more computationally expensive decoding algorithm, in terms of LER and threshold at drastically reduced complexity.

Physical Review A•Apr 18, 2025•1 citation

Decoding across the quantum low-density parity-check code landscape

Joschka Roffe, David R. White, Simon Burton +1 more

We show that belief propagation combined with ordered statistics post-processing is a general decoder for quantum low-density parity-check codes constructed from the hypergraph product.To this end, we run numerical simulations of the decoder applied to three families of hypergraph product code: topological codes, fixed-rate random codes, and a new class of codes that we call semitopological codes.Our new code families share properties of both topological and random hypergraph product codes, with a construction that allows for a finely controlled trade-off between code threshold and stabilizer locality.Our results indicate thresholds across all three families of hypergraph product code, and provide evidence of exponential suppression in the low error regime.For the toric code, we observe a threshold in the range 9.9% ± 0.2%.This result improves upon previous quantum decoders based on belief propagation, and approaches the performance of the minimum-weight perfectmatching algorithm.We expect semitopological codes to have the same threshold as toric codes, as they are identical in the bulk, and we present numerical evidence supporting this observation.

arXiv:2005.07016•Physical Review Research•Dec 28, 2020•191 citations
Belief propagation (BP) is well-known as a low complexity decoding algorithm with a strong performance for important classes of quantum error correcting codes, e.g. notably for the quantum low-density parity check (LDPC) code class of random expander codes. However, it is also well-known that the performance of BP breaks down when facing topological codes such as the surface code, where naive BP fails entirely to reach a below-threshold regime, i.e. the regime where error correction becomes useful. Previous works have shown, that this can be remedied by resorting to post-processing decoders outside the framework of BP. In this work, we present a generalized belief propagation method with an outer re-initialization loop that successfully decodes surface codes, i.e. opposed to naive BP it recovers the sub-threshold regime known from decoders tailored to the surface code and from statistical-mechanical mappings. We report a threshold of 17% under independent bit-and phase-flip data noise (to be compared to the ideal threshold of 20.6% ) and a threshold value of 14% under depolarizing data noise (compared to the ideal threshold of 18.9% ), which are on par with thresholds achieved by non-BP post-processing methods.
In the quest for fault-tolerant quantum computation, the delicate nature of qubits demands the need for robust quantum error correction. Quantum error correcting codes, the quantum counterpart to classical error correcting codes in information theory, have been developed to address the unique challenges quantum bits face against the noise of their environment in storing information. These codes include but are not limited to the Kitaev surface code, toric code, rotated surface code, generalized bicycle code, and bivariate bicycle code. Fast and reliable decoders for these quantum error correcting codes are needed to correct errors and achieve fault tolerance on these qubits. The belief propagation algorithm, which is a efficient and reliable heuristic for decoding classical low-density parity check codes, has been generalized to different types of quantum error correction codes. Paired with the ordered statistics decoding algorithm as a post-processing step from the soft outputs of the belief propagation decoder, belief propagation and ordered statistics decoding has been one of the most promising avenues of efficient quantum error correction. This thesis combines the state-of-the-art belief propagation and ordered statistics decoding algorithms with the exploration of the neural belief propagation algorithm to leverage classical deep learning machines to learn message passing patterns in decoding the newest quantum codes, the rotated surface code and bivariate bicycle code. The neural network exploits the local lattice structure of these codes to adjust the trainable weights and biases to more learn message update patterns more efficiently than the vanilla belief propagation algorithm. In this thesis, we prove a new threshold for the physical error rate on the rotated surface code using a neural belief propagation algorithm and ordered statistics decoding that consistently outperforms the threshold established by the vanilla belief propagation algorithm with ordered statistics decoding. We additionally show the results for similar efforts on the bivariate bicycle codes, and discuss the difficulties in achieving a threshold using the current neural belief propagation algorithms.
Quantum error correction is crucial for universal fault-tolerant quantum computing. Highly accurate and low-time-complexity decoding algorithms play an indispensable role in ensuring quantum error correction works effectively. Among existing decoding algorithms, belief propagation (BP) is notable for its nearly linear time complexity and general applicability to stabilizer codes. However, BP's decoding accuracy without post-processing is unsatisfactory in most situations. This article focuses on improving the decoding accuracy of BP over GF(4) for surface codes. Inspired by machine learning optimization techniques, we first propose Momentum-BP and AdaGrad-BP to reduce oscillations in message updating, breaking the trapping sets of surface codes. We further propose EWAInit-BP, which adaptively updates initial probabilities and provides a 1 to 3 orders of magnitude improvement over traditional BP for planar surface code, toric code, and XZZX surface code without any post-processing method, showing high decoding accuracy even under parallel scheduling. The theoreticalO(1)O(1)O(1)time complexity under parallel implementation and high accuracy of EWAInit-BP make it a promising candidate for high-precision real-time decoders.
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.
Quantum error-correcting codes (QECCs) are necessary for fault-tolerant quantum computation. Surface codes are a class of topological QECCs that have attracted significant attention due to their exceptional error-correcting capabilities and easy implementation. In the decoding process of surface codes, the syndromes are crucial for error correction, however, they are not always correctly measured. Most of the existing decoding algorithms for surface codes need extra measurements to correct syndromes with errors, which implies a potential increase in inference complexity and decoding latency. In this paper, we propose a high-performance list decoding algorithm for surface codes with erroneous syndromes, where syndrome soft information is incorporated in the decoding, allowing qubits and syndrome to be recovered without needing extra measurements. Precisely, we first use belief propagation (BP) decoding for pre-processing with syndrome soft information, followed by ordered statistics decoding (OSD) for post-processing to list and recover both qubits and syndromes. Numerical results demonstrate that our proposed algorithm efficiently recovers erroneous syndromes and significantly improves the decoding performance of surface codes with erroneous syndromes compared to minimum-weight perfect matching (MWPM), BP and original BP-OSD algorithms.
Surface codes have gained widespread popularity as quantum error-correction codes due to their unique structural feature that encoders and decoders can be implemented by leveraging interactions between physically neighboring qubits. The implementational advantage of surface codes has driven extensive research into decoding algorithms for surface codes, aimed at improving error-rate performance and/or reducing decoding complexity. In this paper, we propose a low-complexity postprocessing algorithm that effectively resolves failures of a syndrome-based belief-propagation (SB-BP) decoder for surface codes. In particular, we carefully analyze the topological structure of surface codes and present a method for selecting reliable qubits, enabling efficient recovery operator identification through a simple syndrome matching technique with a lookup table. Furthermore, we present an efficient way to construct lookup tables tailored to the proposed postprocessing algorithm. Numerical results demonstrate that the proposed postprocessing algorithm requires substantially reduced complexity as compared to that of a competing postprocessing algorithm, the ordered statistics decoding in the depolarizing error model, while providing the same logical error-rate (LER) performance. It is also demonstrated that the combination of SB-BP decoding and the proposed postprocessing algorithm outperforms minimum weight perfect matching, a more computationally expensive decoding algorithm, in terms of LER and threshold at drastically reduced complexity.
We show that belief propagation combined with ordered statistics post-processing is a general decoder for quantum low-density parity-check codes constructed from the hypergraph product.To this end, we run numerical simulations of the decoder applied to three families of hypergraph product code: topological codes, fixed-rate random codes, and a new class of codes that we call semitopological codes.Our new code families share properties of both topological and random hypergraph product codes, with a construction that allows for a finely controlled trade-off between code threshold and stabilizer locality.Our results indicate thresholds across all three families of hypergraph product code, and provide evidence of exponential suppression in the low error regime.For the toric code, we observe a threshold in the range 9.9% ± 0.2%.This result improves upon previous quantum decoders based on belief propagation, and approaches the performance of the minimum-weight perfectmatching algorithm.We expect semitopological codes to have the same threshold as toric codes, as they are identical in the bulk, and we present numerical evidence supporting this observation.