Fully Parallelized BP Decoding for Quantum LDPC Codes Can Outperform BP-OSD

Ming Wang, Ang Li, Frank Mueller · 2025

Read Fully Parallelized BP Decoding for Quantum LDPC Codes Can Outperform BP-OSD by Ming Wang, Ang Li, Frank Mueller (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-00254.txt.

Introduction

Ming Wang, Ang Li, and Frank Mueller describe a computer method from 2025 for fixing errors in quantum machines. Their work targets a class of quantum codes that needs fast, low-cost checks. The new decoder watches for bits that flip back and forth during a first pass, then tests flipped versions of the error pattern.

Each test runs on its own, so the work can spread across many cores at once. On a test code, the method matched or beat a standard rival on error rates while cutting wait time to about seven tenths of the rival time. With full parallel work, the wait fell further. Readers get a practical route toward fast error control in future machines.

Catalog record

CREATORMing Wang, Ang Li, Frank Mueller
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-00254

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fully Parallelized BP Decoding for Quantum LDPC Codes Can Outperform BP-OSD Ming Wang, Ang Li, Frank Mueller Abstract . In this work, we propose a lightweight decoder based solely on belief-propagation (BP), augmented with a speculative post-processing strategy inspired by classical Chase decoding. Our method identifies unreliable bits via BP oscillation statistics, generates a set of modified test patterns, and decodes them in parallel using low-iteration BP. We demonstrate that our approach can achieve logical error rates comparable to or even better than BP-OSD, but has lower latency over its parallelization for a variety of bivariate bicycle codes, which significantly reduces decoding complexity. 1. Introduction Quantum low-density parity-check (qLDPC) codes have attracted significant attention in recent years due to their potential to encode more logical qubits than surface codes while maintaining a high threshold ( Tillich and Zémor 2014 ; Panteleev and Kalachev 2021 ; Bravyi et al. 2024 ) . However, decoding qLDPC codes remains a major challenge. To ensure reliable operation, especially in fault-tolerant quantum memory and computation, errors must be corrected both quickly and accurately, placing stringent demands on the decoding algorithm in terms of performance and computational efficiency. Belief propagation (BP)-based decoders, widely used in classical LDPC codes, are appealing due to their low complexity, parallelizability, and near-optimal performance. However, their effectiveness diminishes significantly when applied to qLDPC codes. This degradation is primarily due to inherent properties of qLDPC codes, such as degeneracy, the presence of many low-weight stabilizers, and the prevalence of trapping sets ( Raveendran and Vasić 2021 ) , which hinder convergence and reliability of BP decoding. Many works have sought to address the limitations of BP-based decoders on qLDPC codes. In ( Poulin and Chung 2008 ) , Poulin and Chung proposed several techniques to enhance convergence, including random freezing of variable nodes, perturbing priors, and colliding unsatisfied check nodes. In ( Chytas et al. 2024 ) , instead of performing static trapping set analysis prior to decoding, the authors identify bits affected by trapping sets dynamically during the decoding process. Once identified, the priors of these bits are modified, similar to the approach in ( Poulin and Chung 2008 ) , to help the decoder escape local minima and converge. Raveendran et al. ( Raveendran and Vasić 2021 ) analyzed different types of trapping sets and proposed using a layered BP decoder to mitigate the effect of symmetric trapping sets. While this approach can reduce complexity, it often comes at the cost of increased decoding latency. More recently, Yin et al. ( Yin et al. 2024 ) leveraged the degeneracy property of quantum LDPC codes to enhance BP decoding. By analyzing bit-wise marginal probabilities from BP, they selectively split rows in the parity-check matrix and modify the corresponding Tanner graph. This symmetry-breaking technique helps the decoder avoid convergence stalls caused by structural degeneracies in the code. Apart from efforts aimed at improving the BP decoder itself, several works focus on post-processing techniques to enhance decoding performance. A widely used approach is belief propagation combined with ordered statistics decoding (BP-OSD) ( Panteleev and Kalachev 2021 ; Roffe et al. 2020 ) . While BP-OSD significantly enhances error correction performance, its reliance on a Gaussian elimination step during the OSD phase introduces substantial computational overhead. Specifically, this step incurs a complexity of O(N^{3}) , where N denotes either the code length (in the code-capacity error model) or the number of error mechanisms (in the circuit-level noise model). In contrast, each iteration of BP has only O(N) complexity. This difference makes BP-OSD computationally expensive and less suitable for large-scale or real-time decoding applications. To address this limitation, recent works such as ( Wolanski and Barber 2024 ; Hillmann et al. 2024 ) propose partitioning the Tanner graph into several clusters. This localized decoding approach reduces the size of the matrices involved in Gaussian elimination, thereby lowering the overall computational burden without substantially compromising decoding performance. In this work, rather than aiming to improve BP itself, we focus on achieving decoding performance comparable to BP-OSD while avoiding computationally expensive post-processing steps such as Gaussian elimination. To this end, we propose a lightweight post-processing technique based entirely on BP and demonstrate that, with appropriate design and a speculative decoding strategy, it can closely match the logical error rates achieved by BP-OSD. Through simulations on various bivariate bicycle codes, we show that the proposed decoder performs similarly in terms of syndrome analysis to BP-OSD with a combination-sweep of order 10. Additionally, the proposed BP decoder requires lower latency given it is fully parallelizable, which means it can outperform BP-OSD in execution efficiency, making it a promising candidate for scalable and efficient decoding of quantum LDPC codes in practical fault-tolerant quantum computing systems. Throughout the paper, we adopt the widely used min-sum variant of BP because of its simplicity and computational efficiency. Nonetheless, our approach could potentially benefit from incorporating more advanced BP-based techniques. 2. Background 2.1. Quantum LDPC Codes Stabilizer codes are among the most commonly used codes in quantum error correction. One can measure each stabilizer to infer both the type and location of errors in a multi-qubit system. To construct such a code, all stabilizers must commute with each other. Thus, they have a common eigenspace and form a stabilizer group \mathcal{S} . The code space \mathcal{C} defined by such group is (1) \mathcal{C}=\{\ket{\psi}|\>s\ket{\psi}=\ket{\psi},\>\forall s\in\mathcal{S}\}. An \llbracket n,k,d\rrbracket stabilizer code can be defined by n-k independent stabilizers, allowing us to encode k qubits of logical information into an n -qubit block tolerating up to {\lfloor(d-1)/2\rfloor} errors. CSS codes are an important class of stabilizer with two sets of stabilizers, X -type and Z -type, represented by parity-check matrices H_{X} and H_{Z} , respectively. Each row in a parity-check matrix corresponds to a stabilizer generator, and each column corresponds to a physical qubit. A “1” entry indicates an X or Z operator (depending on whether it is in H_{X} or H_{Z} ), while a “0” indicates the identity. Consequently, an X -type stabilizer acts as X or the identity on each qubit, and a Z -type stabilizer acts as Z or the identity on each qubit. Errors can therefore be corrected by handling Z errors and X errors separately. Since all stabilizers must commute with each other, it follows directly that for a CSS code H_{X}H_{Z}^{T}=0 . 2.2. Decoding Problem Assuming the noise is uniform on each bit, the optimal syndrome decoding problem for classical codes can be formalized as follows: Given a code with parity-check matrix H\in\mathbb{F}_{2}^{M\times N} and syndrome \bm{s}\in\mathbb{F}_{2}^{M} , we want to find an error \hat{\bm{e}}\in\mathbb{F}_{2}^{N} that satisfies the syndrome (2) \hat{\bm{e}}=\arg\min_{\hat{\bm{e}}H^{T}=\bm{s}}(\sum_{i}^{N}\hat{\bm{e}_{i}}). Quantum stabilizer codes face a problem due to the phenomenon of degeneracy , where multiple errors have the same effect on the code space. As a result, the goal of decoding is not to identify the most likely error itself, but rather the most likely equivalence class of errors modulo stabilizers, since errors that differ by a stabilizer operation act identically on the code space. Given a syndrome, \bm{s} , the optimal decoding problem considering degeneracy becomes (3) [\hat{E}]=\arg\max_{[E]:\text{synd}(E)=\bm{s}}\Pr([E]), where [E] denotes the equivalence class of errors under the stabilizer group and \Pr([E]) is the total probability of all errors

Read the complete text