QuPort: Topology-, Port-, and Congestion-Aware Compilation for Modular Multi-QPU Quantum Systems

本論文は、3 段階モデルと TPCCAP アルゴリズムを採用して量子ビットマッピング、ポート割り当て、および相互接続混雑を統合的に最適化し、これにより QPU 間トラフィックと通信ボトルネックを最小化するモジュール型マルチ QPU システム向けのコンパイルフレームワークである QuPort を紹介する。

要約

あなたは、ゲストが「量子ビット」（qubits）で、彼らが集まる部屋が「QPU」と呼ばれる小さく独立した量子コンピュータである、巨大で複雑なパーティーを整理しようとしていると想像してください。

昔は、すべてのゲストが一つの巨大なボールルームにいました。「パーティープランナー」（コンパイラ）の仕事は、互いに会話する必要があるゲストが隣同士になるようにすることだけでした。もしそうでなければ、プランナーは彼らが会話できるように人々を移動させ（このプロセスを「ルーティング」と呼びます）なければなりませんでした。

しかし現在、私たちはモジュール型量子コンピュータを構築しています。一つの巨大なボールルームの代わりに、多くの小さく独立した部屋（QPU）を持つ建物を想定してください。いくつかの部屋は廊下でつながっていますが、その廊下は狭く、利用するには高価です。

この論文は、QuPortという新しいパーティープランナーを紹介します。その仕組みを、簡単な比喩を用いて説明します。

1. 3 つの地図

パーティーを計画するために、QuPort は同時に 3 つの異なる地図を参照します。

• ゲストリスト（論理グラフ）： 誰が誰と、どれくらい会話する必要があるか？（一部のゲストは親友で絶えず会話が必要ですが、他のゲストは一度「こんにちは」と言うだけです）。
• 部屋の間取り（物理マップ）： 各小さな部屋の中で、どの椅子が隣り合っていますか？
• 建物の設計図（相互接続グラフ）： 部屋はどのように接続されていますか？直接の廊下があるのか、それとも次の部屋に行くために他の 3 つの部屋を通って歩かなければならないのでしょうか？

2. 大きな問題：「入り口」のボトルネック

2 人の親友を異なる部屋に入れた場合、彼らは廊下を越えて叫ぶ必要があります。しかし、ここには 2 つの大きな問題があります。

1. 叫びすぎ： 異なる部屋にいる親友のペアが多すぎると、廊下が混雑します。
2. 入り口が少なすぎる： 各部屋には限られた数の「通信用入り口（ポート）」しかありません。100 人のゲストを部屋に入れたが、外へ叫ぶ必要があるのがそのうち 5 人だけの場合、一度に外へ出せるのは 5 人だけです。残りは立ち往生します。

3. 解決策：TPCCAP 戦略

QuPort は、誰をどの部屋に入れるかを決めるために、TPCCAPと呼ばれる特別な戦略を使用します。これは 3 つの要素のバランスを取ろうとします。

• 距離： 親友を同じ部屋に留めようとします。異なる部屋に入れなければならない場合は、隣り合った部屋（短い廊下）に配置します。
• 入り口の圧力： どの部屋も、実際に持っている入り口数を超えて使用することを強要されないようにします。入り口が 5 つしかない部屋に、10 人の叫ぶゲストを入れることはしません。
• 廊下の交通量： 叫びを分散させ、単一の廊下が交通量で詰まらないようにします。

4. QuPort がパーティーを計画する方法（アルゴリズム）

QuPort は単に推測するのではなく、最良の配置を見つけるためにいくつかの巧妙なトリックを使用します。

• 重み付きエッジのクラスタリング： 最も強い友情関係から見て、残りを気にする前に、それらのペアを同じ部屋に固定します。
• バランス型貪欲法： 1 人ずつゲストを部屋に割り当て、そのゲストにとって最も理にかなった部屋を選びつつ、部屋が混みすぎないようにします。
• シミュレーテッド・アニーリング： これは「二の踏ん切り」フェーズのようなものです。初期計画の後、2 人のゲストを入れ替えるなどのランダムな小さな変更を試して、パーティーがよりスムーズに進むかどうかを確認します。変更が状況を改善すれば、それを維持します。悪化させる場合でも、一時的に維持して「十分良い」が「完璧」ではない計画に陥るのを避けることがあります。

5. 「遠隔イベント」リスト

ゲストが部屋に割り当てられると、QuPort は特別な指示リストを作成します。

• ローカル命令： 「ゲスト A とゲスト B は部屋 1 にいます。彼らは通常通り会話できます」。
• 遠隔イベント： 「ゲスト A は部屋 1 に、ゲスト B は部屋 2 にいます。彼らは会話する必要があります」。

QuPort は、彼らが廊下を越えてどのように会話するか（レーザー、配線、あるいは魔法を使うかどうか）を決定しません。単にその会話が発生する必要がある場所をマークし、ハードウェアエンジニアに「ここにはこの特定の叫びを処理するためのプロトコルを構築する必要があります」と伝えます。

6. スケジュール

最後に、QuPort はパーティーにかかる時間を推定します。廊下が詰まったり、入り口が不足したりすることなく、同時に発生できる「叫び」の数を数えます。これらの抽象的なルールに基づき、総所要時間（メイクスパン）の大まかな見積もりを提供します。

QuPort が何でないか

この論文は、このツールが何でないかについて非常に明確に述べています。

• 物理的な機械ではありません。
• 量子コンピュータの特定の物理（バッテリーの寿命やレーザーが作り出すエラーの量など）を知りません。
• 実際には部屋を越えて「叫び」を実行するわけではありません。

要約： QuPort は、モジュール型量子コンピュータのための賢い交通管理者です。異なる小さなコンピュータ間で作業を分割する最良の方法を決定し、互いの待ち時間に立ち往生しないようにしながら、実際に存在する入り口や廊下を超えて使用しようとはしないようにします。これは、実際のハードウェアエンジニアが後で「叫び」の技術を開発する最良の方法を考えられるように、指示を準備するものです。

技術概要

技術概要：モジュール型マルチ QPU 量子システム向けトポロジー・ポート・輻輳認識コンパイラ「QuPort」

1. 問題定義

複数の量子処理ユニット（QPU）を相互接続で結合するモジュール型量子アーキテクチャは、単一デバイスとは異なる固有のコンパイル課題を提示する。単一デバイスにおけるコンパイルでは、主要な制約は局所的な結合マップであり、非局所的な相互作用は SWAP 挿入によって解決される。しかし、モジュール型システムでは、異なる QPU 上の量子ビット間の相互作用は単なる「より長い」局所ゲートではなく、希少な通信リソース（相互接続トポロジー、通信ポート、リンク容量）に依存する。

既存のコンパイラは、QPU 間通信を二次的な課題として扱うか、標準的なルーティングに隠蔽する傾向がある。しかし、このアプローチはモジュール型システムには不十分である。なぜなら、単一の結合グラフ上で許容されるマッピングであっても、以下の条件を満たす場合、モジュール型環境では失敗する可能性があるからである。

1. 過剰な QPU 間トラフィックを生成する。
2. 相互接続リンクの少数にトラフィックを集中させ（輻輳を引き起こす）。
3. 通信ポートが不足している QPU に、境界量子ビット（他の QPU と相互作用する量子ビット）を割り当てすぎる。

本論文は、特定の物理的リモートゲートプロトコル（例：光リンク、エンタングルメント生成）の選択に先立ち、局所デバイスの接続性とQPU 間通信を明示的に同時に考慮するコンパイラフレームワークの必要性に取り組む。

2. 手法

QuPort は Qiskit を基盤とした Python ベースのコンパイルフレームワークである。これはリソース使用量を最適化するための 3 段階のシステムモデルと、特定の分割アルゴリズムを導入する。

2.1 システムモデル

フレームワークは、コンパイル問題を 3 つの異なるグラフに抽象化する。

1. 論理相互作用グラフ ($G_L$): 節点が論理量子ビットであり、辺の重みが 2 量子ビット相互作用の頻度または時間的重要性を表す重み付き無向グラフ。
2. 物理結合マップ: 各個別の QPU 内の接続性（例：グリッド、リング、クライク）を表す有向グラフ。
3. QPU 相互接続グラフ ($G_Q$): QPU を相互接続するトポロジー（例：メッシュ、リング、Clos、ファットツリー）を表す無向グラフ。このグラフはホップ距離とリンク負荷の計算に使用される。

システムは、それぞれ $C$ 個の計算量子ビットと $P$ 個の通信量子ビットを持つ $N$ 個の QPU を想定する。論理から QPU への分割 ($\pi$) は、QPU ごとに容量制約 ($C+P$) を遵守しなければならない。

2.2 TPCCAP 目的関数

QuPort の核心は、3 つのコスト項の加重和を最小化するTPCCAP（トポロジー・ポート・輻輳認識分割）目的関数 $J(\pi)$ である。

1. 加重カット距離: $\sum w_{ij} \cdot d(\pi(i), \pi(j))$。相互接続グラフ上で遠く離れた QPU に割り当てられた量子ビット間の相互作用にペナルティを課す。ここで $d$ は最短経路距離である。
2. 通信ポートオーバーフロー: $\sum \max(0, b_q - P)^2$。境界量子ビットの数 ($b_q$) が利用可能な通信ポート数 ($P$) を超える QPU にペナルティを課す。
3. ルーティング済みリンク負荷輻輳: $\sum L_e^2$。相互接続エッジ ($e$) 上の負荷の二乗にペナルティを課し、特定のリンクへのトラフィック集中を抑制する。

2.3 アルゴリズム

QuPort は、分割とレイアウト問題を解決するためのヒューリスティックのパイプラインを実装する。

• Heavy-Edge Clustering: クラスターサイズが QPU 容量を超えない限り、重みの高い論理ペアをクラスターにマージする。
• Balanced Greedy Partitioning: 重み付き次数に基づいて論理量子ビットを 1 つずつ割り当て、QPU 間の負荷をバランスさせながら、既に割り当てられた近隣への配置を報酬として与える。
• TPCCAP Local Search: 容量制約を維持しつつ、$J(\pi)$ 目的関数を削減するために量子ビットを移動させることで、初期分割を洗練させる。
• TPCCAP-SA (Simulated Annealing): 目的関数を増加させる移動を時折受け入れることで局所最小値から脱出する、確率的な洗練段階を追加する。
• Communication-Port-Aware Layout: 分割後、他の QPU との相互作用の総重みである「外部スコア」に基づき、通信ポートを占有する特定の論理量子ビットを選択する。
• Distributed Program Construction: 分散モードでは、フレームワークは QPU 間の 2 量子ビット操作を明示的なリモートイベントとして抽出し、同期バリアを挿入する。一方、局所操作はそれぞれの QPU 結合マップ内でのみルーティングされる。

2.4 スケジューリングとコスト推定

QuPort には、抽象的なコストパラメータを用いて実行時間（メスパン）を近似するトポロジー認識推定器が含まれる。

• 局所コスト: 単一量子ビット、2 量子ビット、および SWAP 操作のゲート実行時間。
• リモートコスト: エンタングルメント生成コスト ($\tau_E$)、古典的往復コスト ($\tau_C$)、およびリモートオーバーヘッド ($\tau_R$) を組み合わせたモデル。
• スケジューリング: 利用可能な通信ポートとリンク容量、および相互接続トポロジーを尊重し、リモート操作を「ラウンド」にパッキングする。

3. 主要な貢献

1. 明示的な 3 段階抽象化: 本論文は、論理相互作用グラフ、物理結合マップ、QPU 相互接続グラフを分離するコンパイラレベルの抽象化を提案する。この分離により、標準的な単一デバイスコンパイラには見えないモジュール固有のコスト（距離、ポート、輻輳）の最適化を可能にする。
2. TPCCAP 目的関数: これらを個別または二次的な課題として扱うのではなく、QPU 間距離、通信ポートの希少性、リンク輻輳を共同で最適化する新規の目的関数。
3. 分散コンパイルパス: 局所回路とリモートイベントを明示的に分離する中間表現を生成するメカニズム。これにより、コンパイラは特定のリモートゲートのハードウェア実装にコミットすることなく、モジュール認識スケジューリングを生成できる。
4. オープンソースフレームワーク: これらのアルゴリズムを Python/Qiskit で実装し、モジュール型コンパイル戦略の研究のための再現可能な環境を提供する。

4. 結果と検証

本論文は、較正されたハードウェア実行時間の結果を報告するのではなく、フレームワークのアルゴリズム構造と正当性に焦点を当てている。

• 正当性: 著者は、分割アルゴリズム（Heavy-edge、Greedy、TPCCAP、TPCCAP-SA）が QPU ごとの容量制約を厳密に満たし、マルチパスルーティング手順がトラフィック重みを保存することを示す形式的な証明（命題 1 および 2）を提供する。
• 検証: フレームワークは、分割入力、レイアウト構築、トラフィック行列に対して検証チェックを強制し、有限で非負かつ対称な値であることを保証する。
• 結果の範囲: 本論文は、特定のプロトコルを上回るとか較正されたエラー率を提供すると主張するものではない。代わりに、フレームワークが定義された抽象制約を尊重する有効な分割と分散プログラムを正常に生成することを示している。

5. 意義と主張

本論文は、QuPort をハードウェア実装ではなくコンパイラレベルの抽象化として位置づける。その意義は以下の点にある。

• コンパイルとハードウェアプロトコルの分離: 論理分割とリモートイベント抽出を、リモートゲートの物理的実現から分離することで、QuPort は特定の相互接続技術（例：光対マイクロ波）が確定する前に、モジュール型コンパイルのアルゴリズム構造を研究することを研究者に可能にする。
• リソース認識マッピング: モジュール型コンパイルには、SWAP の最小化から「カット距離」、「ポートオーバーフロー」、「リンク輻輳」の最小化への転換が必要であることを浮き彫りにする。
• 主張の謙虚さ: 著者は明示的に、フレームワークが較正されたハードウェア実行時間を主張するものではなく、物理的リモートゲートプロトコルを実装するものでもないとしている。「リモートイベント」は、バックエンドがプロトコルを提供すべき場所を示す中間表現である。スケジューリング推定器は、検証済みのネットワーク制御スケジューラではなく、「レイヤーベースの貪欲モデル」として記述されている。

要約すると、QuPort は、モジュール型量子コンピューティングに固有の複雑なリソース割り当て問題に対する構造化されたヒューリスティック駆動のアプローチを提供し、プラットフォームに依存しない方法でトポロジー、ポートの可用性、および輻輳の間のトレードオフを探索するためのツールを提供する。