参数列表化置信传播-顺序统计译码算法

针对量子纠错码中置信传播-顺序统计译码 (BP-OSD) 在单一归一化因子下搜索空间受限、易陷入局部最优而影响性能的问题，该文提出一种兼顾复杂度且提升译码性能的改进方案。所提增强型BP-OSD 算法的核心思想是在前处理BP译码阶段对归一化因子 α 进行列表化。与传统算法仅采用单一 α 值不同，所提方法针对多个 α 取值分别执行BP译码，并对每个取值下得到的后验概率利用 OSD 算法进行后处理，形成候选列表，最终选取最似然结果作为译码输出。为降低计算复杂度，该文仅在第1阶段 BP 译码失败时才触发参数列表化 BP-OSD 算法，并进一步对所提算法复杂度进行了理论分析与数值验证。结果显示，所提方案在低物理错误率区域与 BP 译码具有相似的复杂度。在实验方面，该文通过蒙特卡罗仿真对主流 Surface 码和量子低密度一致校验 (QLDPC) 码进行了性能评估。数值结果表明：(1) 对于 Surface 码，所提方法相较于最小权重完美匹配 (MWPM) 算法和原始 BP 算法，可明显降低逻辑比特错误率并提升阈值 (从 MWPM 的约 15.5% 提升至约 18.3%)； (2) 对于 QLDPC 码，所提方法较原始BP和原始 BP-OSD 算法可显著提高译码性能，降低逻辑错误率。
Objective    Traditional Belief Propagation-Ordered Statistics Decoding (BP-OSD) algorithms for quantum error-correcting codes often rely on a single normalization factor (α) in the Belief Propagation (BP) stage, which restricts the search space and limits decoding performance. An enhanced BP-OSD algorithm is presented to address this limitation by employing a list of candidate α values. The central idea is to perform BP decoding iteratively for multiple α values, with the resulting posterior probabilities post-processed by Ordered Statistics Decoding (OSD). To balance performance gains with computational tractability, the multi-α BP-OSD process is embedded within a two-stage framework: the more computationally intensive parameter-listed decoding is activated only when an initial BP decoding with a fixed α₀ fails. This design broadens the parameter search to improve decoding performance, while conditional activation ensures that computational complexity remains manageable, particularly at low physical error rates.
Methods    The proposed enhanced BP-OSD algorithm (Algorithm 1) introduces a two-stage decoding process. In the first stage, decoding is attempted using standard BP with a single predetermined normalization factor (α₀), providing a computationally efficient baseline. If this attempt fails to produce a valid syndrome match, the second stage is activated. In the second stage, parameter listing is employed: BP decoding is executed independently across a predefined list of L distinct normalization factors (α₁, α₂, ..., α_L). Each run generates a set of posterior probabilities corresponding to a different BP operational point. These posterior probabilities are then individually post-processed by an OSD module, forming a pool of candidate error patterns. The final decoded output is selected from this pool according to the maximum likelihood criterion, or the minimum Hamming weight criterion under a depolarizing channel. Complexity analysis shows that this conditional two-stage design ensures that the average computational cost remains comparable to that of standard BP decoding, particularly at low physical error rates where the first stage frequently succeeds.
Results and Discussions    The effectiveness of the proposed algorithm is evaluated through Monte Carlo simulations on both Surface codes ⟦2d² - 2d + 1, 1, d⟧ and Quantum Low-Density Parity-Check (QLDPC) codes ⟦882, 24⟧ under a depolarizing channel. For Surface codes, the enhanced BP-OSD algorithm achieves a substantially lower logical error rate compared with both the Minimum-Weight Perfect Matching (MWPM) algorithm and the original BP algorithm (Fig. 4(a)). The error threshold is improved from approximately 15.5% (MWPM) to about 18.3% with the proposed method. The average decoding time comparison in Fig. 4(b) demonstrates that, particularly at low physical error rates, the proposed algorithm maintains a decoding speed comparable to the original BP algorithm. This efficiency results from the two-stage design, in which the more computationally intensive parameter-listed search is activated only when required. For QLDPC codes (Fig. 5(a)), the proposed algorithm outperforms both the original BP and BP-OSD algorithms in terms of logical error rate, even when a smaller OSD candidate list per α value is employed. As shown in Table 3, increasing the parameter list size L (e.g., L = 4, 8, 16) improves decoding performance, although the gains diminish as L grows. This observation supports the choice of L = 16 as an effective balance between performance and complexity. Furthermore, the activation probability of the second stage (Table 2) decreases rapidly as the physical error rate declines, confirming the efficiency of the two-stage framework.
Conclusions    An enhanced BP-OSD algorithm for quantum error-correcting codes is presented, featuring a parameter-listing strategy for the normalization factor (α) in the BP stage. Unlike conventional approaches that rely on a single α, the proposed method explores multiple α values, with the resulting posterior probabilities processed by the OSD module to select the most likely output. This systematic expansion of the search space improves decoding performance. To control computational overhead, a two-stage decoding mechanism is employed: the parameter-listed BP-OSD is activated only when an initial BP decoding with a fixed α₀ fails. Complexity analysis, supported by numerical simulations, shows that the average computational cost of the proposed algorithm remains comparable to that of standard BP decoding in low physical error rate regimes. Monte Carlo simulations further demonstrate its efficacy. For Surface codes, the enhanced BP-OSD achieves lower logical error rates than the MWPM algorithm and raises the error threshold from approximately 15.5% to 18.3%. For QLDPC codes, it exceeds both the original BP and BP-OSD algorithms in logical error rate performance, even with a reduced OSD candidate list size in the second stage. Overall, the proposed algorithm provides a promising pathway toward high-performance, high-threshold quantum error correction by balancing decoding power with operational efficiency, highlighting its potential for practical applications.