扩张码（经典与量子）

扩张码（expander code）由 Sipser 与 Spielman 在 1994 年提出：把 Tanner 图的校验节点放在一张扩张图上，图的"小集合的邻点充分展开"性质直接兑换成码的距离与线性时间译码——第一批显式构造的渐进好码。2015 年 Leverrier–Tillich–Zémor 把同一译码思想量子化，对超图积量子码给出线性时间算法、可证对抗式纠正 Ω(√n) 个错误，是经典 LDPC 技术第一次成功移植到量子码的非恒数错误场景；2022 年的量子 Tanner 码把距离推到 Θ(n)，2026 年的代数扩张码继续推进速率下界。

扩张图

双正则二部图 $G=(A\cup B,E)$，左度 ${\Delta }_A$、右度 ${\Delta }_B$。称 $G$ 为 $({\gamma }_A,{\delta }_A)$-左扩张，若任意左子集 $S\subseteq A$（$|S|\le {\gamma }_A{n}_A$）满足

$|\Gamma (S)|\ge (1-{\delta }_A){\Delta }_A|S|,$

即小集合的邻点几乎”满展开”（${\delta }_A$ 越小越强）。随机双正则图以高概率是好扩张图；显式构造（如 zig-zag 积）可多项式时间给出Leverrier, Tillich & Zémor 2015 (FOCS)。

扩张码：构造、速率与距离

构造：比特放在左侧 $A$；每个右侧节点 $b\in B$ 携带一个局部码 $C_0\subseteq {\mathbb{F}}_2^{{\Delta }_B}$（码率 $r_0$、相对距离 ${\delta }_0$，如取扩展汉明码），约束是”$b$ 的邻接比特构成 $C_0$ 的码字”。这是 Tanner 广义 LDPC 的特例（局部约束替换单奇偶校验，见tanner-graphs）。扩张把局部约束”摊开”到全局：速率 $\ge 2r_0-1$（Sipser–Spielman 的约束计数论证给出），且该下界在 Kopparty–Tamo 的代数扩张码中被推广到更低速率区域Kopparty & Tamo 2026 (arXiv)。

唯一邻居引理（距离分析的工具）：记 ${\Gamma }_u(S)$ 为恰有一个邻点在 $S$ 中的右侧节点。${\delta }_A<\frac{1}{2}$ 时

$|{\Gamma }_u(S)|\ge (1-2{\delta }_A){\Delta }_A|S|.$

证明：边计数 ${\Delta }_A|S|=|{\Gamma }_u|+{\sum }_{b\in {\Gamma }_m}{\mathrm{deg}}_S(b)\ge |{\Gamma }_u|+2|{\Gamma }_m|$，故 $|{\Gamma }_m|\le \frac{1}{2}({\Delta }_A|S|-|{\Gamma }_u|)$；代入展开式 $|{\Gamma }_u|+|{\Gamma }_m|\ge (1-{\delta }_A){\Delta }_A|S|$ 整理即得。∎

距离定理：${\delta }_A<\frac{1}{2}$ 时扩张码距离 $d\ge {\gamma }_A{n}_A$——渐进好码。证明：设非零码字支撑 $S$，$|S|\le {\gamma }_A{n}_A$。取唯一邻居 $b\in {\Gamma }_u(S)$：$b$ 的邻接比特中恰有一个落在 $S$ 内（取值 1），其余全在 $S$ 外（取值 0），局部字重恰为 1；但 $C_0$ 距离 $\ge 2$，不含重量 1 的字，矛盾。∎ 这是显式构造渐进好码的第一个例子——GV 界只保证随机码好（见classical-bounds），扩张码把”存在”变成”可写出、可译码”Sipser & Spielman 1994 (FOCS)。

Sipser–Spielman 线性时间译码

算法（翻转译码，单奇偶校验版）：接收 $\mathbf{y}$，算综合征；反复寻找”多数校验失败”的错误比特并翻转它，直到综合征归零。

为什么存在可翻的比特：设错误集 $E$，$|E|\le \frac{{\gamma }_A}{2}{n}_A$。$E$ 的唯一邻居必不满意（恰一个错误邻居 ⇒ 局部奇偶破坏 ⇒ 该综合征比特为 1），故不满意校验 $\ge |{\Gamma }_u(E)|\ge (1-2{\delta }_A){\Delta }_A|E|$；而 $E$ 的邻点总数至多 ${\Delta }_A|E|$，满意校验至多占其余部分 $\le 2{\delta }_A{\Delta }_A|E|$。当

${\delta }_A<\frac{1}{4}⟺1-2{\delta }_A>2{\delta }_A$

时不满意校验严格占多数，逐个累加可知存在某个错误比特 $a\in E$，其邻点中过半校验失败——翻转 $a$ 使综合征重量严格下降。综合征重量单调下降且有下界 0，算法必终止；只要初始错误 $\le \frac{1}{2}{\gamma }_A{n}_A$，终止时必归零。每步局部计算 $O(\Delta )$，总步数线性，编码与译码都是线性时间Sipser & Spielman 1994 (FOCS)。Gallager 式的比特翻转（见ldpc-classical）在扩张图上第一次获得可证明的收敛保证。

量子扩张码（Leverrier–Tillich–Zémor 2015）

经典翻转要”猜单比特的值”，量子上测单比特会摧毁叠加——直接移植不可行。LTZ 的解法是以生成元为单位操作：对超图积构造（把一个经典码 $C$ 与自身做积，得 CSS 码；见hypergraph-product），每步在单个稳定子生成元（$H_X$ 或 $H_Z$ 的一行）的支撑内寻找一个比特模式 $e_1$，使综合征重量严格下降（并取降幅/代价比最大者）。扩张性保证只要当前错误 $<\frac{1}{3(1+{\Delta }_B)}\min ({\gamma }_A{n}_A,{\gamma }_B{n}_B)$，改进步必存在。

图:量子扩张码的临界生成元 $g_{ba}$ 六分区——翻转 $x_a\cup x_b$ 使两组综合征比特由 1 变 0、另两组不变、至多一组 +1,从而严格降低综合征重量(来源:QE056)

改进步的构造如上图：把候选生成元 $g_{ba}$ 划分为六份，翻转其中两份 $x_a\cup x_b$ 让”单侧错误”的两组校验从失败转为通过、交叉组不变、剩余组至多增加一个失败——净效果必为负。定理（LTZ）：${\delta }_A,{\delta }_B<\frac{1}{6}$ 时，算法线性时间纠正任何重量 $\le \frac{1}{3(1+{\Delta }_B)}\min ({\gamma }_A{n}_A,{\gamma }_B{n}_B)$ 的对抗错误。对码长 $n=n_A^2+n_B^2$、参数 $[[n,k\ge (n_A-n_B{)}^2,\min (d,d^{\mathsf{T}})]]$ 的超图积码族（常数码率、距离 $\Theta (\sqrt{n})$），这是纠到距离常数分数的第一个线性时间量子算法Leverrier, Tillich & Zémor 2015 (FOCS)。

谱系：从 FOCS’94 到量子 Tanner 码

Sipser–Spielman（经典，线性时间好码）→ LTZ 2015（量子，$\Omega (\sqrt{n})$ 对抗纠错）→ 量子 Tanner 码 2022（距离 $\Theta (n)$ 且保留扩张式线性时间译码，见quantum-tanner）→ Panteleev–Kalachev 渐进好量子码（见good-quantum-codes）。2026 年 Kopparty–Tamo 的代数扩张码把局部码换成代数结构，将正速率的参数区域向下推广Kopparty & Tamo 2026 (arXiv)——“扩张图 + 局部约束”这个 1994 年的配方，至今仍是构造好码与可译码的主力框架（见qldpc-frontier-2026）。

延伸阅读

• tanner-graphs
• ldpc-classical
• hypergraph-product
• quantum-tanner
• good-quantum-codes