General circuit mapping algorithm for neutral atom quantum computers

技術要約：中性原子量子コンピュータのための汎用回路マッピング・アルゴリズム

問題提起
中性原子量子コンピュータ（NAQC）は、長いコヒーレンス時間、柔軟な量子ビット配置、およびネイティブな多量子ビットゲート機能（例：CCZ、Ck-phase）を特徴とするスケーラブルなプラットフォームである。しかし、NAQCハードウェア上で量子回路を実行するには、エンタングルメント・ゲート（リドバーグ・ブロック）のために光ピンセットを用いて量子ビットを物理的に移動させ、近接させる必要がある。この「リマッピング」プロセスは、以下のような重大なオーバーヘッドをもたらす：

1. フィデリティの損失： 各転送は、原子の消失や状態変化のリスクを伴う。単一の転送成功率は高い（>0.99）ものの、多くの量子ビットや転送を伴う回路では、累積的なエラーが致命的となる。
2. 時間的オーバーヘッド： 転送は時間を消費するため、計算ウィンドウを縮小させる。
3. 最適化の課題： 既存のコンパイラ（ZAC、MGTなど）は、シミュレーテッド・アニーリングや貪欲法（greedy algorithms）といったヒューリスティックに依存することが多い。これらは従来の手法よりも改善されているものの、必要な転送回数の明示的な理論的下限を提供しておらず、また、モノリシック（M-arch）およびゾーン型（Z-arch）の両方のアーキテクチャにおいて、総移動距離と並列転送操作（PTO）を同時に最適化するための一般的な定式化も提供していない。

手法
著者らは、グラフ理論に基づく組合せ最適化を用いた、統一的かつ回路に依存しない数学的フレームワークを提案している。本手法は、以下の4つの段階で進行する：

1. グラフ表現（理論的基礎）：

   • 量子回路は、頂点が「命令」（特定のステージにおける特定の量子ビットに作用するゲートのグループ）を表し、エッジがステージ間の遷移を表す有向非巡回グラフ（DAG）へと分解される。
   • ステージ間の転送を最小化する問題は、連続するステージ間を接続する二部グラフにおける最大重みマッチングを見つける問題としてモデル化される。
   • 定理 3.1 & 3.2： 著者らは、M-archおよびZ-archの両方における最小転送回数が、これらのマッチングの局所的な最小値の総和によって導出できることを証明している。Z-archの場合、グラフはゾーン固有のサブグラフに分解され、ゾーン間では強制的な転送が発生する。

2. スティック・エンコーディング（問題の簡約化）：

   • 原子配置を最適化するために、著者らは「スティック・エンコーディング」を導入した。この表現は、ステージ間で静止したままの状態にある量子ビットを「スティック」としてグループ化することで、マッピング問題を抽象化する。
   • スティック内には「サブスティック」が存在する。このエンコーディングは、原子グリッド上のスティックの2次元空間座標と、マルチ量子ビット・スティック内のサブスティックが入れ替わっているかを示すブール変数という、内在的な自由度（DoFs）を捉える。
   • このエンコーディングにより、どの量子ビットを動かすかという決定（グラフ・マッチングによって決定される）と、それらの量子ビットの配置を切り離すことができ、移動距離の効率的な最適化が可能になる。

3. 遺伝的アルゴリズム（最適化）：

   • 非線形整数計画問題を解くために、遺伝的アルゴリズム（GA）が採用されている。
   • GAはクロスオーバーを行わず、代わりに局所的なランダム変更（スティックの移動またはサブスティックのシャッフル）に依存して探索空間を探索する。
   • 目的関数は柔軟であり、ユーザーは総移動距離の最小化、あるいは並列転送の最大化、またはその両方の加重結合のいずれかを優先するように設定できる。

4. 並列転送操作（PTO）の構築：

   • 後処理ステップとして、並列転送のシーケンスを構築する。
   • アルゴリズムは転送ダイグラフを分析し、サイクルを検出する。もしサイクルが存在する場合（原子が互いの経路を塞いでいる場合）、サイクルを解消するために「パーキングスペース」（空の原子スロット）を使用し、これにより1回の追加転送が必要となる。
   • その後、貪欲法を用いて転送をスケジューリングし、ハードウェアの制約（例：アコースティック・オプティカル・ディフレクタの制限）との互換性を確保しながら、衝突を避けつつ並列性を最大化する。

主な貢献

• 一般的な数学的フレームワーク： 本論文は、NAQCプラットフォームにおける任意の量子回路に必要な原子転送回数の理論的下限を決定する、初のグラフ理論的定式化を提供しており、これはモノリシックおよびゾーン型アーキテクチャの両方に適用可能である。
• 斬新なエンコーディング： 「スティック・エンコーディング」の導入により、空間配置および内部の量子ビット順序に関連する自由度を分離することで、マッピング問題の複雑さを効果的に軽減した。
• トレードオフの制御： 本フレームワークは、原子の総移動距離（時間の短縮）を最小化することと、並列転送操作（レイテンシの低減）を最大化することの間のトレードオフを明示的に可能にする。
• 理論的保証： 従来のヒューリスティックなアプローチとは異なり、本研究は転送回数に関する証明可能な下限（定理 3.1/3.2）を提供し、提案手法が一貫してこれらの下限に到達することを示している。

結果
著者らは、提案アルゴンドリズムを、最先端のマッパーであるZAC（再利用を考慮したゾーン型アーキテクチャ・マッパー）およびMQT（Munich Quantum Toolkit）と比較してベンチマークを行った。

• 転送回数： 提案手法は、テストされたすべての回路において、理論的な最小転送回数（サイクル解消の要件による0〜2回の差を除いて）を一貫して達成している。対照的に、ZACはしばしばこの理論的最小値を超過する。
• 距離と並列性：
  • 距離を最適化する場合、提案手法はZACと比較して、総移動距離を大幅に削減する（例：QFT回路において約333%の改善）。
  • 並列転送を最適化する場合、提案手法は、特に複雑な回路において、PTOの数に関してZACおよびMQTの両方を上回ることが多い。
• 柔軟性： 結果は、一つのトレードオフを浮き彫りにしている。すなわち、距離を最適化することは、必ずしもPTOを最小化することにはならない。GAを用いることで、実務者は特定のハードウェアパラメータ（例：ツィーザーの移動速度とトラップ切り替え速度の相対関係）に基づいて目的関数を調整できる。

意義と主張
本論文は、効率的な、アーキテクチャを意識した量子回路コンパイルのための、理論的ベースラインと実践的なツールの両方を提供すると主張している。

• 理論面： 最小の転送回数はグラフ・マッチングを通じて決定できることを確立し、将来のコンパイラ開発のためのベンチマークを提供している。
• 実践面： 実務者がハードウェアに即したマッピングを生成することを可能にする、柔軟な最適化ツールを提供する。移動に起因するエラーを減少させ、原子転送の並列性をより良く活用することで、本手法はNAQCデバイス上での実行効率を直接的に向上させる。
• スケーラビリティ： 本アプローチは、様々なゲートセット（多量子ビットゲートを含む）を扱える汎用的かつスケーラブルなものとして記述されており、追加のゾーン（例：CCZゲート用）を持つ将来のNAQCアーキテクチャにも適応可能である。

著者らは、実行時間に関する点については控えめなトーンを維持しており、距離の最小化とPTOの最小化のどちらを選択すべきかは、特定のハードウェアパラメータ（例：SLM/AODの切り替え速度とツィーザーの移動速度）に依存することを述べている。これらはプラットフォームによって異なるため、特定のデバイスに対して最適なソリューションを選択するために、異なるパラメータでマッパーを実行することを推奨している。