量子低密度奇偶校验码的局部统计解码：一种并行高效解码新方法

研究人员针对量子低密度奇偶校验码（QLDPC）解码过程中BP+OSD算法运行时延长、难以满足实时解码需求的问题，开发了局部统计解码（LSD）算法。该算法通过并行处理解码图中的独立子图，结合创新的动态消元技术，实现了与BP+OSD相当的纠错性能，同时显著提升了解码效率。这一突破为大规模量子计算中实时解码提供了可行方案，相关成果发表于《Nature Communications》。

　　

量子计算面临的核心挑战之一是量子比特的脆弱性，量子纠错码（QEC）被视为实现可靠量子计算的关键。在众多量子纠错码中，量子低密度奇偶校验码（QLDPC）因其低开销和高编码率备受关注，被认为是表面码（surface code）的有力替代者。然而，QLDPC码的解码过程面临严峻挑战：当前最先进的BP+OSD（置信传播+有序统计解码）算法虽然性能优异，但其立方级时间复杂度的矩阵求逆步骤导致运行时延长，难以满足大规模量子计算对实时解码的严苛要求。

为突破这一瓶颈，研究人员在《Nature Communications》发表论文，提出了一种名为局部统计解码（LSD）的创新算法。该算法充分利用QLDPC码在亚阈值区域（sub-threshold regime）下错误通常分布在解码图（decoding graph）不连续区域的特点，将复杂的全局矩阵求逆问题分解为多个独立的局部子问题并行处理。

研究采用了三项关键技术：1）基于加权可靠性的聚类生长策略，动态识别解码图中的独立区域；2）创新的动态消元（on-the-fly elimination）技术，将传统串行高斯消元转化为并行过程；3）局部高阶后处理（LSD-μ）方法，在保持精度的同时降低计算复杂度。实验样本来源于[[144,12,12]]双变量自行车码（bivariate bicycle code）、[[25s²,s²]]超图乘积码（HGP code）和旋转表面码（rotated surface code）的电路级噪声模拟数据。

主要研究结果

解码问题重构

通过构建检测器-故障二分图（detector-fault bipartite graph），将量子纠错的最小权重解码问题映射为经典线性码解码问题。该模型明确显示，在亚阈值区域，错误模式会自然形成多个独立簇（cluster）。

局部统计解码算法

如图1所示，LSD算法通过动态生长和合并簇（cluster），仅对局部子矩阵进行求逆。当簇的有效性条件（validity condition）满足时（即局部综合征s_[C]∈image(H_[C])），即可独立求解。

簇规模统计

图3显示，在物理错误率p≤0.1%时，BP+LSD识别的最大簇规模κ接近最优值，平均形成10个独立簇，为并行解码提供可能。动态消元技术使算法复杂度从O(κ³)降至O(κ²)。

解码性能比较

图4表明，BP+LSD对距离d=13的旋转表面码的解码阈值达到0.7%，与BP+OSD相当。图5显示，对[[625,25]]超图乘积码，BP+LSD在p≈0.1%时将逻辑错误率比BP+SSF（small set-flip）降低近两个数量级。

结论与展望

该研究提出的LSD算法通过并行局部解码和动态消元技术，在保持BP+OSD纠错性能的同时，显著提升了解码效率。其创新性体现在：1）首次实现QLDPC码的完全并行解码；2）动态消元技术可拓展至推荐系统（recommender systems）和压缩感知（compressed sensing）等领域；3）为FPGA/ASIC硬件实现实时解码奠定基础。未来研究方向包括：1）在擦除偏置（erasure-biased）系统中验证算法；2）结合最大似然解码（maximum-likelihood decoding）优化局部簇处理；3）探索并行窗口解码（parallel window decoding）策略以解决积压问题（backlog problem）。这项研究标志着量子纠错向实用化迈出关键一步，为构建大规模容错量子计算机提供了新的解码范式。