技術要約: MOSAIQC

問題提起

現在の量子コンピュータ、特にNISQ（Noisy Intermediate-Scale Quantum）時代においては、ほとんどの実用的な量子アルゴリズムを実行するために必要な、十分な量子ビット資源と忠実度（フィデリティ）が不足しています。これらのハードウェアの制限を回避するために、「量子回路の切断（quantum circuit cutting）」または「回路の編み込み（circuit knitting）」という手法が登場しました。これは、大規模なアルゴリズムを、利用可能なハードウェア上で実行可能な小さなパーティションに分割する手法です。しかし、このアプローチは、正確な状態再構成に必要なカットの数に対して指数関数的にスケールする、重大なサンプリングオーバーヘッドを導入します。

カットの位置を決定するための既存の最適化フレームワークには、以下のいくつかの決定的な制限があります：

1. スケーラビリティ: 精密な手法（例：混合整数計画法、SMTソルバー）は、しばしば階乗的または指数関数的な計算複雑性を呈し、1000量子ビット規模に迫る回路に対しては実行不可能となります。
2. カット形式の制限: 多くのヒューリスティックは、ワイヤカット（wire cuts）またはゲートカット（gate cuts）のいずれか一方のみを最適化しており、両方を単一の最適化手順内で組み合わせることは稀です。
3. ハードウェアへの適応性: 多くの手法は均質なハードウェア・パーティションを想定しており、不均質な量子バックエンド特有のノイズ特性や接続制約を無視しているため、実行時の忠実度が最適ではなくなります。
4. トレードオフ: サンプリングオーバーヘッドの最小化と、ハードウェアの忠実度（ノイズ低減）の最大化のバランスを取ることは複雑な多目的問題であり、既存のスケーラブルなヒューリスティックはこれらを共同で対処できていません。

手法

本論文では、サンプリングオーバーヘッド、ハードウェアを考慮した配置、および混合ゲート/ワイヤカットを、多項式時間の実行複雑性を維持しながら同時に最適化するように設計されたヒューリスティック最適化フレームワーク、MosaiQCを提示しています。このフレームワークは、階層的な4段階の最適化パイプラインを通じて動作します。

1. グラフ表現

計算オーバーヘッドを削減するため、量子回路とハードウェアのトポロジーは、反復的な有向非巡回グラフ（DAG）の評価に頼るのではなく、コンパクトなグラフ表現へと変換されます。

• 接続グラフ (Connectivity Graph): 量子ビットをノード、2量子ビットゲートをエッジとして表し、ゲート数によって重み付けされます。
• 時間的依存関係 (Temporal Dependencies): パーティション間で量子ビットが共有される場合のワイヤカットを効率的に評価するために、別途保存されます。
• ハードウェア・トポロジー: ノイズ指標（例：$1-q$ および $2-q$ ゲートエラー）とルーティングコスト（Floyd-Warshall最短経路法により推定）をエッジの重みに組み込んだ、重み付きグラフとしてモデル化されます。

2. 初期パーティショニング（ウォームスタート）

フレームワークは、グローバルなグラフ分割を行うために METIS ライブラリを利用します。このステップは、ハードウェアの容量制約を満たす初期解を生成し、その後の洗練のための高品質な開始点を提供します。この段階では、主にゲートカットまたはワイヤカットを個別に扱うことで、ベースラインを確立します。

3. ローカルな洗練 (Local Refinement)

タブー探索 (Tabu Search) アルゴリズムが、ローカルな移動を通じて初期パーティションを反復的に洗練させます。

• パーティションへのノードの追加（容量の範囲内）。
• パーティション間のノードの移動。
• パーティション境界におけるノードの入れ替え。
• 混合カットの評価: コスト関数は、ゲートカットとワイヤカットの両方を明示的に考慮します。オーバーヘッドは $Overhead = (GateCost)^g \cdot 16^w$ （ここで $g$ と $w$ はそれぞれゲートカットとワイヤカットの数）として計算されます。計算を最適化するため、探索中にはこのコストの対数が使用されます。
• ローカル評価戦略: グローバルグラフを再評価する代わりに、フレームワークは量子ビットレベルのグラフ表現に基づくローカルなワイヤカット・ルックアップ戦略を使用し、複雑さを $O((a+1)p \log p)$ まで大幅に削減します。

4. ハードウェアを考慮したパーティション割り当て

実行時の忠実度を最適化するために、MosaiQCは Frank-Wolfeアルゴリズム を用いた 二次割当問題 (QAP) ソルバーを採用しています。

• 目的: 回路のパーティションをハードウェアバックエンドにマッピングする置換行列を見つけ、期待される忠実度を最大化（ノイズを最小化）すること。
• スコアリング: アルゴリズムは、回路パーティション行列とハードウェアノイズ・トポロジー行列の積のトレースを最小化します。ノイズの重みは、異なるスケールを効果的に扱うために対数変換（$w = \ln(1 - \epsilon_{noise})$）されます。
• 適応型コスト関数: QAP評価の計算コストと最適化の質のバランスを取るため、フレームワークは、カットオーバーヘッドをQAP配置スコアに対して正規化する適応型コスト関数（$S_{adapt}$）を使用します。QAPの評価は、毎回のイテレーションではなく、一定の間隔で行われます。

主な貢献

本論文は、以下の具体的な貢献を主張しています。

1. 結合最適化フレームワーク: 単一の手順内で混合ワイヤ/ゲートカットを最適化するヒューリスティックフレームワークであり、これは既存のスケーラブルなツールでは滅多に見られない能力です。
2. ローカル・ワイヤカット評価: 繰り返されるDAGベースの最適化による計算複雑性を軽減する、量子ビットレベルのグラフ表現に基づく戦略。
3. 不均質ハードウェアのサポート: 様々な量子ビット容量とノイズ特性を持つ量子バックエンドをサポートする抽象化レイヤーを提供し、混合サイズのハードウェアパーティションを可能にします。
4. ハードウェアを考慮した配置: 二重重み付きグラフマッチング（Frank-Wolfeにより解決）を用いて、ノイズ低減を明示的に最適化しながらパーティションをハードウェアに配置する手法。
5. スケーラブルなハイブリッド戦略: ウォームスタート初期化のためのグローバルなMETIS分割と、ローカルなタブー探索の洗練を組み合わせ、多項式時間複雑度 $O(k \cdot n_q + m \cdot n_q^3)$ を達成。

結果

フレームワークは、様々なベンチマーク（Adder, BV, AQFT, QAOA, VQEなど）および回路サイズ（6から1000量子ビット）にわたって、Qiskitの回路切断アドオン（Dijkstraのアルゴリズムを使用）および全探索手法と比較して評価されました。

• 実行性能: MosaiQCは、ベースラインと比較して、実行時間において 2.88倍の幾何平均スピードアップ を達成しました。極めて重要なことに、ベースラインが頻繁にタイムアウトしたりメモリオーバーフローに遭遇したりする中で、MosaiQCは1000量子ビットまでの回路を正常に最適化できました。
• サンプリングオーバーヘッド: 本フレームワークは、ベースラインと比較して、カットの数を平均で 16.84%削減 しました。これにより、サンプリングオーバーヘッドの幾何平均改善率は約 $5.38 \cdot 10^{11}\times$ に達しました（オーバーヘッドの指数関数的な性質による）。
• 忠実度の向上: ハードウェアを考慮した配置戦略は、QAPスコアと測定された忠実度の間に強いピアソン相関（$r \approx 0.83 - 0.87$）を示しました。忠実度のベンチマークにおいて、ノイズの重みが優先された場合、MosaiQCはベースラインに対して平均 +19.56% ± 6.17% のローカル忠実度向上を達成しました。
• 収束性: ハイブリッドなウォームスタート・アプローチは、洗練のみを行うアプローチと比較して、収束に必要なイテレーション回数を大幅に削減し、探索の初期段階でオプティマイザが局所解に陥るのを防ぎました。

意義と主張

著者らは、MosaiQCを量子コンパイルツールの必然的な進化として位置づけています。彼らは、量子回路が1000量子ビット規模へと拡大するにつれ、カット配置自体の最適化が計算上のボトルネックになってはならないと主張しています。

本論文は、MosهاییQCが、既存の競合製品では排除されている基本機能（混合カット、不均質ハードウェアサポート、およびノイズを考慮した配置）を加え、実行速度と解の品質の間の優れたトレードオフを実証していると述べています。実用的な回路切断自体が、再構成に必要な指数関数的なサンプリングオーバーヘッドによって根本的に制約されていることを認めつつも、著者らは、MosaiQCが将来の不均質な量子コンピューティングシステムにおけるスケーラブルな回路切断の基礎を築くものであると主張しています。この研究は、スケーラブルなヒューリスティック最適化が、回路切断配置の計算オーバーヘッドを大幅に削減し、現在のハードウェアでは実行不可能であったアルゴリズムの実行を可能にすることを示唆しています。