哪些优化问题可能让解码量子干涉获得优势？

为什么 DQI 需要先筛选再构建解码器

DQI 通常应用于 max-LINSAT：一个实例由有限域上的矩阵 B 以及每一行的一个接受集组成，目标是尽可能多地满足行。矩阵 B 定义了两个对偶线性码——优化器码 im B 和解码器码 ker Bᵀ。DQI 在稀疏错误模式上制备叠加态，计算它们在 Bᵀ 下的校验子，然后通过相干地运行 ker Bᵀ 的经典解码器来擦除这些模式。该解码器码的最小距离限制了最坏情况下可纠正的错误数量，也限制了 DQI 能保证的解质量。

问题在于，此前每个候选问题都是各自独立研究的，针对那一个问题构建一套码、解码器和经典比较。这使得事先很难判断哪些问题值得进一步研究。论文的应对方式是把 DQI 的结构转化为明确的筛选标准，从而在任何人构建解码器或经典攻击之前，就能按码参数、解码保证和经典基线过滤候选问题。

Prange 补全划出经典基线

经典基线直接在 im B 中构造一个码字。假设 B 有 m 行和 n 个线性无关的列。一次 Prange 补全选取 n 个线性无关的行——称为信息集——并为每一行取一个接受值。求解这 n 个线性方程得到 x，因此被选中的行按构造即被满足；计算 Bx 随后确定了其余 m − n 个坐标。这一步就是“补全”，它不需要解码。

如果信息集事先固定，且接受集相互独立、随机、密度为 ρ，那么每个剩余坐标被满足的概率为 ρ。因此单次尝试满足的期望比例为 n/m + (1 − n/m)ρ。优化器码率 n/m 是 Prange 补全刻意满足的比例，其余部分按随机猜测的速率被满足。这就是论文的余量上限所对照的基准，它是一个理论基线，而不是对任何特定问题最强经典算法的描述。

余量上限与 OPI 已经达到的水平

对于计数被满足约束这一标准目标，在最坏情况汉明解码下，论文证明 DQI 相对一次 Prange 补全的渐近期望质量余量至多为 κ(α) = √((α/2)(1 − α/2)) − α/2，其中 α 是优化器码率。对码率取最大值得到通用上限 (√2 − 1)/2。最优多项式交集（OPI）在域大小增大、接受集密度趋于 1/2 时渐近地达到该固定码率上限。

其后果是对整个类别的封顶：在这一设定下，没有任何候选问题能超过 OPI 的余量。因此 OPI 的已知表现是汉明许可分析所覆盖类别内可能达到的最好水平，它充当其他候选构造的基准，而不是众多有前景例子中的一个。该上限是关于特定解码许可下渐近期望质量的陈述，而不是关于实际运行时间或关于所有可能目标的断言。

实值目标改变需要解码哪些错误

论文把分析从计数目标扩展到实值目标，其中每一行在素域上使用同一个函数（至多相差一个平移）。该函数有两个性质很重要。它的矩给出了 DQI 在每个长度上期望得分的精确公式。它的傅里叶支撑决定了解码器必须纠正哪些错误值——即错误字母表——因此只为这些值构建的解码器就足够了。

对于余弦目标，傅里叶支撑是 {±1}，针对这些带符号错误的解码器可以证明其纠正范围超过最小汉明距离的一半。这就是论文第二个候选问题背后的机制：受限的错误字母表即使在没有相应汉明保证时，也可能容许有用的解码保证。因此目标同时决定了求解质量和解码器必须纠正哪些错误，这也是论文把目标当作设计变量、而非问题陈述中固定部分的原因。

交错最大一致检验秘密解码器的价值

交错最大一致（AMA）要求在一个公开线性码中找到一个码字，使其落在尽可能多的逐坐标接受集中。这些实例由 McEliece 型公钥构建：公开矩阵是一个交错码的置乱校验矩阵，该交错码通过把扩域上的一般化 Reed–Solomon 码限制到基域元素的码字而得到。秘密密钥暴露了交错结构，而由于 ker(Bᵀ) = ker(H_pub)，密码系统的秘密解码算法恰好就是 DQI 所需之码的解码器。知道底层的 Reed–Solomon 描述，就能纠正最多 ⌊r/2⌋ 个汉明错误，其中 r 是校验行数。

这种比较是刻意不对称的：DQI 获得秘密解码器，而经典基线只拿到公开实例——公开矩阵和接受集。相对有限预算的 Prange 重启基线，这一优势是一个定理。相对只看公开实例的经典搜索，比较在 m = 6000 与 m = 14000 之间转向有利于 DQI，而在 m = 14000 和 20000 时，作者测试的搜索即使拿到密钥也仍低于 DQI。有了密钥，问题就变成带迹定义接受集的 OPI，因此 AMA 也在追问量子和经典优化如何使用同一套解码表示。其困难性假设针对的是只看公开实例的求解器。

乘法多项式交集让双方都拿到解码器

乘法多项式交集（MPI）是一个余弦优化问题，其矩阵元素是有限域元素的离散对数。它的公开多项式格解码器使用有理重构来恢复带符号错误，而这些错误正是余弦目标产生的错误。这种配对提供了目标依赖定律所需的受限错误许可，并由此给出严格的 DQI 质量保证——与 AMA 不同，量子和经典求解器都获得了解码结构。

相对所测试的经典求解器（包括格约化），比较在 m = 1000 与 m = 2000 之间转向有利于 DQI，而在 m = 2000 和 6000 时 DQI 的精确期望得分更高。论文明确指出，有效的 DQI 保证可以与更强的经典算法并存：在测试的最小长度上，格方法胜过 DQI。在测试的较大长度上 DQI 保持领先，而扩展性研究表明，所测试攻击要追平它所需的投入随长度增长，尽管这是对实测预算之外的外推。

三种强度的证据与一个未决问题

对这两个构造而言，证据有三种不同强度。与 Prange 重启的比较是一个定理。与作者所测试求解器的比较是实验，其中的 DQI 数值是计算出的期望值，而不是观测到的量子采样平均值。更广泛的经典困难性则作为假设陈述——AMA 在 m = 40000 时的假设 (A) 和 (B)，以及 MPI 的假设 (C)。攻击成本计算是在其所述模型内的估计，而从扩展性运行推导出的成本是外推而非界。

还有一个问题未决。一个能达到存在性线的有效经典编码器将消除这一优势，而目前尚无人知道这样的编码器。因此满足筛选条件只是让每个问题成为候选，而不是已证明的量子优势。这些保证关注的是所述解码许可下的期望优化质量，而要把质量优势转化为运行时间优势，还需要计入态制备、相干解码以及获得目标得分所需的采样次数。

论文自身的重点在于区分解码保证与解码范围的上界。例如，扩展码对正比例的错误容许最坏情况解码器，但在搜索中考察的扩展码和 Tanner 解码器，其已确立的半径低于临界阈值，因此不能证明优势。由于这些半径来自具体解码器而非距离界，它们既不排除同一码的更好解码器，也不排除稀疏码这一类别。这就是值得带走的判断：一个候选问题只是相对于某个具名解码器和某个具名基线才被排除，而被违反的条件指明了该候选问题必须改变哪个特征。

本文引用的文献