Optimised T counts and active volume estimates for high- and low- level arithmetic subroutines

タイトル：高次および低次算術サブルーチンにおける最適化されたTカウントとアクティブボリュームの推定

著者： Sam Heavey (インペリアル・カレッジ・ロンドン)

問題提起

表面符号ベースの量子コンピュータは、フォールトトレラント量子計算の有力な候補である。しかし、局所接続された量子ビットの2次元配列に依存する従来の「ベースライン」アーキテクチャは、重大な非効率性を抱えている。これらの計算における時空ボリュームの大部分は「アイドル（待機）」状態であり、これは特定の操作中に使用されずに置かれている論理量子ビットに対応している。このアイドルボリュームは、論理計算に寄与することなく、全体の計算リソース（時空ボリューム）を増大させる。

「アクティブボリューム（AV）」アーキテクチャは、操作を並列化するために長距離接続を利用することで、このアイドルボリュームを排除することを目指しているが、最適化された算術サブルーチンの包括的なカタログと、正確なアクティブボリュームの推定値は不足している。既存の文献は、多くの場合、ベースラインアーキテクチャにおけるTカウントの削減に焦点を当てており、特に状態注入や反応的測定が関与する場合に、回路構造がいかにアクティブボリュームに影響を与えるかを完全には考慮していない。

手法

本論文は、低次（例：インクリメント、シフト、加算）および高次（例：平方根、三角関数、対数）の算術サブルーチンに対するアクティブボリュームとTカウントを導出し、最適化するための手法を提案する。

1. 最適性の仮定： 本研究は、ベースラインアーキテクチャにおいてTカウントと量子ビット数を最小化する回路設計が、最小のアクティブボリュームをもたらすという仮定に基づいて動作する。これにより、著者はあらゆる可能な設計バリエーションに対してアクティブボリュームを計算するのではなく、Tカウント（具体的にはToffoliゲートおよび一時的ANDゲート）の最小化に集中することができる。
2. ゲートセットの最適化： 著者は、特定の操作のTカウントを半分にするために、「一時的AND」ゲート（Gidneyによって導入されたもの）を利用する。また、Toffoliゲートおよび一時的ANDゲートの実装には、T状態ではなくCCZマジック状態を用いることを選択している。これは、アクティブボリュームモデルにおいてCCZ蒸留の方が安価であることが多いためである。
3. 配向型ZX図によるアクティブボリュームの計算：
   • 標準的な回路図をZX図に変換し、さらに配向型ZX（OZX）図へと変換する。
   • OZX図は空間的な認識を取り入れ、スパイダーを3次元時空ブロックの特定のポート（U、D、N、S、E、W）にマッピングする。
   • OZXの接続性の制約内でZX計算則（スパイダーの結合など）を適用することにより、図を簡略化し、最小限の論理ブロック（スパイダー）の数をカウントする。
   • 総アクティブボリュームは、スパイダーのブロック数の合計に、必要なマジック状態（例：CCZ状態）の蒸留コストを加算することで算出される。
4. 反応深度（Reaction Depth）の分析： 論文では、非クリフォードゲートに対する補正操作を決定するための古典的処理に要する時間である「反応深度」を考慮している。総反応深度は、逐次的なコンポーネントの深さの合計として計算され、計算時間の理論的な上限を提供する。

主要な貢献と結果

1. 低次算術サブルーチン
本論文は、Qiskitシミュレーションによって検証された、基礎的な操作のための最適化された回路を提示している：

• インクリメントおよび制御インクリメント： 一時的ANDゲートを使用するように修正されており、Tカウントを（インクリメントで $7n - 14$、制御インクリメントで $7n - 7$ へ）削減している。
• シフト： アクティブボリュームアーキテクチャにおいては、ラベルの付け替えを通じて、制御なしのシフトは「無料」（論理ブロックコストがゼロ）であることを示した。制御付きシフトは、ZXスパイダーの結合を用いて最適化されているが、非最適化バージョンと比較したブロック数の減少は限定的である。
• 制御加算・減算（CAS）： 新しいGidneyスタイルの制御加算器を設計した。これは、コストの単純な総和と比較して約8%のアクティブボリューム削減を達成し、Tカウントは $7n - 7$ である。
• 乗算： ToffoliアレイとControlled Overflow Gidney (COG) 加算器を用いた新しい乗算器を提案している。これは、Muñoz-Coreas & Thapliyal [21] の最先端のデザインと比較して、Tカウントの主要項を62%削減している。
• 平方（Squaring）： 量子ビット数をCNOTゲートとトレードオフにすることで最適化されており、乗算における量子ビット要件を $6n+2$ から $5n$ へと減少させている。これには平方のための特定の設定が含まれる。

2. 高次算術サブルーチン
著者は、これらの低次コンポーネントを高次の関数へと拡張している：

• 平方根： 最適化された非復元型平方根アルゴリズムを提示している。これは、主要なデザイン [19] と比較してTカウントを大幅に削減しているが、量子ビット数はわずかに多く必要となる（$3n$ 対 $2n+1$）。
• 三角関数（区分的多項式評価 - PPE）： HänerのPPE回路を適応させている。元の加算器および乗算器を著者の最適化されたバージョン（OG加算器、COG乗算器）および新しい比較器に置き換えることで、元の実装 [20] と比較して、主要項のTカウントを約3分の2削減している。
• 逆三角関数（アークサイン）： 多項式評価と平方根を組み合わせた回路を構築した。この新設計は、Hänerの実装 [20] と比較して、Tカウントの $n^2$ 項をほぼ6分の1に削減する。
• 対数： WangらによるqFBE法の実装を、アクティブボリューム計算用に適応させている。本論文は、この手法に対するアクティブボリュームとTカウントの推定値を初めて提供しており、それが量子操作において $O(n^3)$ であることを指摘している。

3. アクティブボリュームの構造的感度
重要な知見として、回路構造はゲート数とは独立してアクティブボリュームに影響を与えることが挙げられる。著者は、ゲート数が同一であっても、制御とターゲットの配置によって論理的に等価な回路が異なるアクティブボリュームを持つことを実証している。具体的には、制御とターゲットの途切れないラインを最大化する設計は、ZX計算におけるより効率的なスパイダー結合を可能にし、ブロック数を減少させる。これは、アクティブボリュームアーキテクチャにおいては、ゲート数のみを最適化するだけでは不十分であることを示唆している。

意義と主張

本論文は、配向型ZX図を用いてアクティブボリュームを推定および最適化するための「単純な手法」を提供することを主張している。その主な意義は以下の通りである：

• リソースの削減： 主要な量子アルゴリズム（例：素因数分解、HHL）の構成要素となる幅広い算術サブルーチンのTカウントおよびアクティブボリュームを大幅に削減している。
• アーキテクチャへの意識： 「アクティブボリューム」という指標が、単なるゲートの複雑さではなく、回路のトポロジーに敏感であることを強調している。これは、長距離接続を持つアーキテクチャのために、回路設計のあり方を変える必要があることを示唆している。
• カタログの拡充： アクティブボリューム計算の文脈において、これまで不足していた最適化されたサブルーチン（$\log x$ や $\arcsin x$ などの高次関数を含む）という必要なリソースを提供している。

著者は、自身の研究はTカウントとアクティブボリュームに焦点を当てているものの、今後の研究では、クリフォードゲートの最適化や、キャリー・ルックアヘッド加算器や除算回路のような他の低次サブルーチンの導入も考慮すべきであると結論づけている。彼らは、すべてのリソース推定問題を解決したと主張しているのではなく、AV（アクティブボリューム）を意識した回路設計へのさらなる調査を促すことを目的としている。