A reduction scheme for general-order Ising-like Hamiltonians in quantum heuristic solvers

技術要約：高次イジング型モデルのための一般的ハミルトニアン簡約

問題設定
イジングモデルは、組合せ最適化問題をエンコードするための標準的な枠組みであり、そこでは基底状態を見つけることが最適解を見つけることに相当する。量子アニーリングやシミュレーテッド・ビファーケーション（模擬分枝法）などのヒューリスティック・ソルバーは進歩しているものの、大規模なインスタンスに固有の組合せ爆発に直面することが多い。一般的な前処理戦略はハミルトニアン簡約であり、これは、すべての基底状態において固定された相対的構成を維持するスピンのサブセットを特定することによって、論理変数の数を減らすことを目的としている。

FastHareや屋根双対性（roof duality）といった既存の簡約手法は、主に二次（二次形式）のイジングモデル向けに設計されている。しかし、充足可能性問題や高次ネットワークモデルを含む多くの実用的な最適化問題は、多体相互作用を含む高次のイジング型ハミルトニアンとして自然に定式化される。現在の手法はこれらの高次項を直接扱うことができず、高次問題を二次形式に変換する次数低減技術も存在するが、それらはしばしば補助変数（auxiliary variables）を導入し、問題のサイズを増大させてしまう。一般の次数を持つ相互作用に対する特化したハミルトニアン簡約スキームは不足している。

手法
著者らは、非分離群（Non-Separable Groups: NGs）の理論を任意の次数のイジング型モデルへと一般化したフレームワークである**GeneralHare (GH)**を提案する。その核となる手法は、主に以下の3つのコンポーネントで構成される。

1. 一般化された非分離群 (gNGs):
   本論文では、すべての基底状態においてグループ内のすべてのスピンが同じ符号を共有するというNGの定義を、gNGへと拡張する。gNGとは、特定の相対的構成（例：$\sigma_a = -\sigma_b = \sigma_c$）、またはそのグローバルな逆転をすべての基底状態において維持するスピンのサブセットである。これにより、単なる同一の構成だけでなく、複雑な内部相関を持つスピンの統合が可能になる。

2. 識別可能な判定基準:
   正確な非分離指数（分離可能な構成と非分離な構成の間のエネルギーギャップ）を計算することはNP困難である。アルゴリズムを計算可能にするため、著者らは非分離指数の容易に計算可能な下限値（$\hat{\nu}_H(X)$）を導出した。

   • この手法は、相互作用の次数（$m$）ごとにハミルトニアンを分解する。
   • すべての可能なスピン構成について最小化を行うのではなく、候補となるグループ$X$の特定の二分（bisection）を考慮することで、下限推定を利用する。
   • もし下限値 $\hat{\nu}_H(X) > 0$ であれば、そのグループは非分離グループとして識別される。$\hat{\nu}_H(X) = 0$ の場合は、「弱く」非分離なグループとして扱われる。

3. GeneralHare アルゴリズム:
   このスキームは、これ以上の簡約ができなくなるまで反復的にラウンドを実行する：

   • ノードの固定 (Node Fixation): グループの識別を行う前に、線形項（バイアス）が局所的な相互作用を支配しているノードを特定の値（$\pm 1$）に固定し、それらを除去することで、付随するハイパーエッジの次数を下げる。
   • 識別 (Identification): アルゴリズムは、導出された下限判定基準を用いて、ハイパーエッジ（サイズ制限 $\xi$ まで）を走査し、gNGおよび弱gNGを検出する。
   • 拡大 (Enlargement): 「和による閉包（closure under union）」の性質を用いて、重複するgNGを結合してより大きなグループを形成する。
   • 圧縮 (Compression): 特定されたグループを単一のノードへと統合する。これには、相対的構成を整えるためのスピンの反転、ノードの結合、および並行するハイパーエッジの重みの集計が含まれる。基底状態の対応関係を維持するために、このプロセスから生じる加法的定数は追跡される。
   • 最適化 (Optimization): 高速化のために、アルゴリズムは更新された近傍に候補探索を制限し、独立した弱gNGの同時結合を採用する。

主な結果
著者らは、合成ハイパーグラフ（Erdős-Rényiおよびスケールフリー）および公開されている高次ネットワークデータセット（接触ネットワーク、メールネットワークなど）を用いてGeneralHareのベンチマークを行った。

• 簡約性能:
  • 合成データにおいて、GeneralHareは大幅な簡約比率（疎なスケールフリー・ハイパーグラフで最大約50%）を達成した。
  • グラフの密度（平均次数）が増加し、相互作用の次数が上昇するにつれて、簡約効率は低下する（4次のグラフは3次のグラフの約半分の簡約比率を示した）。
  • 実世界のデータセットでは、簡約比率は2.1%から67.4%の範囲にあり、7つのインスタンスのうち5つが20%を超えた。
• FastHare（二次形式の場合）との比較:
  • 二次形式のイジングモデルに適用した場合、GeneralHareはその一般化された判定基準により、より多くの非分離グループを識別できるため、標準的なFastHareアルゴリズムよりも高い簡約比率を示す。
  • GeneralHareは非常に小さなグラフに対しては高い計算実行時間を要するが、効率的にスケールし、約5,000ノードでクロスオーバーポイント（Fasterまたは同等の速度になる点）を示す。
• 次数低減との統合:
  • 本論文では、次数低減（二次化/quadratization）とダウンストリーム・ソルバーを組み合わせたパイプラインを評価している。
  • 結果は、GeneralHareを二次化の前に適用すること（具体的には保守的なデモンストレーター GH_minimal を使用）が、二次化の後にFastHareを適用することよりも、最終的な変数のオーバーヘッドを低く抑えられることを示している。
  • 最も効果的な戦略として特定されたのは、以下の組み合わせパイプラインである：GeneralHare $\to$ 二次化 $\to$ FastHare。

意義および主張
本論文は、GeneralHareが高次のイジング型最適化問題におけるハミルトニアン簡約の基礎を確立するものであると主張している。その主な貢献は以下の通りである：

1. 理論的拡張: 非分離理論を二次から任意の次数のモデルへと正常に一般化し、高次の相互作用に対するこのような手法の欠如に対処した。
2. 実用的効率性: 問題の論理的なサイズを減少させる前処理ツールを提供し、検索空間を縮小することで、ダウンストリームのヒューリスティック・ソルバー（古典的および量子インスパイア型双方）の性能を向上させる可能性がある。
3. 基底状態の保存: 明示的な再構成マップを通じて、簡約されたハミルトニアンの基底状態が元の問題の基底状態に対応することを保証する。

著者らは、本手法は一般に適用可能であるが、その有効性は問題の構造（例：3-SAT問題における均質な次数分布は低い簡約比率をもたらす可能性がある）に依存する場合があることを注記している。彼らは、今後の課題として、特定のクラスの問題に対して専用のSATソルバーのような特殊なソルバーと組み合わせることを挙げている。