Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry

技术摘要：超越解码量子干涉的优化多项式交集最坏情况量子算法

问题定义
本文研究了优化多项式交集 (Optimal Polynomial Intersection, OPI) 问题。给定一个有限域 $\mathbb{F}_q$，一组不同的评估点 $\alpha = (\alpha_1, \dots, \alpha_n)$，以及每个 $i \in [n]$ 对应的子集 $S_i \subseteq \mathbb{F}_q$，目标是寻找一个次数小于 $k$ 的多项式 $P \in \mathbb{F}_q[X]$，使得对于至少 $s$ 比例的输入，满足 $P(\alpha_i) \in S_i$。该问题由速率 $R = k/n$ 和密度 $\rho = |S_i|/q$ 进行参数化。

在此项工作之前，解码量子干涉 (Decoded Quantum Interferometry, DQI) 算法 [JSW+25] 在特定的参数范围内为 OPI 提供了量子解法，超越了已知的最佳经典启发式算法（Prange 算法）。然而，DQI 的最坏情况性能受到限制；例如，当 $\rho = 1/2$ 时，除非 $R=1$，否则 DQI 无法实现满足率 $s=1$。虽然近期的平均情况分析 [Cha25] 改进了这些界限（在 $\rho=1/2$ 时允许 $s=1$ 且 $R > 0.75$），但这些分析依赖于集合 $S_i$ 的随机选择。Sun 和 Wootters [SW26] 的一个纯存在性结果表明，即使在最坏情况下，解也存在于比 DQI 覆盖范围更广的参数区间内，但并未提供相应的量子算法。

方法论
作者提出了一种改进 DQI 在最坏情况下表现的量子算法。该方法是 Regev 式量子归约 [Reg0l9] 与列表解码策略（类似于 Yamakawa 和 Zandry [YZ24] 以及 Chailloux [Cha25] 的框架）的变体。

1. 算法框架： 该算法准备一个与码（Reed-Solomon 码 $C$）与约束集 $S = \prod S_i$ 之交集成比例的量子态。它利用有限域上的量子傅里叶变换 (QFT) 以及对对偶码 $C^\perp$ 的解码器。
2. 列表解码策略： 不同于以往依赖唯一解码的最坏情况尝试，本算法采用了针对对偶码 $C^\perp$ 的列表解码器 (list decoder)。该解码器输出候选列表中的一个随机元素。如果列表大小为多项式级别且解码器以逆多项式概率成功，则算法成功。
3. 基于 Brascamp–Lieb 不等式的最坏情况分析： 核心技术挑战在于如何界定最坏情况下的“误差”项，即集合 $S_i$ 被对手性选择的情况。作者引入了一种新型的 Brascamp–Lieb 型不等式 的应用，并将其适配于最大距离可分 (MDS) 码。
   • 他们将误差概率分解为对偶码上的位移相关性 $\Gamma(u)$。
   • 他们利用二元生成多项式及其系数的 $\ell_1$ 范数来界定这些相关性。
   • 至关重要的是，他们应用了 MDS Brascamp–Lieb 不等式（定理 3.1）来界定对偶码上傅里叶偏差的乘积之和。该不等式利用 MDS 性质（高最小距离）来控制求和，使作者能够证明即使对于最坏情况下的集合，误差也是可以忽略不计的。
4. 傅里叶偏差界限： 为了完成分析，论文推导了集合 $S_i$ 指示函数傅里叶系数 $Q$ 次幂之和的紧致界限。这些界限依赖于加法组合学（特别是通过 Pollard 定理和 Green-Ruzsa 结果得到的关于加法能量的界限）以及傅里叶偏差估计。

主要贡献与结果

1. 首个超越 DQI 的最坏情况量子算法： 本文提出了第一个在最坏情况下求解 OPI 且参数严格优于 DQI 的量子多项式时间算法。

   • 平衡情况 ($\rho = 1/2$)： 每当 $R > 0.75$ 时，该算法能找到完美解 ($s=1$)。这匹配了已知的最佳平均情况界限 [Cha25]，但对于任何选择的子集 $S_i$ 均成立。相比之下，DQI 在此区间要求 $R=1$ 才能实现 $s=1$。
   • 一般区间： 当 $\rho=1/2$ 时，对于 $R > 0.6976$，该算法改进了 DQI 的区间。论文提供了涉及二元熵函数 $H(R)$ 和傅里叶偏差矩的显式条件（定理 1.1 中的方程 1 和 2），用于确定可实现的满足率 $s$。

2. 改进的存在性界限： 作为算法分析的副产品，作者推导了 OPI（及 MDS 码的广义 MaxLINSAT 问题）解存在的改进存在性界限。

   • 对于 $\rho = 1/2$，他们证明了只要 $R > 0.7158$，解就存在，这改进了 Sun 和 Wootters [SW26] 建立的 $R > 0.7495$ 的先前阈值。
   • 该存在性结果适用于任何 MDS 码，而算法结果目前仅限于其对偶码具有高效列表解码器的码（例如 Reed-Solomon 码）。

3. 技术创新： 本文引入了 Brascamp–Lieb 不等式在编码理论和量子算法背景下的新应用。这种技术允许在最坏情况下控制对偶码上的傅里叶和，而之前的平均情况分析通过假设随机集合选择规避了这一任务。

意义
本文声称填补了 OPI 问题在最坏情况设定下，存在性保证与算法性能之间的显著差距。虽然 Sun 和 Wootters [SW26] 展示了在 DQI 失效的区间内解确实存在，但他们留下了关于是否能用量子算法找到这些解的问题。这项工作肯定地回答了这个问题。

作者指出，其结果特定于具有超常数特征（即 $p = \omega(1)$）的域，并且依赖于对偶码的可列表解码性。他们并未声称解决了任意码或小特征域（如 $\mathbb{F}_2$）的最坏情况下的 MaxLINSAT 问题，并指出 DQI 及他们自己的结果目前都无法扩展到这些设置。这项工作为多项式交集问题的量子优势树立了新的基准，证明了量子算法可以在最坏情况下达到此前仅已知在平均情况或存在性意义上可行的性能。