dSABRE: A SABRE-Style Router for Multi-Core Distributed Quantum Computers

あなたは、大規模で重要なダンスパーティーを主催しようとしていると想像してください。しかし、会場は複数の別々の部屋（コアと呼ばれます）に分かれています。ダンサーたちは量子ビット（qubits）であり、音楽は量子回路（指示のセット）です。

ダンスを成立させるために、ダンサーのペアはときどき手を取り合って一緒に回転する必要があります。もし彼らが同じ部屋にいるなら、簡単に互いの元へ歩いて行くことができます。しかし、もし彼らが異なる部屋にいるなら、壁をただ通り抜けることはできません。彼らは、ある部屋から別の部屋へ移動するための、特殊で高価かつ遅い「テレポーテーション」サービスを利用しなければなりません。このサービスは、EPR ペアと呼ばれる限られたリソースを消費します（これを貴重な「魔法のチケット」と考えてください）。

問題はこうです：ダンサーたちをどのように動かせば、彼らが一緒に踊れるようにしつつ、魔法のチケットを最小限に済ませることができるでしょうか？

これがDSABREが解決する問題です。以下に、この論文がそれを簡単な言葉で説明する様子を記します。

1. 従来の方法の問題点

DSABRE の以前、他のルーター（TELESABREなど）は、問題が発生したときだけ反応する交通整理員のようなものでした。

部屋にダンサーが多すぎて混雑すると、古いルーターは渋滞が発生するまで待ちました。
一度渋滞が発生すると、彼らはダンサーを無理やり外へ追い出そうとしましたが、これにより余分な魔法のチケットが消費されたり、パーティー全体が停止（「デッドロック」）したりすることがよくありました。
また、彼らはダンスの指示を散漫で無秩序な順序で見ていたため、次に誰を動かす必要があるかを予測するのが困難でした。

2. DSABRE の解決策：より賢く先手を打つ管理者

DSABRE は、より賢い戦略を用いる新しい「ルーター」（交通管理者）です。魔法のチケットを節約するために、3 つの主要なトリックを持っています。

A. 「5 項目スコアカード」（より良い意思決定）

DSABRE がダンサーを新しい部屋へ移動させるかどうかを決定する際、単に「パートナーがどのくらい近いか」だけを見るわけではありません。それは5 つの項目からなるスコアカードを使用します。

ステージングコスト: ダンサーが現在の部屋の中でドアに到達するために何歩必要か？
容量ペナルティ: これが最も重要です。もし目的地の部屋がすでにダンサーで満員であれば、DSABRE はその部屋に大きな「悪いスコア」を与えます。ダンサーをその部屋へ送ることを拒否し、その部屋が渋滞になるのを防ぎます。
ホップゲイン: ダンサーを最終的な目的地の部屋に近づける移動に対して報酬を与えます（まだそこに到達していなくても）。
即時ゲイン: この移動により、ダンサーは現在、パートナーにどのくらい近づきますか？
先読み: 今後のダンスにこの移動が役立つかどうかを確認するために、数歩先を覗き見します。

比喩: あなたが家具を移動させると想像してください。古いルーターは、その部屋がすでに箱でいっぱいであったとしても、「近いから」という理由だけでソファを隣の部屋へ押し込んでいました。DSABRE はまず部屋が満員かどうかをチェックし、「いいえ、あの部屋は混雑しすぎているので、ソファを廊下に置いておきましょう」と言います。

B. 「先駆的な避難」（渋滞が発生する前にはがす）

これが DSABRE の秘密兵器です。

古い方法: 部屋が 100% 満員になるまで待ち、パニックになって人々を移動させようとします。
DSABRE の方法: 「需要リスト」を保持します。もし、今後のダンスのために部屋 A がダンサーで溢れかえる予定だと分かっても、部屋 A がすでにほぼ満員であれば、DSABRE は先駆的に、現在踊っていないアイドル状態のダンサーを、ラッシュが始まる前に部屋 A から移動させます。
結果: ラッシュが到着したとき、スペースが確保されています。渋滞も、無駄な魔法のチケットの消費もありません。

C. 「層別マップ」（より良い計画）

DSABRE が今後のダンスを先読みして確認する際、リストを無秩序にスキャンするわけではありません。ダンスの順序を尊重して、層ごとにマップを構築します。

比喩: レシピを読んでいると想像してください。古いルーターは、スープの前のデザート用の材料を読むかもしれません。DSABRE は正しい順序でレシピを読み、次に必要な材料（ダンサー）が何であるかを正確に把握するため、まだ必要ないものを移動させる時間を無駄にしません。

3. 結果：はるかに効率的なパーティー

著者たちは、DSABRE をさまざまなサイズ（25、36、64 のダンサー）の多くの異なる「パーティー」（量子回路）でテストしました。

結果: DSABRE は、以前の最良の方法（TELESABRE）よりも**41% から 44% 少ない魔法のチケット（EPR ペア）**を使用しました。
スケーラビリティ: 最大 360 人のダンサーがいる巨大なパーティーでテストした際、DSABRE は完璧に機能しましたが、古い方法はしばしば停止し、諦めてしまいました。

まとめ

要約すると、DSABREは、多数の小さなチップが相互接続された量子コンピュータを整理するためのより賢い方法です。渋滞が発生するのを待つ代わりに、以下のことを行います。

ダンサーを混雑した部屋へ送る前に容量を確認します。
スペースを作るためにアイドル状態のダンサーを早期に移動させます。
論理的で段階的な順序で移動を計画します。

これにより、チップを接続するために必要な高価な「魔法のチケット」（EPR ペア）が節約され、量子コンピュータがより効率的に動作するようになります。

技術概要：DSABRE – マルチコア分散型量子コンピュータ向け SABRE スタイルのルーター

問題定義
フォールトトレラント量子計算への道筋は、単一のモノリシックチップを超えて、複数の小型量子処理ユニット（QPU、または「コア」）をフォトニックリンクまたはマイクロ波リンクで相互接続する分散型量子コンピュータ（DQC）へと拡張することを必要とする。DQC 上での回路実行には、量子ビット割当、通信プリミティブの選択、およびルーティング/スケジューリングからなるコンパイルパイプラインが伴う。この文脈における支配的な目的は、EPR 消費（もつれペア）の最小化である。なぜなら、EPR 生成は、局所ゲート操作と比較して遅く、ノイズが多く、レート制限されるからである。

TELESABRE などの最先端ルーターは、コア間を回路をルーティングするために SABRE スタイルのヒューリスティクスを利用するが、それらは防御的に混雑に対処する。TELESABRE は、ペナルティを通じて飽和したコアへの着陸を抑制し、先読み情報を破棄することでデッドロックからの回復を試みる。しかし、高密度または大規模なインスタンスにおいて、この反応的アプローチは過剰な EPR ペアを消費するか、あるいは全く収束しないことが多い。本論文が扱う核心的な課題は、能動的な混雑管理の欠如と、コア間設定における既存の先読みメカニズムの非効率性である。

手法：DSABRE
DSABRE は、マルチコアプロセッサ向けに設計された SABRE スタイルのルーターである。これは、Qiskit SabreLayout によって生成された固定された初期レイアウト内で動作し、ルーティング段階、すなわちコア内 SWAP の順序付けと、コア間テレポーテーション（具体的には、論理量子ビットをコア間で移動させる teledata）に焦点を当てる。アルゴリズムは、1 回のイテレーションあたり 4 つのフェーズを持つ先読み駆動ループを実行する：

Drain（排水）: 1Q ゲートと隣接するコア内 2Q ゲートを実行する。
Partition（分割）: 残りのフロント層ゲートを、コア内（ $F_{intra}$ ）とコア間（ $F_{inter}$ ）に分離する。
Score & Apply（スコアリングと適用）:
- $F_{intra}$ が空でない場合、最良のコア内 SWAP を選択する。
- $F_{intra}$ が空の場合、コア間テレポーテーション候補と能動的混雑緩和候補をスコアリングし、最低スコアの移動を適用する。
Checkpoint/Rollback（チェックポイント/ロールバック）: 進捗があった場合に状態を保存する。設定されたイテレーション数で停止した場合、チェックポイントを復元し、強制的に進捗させることでデッドロックから脱出する。

主要な貢献とメカニズム
本論文は、DSABRE の最先端に対する改善を推進する 3 つの特定のメカニズムを特定している：

5 項ゲート中心テレポーテーションスコア:
TELESABRE のグローバルエネルギー推定とは異なり、DSABRE はコア間移動に対して局所的でゲート中心のスコア（ $s$ ）を使用する。このスコアは 5 つの項を組み合わせる：
- ステージングコスト（ $d_{prep}$ ）: 量子ビットを通信ポートへ移動させるために必要なコア内 SWAP。
- 容量ペナルティ（ $c_{cap}$ ）: 空き容量が低いコアへのテレポーテーションを明示的にペナルティ化する項。これにより、ルーターが飽和したコアを洪水のように埋め尽くすことを防ぐ。
- ホップゲイン（ $g_{hop}$ ）: 目標までのコア間距離を短縮する移動に対する方向的な報酬。着陸ポートが最適なステージング位置から遠い場合を補償する。
- フロント層ゲイン（ $\Delta_F$ ）: 現在のゲートに対する物理的距離の即時減少。
- 先読み（ $\tilde{\Delta}_E$ ）: 将来の距離減少の減衰重み付き和。
能動的混雑緩和:
DSABRE は、コア上の明示的な需要ベクトルを維持する。コアが飽和する（需要が高く、容量が低い）前に、ルーターは需要の高いコアからアイドル量子ビットを遠ざける「緩和候補」を能動的に生成する。これらの移動は、同じ目的関数内で（ $\Delta_F=0$ として）スコアリングされ、ゲート駆動の移動と直接競合する。これにより、反応的システムにおいてデッドロックにつながる「排除の連鎖」を防ぐ。
BFS 層コア間拡張セット:
標準的な SABRE はトポロジカル順序で先読みセットを構築するが、これにより無関係なワイヤが混在することがある。TELESABRE は BFS 層を使用するが、ゲートを恣意的に重み付けする。DSABRE は、DAG 上の幅優先探索（BFS）を用いて、層ごとにコア間先読みセットを構築する。重要なのは、各層内で、フロントとワイヤを共有するゲートが最初に放出されることである。先読み減衰は BFS の深さ（ $\gamma^{dep(g)}$ ）に基づいて適用され、近接する後続ノードが信号を支配し、セットがトポロジカル順序よりも厳密に DAG 依存性を尊重することを保証する。

実験結果
著者らは、DSABRE をTELESABREおよびpytket-dqc（ゲートテレポーテーションベースのルーター）と比較評価した。評価対象は、25、36、64 論理量子ビットの MQT-Bench 回路 18 種類であり、グリッド・オブ・グリッド・アーキテクチャ（B-grid および H-grid）を使用している。

EPR 削減: DSABRE は、TELESABRE に対して幾何平均 EPR 消費を**41–44%削減し、pytket-dqc に対して16–68%**削減した。
スケーラビリティ: 64 量子ビットのランダム回路において、TELESABRE はすべてのシードで収束に失敗したが、DSABRE はルーティングを完了した。360 量子ビットまでの量子フーリエ変換（QFT）回路に対するスケーラビリティスイープにより、DSABRE が回路サイズとアーキテクチャの拡大に伴ってその優位性を維持することが確認された。
アブレーション研究:
- 容量ペナルティを除去すると、幾何平均 EPR が（25q で）約 59%、（64q で）約 59% 増加し、これが最も重要なコンポーネントであることが特定された。
- 能動的混雑緩和を無効にすると、64q スイート全体で EPR が 23.4% 増加し、高密度回路（AE、QFT）では 100% 以上増加した。
- BFS 層拡張セットをトポロジカル順序に置き換えると、EPR が 3–11% 増加し、その増加幅はより大きな回路で大きくなった。
コスト感度: 相対的なテレポーテーションコスト（ $c_{tele}$ ）が増加する（フォトニックリンクハードウェアをシミュレート）につれて、DSABRE と TELESABRE の性能差は広がり、高コスト比において DSABRE は最大で約 39% 多くの EPR を節約する。

意義と主張
本論文は、分散型ルーティングが複雑な候補ごとのスコアリング式よりも、先読み信号とアーキテクチャ容量制約が同じスコアリングステップに入ることを保証する方から恩恵を受けることを主張している。能動的混雑緩和と容量を考慮したスコアを統合することで、DSABRE は、防御的かつ反応的なルーターが悩まされるデッドロックと過剰な EPR 消費を回避する。

著者らは、DSABRE を静的割当手法（ハイパーグラフ分割など）や時間意識型スケジューラーと補完的なものとして位置づけている。DSABRE は現在、teledata（状態テレポーテーション）のみを使用しているが、将来の作業において他のプリミティブやバースト実行パスと組み合わせることが可能な堅牢なルーティングエンジンとして設計されていると述べている。結果は、明示的な容量管理が分散型量子コンパイルの拡張に不可欠なコンポーネントであることを示唆している。