Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford$+P_9$ Gates

技術要約：三値Clifford+P9ゲートを用いた多制御Toffoliゲートの効率的な合成

問題提起
多制御Toffoli（MCT）ゲートは、量子回路設計における基本的なプリミティブであり、可逆演算、オラクル構築、および振幅増幅に不可欠である。しかし、その分解は制御量子ビットの数が増えるにつれて、ますますリソース消費が激しくなる。フォールトトレラント・アーキテクチャにおいて、非クリフォード演算（Toffoliゲートなど）は、コストの高いリソース状態の準備と注入を必要とする。従来のバイナリのみの手法は、通常、MCTをより小さなToffoliゲートに分解し、その後Clifford+T集合へと分解するが、これにはTゲートのコスト、補助量子ビットの要件、および回路深さの間のトレードオフが生じる。最近の、条件付きクリーンなアンシラを用いたバイナリ構成は、対数的な深さを達成しているものの、測定補助による逆計算（uncomputation）と古典的なフィードフォワードに依存しており、測定レイテンシやコヒーレントなスケジューリングに関連するオーバーヘッドを導入する。あるいは、近似合成手法も存在するが、それらは厳密な構成を提供するものではない。本論文は、測定オーバーヘッドを回避しつつ、フォールトトレラントな設定において深さと補助量子ビットの要件を改善する、厳密でリソース効率の高いMCT合成の必要性に対処する。

手法
著者らは、三値Clifford+P9フレームワークを用いて、バイナリ部分空間の入出力を持つMCTゲートの厳密な分解を提案する。このアプローチは、論理状態をバイナリ部分空間 $H_{bin} = \text{span}\{|0\rangle, |1\rangle\}$ にエンコードしたまま、非計算的な三値レベル $|2\rangle$ をワークスペースとして一時的に占有することを利用する。

コアとなる手法は、階層的なツリー分解を含む：

1. プリミティブ: 構成は、三値SUMゲート（Clifford）、状態選択的な制御インクリメント $C_2(\text{INC})$（非Clifford）、およびバイナリターゲットの厳密な制御トグル $C_2(X_{01})$（非Clifford）という3つの基本操作を利用する。リソースコストは、非Cliffordゲートを実装するために必要な論理P9注入の数によって測定される。
2. ツリー構造: 制御は、逐次的な再帰的拡張ではなく、バランスの取れたツリーを通じて評価される。
   • リーフブロック: 3つのバイナリ制御が並列にチェックされる。リーフブロックは、SUMゲートと $C_2(\text{INC})$ を使用して、3つの入力すべてが $|1\rangle$ である場合にのみ、制御三値量子ビットを状態 $|2\rangle$ で一時的にマークする。
   • マージブロック: 内部ノードは、2つの子部分木の結果と1つの追加の制御を結合する。これは、クリーンなアンシラ三値量子ビット（$|0\rangle$ に初期化されたもの）と3つの $C_2(\text{INC})$ ゲートを使用する。両方のチャイルドマーカーが $|2\rangle$ であり、かつ中央の制御が $|1\rangle$ である場合、アンシラは $|2\rangle$ に達し、それが中央の制御を $|2\rangle$ へ到達させる。
   • ルート演算: すべての制御がアクティブであることを示すルートマーカーが $|2\rangle$ に達したとき、単一の厳密なトグル $C_2(X_{01})$ がターゲット量子ビットを反転させる。
   • 逆計算（Uncomputation）: 回路を逆転させ、すべてのテンポラリマーカーとアンシラ三値量子ビットを $|0\rangle$ に復元する。

主な貢献と結果
本論文は、バランスの取れた制御幅 $n = 2^h - 1$ に対する厳密なリソース分析を提供し、任意の幅へと構成を拡張する。

• バランスの取れた幅 ($n = 2^h - 1$) に対するリソース効率:

  • P9カウント: この構成は、$6n + 3$ 個の論理P9注入を必要とする。これは、Bocharovら[16]に由来する、状態最高の再帰的アンシラフリー・ベースライン（Baseline B）の正確なP9カウントと一致する。
  • アンシラ三値量子ビット: この構成は、$\frac{n-3}{4}$ 個のクリーンなアンシラ三値量子ビットを必要とする。これは、Baseline Bが要求する $n-2$ 個のアンシラに対して、漸近的に4分の1である。
  • 回路深さ: 独立した部分木を並列に評価することにより、深さは線形な $\Theta(n)$ から対数的な $\Theta(\log n)$ へと減少する。

• トレードオフの境界:
  本論文は、アンシラスペースと非Cliffordコストの間の構成的なトレードオフを特定している。アンシラ三値量子ビットを再利用（同時に生存しているアンシラの数 $A$ を減少）することで、P9カウントは増加する。具体的には、1つの再利用アンシラ（$A=1$）のみを使用すると、P9カウントは $9n - 18$ となり、深さは $\Theta(n)$ となるが、$I(n)$ 個のアンシラを保持することで、P9カウントは $6n+3$ に最小化される。

• 任意の制御幅:
  任意の $n$ に対して、著者らは幅 $m = 2^h - 1 \leq n$ のバランスの取れたコアを選択し、残りの $n-m$ 個の制御を逐次的に付加することで構成を拡張する。これにより、$6n+3$ のP9カウントを維持しつつ、深さは $O(\log m + n - m)$ となる。最悪の場合（例：$n = 2^{h+1}-2$）、深さは $n$ に対して線形にスケールする。

意義と主張
本論文は、提案された分解が、フォールトトレラント領域における、よりリソース効率の高い量子アルゴリズムの設計およびコンパイルのための実用的なビルディングブロックを提供することを主張している。その主な意義は以下の通りである：

1. 深さの削減: 測定やフィードフォワードに頼ることなく、バランスの取れた入力に対して、再帰的な三値ベースラインの線形深さを対数深さに置き換える。
2. アンシラの削減: 既存の最良の厳密な再帰的ベースラインと比較して、非Clifford（P9）コストを維持しながら、クリーンなアンシラ三値量子ビットの漸近的な要求量を4分の1に削減する。
3. 厳密な合成: 多レベルシステムにバイナリ情報を埋め込む、近似合成レジームとは異なる、厳密な構成戦略を提供する。

著者らは、バランスの取れたケースでは対数的な深さが得られる一方で、任意の幅に対する最悪のケースの深さは線形のままであることを指摘している。彼らは、今後の課題として、より詳細なフォールトトレラント・コストモデル（マジックステート蒸留やルーティングを含む）、代替の中間三値設定、および算術回路のようなより大きな可逆的サブルーチンへの統合を探索することを提案している。