针对量子 APM‑LDPC 码最小距离上界见证的启发式搜索

论文信息

标题: Heuristic Search for Minimum-Distance Upper-Bound Witnesses in Quantum APM-LDPC Codes

作者: Kenta Kasai

发布日期: 2026-04-16

arXiv ID: 2604.15307v1

PDF 链接: 下载 PDF

3 分钟速览

• 研究问题：论文研究一类由仿射置换矩阵（APM）构造的量子 LDPC 码的最小距离上界，旨在找到尽可能小的非平凡逻辑算子权重，以收紧对该码族纠错能力的认知。
• 核心方法：采用启发式搜索生成候选向量，再通过严格的核与行空间排除测试验证其是否为合法逻辑算子，将搜索与证明分离，从而给出可认证的上界。
• 关键结果：对多种参数给出了具体的上界值，例如对 $P=768$ 的码 $C_9$，得到 $d_X\le 24$（见论文表 3），这比先前工作汇报的上界更紧。
• 主要局限：只提供上界而非距离下界，因此无法保证实际距离的真实大小，搜索过程也未必穷尽所有低权重逻辑算子。
• 适合读者：从事量子纠错码、尤其是量子 CSS-LDPC 码构造和最小距离评估的研究人员，以及关注启发式编码上界技巧的学者。

论文背景和研究动机

量子 CSS 码将量子纠错问题转换为两个互相正交的经典线性码。在量子 LDPC 码构造中，既要保持校验矩阵的稀疏性以支持高效译码，又要满足 CSS 正交条件，这给码的设计带来强约束。基于仿射置换矩阵（APM）的构造方法通过区分 “活跃行” 和 “潜在行”，只在活跃部分满足正交，而允许潜在部分存在非零混合积，从而在保持围长为 8 的条件下获得高维码。然而，这类码的最小距离一直缺乏严格分析：已知的下界技术难以直接拓张到全距离，而传统精确距离搜索在中等码长下就变得困难。因此，通过寻找尽可能低的权重逻辑算子来获得可靠的上界，成为评估这类码纠错能力的重要途径。论文《Heuristic Search for Minimum-Distance Upper-Bound Witnesses in Quantum APM-LDPC Codes》正是在此背景下，系统性地构建多类启发式上界见证向量，并给出经过验证的数值结果。

核心方法和技术细节

论文的方法论核心是 “搜索仅是候选生成，上界验证始于核与行空间排除测试后”。整个工作围绕一个统一的框架展开，该框架以父矩阵的活跃/潜在分解为基础：

$$\hat{H}_X = \begin{bmatrix} H_X \\ \tilde{H}_X \end{bmatrix}, \quad \hat{H}_Z = \begin{bmatrix} H_Z \\ \tilde{H}_Z \end{bmatrix}$$

其中 $H_X, H_Z$ 为活跃行，$\tilde{H}_X, \tilde{H}_Z$ 为潜在行。CSS 距离分解为潜在部分 $d_X^{(\mathrm{lat})}$ 和非潜在部分 $d_X^{(\mathrm{nlat})}$（见定义 2.1）。针对潜在部分，由命题 4.2 给出精确参数化：只需在潜在行空间内寻找系数向量 $\boldsymbol{\lambda}$ 满足 $H_Z\tilde{H}_X^{\mathsf{T}}\boldsymbol{\lambda}=0$ 且 $\boldsymbol{\lambda}^{\mathsf{T}}\tilde{H}_X\notin C_X^\perp$，则其行组合即给出合法逻辑算子及其权重上界。对于非潜在部分，提出三类受限提升子空间方法：

• 全纤维块压缩：假设 $P=mQ$，将向量约束为每 $m$ 个坐标一组重复值的块常数子空间。通过压缩校验矩阵将问题降维到 $Q$ 规模，搜索低权重压缩向量再提升回原长，权重乘以 $m$（命题 5.4）。
• 选择纤维受限提升：对块常数推广，仅在选定的纤维图案 $S\subset \mathbb{Z}/m\mathbb{Z}$ 上提升，权重的缩放因子为 $|S|$（命题 5.7）。这允许生成块常数子集外的候选，在搜索更灵活。
• CRT 条纹子空间：当 $P=q_1q_2$ 且互质时，利用中国剩余定理构造由模 $q_1$ 或 $q_2$ 余数相同的坐标张成的条纹子空间，在其中直接搜索低权重逻辑算子（命题 5.9）。

此外，还使用了直接 CSS 搜索（对全空间受限支持核求解）、8‑循环连接的基本陷阱集（ETS）以及译码失败残差。所有方法生成的候选向量，最终必须通过 $H_Z\boldsymbol{x}^\mathsf{T}=0$（或 $H_X$）以及 $\boldsymbol{x}\notin \mathrm{Row}(H_X)$ 的秩检验，才被接受为上界，从而保证每个数值结论都有明确的数学依据。

创新点和贡献

本文的主要贡献在于将分散的搜索技术整合进一个严格验证的框架，并明确区分潜在与非潜在上界。创新点主要体现在：1) 潜在距离的精确参数化和块常数核条件（定理 A.1、引理 A.2），使得在特定因子下潜在距离可精确确定为 $48$（示例 A.5）；2) 受限提升族的方法系统化，特别是选择纤维和 CRT 条纹构造，在同样压缩比下得到比全块压缩更小的上界，例如 $C_9$ 的 $d_X\le 24$ 正是通过 $m=4$、$S=\{0,2\}$ 的选择纤维方法获得（例 7.3）；3) 将 8‑循环 ETS 和译码残差纳入统一验证，其中 $P=216$ 码 $C_1$ 的 $d_X\le 10$ 和 $d_Z\le 10$ 分别由 ETS 和译码失败提供，且通过稳定子排除测试（例 7.7、7.8）。这些数值刷新了该码族此前公布的上界，并保持了所有见证向量的可核查性。

实验结果分析

论文以 $J=3, L=12$ 的固定 APM 模板为基础，对 10 种代表性 APM‑LDPC 码（$P$ 从 216 到 768）进行了搜索和验证，结果汇总于表 3。表中记录每种方法下获得的上界值，并用星号标出该码总体最佳上界。例如：

• $C_1$ ($P=216$)：$d_X\le 10$（ETS），$d_Z\le 10$（译码失败）；
• $C_9$ ($P=768$)：$d_X\le 24$（选择纤维），$d_Z\le 64$（块压缩或纤维）；
• $C_{10}$ ($P=768$)：$d_X\le 48$ 且 $d_X^{(\mathrm{lat})}=48$（潜在精确值）。

数据表明，同一码在不同方法下得到的上界差异明显，受限提升（尤其是选择纤维）常能给出比潜在方法更小的值，但并不是所有符码都能从 ETS 或译码残差中获益。论文特意强调，表中每个上界都附有可检查的向量支持（见示例 7.1–7.8），因此结论不会因搜索启发式而丧失数学可靠性。同时，数值仅代表上述参数范围内的结果，对更大块长或不同活跃/潜在拆分的推广性尚未讨论。

局限与待解决问题

首先，全文仅提供距离的上界而非下界，因此无法确定这些码的真实最小距离。文中潜在距离的精确化仅在某些特定因子（如 $m=4$）和核块常数假设成立时有效，无法推广到所有参数。其次，受限提升、ETS 和译码残差等搜索都是启发式的，能否找到更小权重的逻辑算子依赖于搜索规模和算法效率，不保证穷尽所有可能性。论文指出，距离 20 以下尚可通过译码实验直接获得残差，距离更大时这类候选极难出现，这暗示当前方法存在尺度瓶颈。

附录 A 中提出的精确潜在下界取决于混合积核的块常数性质，这对少量码成立，但更一般的设计未必满足这一代数条件。论文未分析将框架扩展到其它 APM 构造（如不同 $J,L$ 或非 3/12 模式）时，这些假设和结果的迁移性。此外，虽然结果表显示最佳上界随码长似乎有线性增长趋势，但论文明确声明此观察不能作为断言，因为计算资源随长度上升而减少，真实最小距离可能在此平台附近停止增长。因此，该码族距离的真实增长性质和纠错潜力的下界仍是悬而未决的核心问题，有待更系统的代数或概率论工具介入。