2025-11-15T23:31:10.781061

Degeneracy Cutting: A Local and Efficient Post-Processing for Belief Propagation Decoding of Quantum Low-Density Parity-Check Codes

Tsubouchi, Yamasaki, Tamiya

Quantum low-density parity-check (qLDPC) codes are promising for realizing scalable fault-tolerant quantum computation due to their potential for low-overhead protocols. A common approach to decoding qLDPC codes is to use the belief propagation (BP) decoder, followed by a post-processing step to enhance decoding accuracy. For real-time decoding, the post-processing algorithm is desirable to have a small computational cost and rely only on local operations on the Tanner graph to facilitate parallel implementation. To address this requirement, we propose degeneracy cutting (DC), an efficient post-processing technique for the BP decoder that operates on information restricted to the support of each stabilizer generator. DC selectively removes one variable node with the lowest error probability for each stabilizer generator, significantly improving decoding performance while retaining the favorable computational scaling and structure amenable to parallelization inherent to BP. We further extend our method to realistic noise models, including phenomenological and circuit-level noise models, by introducing the detector degeneracy matrix, which generalizes the notion of stabilizer-induced degeneracy to these settings. Numerical simulations demonstrate that BP+DC achieves decoding performance approaching that of BP followed by ordered statistics decoding (BP+OSD) in several settings, while requiring significantly less computational cost. Our results present BP+DC as a promising decoder for fault-tolerant quantum computing, offering a valuable balance of accuracy, efficiency, and suitability for parallel implementation.

academic

Degeneracy Cutting: A Local and Efficient Post-Processing for Belief Propagation Decoding of Quantum Low-Density Parity-Check Codes

基本信息

论文ID: 2510.08695
标题: Degeneracy Cutting: A Local and Efficient Post-Processing for Belief Propagation Decoding of Quantum Low-Density Parity-Check Codes
作者: Kento Tsubouchi, Hayata Yamasaki, Shiro Tamiya
分类: quant-ph (量子物理)
发表时间: 2024年10月9日
论文链接: https://arxiv.org/abs/2510.08695

摘要

量子低密度奇偶校验码(qLDPC)因其低开销协议的潜力，在实现可扩展容错量子计算方面极具前景。解码qLDPC码的常见方法是使用置信传播(BP)解码器，然后通过后处理步骤提高解码精度。对于实时解码，后处理算法需要具有较小的计算成本，并且仅依赖于Tanner图上的局部操作以便于并行实现。为了满足这一要求，本文提出了简并切割(DC)，这是一种高效的BP解码器后处理技术，仅在每个稳定子生成元的支撑集上操作。DC选择性地为每个稳定子生成元移除具有最低错误概率的变量节点，在保持BP固有的有利计算缩放和并行化结构的同时，显著提高解码性能。

研究背景与动机

问题定义

核心问题：qLDPC码的置信传播解码因量子码的简并性而性能显著下降，需要高效的后处理方法来提高解码精度
实际需求：容错量子计算需要实时解码能力，要求解码算法具有低计算复杂度和高并行化潜力
现有方法局限性：
- BP+OSD虽然精度高，但计算复杂度为O(n³)，不适合实时应用
- 其他后处理方法要么计算复杂度高，要么依赖全局信息比较，难以并行化

研究动机

量子码的简并性是指不同的物理错误模式可能产生相同的症状，导致BP解码器无法区分这些模式。这种简并性特别在qLDPC码中造成严重的解码失败，因为低权重的稳定子生成元会产生大量可信的简并错误模式。

核心贡献

提出简并切割(DC)算法：一种仅基于局部信息的线性时间后处理技术
保持计算效率：将计算复杂度从O(n³)降低到O(n)，同时保持接近BP+OSD的性能
引入检测器简并矩阵：将方法扩展到现实噪声模型（现象学和电路级噪声模型）
实现高度并行化：算法决策仅基于每个稳定子生成元内的局部比较，便于并行实现
数值验证：在表面码和双变量自行车(BB)码上验证了方法的有效性

方法详解

任务定义

给定：

输入：Z型奇偶校验矩阵H_Z，观测到的症状s_Z，先验错误概率p
输出：估计的X型错误ê_X，满足ê_X H_Z^T = s_Z且残余错误为平凡错误

核心算法：简并切割(DC)

算法流程

Algorithm 1: BP+DC decoder
Input: 奇偶校验矩阵H_X, H_Z; 观测症状s_Z; 先验错误概率p; BP最大迭代次数T_iter
Output: 估计的X型错误ê_X

1. (ê_X, p̂) ← BP_decode(H_Z, s_Z, p, T_iter)
2. if ê_X H_Z^T = s_Z then return ê_X
3. Cut_indexes ← {}
4. for each row vector h_X in H_X do
5.    i_min ← argmin_{i∈{i|(h_X)_i=1}} p̂_i
6.    Cut_indexes ← Cut_indexes ∪ {i_min}
7. Delete columns of H_Z indexed by Cut_indexes
8. (ê_X, p̂) ← BP_decode(H_Z, s_Z, p̂, T_iter)
9. return ê_X