技术摘要：超越局部性与经典可译性的 OPI 变体量子算法

1. 问题定义

本文研究了代码交集问题 (Code Intersection Problem, CIP)：给定一个线性码 $C \subseteq \mathbb{F}_q^m$ 和一个由非线性约束定义的集合 $A \subseteq \mathbb{F}_q^m$，寻找一个向量 $x \in C \cap A$。作者关注两个现有基于 Regev 归约（也称为解码量子干涉，decoded quantum interferometry）的量子算法受到限制的具体情形：

1. 经典可译性 (Classical Decodability)： 先前的成功应用依赖于在测量噪声量子态后能够对对偶码 $C^\perp$ 进行经典解码的能力。这限制了适用范围，使其仅限于具有高效经典解码器的码（例如在特定情形下的低阶多项式码）。
2. 逐坐标约束 (Coordinate-wise Constraints)： 先前的应用要求 $A$ 是一个笛卡尔积 $A_1 \times \dots \times A_m$，即约束独立地应用于每个坐标。这排除了对符号频率（直方图）的全局约束。

本文旨在分别克服这些限制，以识别新的量子优势候选领域并建立量子-经典分离。

2. 方法论

其核心框架利用了 Regev 归约，将 CIP 归约为对偶码 $C^\perp$ 的量子解码问题 (Quantum Decoding Problem, QDP)。给定一个支撑在 $A$ 上的态 $|\psi\rangle$，该归约要求从状态 $\sum_c X_c \text{QFT}^\dagger |\psi\rangle$ 中恢复一个随机码字 $c \in C^\perp$。

本文开发了两个不同的贡献来扩展这一框架：

贡献 1：超越经典可译性（量子解码）

• 目标： 解决寻找 $y \in (\mathbb{F}_q \setminus \{0\})^m$ 使得 $By = 0$（其中 $B$ 的行张成 $C^\perp$）的问题，而不假设 $C^\perp$ 存在高效的经典解码器。
• 方法论：
  • 作者改编了 Chen, Liu, and Zhandry (CLZ22) 的模板，但将对完整二次单项式空间的依赖替换为**“两倍乘法性质” (two-fold multiplication property)**。
  • 他们定义了空间 $W = \text{span}\{u \odot v : u, v \in C^\perp\}$，其中 $\odot$ 是逐坐标乘法。如果 $\dim(W) = s_2 \ll m$，则用于重线性化 (relinearization) 的辅助变量数量会减少。
  • 量子步骤： 他们没有在标准基下进行测量（这会产生噪声码字），而是使用每个坐标上的无歧义测量 (unambiguous measurements) 来获得包含真实符号的对 $\{c_i, c'_i\}$。
  • 线性代数步骤： 这些对产生了二次方程 $(c_i - a_i)(c_i - a'_i) = 0$。通过将这些方程提升到空间 $W$，该系统在 $n + s_2$ 个变量上变为线性系统。
  • 实例化： 他们将此应用于在随机点处置换后的 Reed–Muller (RM) 码。对于 RM 码，两个 $r$ 次多项式的乘积其次数至多为 $2r$。这使得他们可以解决 $m \le n^{2-\Omega(1)}$ 的实例，在这一情形下，已知不存在针对对偶 RM 码的高效经典解码器。

贡献 2：超越乘积约束（直方图局部约束）

• 目标： 解决 $A$ 由直方图局部约束（关于符号频率的全局约束）定义的 CIP 问题，其中可以在每个坐标上应用任意置换 $\pi_i$。
• 方法论：
  • 他们引入了替换稳定性 (replacement stability) 的概念。他们分析了当一个坐标被替换为随机符号后，均匀元素 $A$ 仍留在 $A$ 中的概率 $p_{stay}$。
  • 傅里叶分析： 他们证明了均匀态 $|A\rangle$ 的傅里叶变换的期望相对汉明重量恰好为 $1 - p_{stay}$。
  • 解码策略： 如果 $1 - p_{stay}$ 足够小（具体而言，小于 $C^\perp$ 的列表解码半径），则经典列表解码器可以以常数概率成功。
  • 稳定性计算： 使用倾斜泊松分布 (tilted Poisson distributions) 和局部中心极限定理，他们表明对于广泛的约束族（例如“最大负载”约束，即符号出现的次数至多为 $T$），$p_{stay}$ 被限制在远离零的范围内，从而确保了足够的傅里叶质量。
  • 预言机分离 (Oracle Separation)： 在随机预言机模型中，他们证明了虽然量子算法可以以常数概率满足这些约束，但进行多项式查询的经典算法失败的概率是指数级小的。这依赖于该码的列表可恢复性以及直方图约束对随机补全的抵抗力。

3. 关键结果

结果 1：RM 码在次二次阶数下的量子优势

• 定理 1.1 (非正式)： 对于行张成码 $C^\perp$ 的矩阵 $B$，如果两倍乘积空间的维度为 $s_2$，则当 $\text{dist}(C^\perp) \log(q-1) \ge 2n + s_2 + 2$ 时，量子算法可以找到一个全支撑核向量。
• 应用： 对于随机置换的 Reed–Muller 码，这产生了在 $m \le n^{2-\Omega(1)}$ 时的多项式时间量子算法。
• 经典对比： 作者还提供了一个使用**“三倍乘法性质”（要求 $\text{dist}(C^\perp) \ge n + s_3$）的经典算法**。
• 差距： 在某些参数范围（特别是对于 RM 码）内，量子条件（涉及 $s_2$）得到满足，但经典条件（涉及 $s_3$）未得到满足，且此时 $m < n^2$。这些范围代表了潜在的量子优势候选区域，因为先前的经典算法（如 ISS12, IS15 等）仅涵盖 $m = \Omega(n^2)$ 的情形。

结果 2：直方图约束下的量子-经典分离

• 定理 1.2 (非正式)： 对于码率为 $7/8$ 的 Reed–Solomon 码及特定的直方图约束（例如，将符号划分为允许计数为 $\{0\}$, $\{1, 2\}$, 和 $\{3, 4\}$ 的类别）：
  • 普通模型 (Plain Model)： 量子算法以反多项式概率找到一个满足条件的码字。
  • 随机预言机模型 (Random Oracle Model)： 量子算法以常数概率成功，而任何进行多项式查询的经典算法成功的概率都是指数级小的。
• 意义： 这证明了在最优多项式交集 (OPI) 问题中加入全局非线性约束（直方图）可以保持量子的易解性，同时增加经典的难度。

4. 重要性声明

本文将其工作定位为从两个不同方向推动 Regev 归约的边界：

1. 打破经典可译性障碍： 作者认为，量子解码器尚未被用于解决经典解码器未知的问题，这是“令人惊讶且不自然”的。通过利用乘积空间的代数结构（两倍乘法），他们证明了量子算法可以在对偶码缺乏已知高效经典解码器的情形下解决码交集问题。这提供了一个具体的量子优势候选，它不依赖于先前工作的“去量化”成功。
2. 扩展非线性约束的范围： 本研究将 Regev 归约的应用范围从坐标向（局部）约束扩展到了全局直方图约束。通过建立替换稳定性与傅里叶稀疏性之间的联系，作者展示了量子算法如何处理经典算法难以处理的复杂全局约束。
3. 预言机分离： 本文提供了相对于随机预言机的这些新约束类型的严格量子-经典分离证明，强化了码交集问题（超出之前研究过的特定 OPI 实例）中潜在量子优势的论据。

5. 谦逊态度与开放问题

作者明确指出了其结果的局限性和开放性：

• 去量化 (Dequantization)： 他们并不声称其针对 Reed–Muller 码的量子算法在经典上是困难的。他们明确指出，“显而易见的一个开放问题”是这些结果是否可以被去量化。他们指出，使用三倍乘法的经典算法留下了中间阶段作为量子优势的候选，但仅使用两倍乘法的经典算法仍然是一个挑战。
• 最坏情况 vs 平均情况： 普通模型中针对直方图约束的结果依赖于对随机置换的平均。作者希望未来的工作可以将这些扩展到最坏情况保证。
• 结合贡献： 他们承认将量子解码器与全局非线性约束相结合的技术难度，因为他们对量子解码器的分析依赖于独立的单坐标态，而这会被全局纠缠所破坏。

总之，本文提供了一个理论框架，用于将量子码交集算法扩展到经典解码未知的情形以及具有全局非线性约束的问题，并提供了特定的参数范围和预言机分离作为潜在量子优势的证据。