Resource-Efficient Synthesis of Sparse Quantum States

技術要約：疎な量子状態の資源効率の高い合成

問題提起
量子状態準備は、ハミルトニアンシミュレーション、線形ソルバー、機械学習を含む数多くの量子アルゴリズムにおける基本的なサブルーチンである。しかし、任意の $n$ 量子ビット状態を準備するには一般に $\Omega(2^n)$ の回路サイズが必要となり、大規模なシステムに対しては資源効率が悪くなる。一方で、多くの実用的なアプリケーションは「疎な」状態（非ゼロ成分がわずかであるベクトル）のみを必要とするが、既存の合成手法は、誤り耐性量子計算（FTQC）における重要な指標を最適化できないことが多い。具体的には、FTQCにおいて、非クリフォードゲート（Tゲートなど）はクリフォードゲートよりも大幅に実装コストが高い。現在の疎な状態合成法は、非クリフォードゲートの数が多い、あるいは回路の深さが過大になる傾向があり、線形な深さを維持しつつ非クリフォード資源を明示的に最小化しようとするアプローチはほとんど存在しない。

手法
著者らは、$s$-疎な $n$ 量子ビット状態の合成を、2つの異なる最適化されたタスクに分解する新しい手法を提案している：

1. 重み付きW状態の生成： 第一ステップでは、疎な状態の振幅をエンコードする、一般化されたW状態 $|W(\vec{\alpha})\rangle = \sum \alpha_i |e_i\rangle$ を準備する。論文では2つの構成戦略を提示している：

   • ツリーベース構成： 二分木構造に基づく帰納的な定義を用いた、アンシラフリーの厳密な手法。この手法は $RY(\theta)$ ゲートを利用し、$O(n)$ のサイズと $O(\log n)$ の深さを達成する。著者らは、これらの回転をClifford+T集合にコンパイルできる条件を分析しており、一様なW状態は大幅なTゲート削減を可能にすることを指摘している。
   • フル状態構成： $\lceil \log_2 n \rceil$ 量子ビット上のフル状態を準備し、基底状態をW状態の基底へと写像する代替アプローチ。この手法は、フル状態準備に関する最新の最適化結果（Gossetら）を活用することで、FTQC領域においてより優れたTカウントを実現するが、より多くのアンシラを必要とする。

2. 古典的可逆回路による置換： 第二ステップでは、W状態の基底状態 $|e_i\rangle$ を、ターゲットとなる疎なベクトルの特定の基底状態へと写像する。これは、バイナリ文字列上の置換問題としてモデル化される。

   • 著者らはこれを、古典的な可逆ゲート（X, CX, CCX）に対応する基本行操作を用いた、バイナリ行列 $M_\chi$ の対角化へと還元している。
   • 並列な消去ステップを利用して回路の深さを最小化する、新しい変種のガウス・ジョルダン消去法を導入している。
   • 主要な最適化として、ターゲットとなる量子ビットが操作後に必ず $|0\rangle$ であることが保証されている場合に、高価なToffoli (CCX) ゲートを、測定と古典制御ゲートを含む「適応的クリフォード回路」で置き換える手法を用いている。これにより、置換回路を $O(s)$ のTカウント（または測定によるゼロTカウント）および $O(s+n)$ の深さで実装できる。

主な貢献と結果

• 資源効率： 提案されたアルゴリズムは、非クリフォードカウントが疎度 $s$ に対して線形（$O(s)$）であり、回路の深さが疎度と量子ビット数の両方に対して線形（$O(s+n)$）である疎な状態を合成する。これは、深さが $O(sn)$ であったり、非クリフォードカウントが超線形であったりする最先端の手法を改善している。
• 誤り耐性コンパイル： Clifford+T ゲートセットにコンパイルする際、著者らはTカウント、深さ、およびアンシラ数のトレードオフを提供する3つの構成法を提供している。
  • 最もTカウントを最適化した構成は、$O(\sqrt{s \log_2(1/\epsilon)} + \log_2(1/\epsilon))$ のTカウントを達成する。著者らは、これがGossetらによる「フル」状態準備の最適性境界と一致していることを指摘しており、この構成が疎な状態に対しても最適である可能性が高いことを示唆している。
• 特殊ケースの最適化： 「T-一様」な疎な状態（非ゼロ成分が $\{e^{ik\pi/4}\}$ の集合にある場合）について、著者らは、ダーティ・アンシラを用いて、成功確率 $> 1/2$ で $O(\sqrt{s})$ 個のTゲートのみを使用する厳密な合成を実証している。
• 行列対角化技術： 本論文は、並列のCXおよびCCX操作を用いたバイナリ行列の対角化のための具体的なアルゴリズムを寄与しており、これが置換回路のコアエンジンとして機能する。

意義
本論文は、主に誤り耐性量子計算における非クリフォードゲートの資源ボトルネックに対処している点において、その意義を主張している。振幅の準備（W状態）と基底の置換を切り離すことで、非クリフォード資源が全量子ビット数ではなく、疎度に対して線形にスケールする合成法を実現している。回路の深さも $s$ と $n$ に対して加法的（additive）に改善されており、これは従来の文献に見られた乗法的（multiplicative）な依存関係に対する大幅な改善である。

著者らは、提案手法がTカウントと深さにおいて非常に効率的である一方で、既存のいくつかのアプローチと比較して、より多くの補助量子ビット（具体的には $\max(s, n) - n$）を必要とする可能性があることを控えめに述べている。また、クリフォードフレンドリーな操作を最大化するためのツリー構造の最適化は、分割問題に関連するNP困難な古典的問題であることを指摘し、今後の課題として、特定のハードウェア接続制約への可逆回路論理の適応や、ディケ状態（Dicke states）へのアプローチの一般化を挙げている。