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

高温ギブス状態からの量子ハミルトニアンの最適学習

基本情報

  • 論文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
  • 発表日時: 2023年3月17日 (arXiv版)
  • 論文リンク: https://arxiv.org/abs/2108.04842

要約

本論文は、既知の逆温度βを持つギブス状態ρ=exp(-βH)/Tr(exp(-βH))のコピーからハミルトニアンHを精度εまで学習する問題を研究している。高温(低β)領域において、著者らは低交差度ハミルトニアンクラスに対する学習アルゴリズムを提案し、サンプル複雑度S=O(logN/(βε)²)および時間複雑度O(SN)を達成し、マッチングする下界を証明することで、アルゴリズムがサンプルと時間複雑度の両方で最適であることを示している。

研究背景と動機

問題定義

ハミルトニアン学習問題は、量子多体物理と機械学習の交差領域における重要な問題である。未知のハミルトニアンHの熱平衡状態(ギブス状態)の複数のコピーが与えられたとき、目標はハミルトニアンの係数を学習することである。この問題は物理的に直接的な動機付けがある:ハミルトニアンは量子系の相互作用と時間発展を記述し、ギブス状態は与えられた温度で環境と熱平衡に達した系の状態である。

研究の意義

  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は学習対象の係数
  • ハミルトニアンは低交差度:各演算子は定数個の量子ビットに作用し、各演算子はその支持集合と非自明な交差を持つ定数個の他の演算子とのみ相互作用

目標:ギブス状態ρ = 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ε

実験設定

理論的検証

本論文は主に理論的研究であり、数学的証明によってアルゴリズムの正確性と最適性を検証し、実証的実験ではなく理論的検証に焦点を当てている。

複雑度分析

  • サンプル複雑度(logN/(βε)²) (ℓ_∞誤差)、O(N/(βε)²) (ℓ_2誤差)
  • 時間複雑度(N logN/(βε)²) (ℓ_∞)、O(N²/(βε)²) (ℓ_2)
  • 前処理時間(LMd log d)は双対相互作用グラフの構築用

実験結果

主要な理論的結果

上界定理(定理1.1)

低交差度ハミルトニアンについて、β < β_c条件下で:

  • ℓ_∞誤差ε:サンプル複雑度O(1/(β²ε²) log(N/δ))
  • ℓ_2誤差ε:サンプル複雑度O(N/(β²ε²) log(N/δ))
  • 時間複雑度はいずれもサンプル複雑度にNを乗じたもの

下界定理(定理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:厳密なサンプル複雑度上界を確立したが、複数のパラメータで最適化が不十分
  • 古典的場合:マルコフ確率場のパラメータ学習には近最適アルゴリズムが存在

技術的関連性

  • クラスター展開:統計力学の高温展開技術から借用
  • ニュートン法:古典的最適化手法の量子設定への応用
  • 情報論的下界の補題を使用した情報論的下界の構築

結論と議論

主要な結論

  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.