On The Complexity of Redundancy-Free Quantum Hamiltonians

技術要約：冗長性のない量子ハミルトニアンの複雑性について

問題の定義
本論文は、「冗長性のない（redundancy-free）」と称される特定の量子ハミルトニアンの計算複雑性を調査している。ハミルトニアン $H = \sum_i J_i O_i$ は、少なくとも一つの項が奇数回現れる項の積に対してトレースがゼロとなる場合、冗長性のないものと定義される。このクラスには、項の非自明な積がいかなる場合も単位行列（identity）にならないパウリ演算子の積の和からなるハミルトニアン（パウリ冗長性のないもの）が含まれる。

この種のハミルトニアンを研究する主な動機は、**ハミルトニアン・デコード量子干渉法（HDQI）**にある。HDQIにおいて、一般的なハミルトニアンのギブス状態を準備することは、次の2つのステップに還元される：(1) 冗長性のない緩和されたハミルトニアンのサーモフィールド二重体（TFD）に相当する「パイロット状態」を準備すること、および (2) 冗長性を取り除くための古典的なデコーディング問題を解くことである。デコーディングのステップは十分に理解されているが、パイロット状態（冗長性のないハミルトニアンのTFD）を準備することの複雑さは未解決の問題であった。本研究は、この状態準備および関連する分配関数の近似の困難さを特徴付けている。

手法と枠組み
著者らは、逆温度 $\beta$ および反交換グラフ $G$ の次数 $d$ の関数として複雑さを分析している。このグラフにおいて、頂点はハミルトニアンの項 $O_i$ を表し、頂点 $i$ と $j$ の間にエッジが存在するのは $\{O_i, O_j\} = 0$ である場合である。中心となるパラメータは $\kappa = \beta^2 d$ である。

本論文では、いくつかの異なる手法を用いている：

1. ポリマー展開（Polymer Expansion）: 小さな $\kappa$ に対して、著者らは自由エネルギーのポリマー展開を利用する。著者らはポリマーを反交換グラフの連結部分グラフとして定義し、分配関数の級数展開の収束条件を導出する。
2. 反交換グラス（Anticommutation Glass）の構成: 大きな $\kappa$ における困難性を確立するために、著者らは「反交換グラス」と呼ばれるシステムを構築する。このシステムは、可逆な反交換行列を持つ2組の演算子（X型とZ型）で構成されており、古典的な冗長性なしに、純粋に反交換関係から生じるフラストレーションを生み出す。
3. Feiguin-Klich ハミルトニアン: 状態準備に関して、著者らは目的のTFDを基底状態に持つ非エルミート演算子である $H_{FK}$ を探索する。彼らはそのスペクトルギャップと冪級数展開の収束を分析する。
4. QMA困難性の還元: 基底状態エネルギーの困難性を証明するために、著者らは三角格子上の反強磁性XYモデルの局所ハミルトニアン問題を、冗長性のないハミルトニアンへと還元する。彼らは、基底状態エネルギーの構造を維持しつつ関係性を除去するために、3量子ビットのエンコーディングスキームを採用している。

主要な結果

1. 分配関数近似の複雑性

• 小さな $\kappa$（容易な領域）: 著者らは、$\kappa$ が十分に小さい場合（具体的には $\beta \lesssim 1/\sqrt{d}$ の場合）、自由エネルギーのポリマー展開が収束することを証明している。これにより、システムサイズ $n$ と誤差 $\epsilon$ に対して多項式時間の計算量を持つ、分配関数を近似するための効率的な古典アルゴリズムが得られる。これは、一般的なハミルトニアン（$\beta \lesssim 1/d$ でのみ実行可能）に対する二次的な改善を意味する。
• 大きな $\kappa$（困難な領域）: 逆に、$\kappa$ が十分に大きい場合、分配関数の近似はNP困難であることが示される。著者らは、冗長性のないハミルトニアンが、その分配関数の中に任意の古典的イジングモデル（強磁性的および反強磁性的相互作用の両方を含む）を効果的にエンコードできることを示している。これは、「反交換グラス」の「盆地（basins）」を用いて有効なイジングモデルを構築することによって達成される。
• 基底状態エネルギー: 冗長性のないハミルトニアンの基底状態エネルギーの推定は、局所性が限定（最大5）され、反交換次数が限定（最大26）されている場合でも、QMA完全であることが証明されている。

2. 量子状態準備

• 劣指数時間アルゴリズム: 小さな $\kappa$ に対して、著者らはサーモフィールド二重体状態を準備するための劣指数時間量子アルゴリズムを提示している。これは、相関の減衰が $\beta d$ ではなく $\kappa = \beta^2 d$ によって支配されることに依拠している。
• 一般的なハミルトニアンに対する多項式時間: 冗る性のないハミルトニアンにおける $\beta \lesssim 1/\sqrt{d}$ でのTFDの多項式時間準備については未証明であるが、著者らは、相互作用グラフの次数 $d$ を持つ一般的なハミルトニアンの $\beta \lesssim 1/d$ におけるTFDを準備するための多項式時間アルゴリズムを提供している。このアルゴリズムは、Feiguin-Klich ハミルトニアンを利用し、十分小さな $\beta d$ におけるスペクトルギャップの証明に基づいている。

3. 物理的性質：相関と絡み合い

• 相関の減衰: 本論文は、冗長性のないハミルトニアンにおける相関が距離に対して指数関数的に減衰することを確立しており、これは $\kappa = \beta^2 d$ によって制御される。この減衰は、一般的なハミルトニアンと比較して、$\beta$ への依存性が二次的に強い。
• 絡み合い（Entanglement）: アルゴリズム的に扱いやすい $\beta \sim 1/\sqrt{d}$ においても、これらのハミルトニアンは真の量子絡み合いを示す。著者らは、熱状態が $\beta \sim 1/d$ で絡み合っている（NPT）ことを示す具体的な例（完全二部反交換グラフの標準的な実現を含む）を構築し、計算の容易さが分離可能性（separability）を意味しないことを実証している。
• 相互情報量: 強化された熱相互情報量の境界が導出されており、一般的なハミルトニアンの線形な $\beta$ スケーリングに対し、冗長性のないハミルトニアンでは $\beta^2$ スケーリングを示すことが示されている。

意義と主張
本論文は、冗長性のないハミルトニアンが、量子状態準備における困難性の源を理解するための重要なテストベッドとなることを主張している。これらの結果は、**ハミタニアン・デコード量子干渉法（HDQI）**が、デコーディングステップが効率的な温度において、特定のハミルトニアンの熱状態の準備を簡略化できる可能性を示唆している。具体的には、本研究は以下のことを示している：

• TFDの準備の困難さは、単に古典的な冗長性に起因するのではなく、純粋に反交換関係（フラストレーション）から生じ得る。
• 冗長性のないハミルトニアンには、一般的なハミルトニアンの「容易な」領域（$\beta \lesssim 1/d$）よりも二次的に広い、「容易な」領域（$\beta \lesssim 1/\sqrt{d}$）が存在する。
• 「反交換グラス」モデルは、一般的な量子ハミルトニアンの本質的な困難さを捉えており、それらの基底状態エネルギー推定は依然としてQMA完全である。

著者らは、$\beta \lesssim 1/\sqrt{d}$ における冗長性のないハミルトニアンのTFDの多項式時間準備に関して、控えめな姿勢を保っている。彼らは、劣指数時間アルゴリズムを提供し、Feiguin-Klich ハミルトニアンを通じた多項式時間への道筋を示してはいるものの、冗長性のないケースにおけるスペクトルギャップの厳密な証明は今後の課題としている。また、彼らが提供する一般的なハミルトニアンに対する $\beta \lesssim 1/d$ での多項式時間の結果は、格子次元の仮定を取り除くことで、先行研究を改善したものであると明記している。