量子 Tanner 码

量子 Tanner 码（quantum Tanner code）由 Anthony Leverrier 与 Gilles Zémor 在 2022 年 FOCS 提出：把量子比特放在左-右 Cayley 复形的方块上，用两个小码的张量码与对偶张量码在顶点处施加局部约束，得到概念上最简的渐近好量子 LDPC 码族。它顺带恢复了 Dinur–Evra–Livne–Lubotzky–Moses 的 c³ 局部可测试码构造，并经后续工作获得线性时间译码。

图:左-右 Cayley 复形的方块(square)——两条 A-边与两条 B-边围成四边形,量子比特就放在方块上(来源:QE024)

左-右 Cayley 复形

设群 G 带两个自逆生成集 $A=A^{-1}$、$B=B^{-1}$，$|A|=|B|=\Delta$。左-右 Cayley 复形的顶点集为 $V=V_0\cup V_1=G\times \{0,1\}$：A-边连接 $(g,0)$ 与 $(ag,1)$（左乘），B-边连接 $(g,0)$ 与 $(gb,1)$（右乘）；每个方块（square）是四元组

$$\{(g,0),(ag,1),(gb,1),(agb,0)\},a\in A,b\in B,$$

即两条 A-边加两条 B-边围成的四边形（见图）。${\mathcal{G}}_A$、${\mathcal{G}}_B$（左/右 Cayley 图的双覆盖）各自是 $\Delta$-正则图；若满足总无交换条件 $ag\ne gb$，则 $n=|Q|={\Delta }^2|G|/2$ 个方块互不重合。把方块视为”边”、只看 $V_0$（或 $V_1$），得到图 ${\mathcal{G}}_0^{\perp }=(V_0,Q)$：$g$ 与 $g^{\prime }=agb$ 相邻Leverrier & Zémor 2022 (FOCS)。具体实例取 Ramanujan 双 Cayley 复形：$G={\mathrm{PSL}}_2(q^i)$、$\Delta =q+1$。

码构造：局部约束挂在顶点

取两个小码 $C_A\subseteq {\mathbb{F}}_2^A$、$C_B\subseteq {\mathbb{F}}_2^B$，组合出两个定义在 $A\times B$ 上的局部码：

$$C_0=C_A\otimes C_B,C_1=C_A^{\perp }\otimes C_B^{\perp }.$$

量子比特放在方块 $q\in Q$ 上。Z 型稳定子挂在 $V_0$ 顶点：$v$ 的 Q-邻域 $Q(v)\cong A\times B$（v 的局部视图），要求局部取值构成 $C_0$ 的码字；X 型稳定子挂 $V_1$，局部取 $C_1$ 码字。这正是把经典 Tanner 码（expander-codes）的配方从图搬到方形复形上——两个经典码 ${\mathcal{C}}_0,{\mathcal{C}}_1$ 就是 ${\mathcal{G}}_0^{\perp }$、${\mathcal{G}}_1^{\perp }$ 上的 Tanner 码。

图:相邻顶点 $v$ 与 $vb$ 的局部视图 $Q(v)\cong A\times B$ 及其共享的一列——正交性论证的几何(来源:QE024)

正交性：共享行/列上的对偶对

CSS 条件 ${\mathcal{C}}_0^{\perp }\subseteq {\mathcal{C}}_1$ 的验证是构造的点睛之笔。取一个 $C_0$-生成元（支在 $v_0\in V_0$ 的 Q-邻域内的 $C_A\otimes C_B$ 码字）与一个 $C_1$-生成元（支在相邻 $v_1\in V_1$ 的 $C_A^{\perp }\otimes C_B^{\perp }$ 码字）。若二顶点由 B-边相连，两个 Q-邻域 $A\times B$ 恰共享一列 $\{(a,b):a\in A\}$（固定 b，见图）：该列上 $C_0$-生成元的取值是 $C_A$ 的码字、$C_1$-生成元的取值是 $C_A^{\perp }$ 的码字，逐坐标内积求和为零——

$$⟨C_A\text{-码字},C_A^{\perp }\text{-码字}⟩=0,$$

故两生成元正交；A-边相邻时对 $C_B/C_B^{\perp }$ 同理。“CSS 配对 ${\mathcal{C}}_1\supset {\mathcal{C}}_0^{\perp }$ 由构造保证”——不需要任何额外搜索。

参数与代价

对称化取 $\mathrm{rate}(C_A)=\rho$、$\mathrm{rate}(C_B)=1-\rho$，则码长 $n={\Delta }^2|G|/2$，校验数 $2\rho (1-\rho ){\Delta }^2|G|$，码率至少 $(2\rho -1{)}^2$（$\rho \ne 1/2$ 时为正）。距离定理：相对距离

$$\frac{d}{n}\ge \frac{\delta }{4{\Delta }^{3/2+\epsilon }},$$

其中 $\delta$ 是小码相对距离、$\epsilon >0$ 可任意小；且存在重量 $\sim n/\Delta$ 的码字，故相对距离上界 $O(1/\Delta )$——$\Theta ({\Delta }^{-3/2})$ 的下界离最优只差 ${\Delta }^{1/2}$Leverrier & Zémor 2022 (FOCS)。代价：每个校验作用于整个局部视图，重量 $\Theta ({\Delta }^2)$——比提升积/平衡积的 $\Theta (\Delta )$ 重一个因子，是”概念简洁”换来的硬件负担。

距离证明骨架：正常顶点与鲁棒性

证明对低重量 $x\in {\mathcal{C}}_1$ 运行”减重循环”：取 $x$ 在 ${\mathcal{G}}_1^{\perp }$ 诱导子图上度数 $<{\Delta }^{3/2-\epsilon }$ 的正常顶点（normal vertices）集 S。核心工具是对偶张量码的 w-鲁棒性（w-robustness）：$C_A\otimes {\mathbb{F}}_2^B+{\mathbb{F}}_2^A\otimes C_B$ 中重量 $\le w$ 的码字支集必集中于少数行加列——随机小码以高概率满足（$w={\Delta }^{3/2-\epsilon /2}$，且抗 $p={\Delta }^{\gamma }$ 比例的 puncturing，方法随 Panteleev–Kalachev 2021）。鲁棒性保证 S 中顶点的局部视图每列都 $O({\Delta }^{1/2-\epsilon })$-接近某个 $C_A$ 码字；${\mathcal{G}}_A\cup {\mathcal{G}}_B$ 的扩展性迫使这些”近似码字列”聚簇到一个顶点集 T；再用张量码 $C_A\otimes C_B$ 自身的鲁棒性，把典型 $v\in T$ 的局部视图与某个非零张量码字 $y$ 的差（重量 ${\Delta }^{3/2-\epsilon }$ 级）加到 $x$ 上——加上稳定子反而降低重量。反复循环，任何重量低于 $\delta n/4{\Delta }^{3/2+\epsilon }$ 的向量必落入 ${\mathcal{C}}_0^{\perp }$，即距离下界。

与 PK 构造的关系及后续

Panteleev–Kalachev 的好码用的也是完全方形复形（每点 link 为完全二部图的复形），但证明走”局部极小链+积扩展”路线（见good-quantum-codes）；量子 Tanner 走”正常顶点+鲁棒张量码”，概念更省、校验更重。后续：小集合翻转式译码推广到量子 Tanner 码给出线性时间算法；经典侧恢复 c³ LTC（常码率、常距离、常数查询局部可测试），量子侧 2026 年得到渐近好量子 LTC 收尾Gay & Jeronimo 2026 (arXiv)；横传非 Clifford 门的变体见Li, Li & Liu 2026 (arXiv)与qldpc-logical-ops。

延伸阅读

• good-quantum-codes
• expander-codes
• lifted-product
• tanner-graphs
• qldpc-frontier-2026