面向 qLDPC 码的量子麦克斯韦擦除解码器

论文信息

标题: Quantum Maxwell Erasure Decoder for qLDPC codes

作者: Bruno Costa Alves Freire, François-Marie Le Régent, Anthony Leverrier

发布日期: 2026-01-15

arXiv ID: 2601.10713v1

PDF 链接: 下载 PDF

3 分钟速览

研究问题：这篇论文要解决量子低密度奇偶校验码（qLDPC）在量子擦除信道上的快速解码问题，现有迭代解码器在遇到停止集（Stopping Set）时容易卡住，而最大似然解码复杂度太高。
核心方法：提出一种量子 Maxwell 解码器，在标准剥离（Peeling）过程卡住时引入 “猜测” 机制，对未知量子比特赋值并继续剥离，同时通过 “受限制校验” 来消除多余的猜测，从而渐进逼近最大似然解码性能。
关键结果：在猜测预算 $G_{\max}$ 固定且码的度有界时，该解码器运行时间为 $O(|\mathcal{E}_0|)$ ——即线性时间复杂度（见论文定理 1）；当 $G_{\max} \ge d-s+1$ 时，其在低擦除概率 $\epsilon \to 0$ 下的逻辑失败指数与最大似然解码一致（见论文推论 2）。
主要局限：定理给出的猜测量下界 $d-s+1$ 在实践中很宽松（论文称 “these bounds may be very loose”），实际所需猜测量取决于具体代码结构；仿真均采用显式分支实现，而非符号算法，因此未直接验证符号实现的完整运行时特性。
适合读者：从事量子纠错码理论、qLDPC 解码算法设计的研究者，以及关注量子容错计算中低开销解码方案的研究生和工程师。

论文背景和研究动机

量子低密度奇偶校验（qLDPC）码是目前最有希望实现低开销量子容错的一类编码方案。然而，将经典 LDPC 码中极为成功的置信传播（Belief Propagation）解码直接移植到量子稳定子码场景时，会遭遇 Tanner 图中短环以及简并性带来的障碍。因此，设计针对 qLDPC 码的高速可扩展解码器，是一项极其紧迫的理论与工程任务。

在这项工作中，作者专注于量子擦除信道。擦除信道的独特之处在于丢失量子比特的位置是对解码器公开的，这使问题简化为在已知擦除位置上求解线性方程组。最大似然解码可归结为对擦除位置进行高斯消元，复杂度为 $O(n^3)$ 。虽然这给出了理论性能上限，但对于大规模量子码并不实用。

最简单的迭代解码方法是 “剥离”：每当一个校验节点在残差 Tanner 图中仅连接一个被擦除的变量节点时，该变量的值直接被确定，并将该信息沿图传播。剥离收敛快、复杂度线性，但一旦陷入停止集（没有度为 1 的校验节点的剩余擦除集），就会永久停滞。在量子码中，低权重的稳定子生成元会诱导出大量小型停止集，这使得标准剥离的性能距离理论极限甚远。

近年来涌现的新构造，如 lifted product 码、双变量自行车（Bivariate Bicycle, BB）码以及量子 Tanner 码，对解码器的通用性和可扩展性提出了更高要求。已有的通用量子擦除解码器包括：簇解码器（将停止集分解为小簇并精确求解）和带引导消去的置信传播解码等。它们都在性能和复杂度之间做了某种折中。本文正是在这一背景下，将经典的 Maxwell 解码思想引入量子领域，提供一种更灵活且理论性质更清晰的折中途径。

核心方法和技术细节

问题规约与符号系统

考虑 CSS 稳定子码，其 $X$ 和 $Z$ 校验矩阵分别为 $H_X$ 和 $H_Z$ ，满足 $H_X H_Z^T = 0$ 。擦除解码被分解为两个独立的二值线性问题：在擦除集 $\mathcal{E}_0$ 上寻找 $w^X$ 和 $w^Z$ ，使得 $H_Z w^X = \sigma_Z$ 及 $H_X w^Z = \sigma_X$ 。两个子问题共享同一个擦除模式，但使用不同的校验矩阵。因此，只需集中求解一个通用子问题：给定 $H \in \mathbb{F}_2^{m\times n}$ 、伴随子 $\sigma$ 和擦除集 $\mathcal{E}_0$ ，找到支撑集限于 $\mathcal{E}_0$ 的解 $w$ 。

剥离的基石与困境

剥离算法在残差图 $T_\mathcal{E}(H)$ 上工作：当某校验节点仅与一个擦除变量相邻（度为 1）时，该变量的值直接被校验方程确定；将该变量从 $\mathcal{E}$ 移除，并更新所有相邻校验的伴随子，往复循环。这一过程相当于迭代消除度为 1 的未知数。若 $\mathcal{E}$ 在剥离后非空且无度为 1 校验，则当前擦除集构成一个停止集。

Maxwell 解码器的符号化猜测机制

Maxwell 解码器的核心思路是：当剥离陷入停止集时，主动猜测一个擦除变量的值，将其视为新的 “枢轴变量”（pivot），然后继续剥离。概念上说， $g$ 次猜测会生成 $2^g$ 个平行分支，每个分支对应猜测变量的一种赋值。为了避免分支数指数爆炸，作者采用符号跟踪：所有变量修正 $w_j$ 和伴随子 $s_i$ 均存储为关于当前枢轴集 $\mathcal{P}$ 中变量的仿射形式 $a_0 + \sum_{p \in \mathcal{P}} a_p x_p$ （系数在 $\mathbb{F}_2$ 中）。

关键在于受限制校验（restrictive checks）机制。在剥离或猜测过程中，某个校验节点可能变为度 0，但其累积伴随子 $s_i(\mathbf{x})$ 并不恒为零。此时， $s_i(\mathbf{x}) = 0$ 给出了一个关于枢轴变量的线性约束。算法通过枢轴降级来执行该约束：从 $s_i$ 的支撑集中选出一个枢轴（按 “最近引入” 策略），将其用其他更早的枢轴表达，然后将该表达式代入所有受影响的仿射形式。这相当于将一次猜测 “偿还” 掉，从而减少活跃枢轴数 $|\mathcal{P}|$ 。

整个过程由参数 $G_{\max}$ （最大猜测预算）控制。当 $|\mathcal{P}|$ 达到 $G_{\max}$ 且仍需新猜测时，算法宣告失败。伪代码见论文算法 1。最终，若算法成功结束，它返回 $w$ 的仿射形式；任意一组枢轴赋值（如全零）即给出一个具体修正，该修正可与真实错误相差一个稳定子元素。

复杂度分析概要

作者在 “最近引入枢轴降级” 策略下证明了如下复杂度定理（见论文定理 1）：

定理 1 对于 $(d_v, d_c)$ -LDPC 码（行列重有界， $d_v, d_c = O(1)$ ），符号化 MAXWELLPEEL 算法的运行时间为 $O(e \cdot d_v d_c \cdot G_{\max}^2)$ 比特操作，其中 $e = |\mathcal{E}_0|$ 是初始擦除数。在 $G_{\max}$ 固定时，该时间复杂度为 $O(e)$ ，即线性于擦除数。

证明要点：每个擦除变量被恰好移除一次，度更新总计 $O(e d_v)$ ；仿射形式传播开销为 $O(e d_v G_{\max})$ ；每次枢轴降级仅影响更新不超过 $G_{\max}$ 次的变量和校验仿射形式，通过归纳论证，总替换成本被严格控制在 $O(e d_v d_c G_{\max}^2)$ 内。该结果给出了明确的理论性能保证。

渐进性能的理论保证

作者建立了猜测量与失败指数之间的严格关系（见论文定理 2 及推论 1、2）。定义分布间隙 $\gamma(t) = |\{0 < w \le t : \text{大小为 } w \text{ 的停止集数目} > \text{大小为 } w \text{ 的非平凡逻辑算子数目}\}|$ 。

直觉：若擦除集是最大似然可纠的，则每次剥离卡住时必然对应一个停止集，其大小必定属于 $W_0(t)$ 中的某个值；一次猜测至少使擦除集的大小降低到严格更小的停止集规模。因此，所需猜测数不会超过可能出现的停止集规模的种类数 $\gamma(t)$ 。

推论 2 设 $d$ 为码距离， $s = \min\{s(H_X), s(H_Z)\}$ 为最小停止距离。则最大似然解码的失败概率为 $p_L^{\mathrm{ML}}(\epsilon) = \Theta(\epsilon^d)$ 。当 $G_{\max} \ge d - s + 1$ 时，量子 Maxwell 解码器的失败概率 $p_L^{\mathrm{QM}(G_{\max})}(\epsilon) \sim p_L^{\mathrm{ML}}(\epsilon)$ （当 $\epsilon \to 0$ ），即两者具有相同的低擦除概率失败指数。

这表明，只需有限且与码构造参数直接相关的猜测量，即可在极限 $\epsilon \to 0$ 下达到信息论最优性能的渐近斜率。

创新点和贡献

首次将 Maxwell 解码框架移植到量子 CSS 码。该解码器用统一的参数 $G_{\max}$ 在剥离与最大似然之间实现平滑插值，架起了一座从快速线性解码到最优解码的性能桥梁。
给出了线性复杂度下的严格理论保证。这与量子纠错场景对可扩展性的强烈需求高度契合，明确了 “常数猜测量换来线性时间” 这一核心折中关系。
建立了猜测量与失败指数的理论联系。推断出 $G_{\max} \ge d - s + 1$ 这一匹配最大似然指数的充分条件，首次从理论上揭示了 qLDPC 码的停止集分布与 Maxwell 解码器所需资源间的量化关系。
提出了猜测回偿和基于评分的猜测策略。枢轴降级机制使猜测具有 “可逆性”，评分策略（选择邻接度为 2 的校验节点数最多的变量作为枢轴）在不增加复杂度的前提下（见论文命题 1）显著改善了低擦除概率下的错误平层。
实验上验证了对 BB 码和量子 Tanner 码的有效性，并与簇解码器进行了系统性对比，展示了两种不同折中策略各自的特点。

实验结果分析

作者在两个 BB 码（ $[\![360,12,\le 24]\!]$ 和 $[\![756,24,\le 30]\!]$ ）及两个量子 Tanner 码上进行了数值仿真（见图 1）。解码采用显式分支实现， $G_{\max} \le 6$ （至多 64 分支），并配合基于评分的枢轴选择策略。

主要观察

平滑插值能力：随着 $G_{\max}$ 从 1 增加到 6，Maxwell 解码器的逻辑失败率 $p_L$ 曲线从剥离曲线（性能最差）稳步向最大似然曲线移动。对 $[\![360,12,\le 24]\!]$ BB 码， $G_{\max}=6$ 时性能几乎与最大似然重合。
瀑布区与错误平层：在其他码上， $G_{\max}=6$ 仍与最大似然存在可见间距，位于瀑布区域。由于码参数较高、 $p_L$ 值极小，加上采样复杂度限制，进一步探究深错误平层困难。
与簇解码器的比较：Maxwell 解码器在瀑布区下降更快，但簇解码器在擦除率降低时追赶更迅速。由于两者的可调节参数（最大猜测数 $G_{\max}$ 与最大簇尺寸 $C$ ）不存在直接对应关系，难以直接断定哪种折中更优。
剪枝与冗余校验的增益（附录 A）：深度为 1 的剪枝（直接消除完整擦除的稳定子生成元）与利用冗余的低权生成元重构校验矩阵，均能进一步提升 Maxwell 解码器性能（见图 2），尤其对于量子 Tanner 码效果显著。
评分策略的价值（附录 B）：与随机枢轴选择相比，基于评分的策略将低 $\epsilon$ 下的错误平层显著降低，且在 $G_{\max}$ 较小时即可见效（见图 3）。论文同时从算法角度证明，评分策略不改变渐进时间复杂度（见论文命题 1）。

局限与待解决问题

本项工作的理论设定和工程应用之间存在若干差距，作者也指出了一个重要方向上的开放性。

理论与实践的猜测量鸿沟。推论 2 给出的 $d-s+1$ 猜测量下界在实践中极为宽松。作者坦言这些界限 “may be very loose”。真实所需 $G_{\max}$ 远小于该理论界值，但如何根据具体码的 Tanner 图结构精确定出更紧的 $G_{\max}$ 需求，仍是一个开放问题。
仿真平台限制。所有数值结果均基于显式分支实现，而非符号化 MAXWELLPEEL 算法。虽然作者强调了在更大猜测量下符号实现的优越性，但论文没有对符号算法本身的常数因子、存取代价等进行实际性能评测。符号实现是否在 $G_{\max} \approx 6$ 时已经比分支实现更快，也尚待数据验证。
未深入处理简并性对性能界的影响。逻辑失败率的分析依赖于停止集与非平凡逻辑算子在集合大小上的分布差异（分布间隙），这是一种遍历码本图结构的组合方法。该方法能够处理简并性，但未给出针对特定码族的、更紧的有限长性能界。这意味着对于不同的码构造， $G_{\max}$ 的有效性可能存在较大波动。
对更一般噪声模型的适应性未验证。如作者在未来工作部分指出，论文严格限定在量子擦除信道。将其扩展到 Pauli 噪声、甚至在电路级噪声模型下评估，是比较明确但并非平凡的后续课题。这其中涉及在非理想伴随子测量和错误传播条件下如何处理仿射形式与猜测回偿。
与其他先进方法的协同潜力尚待挖掘。文中尝试了剪枝和冗余校验等预处理，并与评分猜测结合。然而，是否能与基于强化学习的猜测策略、基于张量网络的停止集分解等方法进一步融合，从而在 $G_{\max}$ 极小的情况下逼近最大似然，仍未涉及。