Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks

技術要約：Toffoliネットワークにおけるコンテキスト検証済み・エラー予算考慮型分解選択

1. 問題定義

NISQ（中規模・ノイズあり量子）ハードウェアにおいて、回路の失敗は2量子ビットゲートのエラーによって支配されており、これらは単一量子ビットエラーよりも1〜2桁悪い。その結果、コンパイルされた回路の実効的なフィデリティは、実行される2量子ビットゲートの数と種類によって決定される。Toffoli (CCX) ゲートは量子算術および可逆論理の基本的なプリミティブであり、アンシラ、深さ、および2量子ビットゲート数をトレードオフする様々な分解手法が存在する。

核心となる課題は、「最も安価な」既知の分解法（具体的には、特定の基底状態に対して対角位相を導入する相対位相Toffoli、および有界な誤差を導入する近似Toffoli）が、特定の**コンテキスト（文脈）**においてのみ正しいという点である。それらの残留位相は、ダウンストリームでアンコンピュート（逆演算）されるか、あるいは実際に遭遇する特定の状態に対して誤差が許容範囲内に留まる必要がある。既存のツールは、以下の間のギャップを埋めることができていない：

• コンテキストを考慮しているが検証されていない最適化器（例：QContext、Maslovのテンプレート）：これらはゲート数に基づいてコンテキスト依存の安価な分解を選択するが、ハードウェアのフィデリティモデルを欠いており、さらに決定的なのは、選択された分解が特定の回路コンテキストにおいて有効であることを検証しない。これは、パターンマッチングによる置換が回路を破損させる「サイレントな」エラーを引き起こす。
• 検証済みだがコンテキストに依存しない最適化器（例：VOQC、Quartz）：これらは書き換えが正しいことを証明するが、それは無条件かつコンテキストフリーな等価性としてのみ証明されるものであり、ハードウェアの不正確さではなくゲート数に対して最適化を行う。

この結果、安全上のリスクが生じる。相対位相Toffoliの、カウントのみを重視した攻撃的な置換は、周囲の回路が残留位相をキャンセルしない場合、サイレントに誤ったものとなる。

2. 手法

著者らは、ゲート数ではなく、ハードウェアの2量子ビット不正確さのエラー予算を最小化するように、Toffoliごとの分解を選択するコンパイラパスを提示する。このパスは、以下の3つの柱に基づいている：

1. コンテキスト解析（許容性）： 各Toffoliゲート $g$ について、周囲の回路に基づく許容可能な分解の集合 $A(g)$ を計算する：

   • **厳密な分解（Exact decompositions）**は常に許容される。
   • 相対位相分解は、残留する対角位相 $D$ がダウンストリームで観測不可能である場合（例：計算／アンコンピュートのペアにおける後続の逆操作によってキャンセルされる場合）に許容される。
   • 近似分解は、誤差が全 $2^n$ の入力に対してではなく、到達可能部分空間 $R(g)$（アップストリームの回路と初期アンシラ状態から実際にゲートに到達可能な状態のスペクトラム）上で許容誤差 $\epsilon$ 以内である場合に許容される。
   • パスは、健全性を確保するために、サポート集合が大きくなりすぎる場合にはオーバーアプロキシメーション（アフィン・スーパーボックス）を用いることで、計算基底に対する健全な前方集合伝播を用いて $R(g)$ を構築する。

2. インスタンスごとの検証ゲート： 構造的なルールを暗黙的に信頼することはない。コンテキスト依存の置換を確定する前に、パスはコンテキストを条件とした等価性の義務を果たす：

   • 相対位相については、元のCCXと候補となる分解が、ダウンストリームのキャンセルを考慮した上で、到達可能な入力に対して同一の測定分布を与えることを検証する。
   • 近似については、到達可能部分空間における誤差境界を検証する。
   • 検証は、小さなウィンドウについては逐一（真理値表／ユニタリ）で行われ、より大きなウィンドウについては決定グラフバックエンド（MQT QCEC）やZX正規化を用いて行われる。チェックに失敗した場合、パスは最も安価な「認証済み」の代替案（通常は厳密な分解）にフォールバックする。

3. エラー予算目的関数： セレクターは、合計2量子ビット不正確さ $B = \sum_g I(d_g)$ を最小化する。ここで $I(d)$ は分解 $d$ に含まれる2量子ビットゲートの不正確さの総和である。この目的関数はハードウェア固有であり、ターゲットデバイスの校正済みエラー率を使用する。選択は貪欲法（Greedy）であり、分離可能なケースに対して最適である。アンシラの共有が制約を生む場合は、整数線形計画法（ILP）として定式化される。

3. 主な貢献

本論文の主な貢献は以下の4点である：

1. 初のエラー予算駆動型セレクター： ゲート数ではなく、ハードウェアの2量子ビット不正確さを最適化するコンパイラパスであり、特にコンテキスト依存のToffoli選択に特化している。
2. インスタンスごとの検証レイヤー： コンテキスト条件付きの等価性義務を果たすまで、相対位相または到達可能部分空間の分解を認めないメカニメントを提供し、攻撃的な選択を健全にする。これには、健全性定理（Theorem 1）と有界誤差予算の合成（Corollary 1）が含まれる。
3. 到達可能部分空間の許容基準： 全入力に対してではなく、コンテキスト内で実際に到達可能な状態に対して分解を認証する技術的中核である。これにより、「到達可能範囲での厳密性」に基づくコントロールのドロップ（定数制御を持つToffoliの除去）が可能になり、全ユニタリ近似コンパイルよりも多くの分解を許容できる。
4. 安全性に関する結果： パターンマッチングによる相対位相の置換が、実際にはサイレントに誤りを含むことを実証した。著者らは、展開されているオープンな最適化器に66個の非等価なライブラリ書き換えが含まれており、カウント重視の接近法が12個のベンチマーク回路のうち6個をサイレントに破損させたのに対し、ゲート付きのパスは0個のエラーを認証したことを示している。

4. 結果

評価は、徹底的な検証のための12回路セット（最大8量子ビット）と、スケーラビリティのための20回路セット（12–24量子ビット）の2つのスイートを用いて行われた。

• 安全性： ゲート付きパスはすべてのサイレントエラーを排除した。カウント重視の置換および検証なしのコンテキスト解析の両方が12回路中6個を破損させた一方で、完全なゲート付きパスは0のエラーを導入した。
• エラー予算の削減：
  • 計算／アンコンピュートが重い12回路セットにおいて、ゲート付きパスは、厳密なみのベースラインと比較して、2量子ビットゲートを39.5%削減し、推定不正確さを36.7%削減した。
  • Qiskit opt-level-3 および tket と比較すると、それぞれ約39%および35%の削減となった。
  • より大規模な12–24量子ビットセットでは、集計された削減率はゲート数で15.6%、不正確さで11.7%であった。
  • この削減はワークロードに強く依存する：Grover AND-ladder オラクル（完全にペアリングされている）では約49%の削減、キャリー・ルックアヘッド加算器では約28%、リップル加算器では約6%、配列乗算器では0%（ANDが「ライブ」であり簡略化できないため）であった。
• スケーラビリティ： 検証バックエンドは効果的にスケールする。24量子ビットまでの回路において、決定グラフによるチェックは、すべての受け入れられた置換を0.025秒未満で認証した。逐一検証から決定グラフ検証へのクロスオーバーは約11–12量子ビット付近で発生し、3000倍以上の高速化を実現している。
• 実世界への適用： 量子状態リセット（同期ワード）回路において、本パスはネイティブ2量子ビットゲートの48.8%を削除し、すべての置換が検証された。これにより、予算制限のある同期実験が可能となった。
• ハードウェアへの関連性： 超伝導（IBM, Google）および捕捉イオン（IonQ, Quantinuum）デバイスの現在のエラー率において、認証された置換は推定回路不正確さを36–43%低下させる。

5. 意義と主張

本論文は、コンテキストを考慮しているが検証されていない最適化器と、検証済みだがコンテキストに依存しない最適化器の間のギャップを埋めることを主張している。その中心的な結果は、安全性保証である。パターンマッチングによる相対位相の置換は、インスタンスごとの検証なしには本質的にリスクが高い。著者らは、彼らのアプローチが、インスタンスごとに証明可能な形で安全な、フィデリティ駆動型の攻撃的なToffoli選択を可能にすると断言している。

本研究はすべての最適化問題を解決することを目的としているわけではない。以下の制限を明示している：

• 境界近似領域（$\epsilon > 0$ の分解を認める領域）は、現在の集合ベースの到達可能性判定においては、基底状態を追跡しており振幅を追跡していないため、機能していない。このトレードオフを活性化するには、振幅を考慮した到達可能性フロントエンドが必要であり、これは今後の課題とされている。
• ゲート数および不正確さの削減は、回路構造（キャンセル可能なペアの割合）の厳密な関数であり、すべての回路に対する普遍的な定数ではない。

著者らは、このフレームワークが、エラー予算に制限された物理的量子コンピューティングの実行可能性を高める、健全でエラー予算を考慮したレイヤーを提供すると結論付けている。そこでのすべての削減は、健全であることが証明されている。