Hamiltonian locality testing and certification do not achieve the Heisenberg limit

技术摘要：哈密顿量局部性测试与认证无法达到海森堡极限

问题陈述
本文探讨了在特定访问模型下，哈密顿量学习与测试的基本极限。在该模型中，算法可以访问时间演化算符 $U_H(t) = e^{-itH}$（其中 $t > 0$），但无法访问逆算符 $U_H(-t)$。目标是确定解决特定问题所需的总演化时间缩放比例，且精度为 $\epsilon$。

研究了两个主要问题：

1. 哈密顿量局部性测试（Hamiltonian Locality Testing）： 判断一个未知的 $n$ 量子比特哈密顿量 $H$ 是 $k$-局部的，还是距离所有 $k$-局部哈密顿量有 $\epsilon$ 远（距离通过归一化 Frobenius 范数衡量）。
2. 哈密顿量认证（Hamiltonian Certification）： 判断一个未知的哈密顿量 $H$ 是否等于已知的目标哈密顿量 $H_0$，或者距离它有 $\epsilon$ 远。

此外，本文还研究了连续时间查询模型下的量子振幅估计（Quantum Amplitude Estimation），即在无法获取逆幺正算符的情况下，是否可以达到海森堡极限（缩放比例为 $1/\epsilon$）。

方法论
作者通过证明区分零哈密顿量（$H=0$）与一种精心构造的随机对角哈密顿量系综的难度，建立了下界。其核心技术贡献在于将**连续时间对抗者方法（continuous-time adversary method）**应用于仅限正向的哈密顿量演化。

关键方法步骤包括：

• 随机系综构造： 作者构造了一个随机对角哈密顿量族 $H = \sum_{x} h_x |x\rangle\langle x|$，其中系数 $h_x$ 是从特定分布 $\nu_\epsilon$ 中独立抽取的随机变量。该分布经过精心设计（使用作用在辅助空间上的算符 $J_\epsilon$），以满足特定的矩条件（$E[h_x]=0, E[h_x^2]=\epsilon^2$），同时确保该系综难以与零哈密顿量区分开来。
• 随机性的纯化（Purification of Randomness）： 为了应用对抗者方法，将输入哈密顿量的随机性纯化到一个额外的输入寄存器中。这使得算法的演化可以被追踪为单一纯态 $|\Psi_F(t)\rangle$（针对随机系综）与 $|\Psi_Z(t)\rangle$（针对零哈密顿量）。
• 进度函数（Progress Function）： 定义了一个进度函数 $P(t)$ 来量化两种情况之间的可区分度。其构造如下：
  $$P(t) = 1 - \text{Re}\langle \Psi_Z(t) | \Psi_F(t) \rangle + \frac{1}{4}\langle \Psi_F(t) | (I_A \otimes G) | \Psi_F(t) \rangle$$
  其中 $G$ 是作用在输入寄存器上的一个精心选择的非负算符。
• 边界判定： 作者证明，对于任何成功的算法，最终进度 $P(t_f)$ 必须为 $\Omega(1)$。然而，他们表明进度的增长速率受限于查询强度 $\lambda(t)$ 和精度参数 $\epsilon$：$\frac{d}{dt}P(t) \leq O(\epsilon^2 \lambda(t))$。
• 积分： 通过结合总进度的要求与增长率的边界，得出了总演化时间 $T = \int \lambda(t) dt$ 的下界。

主要贡献与结果
本文确立了以下下界，这些下界均要求 $\Omega(1/\epsilon^2)$ 的总演化时间，从而在仅限正向演化访问的模型下，排除了实现海森堡极限（$1/\epsilon$）的可能性：

1. 局部性测试： 测试一个哈密顿量是 $k$-局部的还是距离 $k$-局部哈密顿量有 $\epsilon$ 远，需要 $\Omega(1/\epsilon^2)$ 的总演化时间。这与 Kallaugher 和 Liang (TQC'25) 提供的上界相匹配。
2. 哈密顿量认证： 认证一个未知哈密顿量是否等于目标 $H_0$ 或距离其有 $\epsilon$ 远，需要 $\Omega(1/\epsilon^2)$ 的总演化时间。这一结果专门回应了关于无结构哈密顿量是否可能实现海森堡极限缩放的问题，给出了否定的回答。这与 Sinha 和 Tong (2025) 的上界相匹配。
3. 振幅估计： 在仅使用对幺正算符 $U = e^{-iH}$ 的正向查询的情况下，估计具有 $\epsilon$ 加性误差的振幅，需要 $\Omega(1/\epsilon^2)$ 的总演化时间。这恢复了 Tang 和 Wright (QIP'26) 在连续时间查询模型下的结果。

意义与主张
作者声称，这些是首个针对自然哈密顿量学习与测试问题，在标准正向演化访问模型下排除海森堡极限缩放的下界。

• 最优性： 结果被证明是优的，因为它们与局部性测试和认证的现有上界相匹配。
• 逆算符的必要性： 本研究表明，海森堡极限并非在哈密顿量学习中普遍可达；具体而言，要在认证和无结构哈密顿量局部性测试中实现 $1/\epsilon$ 缩放，可能需要访问逆时间演化算符，而这在所研究的模型中是不可用的。
• 技术新颖性： 将连续时间对抗者方法应用于正向哈密顿量演化的过程，被视为一种具有独立价值的技术，可能导致其他量子查询设置下的新下界。

假设与局限性
这些下界是在精度参数 $\epsilon$ 相对于系统规模 $n$ 不呈指数级微小（具体为 $(1/\epsilon) = 2^{O(n)}$）的假设下成立的。作者指出，由于希尔伯特空间的有限维度，对于固定的 $n$，$\Omega(1/\epsilon^2)$ 的下界无法对任意小的 $\epsilon$ 成立，因为在 $O(2^n/\epsilon)$ 时间内即可完成完整学习。研究结果适用于算符范数 $\|H\|_{op} \leq 1$ 的哈密顿量。