An Efficient Algorithm to Sample Quantum Low-Density Parity-Check Codes

技术摘要：一种高效采样量子低密度奇偶校验码的算法

问题陈述
本文解决了高效生成随机量子低密度奇偶校验（LDPC）码的挑战。虽然经典的 LDPC 码可以通过简单地对稀疏矩阵进行采样来生成，但量子 LDPC 码需要一个额外的约束条件：校验矩阵必须满足辛积条件（具体而言，对于对偶包含码，需满足 $HH^\top = 0$），以确保相关的泡利群子群是阿贝尔（Abelian）的。现有的量子 LD 代码构造主要基于代数方法（例如，准循环、超图积或基于特定的几何结构）。这些代数方法对代码参数（长度、维度、稀疏度）施加了严格的限制，导致生成的代码远离随机性。本文提出了这样一个问题：能否在不依赖特定代数结构的情况下，高效地生成随机量子 LDPC 码？

方法论
作者提出了一种纯组合算法，用于逐行采样稀疏且自正交的二元矩阵。其核心方法论依赖于信息集译码（ISD），具体采用了针对此采样任务改进的 Lee-Brickell (LB) 算法。

该算法通过 $r$ 个步骤来构建一个矩阵 $H \in \mathbb{F}_2^{r \times n}$：

1. 迭代采样： 在第 $u$ 步，算法假设已经找到了 $u-1$ 个线性无关、稀疏且相互正交的向量 $\{h_1, \dots, h_{u-1}\}$。
2. 代码定义： 这些向量构成了线性码 $C_u$ 的校验矩阵。算法寻求一个新的向量 $h_u$，使其为 $C_u$ 中的一个码字（以确保与之前的行正交），并且具有特定的汉明重量 $v$（以确保稀疏性）。为了强制执行偶重（这是二进制域中自正交性的要求），算法将全一向量作为一个额外的校验方程加入其中。
3. 利用 ISD： 为了在 $C_u$ 中找到一个重量为 $v$ 的码字，算法采用了 ISD。这是该方法的核心组件；如果没有 ISD，在高维空间中寻找此类稀疏向量在计算上是不可行的。
4. 基底更新： 如果找到了一个有效的 $h_u$ 且其不在之前向量的张成空间内，则将其添加到矩阵中，并重复此过程，直到生成 $r$ 行。

理论分析与参数选择
论文提供了关于该算法可行性的理论特征描述，重点关注中间码 $C_u$ 的期望重量分布（EWD）。

• 解的存在性： 作者推导了在概率极高的情况下存在重量为 $v$ 的码字的条件。他们将校验矩阵 $H_u$ 建模为来自分布 $H_{n,u,v}$ 的样本，其中各行具有恒定的重量 $v$。
• 重量约束： 通过渐近分析，他们证明了对于常数码率 $R$，仅当行重量 $v$ 满足以下条件时，亚线性重量 $w = o(n)$ 的码字才会以高概率存在：
  $$v < \frac{\ln(2)}{1-R} \log_2(n)$$
  这意味着，为了使算法高效运行，行重量必须与代码长度 $n$ 成对数关系。
• 复杂度： 论文使用标准的 ISD 启发式方法分析了时间复杂度。虽然作者指出，要严谨地证明多项式时间需要对 ISD 在稀疏矩阵上的行为（这与在随机矩阵上的行为不同）做出假设，但他们认为，在合理的启发式假设下，当 $v = O(\log n)$ 时，算法以多项式时间运行。具体而言，如果重量为 $v$ 的码字的期望数量很大，那么所需的 ISD 调用次数就会非常少（通常接近 1）。

结果与数值验证
作者在 Sagemath 中实现了该算法，并在标准笔记本电脑上进行了基准测试。

• 可行性： 算法成功为各种参数（例如 $n=250, 500, 1000$）生成了对偶包含码（dual-containing codes）。
• 效率： 表 I 和表 III 显示，对于满足理论边界的参数，生成代码的平均时间是合理的（根据 $n$ 和 $v$ 的不同，从几秒到几分钟不等）。
• ISD 调用次数： 一个关键发现是，每一步的平均 ISD 调用次数极其接近 1（通常正好为 1），这证实了理论条件 $m_v^{(r)} \gg 1$ 确保了算法很少陷入停滞。
• 列分布： 论文验证了生成的矩阵具有可预测的列重量分布，这使得可以通过打孔（puncturing）操作移除“运气不佳”的列（例如空列或重量为 1 的列），且不会破坏自正交性。

推广
论文概述了如何扩展该方法：

• 非二元域： 该算法可以通过修改 ISD 并处理自正交性条件（如果域特征不是 2，则需要拒绝采样）来适配 $\mathbb{F}_q$。
• 通用稳定器码： 该方法可以通过迭代采样满足辛积条件 $a_i b_j^\top + b_i a_j^\top = 0$ 的向量对 $(a_i, b_i)$，来采样通用的量子稳定器码（不仅限于 CSS 码）。

意义与主张
本文声称为“是否可以高效生成随机量子 LDPC 码”这一问题提供了肯定的回答。

• 组合方法 vs 代数方法： 与现有方法不同，这种方法不依赖于代数结构（如准循环性），从而允许采样尽可能接近随机的码，仅受限于稀疏性和正交性。
• 对复杂度的适度主张： 作者对于声称具有形式化的多项式时间证明持谨慎态度。他们明确指出，其复杂度分析依赖于关于 ISD 在稀疏矩阵上表现的启发式假设（这与标准的随机码假设不同）。他们承认，虽然数值模拟强烈表明其具有多项式时间行为，但严谨的理论证明仍是一个开放性问题。
• 未来工作： 他们指出，设计专门针对 LDPC 码的 ISD 算法是一个有前景的方向，用以进一步提高效率并解决有关正式复杂度界限的开放性问题。

综上所述，本文提出了一种全新的组合采样技术，弥合了生成经典 LDPC 码的简易性与量子码结构约束之间的鸿沟，证明了随机量子 LDPC 码可以通过基于 ISD 的高效采样来获取。