Cubical Sheaf Complexes with Constant Expansion with Applications to Asymptotically Good qLTCs
Yeyuan Chen, Miryam Mi-Ying Huang, Yinchen Liu, Er-Cheng Tang
cs.IT, cs.CC, quant-ph
2026-09-23
在算术立方体上放置 Reed-Solomon 层码,对每个 r≥4 与 2≤k≤r−2 给出常数码率、线性距离、常数可测性且校验权重有界的 CSS 码;四维度 2 的二元 qLTC 码率下界为 1/48。
量子纠错要把 K 个逻辑比特装进 N 个物理比特,并扛住大约 D/2 个错误。渐近好的家族要求码率 K/N 和相对距离 D/N 都是与块长无关的正常数。量子 LDPC 再加一条:每个校验只看常数个比特,每个比特也只进常数个校验。
稀疏校验仍可能漏报。一段离所有合法码字都很远的错误,可以只触发极少几个检查。Aharonov 与 Eldar 定义的量子局部可测码(qLTC)要求:相对距离为 δ 的字,至少触发 ρδ 比例的校验,ρ 叫 soundness(可测性)。目标是四件事同时成立:常数码率、线性距离、常数可测性、有界校验与比特度数。
Panteleev–Kalachev 与 Leverrier–Zémor 已经给出渐近好的 qLDPC,但没有常数可测性。Dinur、Lin、Vidick(FOCS 2024,下称 DLV)做到了常数码率和有界校验权重,距离和可测性各掉一个 log³ N。这篇要把这两处三次对数拿掉。
几何来自 r 棵 Bruhat-Tits 树的算术商:有限群 Γs 作用在树的乘积上,得到有界度数的立方复形。平行面图连通,谱隙 λ ≤ max 2√qi/(qi+1),与商的大小无关。把树度数开大,几何扩张变好,局部邻域的形状保持不变。DLV 用阿贝尔提升把度数卡住,平行图会裂成许多互不连通的扩张块,可用的扩张只覆盖逆对数密度的集合,log³ 损失就从这里来。
局部码用 Reed-Solomon。树顶点的 q+1 条边自然标成射影直线 P¹(Fq),用齐次多项式求值。算术商会把不同邻域粘起来并做置换和缩放,随机码过不了这一关。Frobenius 扭转让边两端的缩放因子对齐,层结构才能从树上降到有限商,对偶层同样能降。
稳健性靠乘积扩张:网格上若干行码字与列码字相加后大量抵消,仍应能改写成总长度与最终支撑成正比的分解。关键定理是,在范数为 1 的求值集上,局部码率落在 [β, 1-β] 时,这些 RS 码及其对偶的乘积扩张常数 ϱ = cr β^r > 0,与码长无关。证明把支撑扩成低次多项式包,再证明这个包是 inner-generated(内部可生成):包内的字只用包内的坐标线就能分解。有了均匀局部扩张,就可以先把树度数开到满足 DLV 的谱条件,再只放大商的尺寸。
码率靠非对称局部维数:k 个方向给小固定码率,其余方向给互补码率。DLV 的 local-to-global 加上层对偶,给出 CSS 两侧的线性距离和常数可测性。最后把系数域限制到 F2,校验矩阵的行、列重仍有界。
对每个固定 r ≥ 4 和 2 ≤ k ≤ r−2,度 k 的 CSS 码满足 K = Ω(N)、D = Ω(N)、ρ = Ω(1),校验矩阵行、列重有界,且可在 N 的多项式时间内算出。r = 4、k = 2 给出二元渐近好 qLTC。码率下界为
K/N ≥ 1 / (2 · C(r,k) · 2^{r−k})
四维、度 2 时 C(4,2) = 6,于是 K/N ≥ 1/48。对照 DLV:码率仍是常数,距离从 Ω(N/log³ N) 升到 Ω(N),可测性从 Ω(1/log³ N) 升到 Ω(1)。块长按同余素数次数增长,N = 2^{Θ(s)}。
同时期 Gay 与 Jeronimo 也构造了渐近好 qLTC。Bafna、Li、Nguyen 的相近构造把均匀乘积扩张写成猜想;这篇对范数 1 族给出证明,覆盖了他们用的参数族。Li、Li、Liu 给 Gay–Jeronimo 码加上横向多控 Z 门,这篇不讨论逻辑门。
量子 PCP 和 qLTC 是同一条线索上的两个问题。常数可测性意味着局部校验能忠实地报告全局距离,这是把经典局部可测码的测试图景搬到量子 CSS 上缺的那一块。对做量子 LDPC 的人,几何从「两个方向的群左右乘」换成「r 棵树的算术立方体」,局部码从随机码换成可显式放置的 RS 码,这条路径可以复用。
这是存在性与多项式时间可构造性结果,近期硬件编不了这种码。1/48 的码率下界已经能写进标题,距离和可测性的隐含常数仍随 r、k 和局部参数走,正文没有给出数值。
作者写明:常数可以依赖 r、k 和固定的局部参数,不能依赖块长;不研究逻辑门。树度数必须足够大才能压住谱隙,校验权重 Δ 是常数,这个常数可能非常大。块长随 s 指数跳,没有「任意 N」的细粒度家族。乘积扩张只对范数 1 求值集上的 RS 码成立,没有解决 Bafna–Vyas 对一般乘法子群的高维猜想。α、δ、ρ 没有显式数值,1/48 只是码率下界。
论文首页有一段 AI 披露:主要构造和技术想法由 GPT-6 Astra 在 9 月 7 日生成,人类花了大量时间消化、核对并重写证明。这是关于证明可读性的诚实声明,不能代替同行审稿。