Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy

技術的要約：Weisfeiler–Leman階層におけるスケーラブルなメッセージパッシング量子グラフニューラルネットワーク

問題提起

グラフニューラルネットワーク（GNN）は、「メッセージパッシング」というプリミティブによって、化学、生物学、最適化における関係データの学習において中心的な役割を果たしてきました。しかし、既存の量子対応モデルには重大な限界があります：

1. 真のメッセージパッシングの欠如： 提案されているほとんどの量子グラフモデルは、量子回路内でのメッセージパッシングを行っていません。代わりに、グラフのエッジを回路ゲートにマッピングしていますが、近傍情報の集約を古典的な後処理に依存しており、量子演算によるコヒーレントな利点を逃しています。
2. 表現力の天井： 標準的なメッセージパッシング型GNNは、1-Weisfeiler–Leman（1-WL）テストによって制限されています。つまり、特定の非同型な分子や部分構造などの、構造的に異なるグラフを区別できないことを意味します。
3. 学習可能性とスケーラビリティ： 変分量子回路（VQC）は、回路サイズが大きくなるにつれて勾配が指数関数的に消失する「バレン・プラトー（不毛な台地）」問題にしばしば直面し、大規模なグラフの学習を不可能にします。さらに、置換等変性（permutation equivariance）の保証や、大規模なグラフインスタンスへのスケーラビリティを提供する量子モデルはほとんど存在しません。

手法

著者らは、量子領域内で完全に動作する、**部分空間保存回路（subspace-preserving circuits）に基づいた量子グラフニューラルネットワーク（QGNN）**フレームワークを導入しています。このアーキテクチャは、以下の4つの主要コンポーネントで構成されています。

1. 階層的データローダー ($V$)： システムは2つのレジスタを使用します。

   • ノードレジスタ ($N$ 量子ビット)： 特定のハミング重み $j$ におけるグラフノードをエンコードします。基底状態は、$j$ 個のノードのサブセット（例：$j=1$ では単一ノード、$j=2$ ではエッジ、$j=3$ では三角形）を表します。
   • 埋め込みレジスタ ($D$ 量子ビット)： ハミング重み $k$ における特徴量をエンコードします。
   • 制御Givens粒子数エンコーダが、ノード特徴量を結合部分空間 $H^j_N \otimes H^k_D$ にロードします。

2. 等変隣接レイヤー ($A(G)$)： このレイヤーは、エッジに対応するノード量子ビット間のGivens回転を適用することで、グラフの接続性をエンコードします。回転角は、ノードラベルに依存せず、グラフ構造を尊重するように、カノニカルな順序に従ってエッジの重みから導出されます。

3. 学習可能な進化 ($W(\theta)$)： 埋め込みレジスタのみに作用し、ノード特徴量を更新します。これは、部分空間保存ゲート（具体的には、複合表現にリフトされた $SO(D)$ のケイリー・パラメトリゼーション）を使用しており、ダイナミクスが構造化された部分空間内に留まり、バレン・プラトーを回避することを保証します。

4. 結合レジスタ混合 ($M(\theta_M)$)： 最終レイヤーは、Givens回転を介してノードレジスタと埋め込みレジスタを結合し、構造的部分空間と特徴的部分空間の間で情報の流れを可能にします。

主要メカニズム：

• メッセージパッシング： 回路はコヒーレントにメッセージパッシングを実行します。隣接レイヤーがエッジに沿って振幅をルーティングし、学習可能な進化が特徴量を更新します。各レイヤーでローダーを再アップロードすることで非線形性が導入されます。
• 置換等変性： アーキテクチャは、構成上、厳密に置換等変です。学習可能な進化が共有される埋め込みレジスタに対してのみ作用し、かつ隣接/混合レイヤーがノードラベルではなくエッジの重みに基づくカノニカルな順序に従うため、ノードのラベル付けを変更しても、関数自体は変化せず出力のラベルが変わるだけとなります。
• リードアウト（読み出し）： 特徴量は、埋め込みレジスタの一次密度行列（1-RDM, $\gamma_{pq} = \langle \psi | a^\dagger_p a_q | \psi \rangle$）を介して読み出されます。これは、matchgate shadowや決定論的なハートリー・フォック読み出しを用いることで、全ノード数 $N$ に依存せず、多項式コスト（$O(D^3/\epsilon^2)$）で推定可能です。

主な貢献

1. 理論的保証： 本論文は、QGNNが真のメッセージパッシングを行い、厳密に置換等変であり、$j$-WL表現力を達成することを証明しています。ノードレジスタの粒子数を $j \ge 3$ に設定することで、標準的な1-WLテスト（および標準的なメッセージパッシング型GNNすべて）が識別できないグラフペアを区別できます。
2. 部分空間保存によるスケーラビリティ： ダイナミクスを固定サイズの部分空間（$N$ ではなく $D$ と $k$ によって決定される）に限定することで、一般的なVQCに関連する指数関数的な勾配消失を回避します。
3. 事前学習戦略： フレームワークは「小さく訓練し、大きく展開する（train-small, deploy-large）」アプローチを採用しています。学習パラメータが（グラフのサイズに依存しない）埋め込みレジスタに対してのみ作用するため、小さなグラフで訓練されたモデルを、そのパラメータを用いて大きなインスタンスへ転移させることができます。

結果

本フレームワークは、3つのデータセットにわたる最大56量子ビットの大規模な古典シミュレーションを通じて検証されました。

1. Cai–Fürer–Immerman (CFI) グラフ：

   • 目的： 1-WLでは分離できない非同型なグラフペアを区別すること。
   • 結果： QGNNは、予測された粒子数（CFI(K3)に対して $j=3$、CFI(K4)に対して $j=4$）において正確に100%のテスト精度を達成しました。一方で、1-WLベースラインはチャンスレベルにとどまりました。これは、モデルが1-WLの天井を超える能力を持つことを裏付けています。

2. QM9 分子特性予測：

   • 目的： 130,831個の分子のHOMO–LUMOギャップを予測すること。
   • 結果： 粒子数 $j$ を1から3に増やすことで、パラメータ数をほぼ一定に保ったまま、平均絶対誤差（MAE）を0.398 eVから0.235 eVに減少させました。これは、より高次の構造的解像度が実世界の化学タスクにおいて性能を向上させることを示しています。

3. ユークリッド・巡回セールスマン問題 (TSP)：

   • 目的： $N$ 個の都市（$N$ 最大50）に対する近似最適ツアーを見つけること。
   • 結果： モデルは $N=50$ において1.201の比率（最適値は1.0）のツアーを生成しました。極めて重要な点として、モデルはこのスケールでも学習可能でした。
   • 学習可能性： 量子ビット数が増加しても、勾配の分散は指数関数的ではなく多項式的に維持されました。転移学習（小さなモデルから大きなモデルを初期化する）により、勾配信号はランダム初期化よりも1〜2桁高い値を維持しました。
   • リードアウト： Matchgateベースの読み出しは、計算基底の読み出しを大幅に上回り、タスクの性能に不可欠な非対角情報を回収しました。

意義と主張

本論文は、理論的保証と実用的なスケーラビリティの両方を備えた近未来の量子アルゴリズムへの道を切り開くと主張しています。

• 理論と実践の架け橋： グラフ学習の原理（メッセージパッシング、等変性、WL階層）を、ヒューリスティックな量子モデルを超えて、量子回路設計に直接持ち込んでいます。
• 学習可能性の解決： 部分空間保存ダイナミクスと事前学習を利用することで、バレン・プラトーの問題に対処し、量子グラフモデルが大規模なインスタンスに対して学習可能であることを示しました。
• 表現力： 1-WLの表現力制限を超えることが証明された最初の量子グラフモデルを提供し、標準的なメッセージパッシング型ネットワークが逃してしまう複雑なグラフ構造を区別するための理論的根拠を提示しました。

著者らは、現在の検証は古典シミュレーションによるものであるものの、アーキテクチャは近未来の量子ハードウェア（$N=50$ に対して約56量子ビットが必要）と互換性があり、読み出しコストはグラフのサイズではなく特徴次元に対して多項式的にスケールするように設計されていることを強調しています。