Oracle Separations in the Fourier Hierarchy

技术摘要：傅里叶层级中的 Oracle 分离

问题陈述
由 Shi (2005) 引入的傅里叶层级 ($FH_k$) 根据量子计算所使用的全局 Hadamard 层（傅里叶深度）的数量对计算进行分类。在这些层之间，电路执行保持基态不变的操作（置换和相位附加），但无法创建新的叠加态。该层级定义为 $FH_0 \subseteq FH_1 \subseteq FH_2 \subseteq \dots$。其中 $FH_0 = P$ 且 $FH_1 = BPP$（在标准查询模型中），而 $FH_2$ 包含因数分解和 Simon 问题。然而，增加一个 Hadamard 层是否会严格增加计算能力，一直是一个悬而未决的问题。Shi 曾猜想对于所有 $k \ge 0$，都有 $FH_k \subsetneq FH_{k+1}$，并要求将寻找相邻层级之间的 Oracle 分离作为第一步。在此项工作之前，对于任何 $k \ge 2$ 的层级都未知的分离关系。

方法论
作者通过在两种不同的查询模型中为每个常数 $k \ge 2$ 构建 Oracle 分离来解决这一问题：

1. 相位查询模型 (Phase-query model)： 查询将基态乘以一个符号（$F(x)|x\rangle \to (-1)^{F(x)}|x\rangle$）。
2. 标准查询模型 (Standard-query model)： 查询将答案写入寄存器（$|y\rangle|b\rangle \to |y\rangle|b \oplus F(y)\rangle$）。

该方法的核心在于利用 Forrelation 问题，特别是其 $K$ 重推广版本，该问题衡量了在交替进行傅里叶变换的布尔函数链之间的相关性。作者利用了以下结构性见解和工具：

• 奇数与偶数 Forrelation： 作者利用了 Forrelation 阶数 $K$ 的奇偶性。他们证明了 $(2k-1)$ 阶 Forrelation（奇数阶）可以通过一个控制比特干涉测试（或 SWAP 测试）在傅里叶深度 $k+1$ 下解决，该测试将计算分为两个深度为 $k$ 的部分。相反，$(2k-2)$ 阶 Forrelation（偶数阶）可以在深度 $k$ 下解决。
• 通过自适应性模拟深度（相位模型）： 一个关键的结构性引理表明，相位查询模型中任何具有 $q$ 次查询的 $FH_k$ 电路，都可以被一个具有 $k-1$ 轮自适应性和每轮 $q$ 次并行查询的量子查询算法精确模拟。这使得作者能够引入文献中关于有界轮数算法（Girish et al., 2024）的下界。
• 傅里叶增长界限： 下界依赖于接受概率的傅里叶权重。
  • 对于相位模型，模拟引理将问题简化为对 $k-1$ 轮算法的傅里叶增长进行限制。作者应用了 Bansal–Sinha 准则，证明了深度为 $k$ 的电路的傅里叶权重增长过慢，以至于无法区分结构化的 Forrelation 分布与均匀分布，当阶数 $K = 2k-1$ 时。
  • 对于标准模型，由于标准查询允许基于先前答案进行自适应分支，轮数模拟失效。作者开发了一种新技术：通过决策树的叶节点对每个保持基态不变的块进行分解。这产生了一个直接针对标准查询电路的傅里叶增长界限，该界限比相位模型界限略弱（对 $k$ 呈指数依赖），因此需要更高的 Forrelation 阶数（$K = 2k+1$）来实现分离。
• Oracle 构建： 为了从分布间隙转向最坏情况下的 Oracle 分离，作者使用直接积构造（多个 Forrelation 实例的 OR）来放大成功概率，随后使用混合论证（hybrid argument）和对角化法来构建一个单一的 Oracle 系列 $O$，该系列能击败所有一致的 $FH_k$ 系列，同时能被 $FH_{k+1}$ 电路判定。

核心贡献与结果

1. 相邻层级分离（相位模型）： 对于每个常数 $k \ge 2$，存在一个 Oracle $O$，使得 $FH^O_k \subsetneq FH^O_{k+1}$。分离问题是 $(2k-1)$ 阶 Forrelation 实例的 OR。它可以在深度 $k+1$ 下以 $O_k(1)$ 次查询解决，但在任何深度为 $k$ 且进行高达 $N^{c_k}$ 次查询的电路下均无法解决（其中 $c_k = \Theta(1/k^2)$）。
2. 相邻层级分离（标准模型）： 类似地，对于每个 $k \ge 2$，存在一个 Oracle $O$，使得 $FH^O_{k,std} \subsetneq FH^O_{k+1,std}$。此处的分离问题是 $(2k+1)$ 阶 Forrelation 实例的 OR。由于标准查询的自适应性，其下界需要不同的增长分析。
3. 查询模型的分离： 本文证明了在相同的傅里叶深度下，标准查询模型比相位查询模型严格更强大。具体而言，对于每个 $k \ge 2$，都有 $FH^O_k \subsetneq FH^O_{k,std}$。分离问题是 $(2k-1)$ 阶 Forrelation 的 OR，标准深度 $k$ 可以通过读取中间答案位来解决，但相位深度 $k$ 则不能。
4. 与 BQP 的分离： 作者表明，所有有界傅里叶深度层级的并集相对于某个 Oracle 严格包含在 $BQP$ 之中。具体而言，阶数为 $K = \Theta(\log n)$ 的 Forrelation 在 $BQP$ 中，但需要高达 $\approx \frac{1}{4} \log_2 n$ 的傅里叶深度才能解决，这意味着 $\left(\bigcup_k FH_k\right)^O \subsetneq BQP^O$。
5. 非相对化性： 本文证明了相邻层级问题并不具有相对化性质。虽然上述分离在特定 Oracle 下成立，但存在一个 PSPACE 完全的 Oracle，在该 Oracle 相对于下，对于所有 $k \ge 2$，都有 $FH_k = PSPACE$。因此，在非相对化设置下解决 Shi 的猜想需要非相对化技术。

意义与主张
本文声称解决了 Shi 关于所有 $k \ge 2$ 层级的“相邻层级问题”，这一问题自 2005 年以来一直悬而未决。其意义在于：

• 结构特征化： 建立了傅里叶深度与查询自适应性之间的精确联系（具体而言，相位查询深度 $k$ 等价于 $k-1$ 轮并行查询）。
• 方法论进步： 引入了决策树分解技术，用于限制自适应标准查询电路的傅里叶增长，将傅里叶权重方法扩展到了非自适应设置之外。
• 层级定位： 将傅里叶层级定位在经典类（$P, BPP, PH$）以及全量子能力（$BQP$）之间。它确认了第二层（$FH_2$）相对于 Oracle 已经超过了多项式层级，然而整个层级仍然严格弱于 $BQP$。
• 对非相对化猜想的审慎态度： 作者明确指出，其结果并未解决 Shi 的非相对化猜想（即在没有 Oracle 的情况下 $FH_k \neq FH_{k+1}$），因为存在导致层级坍缩的 Oracle，这证明了相对化技术不足以实现此目的。

这项工作提供了傅里叶层级的完整 Oracle 理论图景，证实了其在每一层级的严格性，并阐明了 Hadamard 层作为量子干涉资源的效力。