In this paper, we investigate the use of quaternary reliability statistics for ordered statistics decoding (OSD) of quantum codes. OSD can be used to improve the performance of belief propagation (BP) decoding when it fails to correct the error syndrome. We propose an approach that leverages quaternary reliability information and the hard-decision history output by BP to perform reliability sorting for OSD. This approach improves upon previous methods that separately treat X and Z errors, by preserving the X/Z correlations during the sorting step. Our simulations show that the refined BP with scalar messages and the proposed OSD outperforms previous BP-OSD combinations. We achieve thresholds of roughly 17.5%–17.7% for toric, surface, and XZZX codes, and 15.42% for hexagonal planar color codes.
In this paper, we investigate the use of quaternary reliability statistics for ordered statistics decoding (OSD) of quantum codes. OSD can be used to improve the performance of belief propagation (BP) decoding when it fails to correct the error syndrome. We propose an approach that leverages quaternary reliability information and the hard-decision history output by BP to perform reliability sorting for OSD. This approach improves upon previous methods that separately treat X and Z errors, by preserving the X/Z correlations during the sorting step. Our simulations show that the refined BP with scalar messages and the proposed OSD outperforms previous BP-OSD combinations. We achieve thresholds of roughly 17.5%–17.7% for toric, surface, and XZZX codes, and 15.42% for hexagonal planar color codes.
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.
Codes based on sparse matrices have good performance and can be efficiently decoded by belief-propagation (BP). Decoding binary stabilizer codes needs a quaternary BP for (additive) codes over GF(4), which has a higher check-node complexity compared to a binary BP for codes over GF(2). Moreover, BP decoding of stabilizer codes suffers a performance loss from the short cycles in the underlying Tanner graph. In this paper, we propose a refined BP algorithm for decoding quantum codes by passing scalar messages. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP but with a check-node complexity the same as binary BP. As every message is a scalar, the message normalization can be naturally applied to improve the performance. Another observation is that the message-update schedule affects the BP decoding performance against short cycles. We show that running BP with message normalization according to a serial schedule (or other schedules) may significantly improve the decoding performance and error-floor in computer simulation.
Belief Propagation combined with Ordered Statistics Decoding (BP OSD) is an open-source decoding tool used widely within the community due to its versatility and ease of application to Quantum Low Density Parity Check (QLDPC) codes. However, the degeneracy of quantum codes has been observed to degrade the performance of BP OSD, particularly leading to error floors for low physical error rates. Here, we investigate the low-weight error configurations responsible for such failures in Bivariate Bicycle codes. We show that, at code capacity, BP OSD fails on errors whose weight is significantly smaller than d/2, arising from global symmetries of the decoding graph that prevent the convergence of parallel BP. Furthermore, our analysis reveals new pitfalls that can arise when analysing the performance of BP OSD in the rare events regime, such as loss of ergodicity in splitting methods and numerical instabilities in the decoder. We show how to mitigate these failure mechanisms by modifying the BP update rules and the decoder implementation, leading to substantial improvement in logical error rate.
Efficient and scalable decoding of quantum codes is essential for high-performance quantum error correction. In this work, we introduce Reliable Subset Reduction (RSR), a reliability-driven preprocessing framework that leverages belief propagation (BP) statistics to identify and remove highly reliable qubits, substantially reducing the effective problem size. Additionally, we identify a degeneracy condition that allows high-order OSD to be simplified to order-0 OSD. By integrating these techniques, we present an ADOSD algorithm that significantly improves OSD efficiency. Our BP+RSR+ADOSD framework extends naturally to circuit-level noise and can handle large-scale codes with more than 104 error variables. Through extensive simulations, we demonstrate improved performance over MWPM and Localized Statistics Decoding for a variety of CSS and non-CSS codes under the code-capacity noise model, and for rotated surface codes under realistic circuit-level noise. At low physical error rates, RSR reduces the effective problem size to as little as 1\% (e.g., for ε=0.001 in surface-code DEM), enabling higher-order OSD with drastically reduced computational complexity. These results highlight the practical efficiency and broad applicability of the BP+ADOSD framework for both theoretical and realistic quantum error correction scenarios.
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.
Quantum stabilizer codes constructed from sparse matrices have good performance and can be efficiently decoded by belief propagation (BP). A conventional BP decoding algorithm treats binary stabilizer codes as additive codes over GF(4). This algorithm has a relatively complex process of handling check-node messages, which incurs higher decoding complexity. Moreover, BP decoding of a stabilizer code usually suffers a performance loss due to the many short cycles in the underlying Tanner graph. In this paper, we propose a refined BP decoding algorithm for quantum codes with complexity roughly the same as binary BP. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP but the passed node-to-node messages are single-valued, unlike the quaternary BP, where multivalued node-to-node messages are required. Furthermore, the techniques of message strength normalization can naturally be applied to these single-valued messages to improve the performance. Another observation is that the message-update schedule affects the performance of BP decoding against short cycles. We show that running BP with message strength normalization according to a serial schedule (or other schedules) may significantly improve the decoding performance and error floor in computer simulation.