Binary code rate bounds via classical--quantum channels
Omar Alrabiah, Venkatesan Guruswami
cs.IT, math.CO, quant-ph
2026-08-10
一条 pretty good 准则把 Plotkin 到两条 MRRW 收成信道设计：PGM 比特误码低于相对距离，码率就被容量钉住。混合量子比特信道在全部 δ∈(0,1/2) 上严格压低沿用近五十年的上界。
纠错码有两套尺子。Hamming 这边看最坏情况：码的最小距离 δn 保证任意少于 δn/2 处翻转都能纠正。Shannon 这边看随机噪声：信道容量给出可靠传输的极限码率。
Shannon 侧早在 1948 年就结案了。Hamming 侧的渐近率距函数 R₂(δ) 到现在还没钉死。下界仍是 Gilbert–Varshamov：R₂(δ) ≥ 1−h(δ)，h 是二元熵。上界这边，McEliece、Rodemich、Rumsey、Welch 在 1977 年给出的两条 MRRW 界，几乎五十年没被一般性的更强结果取代。相对距离到 1/2，Plotkin 界已经把码率打到 0；但 BSC 在翻转概率接近 1/2 时容量仍为正。两套尺子差的就是这一截。
Alrabiah 与 Guruswami 把这件事收成一条 pretty good 准则。取一个二元输入、输出对称的经典–量子（cq）信道。对它做 pretty good measurement（PGM），后验采样的量子版。MAP 解码挑最大后验码字；PGM 按后验分布抽一个。如果 PGM 的比特误码率 pe 低于相对距离 δ，那么任意长度 n、相对距离 δ 的二元码，线性或非线性，码率都不超过该信道的 Holevo 容量，误差是 O(n^{-1/2})。
操作含义很直接。PGM 有粗粒化封闭性：整块采样的每一位，同时就是那一位的后验样本。于是期望 Hamming 距离不超过 n·pe。码字一旦解错，距离至少 δn，所以整块解对的概率至少 1 − pe/δ。pe < δ 时这个概率是常数。cq 信道编码的强逆定理说，码率一旦超过容量，块错误概率会趋于 1。常数成功概率已经够把码率钉在容量下面。
选不同信道，就收回已知的四条经典界：
限制在经典信道上，这条准则最强只能到 Elias–Bassalygo。要再往上走，输出态必须不对易。
新信道是混合量子比特信道 MQC：先走一层 BSC 翻转，再制备 PSC 纯态，丢掉经典误差标签。混态让 Holevo 信息下降，PGM 误码上升；只要前者掉得更快，上界就更紧。再给 MQC 加一层掩码，得到 2MQC。
MQC 在全部 δ ∈ (0, 1/2) 上严格低于第一条 MRRW。δ=1/4 是图上标出来的点：第一条 MRRW 约 0.3545789，第二条约 0.3537105，MQC 数值最小点约 0.3503791。靠近 δ→1/2 时差距按 ε⁴ log e 衰减，ε=1/2−δ，低码率端几乎贴在一起。
2MQC 在同一开区间上严格低于第二条 MRRW。论文给的是浮点估计，不是认证全局最优。列出的最大间隙在 δ=0.25：第二条 MRRW 约 0.353711，2MQC 约 0.350379，差约 0.00333。δ=0.05 时差距只有 6.6×10^{-7}。
| 相对距离 δ | 第二条 MRRW | 2MQC 估计 | 间隙 |
| 0.10 | 0.692741 | 0.692727 | 1.3×10^{-5} |
| 0.25 | 0.353711 | 0.350379 | 0.00333 |
| 0.40 | 0.081469 | 0.081337 | 1.3×10^{-4} |
对偶由重量不超过 3 的校验生成的 LDPC 码，用一条稀疏校验的 PSC 局域解码，得到 U₃^{PSC}。它全程低于第一条 MRRW；δ ≥ 1/6 时低于 Shangguan–Yang 2026 的 B₃^{SY}。δ=3/10 时：U₃^{PSC}≈0.2065，B₃^{SY}≈0.2476，第一条 MRRW≈0.2502。
q 元侧给了 pretty good 准则的循环对称推广，擦除、对称、纯态、混合四族信道都能对上已知的 q 元界，没有宣称新的数值纪录。
近五十年二元码一般上界的标杆第一次被一条可设计的信道族系统性地压过去。问题被改写了：找更紧的 R₂(δ) 上界，变成在 pe≤δ 约束下最小化 Holevo 信息。MQC 和 2MQC 只是这个优化里的两个可行点，不是最优信道。
OpenAI 同期也改进了两条 MRRW 界，方法不同。论文写明自己的结果在 OpenAI 公告之前已经拿到；GPT-5.6 Sol Pro 对照后认为第一条 MRRW 的改进量对得上，第二条的 OpenAI 改进可能落进某个四维 cq 信道，作者没有核完。这条工作的卖点是框架：同一套判据覆盖 q 元码和 LDPC 结构。
Fano 不等式加上 Holevo 界保证，这条路跨不过 Gilbert–Varshamov。想证明线性码的 R₂(δ) 就等于 1−h(δ)，还差一个完全经典的问题：距离 δn 的线性码，在 BSC(δ−ε) 上最大似然解码是否一致地高概率成功。目前一般保证只到 Johnson 半径。
最优 cq 信道仍是开的。纯态输出最多到第一条 MRRW；有限维上的精确最优不知道。作者也没说清这套优化和 Samorodnitsky、Navon–Samorodnitsky 那些已有障碍之间是什么关系。
2MQC 的数值表明确写了「浮点估计，不是认证全局最优」。δ=1/4 处 MQC 看起来低于第二条 MRRW，论文把这一点标成数值观察，解析保证只覆盖「低于第一条」。
改进量在多数 δ 上很小。δ=0.05 时第二条 MRRW 只被削了不到百万分之一。对实际码构造几乎没有直接指导：这是渐近存在性上界，不给显式码，也不给可实现的译码器。
GPT-5.2 到 5.6 深度参与了信道候选的启发式搜索，Codex 与 Claude Code 参与了起草。数学设定由作者把关，MQC 作为候选信道是模型先提出来的，写在 AI 使用声明里。