超图积码

超图积码（hypergraph product code，HGP）是 Jean-Pierre Tillich 与 Gilles Zémor 在 2009 年提出的量子 LDPC 构造：把任意两个经典 LDPC 码的 Tanner 图做乘积，量子比特放在乘积图的变量位置上，得到正码率、距离 Θ(√N) 的量子码。它是 qLDPC "√N 时代"的开端——此后的平衡积、提升积直到渐近好码都以它为退化起点，环面码正是"循环码×循环码"的特例。

图:乘积图 ${\mathcal{G}}_1\times {\mathcal{G}}_2$ 的四类节点——量子比特放在变量位置 $V_1\times V_2\cup C_1\times C_2$,X 校验挂 $C_1\times V_2$、Z 校验挂 $V_1\times C_2$(来源:QE112)

构造：Tanner 图的乘积

设经典码 ${\mathcal{C}}_i$ 的 Tanner 图为 ${\mathcal{G}}_i=\mathcal{T}(V_i,C_i,E_i)$（变量点 $V_i$、校验点 $C_i$，见tanner-graphs）。超图积把量子比特放在乘积图的变量位

$$V=(V_1\times V_2)\cup (C_1\times C_2),$$

X 型与 Z 型校验节点取互补的两块

$$C_X=C_1\times V_2,C_Z=V_1\times C_2,$$

即 $n_Q=n_1{n}_2+r_1{r}_2$（$r_i=|C_i|$）。等价的矩阵形式（变量集按 $V_1\times V_2$、$C_1\times C_2$ 排列，X 校验行按 $C_1\times V_2$、Z 校验行按 $V_1\times C_2$ 编号）：给定奇偶校验矩阵 $H_i\in {\mathbb{F}}_2^{r_i\times n_i}$，

$$H_X=[H_1\otimes I_{n_2}{I}_{r_1}\otimes H_2^{\mathsf{T}}],H_Z=[I_{n_1}\otimes H_2{H}_1^{\mathsf{T}}\otimes I_{r_2}],$$

两块列分别对应变量集 $V_1\times V_2$ 与 $C_1\times C_2$Tillich & Zémor 2009 (IEEE-IT)。文献常见简写 $H_X=[H_1\otimes I,I\otimes H_2]$、$H_Z=[I\otimes H_2^{\mathsf{T}},H_1^{\mathsf{T}}\otimes I]$ 隐藏了恒等阵的阶与转置位置——二者随指标约定而变，例如 Panteleev–Kalachev 的重述把第二个因子的 Tanner 图取转置，量子比特相应排在 $(V_1\times C_2)\cup (C_1\times V_2)$ 上，码长变为 $n_1{r}_2+r_1{n}_2$，两个约定给出同构的码族Panteleev & Kalachev 2020 (IEEE-IT)。

CSS 条件的逐项验证

Tillich–Zémor 的原始论证是组合式的：X 校验行 ${\mathbf{h}}_X(c_1,v_2)$ 与 Z 校验行 ${\mathbf{h}}_Z(v_1,c_2)$ 的内积等于同时邻接 $(c_1,v_2)$ 与 $(v_1,c_2)$ 的变量节点个数 mod 2。逐项讨论：

• 若 $v_1$ 在 ${\mathcal{G}}_1$ 中不邻接 $c_1$，或 $c_2$ 在 ${\mathcal{G}}_2$ 中不邻接 $v_2$，则不存在任何公共邻居，内积为 0；
• 若两处都邻接，则公共邻居恰为 $(v_1,v_2)$ 与 $(c_1,c_2)$ 两个——乘积图中连接二校验的 4-圈——内积 $=2\equiv 0(\mathrm{mod}2)$。

两种情形内积都为零，故 $H_X{H}_Z^{\mathsf{T}}=0$ 恒成立，$({\mathcal{C}}_X,{\mathcal{C}}_Z)$ 确实定义一个 CSS 码（css-codes）。矩阵形式下这是两行的事：由混合积法则 $(P\otimes Q)(R\otimes S)=(PR)\otimes (QS)$，

$$H_X{H}_Z^{\mathsf{T}}=(H_1\otimes I_{n_2})(I_{n_1}\otimes H_2^{\mathsf{T}})+(I_{r_1}\otimes H_2^{\mathsf{T}})(H_1\otimes I_{r_2})=H_1\otimes H_2^{\mathsf{T}}+H_1\otimes H_2^{\mathsf{T}}=0,$$

在特征 2 下相消。两个证明互相印证：正交性来自 4-圈结构，“每个 X 校验与每个 Z 校验共享 0 或 2 个量子比特”是 HGP 家族的标志性几何。

维数定理：$k_Q=k_1{k}_2+k_1^T{k}_2^T$

定义转置 Tanner 图 ${\mathcal{G}}^T=\mathcal{T}(C,V,E)$（变量与校验互换），其对应码 ${\mathcal{C}}^T$ 的维数满足恒等式 $\dim \mathcal{C}=|V|-|C|+\dim {\mathcal{C}}^T$。核心引理是把 × 积化归为张量积码（$\dim ({\mathcal{C}}_1\otimes {\mathcal{C}}_2)=\dim {\mathcal{C}}_1\cdot \dim {\mathcal{C}}_2$）：

$${\mathcal{G}}_1{\times }_X{\mathcal{G}}_2=({\mathcal{G}}_1^T\otimes {\mathcal{G}}_2{)}^T,{\mathcal{G}}_1{\times }_Z{\mathcal{G}}_2=({\mathcal{G}}_1\otimes {\mathcal{G}}_2^T{)}^T.$$

于是 $\dim {\mathcal{C}}_X=n_1{n}_2+r_1{r}_2-r_1{n}_2+k_1^T{k}_2$，$\dim {\mathcal{C}}_Z=n_1{n}_2+r_1{r}_2-n_1{r}_2+k_1{k}_2^T$，相加减去 $n_Q$ 得维数定理（Prop.14）：

$$k_Q=\dim {\mathcal{C}}_X+\dim {\mathcal{C}}_Z-n_Q=k_1{k}_2+k_1^T{k}_2^T.$$

随机满秩的 $H_i$ 使 $k_i^T=0$ 以高概率成立，此时 $k=k_1{k}_2$ 随 $N$ 线性——正码率；而且只要 ${\mathcal{C}}_1$ 非平凡，$\mathcal{Q}(\mathcal{G}\times \mathcal{G})$ 恒有正维数，HGP 不会”塌缩”。

距离定理：min 型，不是乘性

记 $d_i$ 为 ${\mathcal{C}}_i$ 的距离、$d_i^T$ 为转置码距离。定理 15：

$$d_Q\ge \min (d_1,d_2,d_1^T,d_2^T),$$

且在非退化情形取等Tillich & Zémor 2009 (IEEE-IT)。两个方向的证明骨架：

• 下界（Lemma 16）：取重量 $<\min (d_1,d_2^T)$ 的 $x\in {\mathcal{C}}_X$，考察其支集在 $V_1$ 上的投影 $V_1^{\prime }$——投影小于 $d_1$ 迫使诱导子图上的”局部经典码”退化为零维，逐步推出 $x$ 的每个 $C_1\times C_2$ 分量也为零，最终 $x\in {\mathcal{C}}_Z^{\perp }$（是稳定子而非逻辑算符）。
• 上界（Lemma 17）：取 ${\mathcal{C}}_1$ 的最小码字 $x_1$（重量 $d_1$）与任一 $v_2\in V_2$，则 $x_1\times \{v_2\}$ 是重量恰为 $d_1$ 的逻辑算符——距离不可能超过任一因子的距离。

⚠️ 一处常见误记：本文的距离定理是 min 型而非乘性 $d\ge d_1{d}_2$——后者属于后续同调积/距离平衡技术的语境（如 Kovalev–Pryadko 的乘性放大与 Hastings 纤维丛码的 $d_X{d}_Z\ge \Omega (N)$）。$\sqrt{N}$ 标度由算术而来：取 $n_1=n_2=n$、$r_i\approx n$，则 $N\approx 2n^2$ 而 $d\approx \delta n=\Theta (\sqrt{N})$——这就是 12 年天花板的结构性来源。

度分布优化与后续

HGP 是早期少数可做度分布优化的 qLDPC 构造：两因子 Tanner 图的度分布 $({\lambda }_i,{\rho }_i)$ 经卷积组合出乘积图的 $({\lambda }_X,{\rho }_X)$、$({\lambda }_Z,{\rho }_Z)$（原文式 8–11），为迭代译码性能调优留出自由度。环面码作为特例（循环码×循环码）在原文先行建立；Kovalev–Pryadko 随后给出更高码率的改进构造Kovalev & Pryadko 2012 (ISIT)；循环超图积码（cyclic HGP）则把准循环结构做彻底Aydin, Delfosse & Tham 2025 (arXiv)。HGP 的两个直接后代——平衡积与提升积——分别在下一词条展开。

延伸阅读

• balanced-product
• lifted-product
• qldpc-overview
• tanner-graphs
• ldpc-classical