技术摘要：交换局部哈密顿量问题：反对 BQP-硬性的相对化证据

1. 问题陈述与背景

交换局部哈密顿量 (Commuting Local Hamiltonian, CLH) 问题询问：在一个所有局部项都两两交换的局部哈密顿量中，其基态能量是否低于阈值 $\alpha$ 或高于 $\beta$。虽然一般的局部哈密顿量问题是 QMA-完全的，但这种交换变体的复杂度仍然是量子计算复杂度理论中的一个核心开放问题。

先前的研究已经证明，对于特定的交换哈密顿量族（例如 2-local、某些 3-local 或特定晶格上的哈密顿量），该问题属于 NP。然而，目前还没有正式的证据能够排除一般 CLH 问题是 QMA-完全 的可能性。

QIMA（具有交换单元的量子交互式 Merlin-Arthur）类由 Bostanci 和 Hwang 引入，旨在捕捉其局部测试单元为相互交换的反射算子的量子验证器的能力。CLH 问题是 QIMA 的完全问题。因此，CLH 是否为 QMA-完全的问题，等价于询问 QIMA = QMA 是否成立。

本文在相对化设置下研究了 QIMA 与 BQP（有界误差量子多项式时间）之间的关系。具体而言，本文试图确定是否存在一个经典预言机 $O$，使得 BQP$^O \not\subseteq$ QIMA$^O$。一个正向结果将为“一般 CLH 问题是 BQP-硬的”这一可能性提供相对化证据，进而反对其为 QMA-完全的可能性。

2. 方法论与定义

2.1 预言机模型 QIMA$^O$

作者定义了一个相对化的 QIMA 模型，记作 QIMA$^O$，并施加了特定的约束，以确保该模型仍然是 QMA$^O$ 的非平凡限制：

• 验证器结构： 在输入 $x$ 时，验证器执行经典预处理（对 $O$ 进行自适应查询）以生成一组作用在量子见证（witness）上的“单元” $W_1^O, \dots, W_m^O$。
• 交换性： 在承诺的实例中，所有单元必须两两交换：$[W_i^O, W_j^O] = 0$。
• 反射要求： 至关重要的一点是，任何包含至少一个量子预言机查询的单元 $W_j^O$ 必须是一个精确反射（即 $(W_j^O)^\dagger = W_j^O$ 且 $(W_j^O)^2 = I$）。不含预言机的单元可以是任意幺正算子。
• 验证： 验证器使用 Hadamard 测试来检查见证是否处于每个单元的 $+1$ 本征空间。
• 无可信辅助比特： 验证器除了用于 Hadamard 测试的新鲜控制比特外，没有可信的工作空间。

作者认为 反射要求 是必不可少的。他们表明，如果将此要求放宽为允许任意交换单元（即使是接近反射的单元）或允许可信的辅助比特，该类将坍缩回 QMA$^O$。

2.2 Forrelation 问题

分离过程基于 Forrelation 问题，该问题由 Aaronson 定义。给定两个布尔函数 $f, g: \{0,1\}^n \to \{-1, +1\}$ 的预言机访问，任务是区分以下两种情况：

• 是 (Yes)： $f$ 与 $g$ 的傅里叶变换高度相关（$\Phi(f,g) \ge \alpha$）。
• 否 (No)： 相关性很小（$|\Phi(f,g)| \le \beta$）。

Forrelation 可以通过一个具有常数个量子查询的 BQP 算法解决。本文旨在证明，对于 QIMA$^O$ 验证器，解决 Forrelation 问题需要指数级的查询次数。

3. 核心贡献与结果

3.1 预言机分离：BQP$^O \not\subseteq$ QIMA$^O$

主要结果是构造了一个经典预言机 $O$，使得 BQP$^O \not\subseteq$ QIMA$^O$。这是通过证明 Forrelation 问题相对于 QIMA$^O$ 验证器的指数级查询下界来实现的。

定理 1.7（非正式）： 任何针对所有承诺对 $(f, g)$ 判定 Forrelation 的 QIMA$^O$ 验证器必须满足：
$$C(n) + T(n) \ge \beta 2^n - O(1)$$
其中 $C(n)$ 是经典预处理查询次数，$T(n)$ 是总量子预言机查询次数。

证明简述：

1. 多项式方法： 验证器的接受概率可以表示为关于预言机真值表条目的多项式。
2. 交换性与反射： 由于包含预了机的单元是精确反射且相互交换，它们的组合接受算子是正交投影算子的乘积。这使得作者可以定义一个单一的投影算子 $P_f$，代表所有接受子空间的交集。
3. 次数界限： 代表接受概率的多项式的次数由总量子查询数 $T(n)$ 限制。
4. 完美 Forrelation 对： 作者利用了“完美 Forrelation 对”（bent 函数），其中 $\Phi(g, h) = 1$。他们展示了通过 $k$ 个比特扰动 $h$ 会使 Forrelation 值线性变化：$\Phi(g, f) = 1 - 2k/N$。
5. 对称化： 通过固定经典转录（transcript）并在与固定汉明距离的函数上进行平均，他们构造了一个一元多项式 $q(k)$。
6. 根计数： 多项式 $q(k)$ 对于所有的“否”实例（一个大的 $k$ 范围）必须为零，而对于“是”实例（$k=0$）必须非零。一个非零多项式的根的数量不能超过其次数，从而迫使次数（以及查询计数）为指数级。

3.2 分离的鲁棒性

论文证明，即使在对模型的轻微放宽下，这种分离仍然成立：

• 可忽略偏差： 如果包含预言机的单元被允许在算子范数意义上与精确反射仅有可忽略的距离，该类仍为 QIMA$^O$，且下界依然成立。
• 受限地址支持： 作者将下界扩展到不是反射但仅进行单次查询的单元，前提是围绕查询的无预言机电路仅在少量的地址比特（$k$）上产生非平凡作用。如果 $n - k(n) = \omega(\log n)$，则查询下界仍然是超多项式的。

3.3 模型的紧致性（坍缩结果）

为了证明 QIMA$^O$ 定义中特定约束的合理性，作者证明了放宽这些约束会导致该类坍缩至 QMA$^O$：

• 逆多项式偏差： 如果允许单元与反射的距离在逆多项式范围内（而非可忽略），该类将坍缩至 QMA$^O$。这是通过使用一种变体的 Marriott-Watros 放大机制（amplification gadget）实现的，通过构造一个能模拟 QMA 验证器的单一单元来完成。
• 无反射的单次查询： 如果完全移除反射要求，但将单元限制为单次查询，该类仍会坍缩至 QMA$^O$。这使用了循环时钟构造（类似于 Feynman-Kitaev），将多查询模拟编码进单次查询中。
• 可信辅助比特： 允许验证器拥有一个可信的辅助比特（初始化为 $|0\rangle$）会将 QIMA 变为 QMA，并将 QIMA$^O$ 变为 QMA$^O$。这依赖于已知为 QMA-完全的“钉定交换局部哈密顿量 (Pinned Commuting Local Hamiltonian)”问题。

4. 意义与主张

本文声称提供了反对一般 CLH 问题是 BQP-硬的可能性的相对化证据。由于 BQP 包含在 QMA 中，如果 CLH 是 BQP-硬的，则意味着 QMA 具有极强的结构性质。$BQP^O \not\subseteq QIMA^O$ 的分离表明，QIMA 中的交换约束（以及由此衍生的 CLH）是一个显著的限制，它阻止了该类捕获 BQP 的全部能力，即使在存在预言机的情况下也是如此。

此外，这项工作阐明了 QIMA 定义的紧致性。作者认为，交换性、预言机查询的反射要求以及缺乏可信辅助比特这三个条件的特定组合，对于定义一个严格弱于 QMA 的类是必要的。放宽其中任何一个条件都会立即恢复 QMA 的全部能力，这表明 QIMA 的“量子性”是非常脆弱的，它精确地依赖于这些结构性约束。

这些结果并未解决 CLH 是否为 QMA-完全的非相对化问题，但它们确立了：任何关于此类完全性的证明都必须使用非相对化技术，因为该命题在所构造的预言机下是不成立的。