2025-11-24T11:49:18.043706

Maximally Extendable Product Codes are Good Coboundary Expanders

Kalachev, Panteleev

We investigate the coboundary expansion property of product codes called product expansion, which plays an important role in the recent constructions of good quantum LDPC codes and classical locally testable codes. Prior research revealed that this property is equivalent to agreement testability and robust testability for products of two codes of linear distance. However, for products of more than two codes, product expansion is a strictly stronger property. In this paper, we prove that the collection of random codes over a sufficiently large field has good product expansion. We believe that in the case of four codes, these ideas can be used to construct good quantum locally testable codes in a way similar to the current constructions using only products of two codes.

academic

Maximally Extendable Product Codes are Good Coboundary Expanders

基本信息

论文ID: 2501.01411
标题: Maximally Extendable Product Codes are Good Coboundary Expanders
作者: Gleb Kalachev, Pavel Panteleev (Moscow State University)
分类: cs.IT math.IT quant-ph
发表时间/会议: 接受发表于 IEEE Symposium on Foundations of Computer Science (FOCS 2025)
论文链接: https://arxiv.org/abs/2501.01411

摘要

本文研究了张量积码的余边界扩展性质（称为乘积扩展），该性质在最近构造良好量子LDPC码和经典局部可测码中发挥重要作用。先前研究表明，对于两个具有线性距离的码的乘积，该性质等价于一致性可测性和鲁棒可测性。然而，对于超过两个码的乘积，乘积扩展是一个严格更强的性质。本文证明了在足够大的域上随机码的集合具有良好的乘积扩展性质。作者相信在四个码的情况下，这些思想可以用于构造良好的量子局部可测码，类似于当前仅使用两个码乘积的构造方法。

研究背景与动机

问题背景

高维扩展器的重要性: 高维扩展器（HDXs）在构造经典局部可测码（LTCs）和量子低密度奇偶校验码（qLDPC）中起到关键作用。
乘积扩展的局限性:
- 对于两个码的乘积，乘积扩展等价于一致性可测性和鲁棒可测性
- 但对于超过两个码的乘积，乘积扩展是严格更强的性质
- 现有构造主要基于两个码的乘积，限制了应用范围
量子LTC猜想: 构造良好的量子局部可测码（qLTCs）需要四维类比的扩展器LP码，这需要四个码的乘积具有良好的乘积扩展性质。

研究动机

扩展现有理论到任意数量码的乘积
为量子LTC猜想提供理论基础
建立随机码具有良好乘积扩展的概率界

核心贡献

主要理论结果: 证明了在足够大的域上，任意数量的随机码集合以高概率具有良好的乘积扩展性质。
最大可扩展乘积码概念: 引入了最大可扩展乘积码的概念，这是继承所有其他相同参数乘积码可扩展性质的通用码。
乘积扩展的重新表述: 将乘积扩展性质用对偶码乘积中的可扩展子集重新表述，简化了高维分析。
LTCs的乘积扩展: 证明了局部可测码（LTCs）集合是乘积扩展的。
任意长度LTCs构造: 证明了任意长度和接近1的码率的LTCs存在。

方法详解

任务定义

给定线性码集合 $C = (C_i)_{i \in [D]}$ ，其中 $C_i \subseteq \mathbb{F}_q^n$ ，定义乘积码：

$C_1 \otimes \cdots \otimes C_D := \{c \in \mathbb{F}_{[n]^D} | \forall i \in [D], \forall \ell \in L_i : c|_\ell \in C_i\}$

其中 $L_i$ 是平行于第 $i$ 轴的线集合。

乘积扩展定义: 码集合 $C$ 是 $\rho$ -乘积扩展的，如果每个码字 $c \in C_1 \boxplus \cdots \boxplus C_D$ 都可以表示为 $c = \sum_{i \in [D]} a_i$ ，其中 $a_i \in C^{(i)}$ ，且满足：

$\rho \sum_{i \in [D]} \|a_i\|_i \leq \|c\|$

核心技术框架

1. 可扩展集合理论

内生成集合: 集合 $M \subseteq [n]^D$ 对码 $C_1 \boxplus \cdots \boxplus C_D$ 是内生成的，如果其每个支撑在 $M$ 上的码字都可以表示为 $M$ 内包含线上码字的和。
可扩展集合: 集合 $M$ 对码 $C_1 \otimes \cdots \otimes C_D$ 是可扩展的，如果满足 $M$ 内局部约束的每个局部码字都可以扩展为全局码字。

2. 最大可扩展性

定义: 乘积码 $C = \bigotimes_{i \in [D]} C_i$ 是最大可扩展的，如果对于具有相同维数的任何其他乘积码 $C'$ ，当集合 $M$ 在 $C'$ 中可扩展时，它也在 $C$ 中可扩展。

3. 关键引理链

引理17: $\rho$ -乘积扩展意味着所有 $\rho$ -闭集都是内生成的
引理19: 如果所有 $\varepsilon$ -闭集都是内生成的，则 $\rho(C_1, \ldots, C_D) \geq \gamma(\varepsilon, D)$
引理20: 最大可扩展码继承LTCs的乘积扩展性质

证明策略

第一步: LTCs的乘积扩展

证明局部可测码集合具有乘积扩展性质：

引理14: 对于具有最小距离至少 $\delta n$ 和声音范围 $(\alpha_l, \alpha_h)$ 的码 $C_1, \ldots, C_D$ ，存在正函数 $f(D, \alpha_l, \alpha_h, \delta)$ 使得 $\rho(C_1, \ldots, C_D) \geq f(D, \alpha_l, \alpha_h, \delta)$ 。

第二步: 码率适配

通过子码构造实现任意码率：

引理10: 对于子码 $C'_1 \subseteq C_1$ ，有： $\rho(C'_1, C_2, \ldots, C_D) \geq \frac{\rho(C_1, C_2, \ldots, C_D)}{1 + \rho(C_2, \ldots, C_D)^{-1}}$

第三步: 随机码的最大可扩展性

引理21: 从 $\text{Gr}_{2^t}(n, k_1) \times \cdots \times \text{Gr}_{2^t}(n, k_D)$ 均匀随机选择的码元组，其乘积码以概率至少 $1 - n^D 2^{n^D - t + 1}$ 是最大可扩展的。

实验设置

理论验证方法

本文主要是理论性工作，通过严格的数学证明验证结果：

概率分析: 使用Schwartz-Zippel引理分析随机码的性质
归纳证明: 对维数 $D$ 进行归纳证明乘积扩展性质
构造性证明: 通过显式构造证明LTCs的存在性

参数设置

域大小: $2^t$ ，其中 $t$ 足够大使得 $n^D 2^{n^D - t + 1} \to 0$
码率: $(R_1, \ldots, R_D) \in (0,1)^D$
码长: 任意 $n \in \mathbb{N}$

实验结果

主要理论结果

定理2: 对于每个码率元组 $(R_1, \ldots, R_D) \in (0,1)^D$ ，存在 $\rho > 0$ 使得对于每个 $n \in \mathbb{N}$ ，从 $\text{Gr}_{2^t}(n, k_1) \times \cdots \times \text{Gr}_{2^t}(n, k_D)$ 均匀随机选择的码元组（其中 $k_i \leq nR_i$ ）以概率至少 $1 - n^D 2^{n^D - t + 1}$ 是 $\rho$ -乘积扩展的。

推论3: 对于任意区间 $I_1, \ldots, I_D \subseteq (0,1)$ ，存在 $\rho > 0$ 使得对于足够大的 $n$ ，存在码 $C_1, \ldots, C_D \subseteq \mathbb{F}_{2^{t_n}}^n$ （其中 $t_n = (n+1)^D$ ）满足：

$\frac{1}{n} \dim C_i \in I_i$
$\rho(C_1, \ldots, C_D) \geq \rho$
$\rho(C_1^{\perp}, \ldots, C_D^{\perp}) \geq \rho$

关键技术结果

LTCs构造 (定理4): 对于每个 $R \in (0,1)$ ，存在常数 $s > 0, \Delta > 0, \delta > 0$ 使得对于每个 $n \in \mathbb{N}$ ，存在 $(\Delta, s)$ -局部可测 $[n, k, d]$ 码，其中 $k \geq Rn, d \geq \delta n$ 。
扩展性保持: 子码的乘积扩展因子至少为原码的 $2^{-D}(\rho)^{2^D}$ 。