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 correction (QEC) requires accurate and efficient decoders, yet belief propagation (BP), despite its linear decoding complexity, often provides insufficient logical accuracy on surface codes. We propose Logical Neural Belief Propagation (L-NBP), a BP-based neural decoder that redirects the decoding objective from physical-level to logical-level decoding. L-NBP uses a neural BP (NBP) module to produce posterior beliefs, which a logical classifier transforms into a continuous-valued soft syndrome for logical-operator prediction. Trained end-to-end by backpropagation, the NBP module learns soft syndromes that are favorable for logical classification. On surface codes, L-NBP matches or outperforms BP with ordered-statistics decoding (BP-OSD) and minimum-weight perfect matching (MWPM) while retaining the linear complexity of BP, and achieves a threshold of
17.5% under depolarizing noise. Under circuit-level noise, L-NBP matches the accuracy of BP-OSD on the distance-
9 surface code while requiring only
0.2% of its complexity.
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.
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.
Belief propagation (BP) combined with ordered statistics decoding (OSD) can achieve near-optimal logical error rates for surface codes. However, OSD requires high-latency and unstable-complexity Gaussian elimination (GE), limiting its practicality. In this paper, we propose BP-LCGCD, a GE-free and high-performance decoder that replaces the GE-based OSD with the GE-free LC-GCD. Moreover, in contrast to the original BP-OSD, which adopts a single fixed normalization factor α, we further propose a list-parameterized variant, BP-LCGCD+ α, which performs multiple BP decodings with different α to generate diverse posterior LLRs. We present complexity analysis, demonstrating that at low physical error rates, the average decoding complexity of the proposed algorithm approaches that of standard BP. Simulation results demonstrate that BP-LCGCD achieves logical error rates close to BP-OSD, while BP-LCGCD+α nearly matches the performance of the BP-OSD. They also show that both proposed decoders significantly outperform standard BP and minimum-weight perfect matching (MWPM) in terms of logical error rate and threshold.
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≲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(Nlog2d) and outperforms BP-OSD at
d=65. The observed
∼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.