Optimal Separations Between Randomized and Quantum Query Complexity under Permutation Symmetry

技术摘要：置换对称性下随机化与量子查询复杂度之间的最优分离

1. 问题陈述

本文研究了具有**置换对称性（permutation symmetry）**的问题中量子加速的极限。具体而言，它探讨了以下两类问题的随机化查询复杂度（$R_\varepsilon(f)$）与量子查询复杂度（$Q_\varepsilon(f)$）之间的关系：

1. 置换不变函数（Permutation-invariant functions）： 函数 $f: D \subseteq A^N \to \{0,1\}$，其中置换输入位置会保持定义域和函数值不变。
2. 图与超图属性（Graph and hypergraph properties）： 定义在图或 $k$-均匀超图上的布尔函数，其中重标记顶点会保持承诺（promise）和答案不变。

核心问题是：对于这些对称问题， $R(f)$ 与 $Q(f)$ 之间可能的最大分离度是多少？ 虽然无结构搜索提供了二次分离（$R = \Theta(Q^2)$），但以往的研究表明，对于对称问题，这种分离可能更大（例如三次或更高次）。本研究旨在收紧这些上界并建立匹配的下界。

2. 研究方法

作者结合使用压缩预言机技术（compressed oracle techniques）、**剩余展开（residual expansions）以及结构化编码（structural encoding）**来推导其结果。

上界（模拟）：
核心技术是通过一个仅查询输入的一个小随机样本的经典随机化算法来模拟量子算法。

• 压缩预言机与采样： 基于 Zhandry 的压缩预言机和 Carolan 的压缩置换预言机，作者将一个完整的随机置换替换为一个存储在相干数据库中的“压缩”版本。随后，他们将该数据库的范围限制为一个大小为 $s = O(T^2)$ 的小随机样本 $S$（其中 $T$ 是量子查询次数）。
• 精确范数公式（Exact Norm Formula）： 一个关键的技术创新是针对将数据库范围限制为样本时所引入误差的精确范数公式。这使得他们能够界定采样引入的状态误差。
• 剩余展开： 为了处理量子算法具有微小成功偏差（不仅仅是常数误差）的情况，作者构造了一个“剩余恒等式（residual identity）”。该式将理想量子期望与采样后的经典期望之差表示为另一个算法带符号输出期望的常数倍（$\lambda = 1/8$）。通过迭代此恒等式，他们生成了一系列几何级数的后处理函数，从而使模拟能够在不增加样本量的情况下保留任意小的偏差。
• 超图编译： 对于图和超图属性，该方法通过编译超边查询进行了扩展。单个 $k$ 个顶点的超边查询被编译为 $2k$ 个辅助置换查询。采样 $O(T^2)$ 个顶点即可实现对整个诱导子图的模拟，查询量为 $O(T^{2k})$。

下界（分离）：
为了证明上界的紧致性，作者构造了显式的承诺问题族，这些问题存在于超图上。

• 编码： 他们将一个任意的 $m$ 位承诺问题编码到一个具有 $N = \Theta(m^{1/k})$ 个顶点的无色、连通、简单 $k$-均匀超图中。
• 结构恢复： 该编码使用“数据顶点”（存储源比特）和“地址顶点”（形成刚性树结构）。超图的结构允许算法利用振幅放大技术，在面对任意顶点重标记的情况下，相干地恢复任何数据顶点的地址。
• 源问题： 他们将此编码应用于 $\ell$-Forrelation 问题（Bansal 和 Sinha），并选择随输入规模缓慢增加的阶数 $\ell$。该源问题具有多项式对数级的量子复杂度，但具有近线性的随机化复杂度。

3. 核心贡献与结果

定理 1.1（置换不变函数）：
对于任意有限字母表上的置换不变函数及误差 $\epsilon \in [1/6, 1/2)$：
$$R_\epsilon(f) = O(Q_\epsilon(f)^2)$$
这改进了 Chailloux (2019) 提出的先前三次界限（$O(Q^3)$）。该界限是紧致的，匹配了无结构搜索的二次分离。

定理 1.2（图与超图属性）：
对于 $k$-均匀超图属性（其中 $k \ge 2$ 固定）且 $\epsilon \in [1/6, 1/2)$：
$$R_\epsilon(f) = O_k(Q_\epsilon(f)^{2k})$$

• 对于图（$k=2$），这将其之前的六次界限（$O(Q^6)$）改进为四次界限（$O(Q^4)$）。
• 对于一般的 $k$，这将其之前的 $O(Q^{3k})$ 改进为 $O(Q^{2k})$。

定理 1.3（界限的紧致性）：
作者构造了显式的 $k$-均匀超图属性族 $\{F_N\}$，使得：
$$R_{1/3}(F_N) \ge N^{k-o(1)} \quad \text{且} \quad Q_{1/3}(F_N) \le N^{1/2+o(1)}$$
由于 $Q \approx N^{1/2}$，这意味着 $R \approx Q^{2k-o(1)}$，证明了定理 1.2 中的上界是近乎紧致的。

4. 意义与主张

本文声称解决了关于对称问题中随机化与量子查询复杂度之间最优分离度的疑问：

• 字符串的最优性： 它确定了置换不变性不会允许超过二次的分离，从而解决了关于这些函数的 $R(f) = O(Q(f)^2)$ 的猜想。
• 图/超图的最优性： 它证明了图和超图属性中固有的对称性（顶点重标记）将量子优势限制在指数上的 $2k$ 倍以内，而非此前怀疑的 $3k$ 或更高。
• 方法论进展： 本文引入了一个稳健的框架，通过小样本和剩余展开在对称输入上模拟量子算法，即使在偏差极小时也能保持成功概率。该技术可适用于比本文分析的具体情况更广泛的一类对称问题。

作者强调，其结果对于置换不变函数是紧致的，对于图和超图属性则是近乎紧致的，两者之间的差距仅为一个次多项式因子（$N^{o(1)}$）。这项工作依赖于置换对称性的“无结构”特性来限制量子加速，这与 Simon 或周期查找等通过特定代数结构实现指数级分离的问题形成了对比。