MQSS-Selector: RL-Guided Pass Selection for an MLIR Compilation Pipeline

技術要約: MQSS-Selector

問題提起と動機
ハイパフォーマンス・コンピューティング（HPC）と量子コンピューティング（QC）が高性能HPCQCインフラストラクチャへと統合されるにつれ、古典的ワークフローと量子ワークフローを橋渡しできるソフトウェアスタックが必要となっている。しかし、現在のNISQ（Noisy Intermediate-Scale Quantum）デバイスは、エラーが発生しやすく、リソースが制約されており、キャリブレーションやトポロジーに対して非常に敏感である。その結果、効果的な実行には専門的なコンパイルと最適化が必要となる。

既存のソフトウェアスタックは、デバイス選択、コンパイラパスの最適化、およびジョブスケジューリングを独立したステージとして扱うことが多く、断片化という問題を抱えている。本論文では、2つの重要な相互依存関係にある課題を特定している：

1. デバイス選択: トポロジー、ゲート忠実度、待ち行列の遅延、およびメンテナンスウィンドウを考慮した上で、利用可能なバックエンドの集合からターゲットとなる量子デバイスを選択すること。
2. フェーズ順序付け（Phase Ordering）: 量子プログラムを変換するためのコンパイラパスの最適なシーケンスを決定し、デバイスへの適合性を確保しつつ、ジャストインタイム（JIT）コンパイル時間と実行実行時間を最小化すること。

著者らは、デバイス選択とフェーズ順序付けの両方がNP困難な問題であることを形式的に証明している（定理1）。ただし、これらは異なる困難性の基礎に帰着する。デバイス選択は分割問題（Partition problem）に帰着し、フェーズ順序付けは停止問題（halting problem）に帰着する（決定不能性の証明）。さらに、それらの相互依存性は「ブートストラップのジレンマ」を生み出し、一方のステージを単独で最適化すると、もう一方のステージが最適ではなくなる可能性がある。現在のソリューションは、静的なヒューリスティックや、個別の学習タスク（例：デバイスには教師あり学習、パスには強化学習）に依存することが多いが、これらは動的なバックエンドの状態や、最適化空間の結合性を考慮できていない。

手法
本論文は、デバイス選択とパス順序付けを、一貫した意思決定プロセスへと統合するために設計された、統一された学習ベースのフレームワークであるMQSS-Selectorを提案している。このアプローチは、MLIR（Multi-Level Intermediate Representation）コンパイルフレームワーク、特にQuakeダイアレクト内で、強化学習（RL）とディープラーニングを活用している。

手法は、統一されたスケジューラの概念的な2つのスキームに基づいて構成されているが、これらは現在、将来的な統合に向けて個別のコンポーネントとして実装されている：

• アプローチ1（ハイブリッド）: 教師あり学習モジュールがデバイス選択を行い、その出力が独立したRLベースのモジュールによるフェーズ順序付けの情報となる、モジュール型の設計。
• アプローチ2（完全RLベース）: デバイス選択とパス順序付けを、単一のより大きなアクション空間へと結合させた、モノリシックな設計。

主要コンポーネント:

• デバイス選択モジュール: 様々なデバイス上でのプログラムのヘリンジャー忠実度（Hellinger fidelity）を予測するために、教師あり学習モデル（MLP、ランダムフォレスト、SVM、KNN）を利用する。システムは実行時間と忠実度を正規化してデバイスをランク付けし、絶対的な値の精度よりも相対的なランキング精度を優先する。
• パス選択モジュール: Actor-Critic強化学習アルゴリズムを実装。
  • 状態（State）: プログラムの特徴（量子ビット数、深さ）、バックエンドのステータス、および中間コンパイル結果を含む。
  • アクション（Action）: 拡張されたMQSSパススイート（92以上のパス）からのコンパイルパスの選択、マッピングパス、または「終了（Finish）」アクション。
  • 報酬関数: 実行可能性（ネイティブゲートへの適合性）、早期停止（同等の結果が得られる場合はより短い経路を好む）、および構造的最適化（深さと操作数の削減）を満たすように設計されている。
• Dual-Annealed Exploration Priming (DAEP): 成功したコンパイルのロールアウトが疎であるという課題に対処するために導入された、新しいトレーニング戦略。DAEPは、減少する確率（$p_{DAEP}$）と大きさ（$\alpha_{DAEP}$）を持つ既定のポリシーによって、アクターの選択を上書きするガイダンス項を損失関数に導入する。これにより、エージェントがクリックの推定値を独立して利用することを学習する前に、初期構造を提供することで収束を加速させる。

実験結果
著者らは2つのデータセットを用いてコンポーネントを評価した：

1. デバイス選択: 128個のMQT-Benchプログラムを、12個の模擬IBMバックエンドおよび2つの実機ローカルデバイス上の2,880個のランダムベンチマークを用いてテスト。
   • 知見: ランダムフォレスト（RF）が模擬デバイスのデータセットにおいて最も適した候補として浮上し、不可能なプログラムの予測に苦戦したMLPを上回った。すべてのプログラムが実行可能であった実機においては、すべてのモデルが高い$R^2$スコアとともに同様の性能を示した。著者らは、SVMやKNNは限定的なデータにおいて良好な忠実度予測を示したが、多様で大規模なプログラムセットに対してはRFほどスケールしない可能性があると指摘している。
2. パス選択: 1,548個の化学ハミルトニアンプログラムのデータセットで評価。
   • 知見: DAEPで訓練されたRLエージェントは、ガイダンスなしのベースラインを大幅に上回った。
     • 実行可能性: ガイダンス付きモデルは、終了時に95.5%の実行可能なプログラム率を達成したが、ガイダンスなしのモデルは42.1%であった。
     • 最適化: ガイダンス付きモデルは、87/154のサンプルでプログラムの深さを削減し、93/154のサンプルで操作数を削減したが、ガイダンスなしのモデルはそれぞれ8個と15個のサンプルでしかこれらの削減を実現できなかった。
     • 終了: ガイダンス付きエージェントは、「終了（Finish）」アクションを効果的に呼び出すことを学習したが（153/154回）、ガイダンスなしのエージェントは早期終了することがほとんどなかった。
   • 批判的考察: 著者らは、ガイド付きモデルにおいてクリティックネットワークの分類性能（真の陽性/偽の陽性）が保守的であったため、さらなる訓練が必要であると述べている。これは、アクターがより少ないステップで効率的に終了することを学習したため、クリティックに提供される訓練サンプルが少なくなったことによるものと考えられる。極めて重要な点として、実験データは、追加の手法（DAEPのような）を用いない強化学習は、検討されているリソース制約下でのコンパイルのためのネットワーク訓練において、実行可能なアプローチではないことを示唆している。

意義と主張
本論文は、データ駆動型かつMLIRネイティブな量子コンパイルのための、基礎的な構成要素（教師あり学習によるデバイス選択とRLベースのパス順序付け）の実現可能性を示すものであると主張している。主な貢献は以下の通りである：

• 統一フレームワークの概念: 本論文は、断片化されたステージ固有のヒューリスティックから脱却し、デバイス選択とパス選択のNP困難で相互依存的な性質に対処するための、結合最適化フレームワークを提案している。ただし、統一されたスケジューラ自体は、将来的な統合に向けた2つの別々のコンポーネントによる概念的な設計であり、完全に統合されたシステムとしてデモンストレーションされたものではない。
• MLIRネイティブの実装: Qiskitを対象とする先行研究（例：TuniQ）とは異なり、本研究は大規模なMLIRベースのパスを備えたMQSSコンパイルパススイートを拡張しており、現代的なコンパイラインフラストラクチャとの統合を可能にしている。
• DAEP戦略: Dual-Annealed Exploration Primingは、コンパイルタスクにおける報酬の希薄化という課題に対処し、ランダムな探索では失敗するような効果的なポリシーをRLエージェントが学習することを可能にする。
• 控えめな展望: 著者らは、統一されたアプローチは、相互依存性を利用することで独立した最適化パイプラインを凌駕する可能性を秘めているものの、パス選択コンポーネントには現在、より広範な訓練とガイダンスが必要であると結論付けている。彼らは、本研究が、完全な統合システムを実現したと主張するのではなく、動的なHPCQC環境を処理できる、完全に統合され適応可能なスケジューラの基礎となる構成要素を確立したものであることを強調している。