Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances

技术摘要：在物理驱动距离下学习稀疏量子哈密顿量的近乎最优算法

1. 问题陈述

本文探讨了学习一个未知的 $n$ 位量子比特哈密顿量 $H$ 的问题，该哈密顿量在泡利基底（Pauli basis）下是 $s$-稀疏的（即其非零泡利系数最多有 $s$ 个）。学习算法通过其时间演化算符 $U(t) = e^{-iHt}$ 来获取哈密顿量的信息。

作者指出了现有文献中的两个关键空白：

1. 缺乏最优性： 许多现有算法缺乏与之匹配的下界，因此无法确定其是否是最优的。
2. 物理意义模糊的度量： 先前的研究通常使用在数学上便于处理的距离（如泡利系数的 $\ell_\infty$ 或 $\ell_2$ 范数）来衡量估计质量，而这些距离缺乏关于底层量子系统可区分性的直接物理阐释。

核心问题是：在具有物理意义的最坏情况距离下，哈密顿量学习的最优复杂度是多少？

2. 方法论与技术

A. 物理驱动的距离
作者引入了两种新的距离度量，用于量化基于操作场景的哈密顿量可区分性：

1. 时间约束距离 ($d_T$)： 定义为两个哈密顿量的时演通道在有限时间区间 $[0, T]$ 内的最大钻石距离（diamond distance）。它量化了通过制备态、演化时间 $t \le T$ 并进行测量来区分哈密顿量的最佳概率。
2. 温度约束距离 ($d_B$)： 定义为两个哈密顿量的吉布斯态（Gibias states/热态）在有限逆温度范围 $[0, B]$ 内的最大迹距离（trace distance）。它通过热态来量化可区分性。

作者证明了在时间约束距离下的学习等价于在算符范数（operator norm, $\|H_1 - H_2\|_{op}$）下的学习，并且在算符范数下的上界意味着在温度约束距离下的上界。

B. 隔离技术（受 Valiant-Vazirani 定理启发）
一个核心技术贡献是受 Valiant-Vazirani 定理启发的创新 隔离技术（isolation technique）。该技术允许算法即使在完整的泡利支撑（Pauli support）未知的情况下，也能“隔离”出稀疏哈密顿量的单个泡利系数。

• 机制： 通过随机选择一组泡利算符 $Q_1, \dots, Q_r$，并利用共轭构造一个修改后的哈密顿量 $H_{Q_1, \dots, Q_r}$，算法确保以 $\Omega(1/s)$ 的概率使得只有一个特定的目标泡利项 $P$ 与所有 $Q_i$ 对易。
• 结果： 这有效地过滤了哈密顿量的演化，从而隔离出单个泡利项 $e^{-ith_P P}$ 的动力学过程，进而实现高效的采样与估计。

C. 算法结构
学习算法分为两个阶段：

1. 有效支撑学习： 利用隔离技术和泡利采样，算法识别出一个大小为 $\tilde{O}(s)$ 的集合 $\mathcal{P}$，该集合包含了 $H$ 的 $\epsilon$-有效支撑（即所有满足 $|h_P| \ge \epsilon$ 的泡利项）。
2. 参数估计： 一旦识别出支撑，算法再次使用隔离技术，将每个泡利系数 $h_P$ 单独估计到误差 $\epsilon$ 以内。

3. 关键结果

上界（算法性能）
作者提出了一种学习具有有界算符范数的 $s$-稀疏哈密顿量的算法：

• 实验次数： $\tilde{O}(s \log(1/\epsilon))$ 次实验。
• 总演化时间： $\tilde{O}(s^2/\epsilon)$。
• 距离： 该算法在时间约束和温度约束距离下均能实现 $\epsilon$-学习。
• 鲁棒性： 该算法对常数级别的状态制备与测量（SPAM）误差具有鲁棒性，且不需要辅助量子比特（通过对标准泡利采样的算法进行修改，去除了对辅助量子比特的需求）。
• 海森堡定标（Heisenberg Scaling）： 总演化时间随 $1/\epsilon$ 缩放，达到了海森堡极限，这在 $\epsilon$ 的依赖关系上是最优的。

下界（最优性）
作者为任何使用 $O(n)$ 个辅助量子比特的学习算法建立了基本限制：

• 实验次数下界： $\Omega((s/n) \log(1/\epsilon) + s)$。这表明该算法对 $s$ 和 $\log(1/\epsilon)$ 的依赖关系是近乎最优的。
• 时间下界： 对于算符范数学习，时间下界为 $\Omega(\sqrt{s}/\epsilon)$。这表明该算法的上界 $\tilde{O}(s^2/\epsilon)$ 与理论下界之间存在差距，说明虽然实验次数是近乎最优的，但总演化时间的缩放尚未达到最优。

中间改进
作为副产品，本文提供了一种学习 $s$-稀疏哈密顿量中每一个泡利系数的算法，其实验次数为 $\tilde{O}(s \log(1/\epsilon))$，总时间为 $\tilde{O}(s/\epsilon)$。这改进了近期一些同期工作（如 [Zha25], [ADE25], [HMG+25], [ST25]）中对 $s$ 和 $1/\epsilon$ 较高的多项式依赖关系。

4. 重要性与主张

本文声称提供了第一个在具有物理意义的距离下，在实验次数上达到近乎最优的哈密顿量学习结果。

• 物理相关性： 通过将度量从抽象的系数范数转向时间约束钻石距离和温度约束迹距离，研究结果直接关联到实验能力（有限的演化时间和有限的温度）。
• 最优性： 本研究确立了所需的实验次数是近乎最优的，在忽略对数因子的情况下与推导出的下界相匹配。
• 通用性： 与许多先前的工作不同，该算法既不假设先验的泡利支撑知识，也不要求哈密顿量具有局部性或几何结构；它仅假设稀疏性。
• 理论桥梁： 本文严谨地将算符范数（一种标准的数学工具）与物理可区分性度量联系起来，证明了在有限的时间和温度预算下，在算符范数下学习足以实现物理距离下的学习。

作者承认，虽然实验次数是近乎最优的，但总演化时间的缩放（$\tilde{O}(s^2/\epsilon)$）仍有提升空间，因为下界为 $\Omega(\sqrt{s}/\epsilon)$。他们指出，寻找最优演化时间是未来的主要研究方向。