2025-11-18T06:07:11.995553

Optimal learning of quantum Hamiltonians from high-temperature Gibbs states

Haah, Kothari, Tang
We study the problem of learning a Hamiltonian $H$ to precision $\varepsilon$, supposing we are given copies of its Gibbs state $ρ=\exp(-βH)/\operatorname{Tr}(\exp(-βH))$ at a known inverse temperature $β$. Anshu, Arunachalam, Kuwahara, and Soleimanifar (Nature Physics, 2021, arXiv:2004.07266) recently studied the sample complexity (number of copies of $ρ$ needed) of this problem for geometrically local $N$-qubit Hamiltonians. In the high-temperature (low $β$) regime, their algorithm has sample complexity poly$(N, 1/β,1/\varepsilon)$ and can be implemented with polynomial, but suboptimal, time complexity. In this paper, we study the same question for a more general class of Hamiltonians. We show how to learn the coefficients of a Hamiltonian to error $\varepsilon$ with sample complexity $S = O(\log N/(β\varepsilon)^{2})$ and time complexity linear in the sample size, $O(S N)$. Furthermore, we prove a matching lower bound showing that our algorithm's sample complexity is optimal, and hence our time complexity is also optimal. In the appendix, we show that virtually the same algorithm can be used to learn $H$ from a real-time evolution unitary $e^{-it H}$ in a small $t$ regime with similar sample and time complexity.
academic

Optimal learning of quantum Hamiltonians from high-temperature Gibbs states

基本信息

  • 论文ID: 2108.04842
  • 标题: Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
  • 作者: Jeongwan Haah (Microsoft Quantum), Robin Kothari (Microsoft Quantum), Ewin Tang (University of Washington)
  • 分类: quant-ph cs.DS cs.LG
  • 发表时间: March 17, 2023 (arXiv版本)
  • 论文链接: https://arxiv.org/abs/2108.04842

摘要

本文研究从已知逆温度β的Gibbs态ρ=exp(-βH)/Tr(exp(-βH))的副本中学习哈密顿量H到精度ε的问题。在高温(低β)区域，作者提出了一种对于低交集哈密顿量类别的学习算法，实现了样本复杂度S=O(logN/(βε)²)和时间复杂度O(SN)，并证明了匹配的下界，表明算法在样本和时间复杂度上都是最优的。

研究背景与动机

问题定义

哈密顿量学习问题是量子多体物理和机器学习交叉领域的重要问题。给定一个未知哈密顿量H的热平衡态(Gibbs态)的多个副本，目标是学习哈密顿量的系数。这个问题在物理上有直接的动机：哈密顿量描述了量子系统的相互作用和时间演化，而Gibbs态是系统在给定温度下与环境达到热平衡时的状态。

研究意义

  1. 物理意义：理解量子系统的基本性质，预测其行为
  2. 计算意义：这是经典马尔可夫随机场学习问题的量子推广
  3. 理论意义：连接了量子信息理论和统计学习理论

现有方法局限性

  • Anshu等人(AAKS21)的工作针对几何局域哈密顿量，样本复杂度为O(2^{poly(β)}N²logN/(β^c ε²))，在β和N的依赖性上都不够优化
  • 时间复杂度方面缺乏明确的分析和优化
  • 仅适用于几何局域的哈密顿量类别

核心贡献

  1. 最优算法：提出了在高温区域学习低交集哈密顿量的最优算法，样本复杂度O(logN/(βε)²)，时间复杂度O(N logN/(βε)²)
  2. 匹配下界：证明了样本复杂度的匹配下界Ω(exp(β)logN/(β²ε²))，在高温区域达到最优
  3. 更广泛的哈密顿量类别：扩展到低交集哈密顿量，这比几何局域哈密顿量更一般
  4. 理论分析：改进了对数配分函数的强凸性分析，将强凸性参数改进到β²/2
  5. 实时演化扩展：证明了相同算法可用于从实时演化酉算子e^{-itH}学习哈密顿量

方法详解

任务定义

考虑N量子比特系统的哈密顿量H = Σ_^M λ_a E_a，其中：

  • E_a是已知的不同的非恒等泡利算子
  • λ_a ∈ -1,1是待学习的系数
  • 哈密顿量是低交集的：每个算子作用在常数个量子比特上，且每个算子只与常数个其他算子的支撑有非平凡交集

目标：从Gibbs态ρ = exp(-βH)/Tr(exp(-βH))的副本中学习系数{λ_a}到加性误差ε。

核心技术框架

1. 簇展开(Cluster Expansion)

利用统计力学中的簇展开技术，将期望值⟨E_a⟩展开为β的泰勒级数：

⟨E_a⟩(x) = β p₁^{(a)}(x) + β² p₂^{(a)}(x) + β³ p₃^{(a)}(x) + ...

其中p_m^{(a)}是m次齐次多项式，且p₁^{(a)}(x) = -x_a。

2. 算法流程

步骤1：估计期望值

  • 对每个泡利算子E_a，估计⟨E_a⟩到精度βε
  • 利用对偶交互图的着色，并行测量不重叠的算子
  • 样本复杂度：O(d/(β²ε²)log(M/δ))

步骤2：牛顿-拉普森方法 定义函数F_a(x) = Σ_^m β^k p_k^{(a)}(x) - Ê_a，目标是找到F(x)足够小的x。

使用修改的牛顿-拉普森迭代：

x^{(t+1)} = Proj_{[-1,1]^M}[x^{(t)} + β^{-1} Σ_{k=0}^{K-1} (I + β^{-1}J(x^{(t)}))^k F(x^{(t)})]

3. 关键技术创新

簇导数计算：

  • 设计了精确计算簇导数D_W L的算法
  • 时间复杂度：(8m + L)poly(m)
  • 利用泡利矩阵的整数性质实现精确算术

雅可比矩阵分析：

  • 证明了雅可比矩阵J具有"带对角"性质
  • 如果b和a距离为k，则J_的量级为β^{k+1}
  • 这使得J接近-βI，从而J^{-1}易于近似

收敛性分析

临界温度条件

算法在β < β_c时工作，其中β_c = (25e^6(d+1)^{10})^{-1}仅依赖于对偶交互图的度数d。

误差传播

通过多元中值定理分析误差传播：

|x_a - λ_a| ≤ ||J^{-1}||_{∞→∞}(||F(x)||_∞ + ||F(λ)||_∞) ≤ 4ε

实验设置

理论验证

论文主要是理论性工作，通过数学证明验证算法的正确性和最优性，而非实证实验。

复杂度分析

  • 样本复杂度：O(logN/(βε)²) (ℓ_∞误差), O(N/(βε)²) (ℓ_2误差)
  • 时间复杂度：O(N logN/(βε)²) (ℓ_∞), O(N²/(βε)²) (ℓ_2)
  • 预处理时间：O(LMd log d)用于构建对偶交互图

实验结果

主要理论结果

上界定理(Theorem 1.1)

对于低交集哈密顿量，在β < β_c条件下：

  • ℓ_∞误差ε：样本复杂度O(1/(β²ε²) log(N/δ))
  • ℓ_2误差ε：样本复杂度O(N/(β²ε²) log(N/δ))
  • 时间复杂度均为样本复杂度乘以N

下界定理(Theorem 1.2)

存在2-局域哈密顿量使得：

  • ℓ_∞误差：样本复杂度Ω(exp(β)/(β²ε²) log(N/δ))
  • ℓ_2误差：样本复杂度Ω(exp(β)N/(β²ε²))

与先前工作比较

方法样本复杂度时间复杂度适用范围
AAKS21O(N²logN/(β^c ε²))O(N³logN/(β^c ε²))几何局域
本文O(logN/(β²ε²))O(N logN/(β²ε²))低交集
经典情况O(logN/(β²ε²))O(N logN/(β²ε²))-

强凸性改进

改进了对数配分函数的强凸性参数从Ω(β^c/N)到Ω(β²)，这对应了宏观可观测量方差的下界改进。

相关工作

量子哈密顿量学习

  • Bairey等人(2019)：首次提出从稳态学习哈密顿量，但缺乏最坏情况分析
  • AAKS21：建立了严格的样本复杂度上界，但在多个参数上不够优化
  • 经典情况：马尔可夫随机场的参数学习已有近最优算法

技术联系

  • 簇展开：借鉴统计力学中的高温展开技术
  • 牛顿方法：经典优化方法在量子设置中的应用
  • 信息论下界：使用Fano引理建立信息论下界

结论与讨论

主要结论

  1. 在高温区域，量子哈密顿量学习可以达到与经典情况相同的最优复杂度
  2. 提出的算法在样本和时间复杂度上都是最优的
  3. 低交集哈密顿量类别比几何局域更一般，但仍可高效学习

局限性

  1. 温度限制：算法只在高温区域工作，临界温度依赖于对偶图度数
  2. 度数依赖：虽然对固定度数最优，但临界温度随度数快速下降
  3. 低温区域：低温区域的学习问题仍然开放

未来方向

  1. 扩大温度范围：寻找在更广温度范围内工作的算法
  2. 一般局域哈密顿量：扩展到度数不为常数的情况
  3. 低温算法：开发低温区域的有效学习算法
  4. 实验验证：在实际量子系统中验证算法性能

深度评价

优点

  1. 理论完备性：提供了完整的上界和匹配下界分析
  2. 技术创新：巧妙结合簇展开和牛顿方法
  3. 最优性：在多个参数上同时达到最优
  4. 一般性：扩展到比先前工作更广的哈密顿量类别
  5. 算法实用性：提供了具体可实现的算法和复杂度分析

不足

  1. 应用范围限制：仅适用于高温区域
  2. 度数敏感性：临界温度对度数的依赖较强
  3. 缺乏实验：纯理论工作，缺乏数值验证
  4. 量子优势不明显：在研究的设置下，量子情况复杂度与经典情况相同

影响力

  1. 理论贡献：为量子哈密顿量学习建立了基准
  2. 方法论价值：展示了经典技术在量子设置中的有效应用
  3. 后续研究：为低温区域和更一般设置的研究奠定基础
  4. 实用潜力：为量子系统的实验表征提供理论指导

适用场景

  1. 量子模拟：验证量子模拟器的准确性
  2. 材料科学：学习凝聚态系统的有效哈密顿量
  3. 量子计算：量子处理器的标定和验证
  4. 基础研究：理解量子多体系统的性质

参考文献

  1. Anshu, A., Arunachalam, S., Kuwahara, T., & Soleimanifar, M. (2021). Sample-efficient learning of interacting quantum systems. Nature Physics.
  2. Kuwahara, T., Kato, K., & Brandão, F. G. (2020). Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature. Physical Review Letters.
  3. Bresler, G. (2015). Efficiently learning Ising models on arbitrary graphs. STOC.
  4. Klivans, A., & Meka, R. (2017). Learning graphical models using multiplicative weights. FOCS.