SpiderLS: Leveraging Full ZX Reduction for Lattice Surgery Compilation

技術要約：SpiderLS: フルZX簡約を活用した格子手術コンパイル

問題提起

フォールトトレラント量子計算（FTQC）は表面符号に大きく依存しており、そこでは論理演算は格子手術（パウリ積測定（PPM）を通じてエンコードされた量子ビットパッチを結合および分割すること）によって実装される。このパラダイムにおける決定的なボトルネックは、論理回路を効率的な格子手術の実装へとコンパイルし、時空コスト（空間領域とタイムステップの積）を最小化することである。

近年のアプローチでは、意味保存的な変換を可能にする中間表現（IR）としてZX計算量（ZX-calculus）を利用している。しかし、TopoLSなどの既存のZXベースのコンパイラは、ZXスパイダーと格子手術ジャンクションの一対一の対応関係を維持するために、ZX簡約を制限している。論理パッチの平面幾何学的な性質により、単一のジャンクションは最大4つの接続（2つの空間的接続、2つの時間的接続）しかサポートできない。その結果、これらのコンパイラは、基礎となる格子手術モデルがマルチパッチ測定による高次（high-arity）の相互作用をサポートしているにもかかわらず、次数が4を超えるスパイダーが生じるような「フル」なZX簡約を実行することができない。この制限は、コンパイラがZX計算量の完全な最適化の可能性を活用することを妨げ、結果として、不適切な時空ボリュームと複雑な埋め込み探索による高いコンパイルオーバーヘッドを招いている。

手法

著者らは、ZXスパイダー表現を物理的なジャンクションの制約から切り離すことで、次数4の制約を克服する格子手術コンパイラであるSpiderLSを提案する。コンパイル・パイプラインは、主に4つのステージで進行する：

1. フルZX簡約と実行順序付け：
   SpiderLSは、入力されたClifford+T回路をZXダイアグラムに変換し、PyZXのfull_reduce()ルーチンを適用する。先行研究とは異なり、このプロセスは4エッジのジャンクション制限に縛られないため、高次スパイダーの生成が可能となる。コンパイラは、簡約されたグラフから直接実行順序を導出する。これはアクティブな「フロンティア」スパイダーの集合を保持し、実行可能な相互作用（CZ操作）とアダマール移動を反復的に抽出することで、簡約されたグラフを実行可能な一連の操作へと効果的に線形化する。

2. ターゲットコード生成：
   実行シーケンスはターゲットプログラムへとグループ化される。SpiderLSは、共通の制御量子ビットを共有する複数のCZゲートが、単一のマルチターゲット操作（例：$CZ^{(k)}(q_c; q_1, \dots, q_k)$）に結合できるという観察を利用している。位相操作（SゲートおよびTゲート）はスパイダーの位相から抽出され、Tゲートはマジック状態注入を介して処理される。このステージでは、マルチターゲットCZ、単一量子ビットゲート、およびアダマールからなるコンパクトなターゲットプログラムが生成される。

3. PPM低次化と論理スケジューリング：
   ターゲットプログラムは、一連の単位時間PPMへと低次化される。決定的なのは、高次CZ操作がマルチパッチ測定（例：3ターゲットCZは、4パッチの$M_{ZZZX}$測定と標準的な$M_{ZZ}$測定になる）へと分解されることである。コンパイラはその後、これらのPPMを論理レイヤーにパッキングする論理スケジューリングを行う。ここでは、無制限のアネシラ・スケジュールの深さを維持しつつ、必要な内部アネシラ量子ビットの数を最小化する戦略を採用している。

4. レイヤード時空ルーティング：
   （TopoLSのように）レイヤーごとにグローバルな埋め込み問題を解くためにモンテカルロ木探索（MCTS）を使用する代わりに、SpiderLSは構造認識型のローカルルーティングを行う。論理スケジュールの確定後、コンパイラは互換性のあるパウリ境界を選択し、A*探索を用いてパスを構築することで各PPMをルーティングする。もし限定されたローカル探索内で有効なルートが見つからない場合は、その操作は後の物理レイヤーへと延期される。この「コミットまたは延期」戦略は、グローバルなレイヤー埋め込みの指数関数的な探索空間を回避し、コンパイル時間を大幅に短縮する。

主な貢献

• 格子手術のためのフルZX簡約： 本論文は、ZXスパイダーが必ずしも有界次数のジャンクションに一対一でマップされる必要はないことを示している。マルチパッチ測定を活用することで、SpiderLSはフルなZX簡約を可能にし、ジャンクションの制約を満たすために断片化されていた相互作用の集約を実現している。
• マルチターゲット操作のグループ化： コンパイラは、共有制御相互作用を識別して単一のマルチターゲット操作へとグループ化し、総論理操作数を減少させ、より効率的な時空パッキングを可能にする。
• 構造認識型ルーティング： 論理スケジューリングと幾何学的ルーティングを分離し、グローバルなMCTSではなく限定的なローカル探索を使用することで、SpiderLSはコンパイルの複雑さを劇的に軽減する。
• 実装と評価： 著者らはSpiderLSの完全な実装を提供し、最先端のコンパイラ（Liblsqecc、DASCOT、およびTopoLS）と比較評価を行っている。

結果

多様なアルゴリズム的（例：Bernstein-Vazirani、QAOA、QFT）およびランダムなClifford+T回路を用いて評価した結果：

• 時空ボリューム： SpiderLSは、TopoLSと比較して時空ボリュームにおいて平均**49.2%**の削減を達成した。この削減は主に、相互作用のグループ化とマルチパッチ測定を通じて実現されたタイムステップ数の減少によるものである。
• コンパイル時間： SpiderLSは、TopoLSと比較してコンパイル時間を**99.8%**削減した。MCTSベースの埋め込みから限定的なローカルルーティングへの移行により、先行するZXベースのコンパイラの主要なボトルネックが解消された。
• スケーラビリティ： SpiderLSは、回路ベースのコンパイラ（Liblsqecc、DASCOT）と同等の低いコンパイルオーバーヘッドを維持しながら、それらよりも優れた時空効率を実現している。問題サイズが増大しても一貫したボリューム削減を示し、回路幅に対して効果的にスケールする。
• マジック状態需要： 時間的な深さを圧縮しているにもかかわらず、SpiderLSはTopoLSと同等かそれ以下のTポート密度を維持しており、時間的圧縮がマジック状態の需要を制御不能な程度に集中させていないことを示している。

意義

本論文は、格子手術コンパイルのためにZX計算量の完全な表現力を活用することの実際的な利点を、SpiderLSが実証していることを主張している。ZXスパイダーが物理的なジャンクションに直接マップされなければならないという人工的な制約を緩和することで、コンパイラはよりコンパクトな時空実現を生成できる。本研究は、これまでマッピングが困難と考えられていた高次相互作用が、マルチパッチ測定を通じて効率的に実現可能であることを確立している。さらに、提案された構造認識型ルーティング手法は、グローバルな埋め込み探索の法外な計算コストを負うことなく、高品質な格子手術コンパイルが可能であることを証明しており、大規模な量子プログラムに対する効率的なコンパイルを現実的なものにしている。