A computational phase diagram for the transverse field Ising model

技術要約：横磁場イジング模型における計算論的相図

問題提起
本研究は、横磁場イジング模型（TFIM）における分配関数 $Z(\beta) = \text{Tr}(e^{-\beta H})$ およびギブス状態の観測量の近似に関する計算量的な複雑さに対処する。TFIMは以下のハミルトニアンによって定義される：
$$H = \frac{1}{2} \sum_{i,j \in [n]} J_{ij} Z_i Z_j + \sum_{i=1}^n h^z_i Z_i + \eta \sum_{i=1}^n X_i$$
ここで、$J$ は対称な相互作用行列、$h^z$ は縦磁場、$\eta$ は横磁場の強さを表す。強磁性系または高温領域（具体的には $\beta \Delta(J) \leq 1$ の場合）については既存のアルゴリズムが存在したが、強い横磁場下における本モデルの扱いやすさ（tractability）は未解決の問題であった。著者は、あらゆる横磁場強度において、効率的な古典的近似可能性とNP困難性の間の正確な境界を特徴付けることを目的としている。

手法
本論文では、リー・トロッター積近似、古典統計力学へのマッピング、および大偏差原理を組み合わせて用いる。

1. 古典分布へのマッピング: 量子分配関数および観測量は、古典分布に対する期待値として書き換えられる。$M$ ステップのリー・トロッター近似を用いることで、量子トレース $\text{Tr}(O e^H)$ は $\text{Tr}(O Q_M)$ で近似される（ここで $Q_M = (e^{H_z/M} e^{H_x/M})^M$ である）。これはさらに、$\sigma$ を閉境界条件を持つサイクルグラフ上の $n$ 個の独立な1次元イジングモデルの構成とし、$W(\sigma)$ を相互作用行列から導出されるポテンシャル関数としたとき、期待値 $E_{\sigma \sim \nu}[e^{W(\sigma)} f(\sigma)]$ として表現できる。
2. Glauber動力学によるサンプリング: 扱いやすい領域において、この問題は傾斜分布 $\mu_\lambda \propto e^{\lambda W} \nu$ からのサンプリングへと還元される。著者は、相互作用行列のスペクトル幅が特定の条件を満たす場合、この分布上のGlauber動力学が急速に混合（KLダイバージェンスを収縮）することを証明する。この急速な混合は、サイクル上の1次元イジングモデルの共分散行列の演算子ノルムを抑えることに依存している。
3. ガジェットによる困難性の証明: 困難性を確立するために、著者はMAXCUT問題からのリダクションを構築する。著者らは、扱いにくい領域における横磁場キュリー・ワイス模型の「二峰性（bimodality）」を利用する。MAXCUTインスタンスの頂点をキュリー・ワイス・ガジェットで置き換えることにより、分配関数の比が最大カット値をエンコードするようなTFIMインスタンスを作成する。この困難性は、ガジェット内の平均スピンが2つの異なる値（$\pm m^*$）の近くに集中するという事実に依拠している。

主な貢献および結果

1. 計算論的相図: 本論文は、以下の条件によって定義される鋭い相転移を確立する：
   $$\Delta(J) \cdot \frac{\tanh(\beta \eta)}{\eta} \leq 1$$
   ここで $\Delta(J) = \lambda_{\max}(J) - \lambda_{\min}(J)$ は相互作用行列のスペクトル幅である。

   • 扱いやすい領域 ($\leq 1$): 著者は、相対誤差 $\epsilon$ 内で分配関数 $Z(\beta)$ を、およびパウリ・ストリングの観測量を加法的誤差 $\epsilon$ 内で近似する、パラメータ $n, \beta, \epsilon^{-1}$ およびモデルパラメータに対して多項式時間で動作するランダム化古典アルゴリズムを提供する。この条件は、従来の条件（例：$\beta \Delta(J) \leq 1$）よりも厳密に弱く、$\Delta(J) \leq |\eta|$ である強磁場極限を含むすべての横磁場強度に適用される。
   • 扱いにくい領域 ($> 1$): 著者は、$\exp(o(n))$-倍率の範囲内で分配関数を近似することがNP困難であることを証明する。具体的には、任意の $\epsilon > 0$ に対して、$\Delta(J) \cdot \frac{\tanh(\beta \eta)}{\eta} \in (1, 1+\epsilon)$ となる対称行列 $J$ が存在し、その場合、近似はNP困難となる。これは、標準的な計算量仮定（$NP \not\subseteq BQP$ および $NP \neq RP$）の下、この領域において効率的な古典的または量子的なアルゴリズムが存在しないことを意味する。

2. ギブス状態の準備: 扱いやすい領域のために開発された効率的なサンプリング手法を活用し、本論文は全変動距離誤差 $\epsilon_{TV}$ を持つギブス状態 $\rho_\beta = e^{-\beta H} / Z(\beta)$ を準備するための効率的な量子アルゴリズムを提供する。

3. 基底状態エネルギーの近似: 横磁場が支配的な領域（$\Delta(J) \leq |\eta|$）において、アルゴリズムは任意の逆温度 $\beta \geq 0$ で適用可能である。これにより、十分大きな $\beta$ を選択することで、基底状態エネルギー $E_0$ を任意の加法的精度で近似できる。

4. 観測量の推定: アルゴリズムは、任意のパウリ・ストリング $P$ に対して $\text{Tr}(P \rho_\beta)$ を推定する。$P$ がX基底において対角である場合（すなわち $P \in \{I, X\}^{\otimes n}$）、アルゴリズムは任意に小さい相対誤差を達成する。一般的なパウリ・ストリングに対しては、任意に小さい加法的誤差を達成する。

意義
本論文は、量子アニーリングや凝縮系物理学の中心的な領域である、強い横磁場下におけるTFIMの扱いやすさの領域を特徴付けるという未解決問題の解決を主張している。$\Delta(J) \cdot \frac{\tanh(\beta \eta)}{\eta} \leq 1$ という条件を正確な境界として特定することで、本研究は強磁性または高温の場合に限定されていた先行研究を統合し、拡張している。補完的な領域におけるNP困難性の証明は、これらのパラメータ空間における古典的および量子的なシミュレーション手法の限界に対して、強力な理論的根拠を与える。さらに、扱いやすい領域におけるギブス状態の準備と観測量推定のための効率的なアルゴリズムの開発は、強い横磁場が存在する量子シミュレーション・タスクに対して実用的なツールを提供する。

著者は、高レベルの戦略は著者自身によって開発されたものであり、AIツールは特定の証明（補題13、定理21、命題8および9）および組版に補助として使用されたが、内容に関する全責任は著者が保持していると述べている。