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

技術要約：物理的に動機付けられた距離における、疎な量子ハミルトニアン学習のためのほぼ最適アルゴリズム

1. 問題設定

本論文は、$n$ 量子ビットのハミルトニアン $H$ を学習する問題を取り扱う。ここで $H$ はパウリ基底において $s$-疎（$s$-sparse） である（すなわち、非ゼロのパウリ係数が高々 $s$ 個存在する）。学習アルゴリズムは、時間発展演算子 $U(t) = e^{-iHt}$ を通じてハミルトニアンにアクセスできる。

著者らは、既存の文献における2つの決定的なギャップを特定している：

1. 最適性の欠如： 多くの既存アルゴリズムは、それらが最適であることを確立するための、一致する下界（lower bounds）を欠いている。
2. 物理的に不透明な指標： 従来の多くの研究では、数学的に便利な距離（例：パウリ係数の $\ell_\infty$ または $\ell_2$ ノルム）を用いて推定の質を測定しているが、これらは基礎となる量子系の識別可能性に関する直接的な物理的解釈を欠いている。

提示される核心的な問いは、「物理的に意味のある最悪ケースの距離において、ハミルトニアン学習の最適な複雑性は何か？」である。

2. 手法と技術

A. 物理的に動機付けられた距離
著者らは、運用シナリオに基づいてハミルトニアンの識別可能性を定量化する、2つの新しい距離指標を導入している：

1. 時間制約付き距離 ($d_T$)： 有界な時間間隔 $[0, T]$ における、2つのハミルトニアンの時間発展チャネル間の最大ダイヤモンド距離として定義される。これは、状態を準備し、時間 $t \le T$ だけ発展させ、測定することによって、ハミルトニアンを識別できる最良の確率を定量化する。
2. 温度制約付き距離 ($d_B$)： 有界な逆温度範囲 $[0, B]$ における、2つのハミルトニアンのギブス状態（熱状態）間の最大トレース距離として定義される。これは、熱状態を介した識別可能性を定量化する。

著者らは、時間制約付き距離における学習が、演算子ノルム（$\|H_1 - H_2\|_{op}$）における学習と等価であることを証明しており、演算子ノルムにおける上界は、温度制約付き距離における上界を意味することを証明している。

B. アイソレーション（分離）テクニック（Valiant-Vaziraniに着想を得たもの）
中心的な技術的貢献は、Valiant-Vaziraniの定理に着想を得た、新しいアイソレーション（分離）テクテクニックである。このテクニックにより、アルゴリズムは、完全なパウリ・サポートが未知であっても、疎なハミルトニアンの単一のパウリ係数を「分離」することができる。

• メカニズム： ランダムにパウリ演算子の集合 $Q_1, \dots, Q_r$ を選択し、共役変換を通じて修正されたハミルトニアン $H_{Q_1, \dots, Q_r}$ を構成することで、特定のターゲットとなるパウリ項 $P$ がすべての $Q_i$ と可換になる確率を $\Omega(1/s)$ で確保する。
• 結果： これにより、ハミルトニアンの発展を効果的にフィルタリングし、単一のパウリ項 $e^{-ith_P P}$ のダイナミクスを分離して、効率的なサンプリングと推定を可能にする。

C. アルゴリズムの構造
学習アルゴリズムは以下の2段階で進行する：

1. 有効サポートの学習： アイソレーション・テクニックとパウリ・サンプリングを用いて、アルゴリズムは $H$ の $\epsilon$-有効サポート（係数 $|h_P| \ge \epsilon$ を持つすべてのパウリ項）を含むサイズ $\tilde{O}(s)$ の集合 $\mathcal{P}$ を特定する。
2. パラメータ推定： サポートが特定された後、アルゴリズムはアイソレーション・テクニックを再度用い、各パウリ係数 $h_P$ を誤差 $\epsilon$ 以内で個別に推定する。

3. 主要な結果

上界（アルゴリズムの性能）
著者らは、有界な演算子ノルムを持つ $s$-疎なハミルトニアンを学習するアルゴリズムを提示している：

• 実験回数： $\tilde{O}(s \log(1/\epsilon))$ 回の実験。
• 総発展時間： $\tilde{O}(s^2/\epsilon)$。
• 距離： このアルゴリズムは、時間制約付きおよび温度制約付きの両方の距離において $\epsilon$-学習を達成する。
• 堅牢性： アルゴリズムは、定数量の状態準備および測定（SPAM）エラーに対して堅牢であり、標準的なパウリ・サンプリングで使用されるアンシラ量子ビットを必要としない（メインアルゴリズムの修正により、アンシラの必要性を排除している）。
• ハイゼンベルク・スケーリング： 総発展時間は $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]）を改善するものである。

4. 意義と主張

本論文は、物理的に意味のある距離における、実験回数に関してほぼ最適なハミルトニアン学習の結果を提供したと主張している。

• 物理的関連性： 指標を抽象的な係数ノルムから、時間制約付きダイヤモンド距離や温度制約付きトレース距離へと移行させることで、結果は実験能力（有限の発展時間および有限の温度）に直接関連付けられている。
• 最適性： 本研究は、必要な実験回数が対数因子を除いて本質的に最適であり、導出された下界と一致していることを確立している。
• 汎用性： 多くの先行研究とは異なり、このアルゴリズムはパウリ・サポートの事前知識を仮定せず、またハミルトニアンが局所的または幾何学的な構造を持つことも要求しない。単に疎性のみを仮定している。
• 理論的架け橋： 本論文は、演算子ノルム（標準的な数学的ツール）を物理的な識別可能性指標へと厳密に結びつけ、有界な時間および温度予算の下では、演算子ノルムにおける学習がこれらの物理的距離における学習に十分であることを示している。

著者らは、実験回数はほぼ最適であるが、総発展時間のスケーリング（$\tilde{O}(s^2/\epsilon)$）には、下界である $\Omega(\sqrt{s}/\epsilon)$ との間に改善の余地があることを認めている。彼らは、最適な発展時間を見つけることが主要な今後の研究方向であると特定している。