Sparse quantum state preparation with improved Toffoli cost

技術要約：改善されたToffoliコストによる疎な量子状態準備

問題提起
量子状態の準備は、量子計算における基本的なプリミティブであり、線形システムソルバーから量子機械学習、量子シミュレーションに至るまで、幅広いアプリケーションに不可欠です。一般的な状態準備については広く研究されていますが、疎な量子状態（sparse quantum states）——$n$個の量子ビット上で、$s \ll 2^n$個の非ゼロ計算基底状態のみを含む状態——には、特化した効率的なアルゴリズムが必要です。

フォールトトレラント量子計算において、主要なリソース指標はしばしばToffoliゲート（およびTゲート）の数となります。これは、これらの非クリフォード演算が、マジック状態蒸留のオーバーヘッドにより、クリフォードゲートよりも実装コストが大幅に高いためです。既存の疎な状態準備のアプローチは、一般に以下の2つのカテゴリに分類されます：

1. 反復的構成法（Iterative construction）: 各基底状態を準備する$s$ステップで状態を構築します。これは通常、$s \lceil \log(s) \rceil$を超えるToffoliコストを要します。
2. 2ステップ・アプローチ（密な準備 + 等長写像）: まず $\lceil \log(s) \rceil$ 量子ビットのサブレジスタ上で密な状態を準備し、次に等長写像（isometry）を介して対象の疎な状態へとマッピングします。密な準備のコストは最適化されていますが（例：Grover-Rudolphアルゴリズム）、等長写像のステップが歴史的にボトルネックとなってきました。Malvettiらによる従来手法では、等長写像の最悪計算コストとして $s(\lceil \log(s) \rceil - 1)$ のToffoliコストを必要とし、これがアルゴリズム全体のコストを支配しています。

手法
著者らは、等長写像ステップを最適化し、それを密な状態準備と統合する洗練された2ステップ・フレームワーク（図1に図示）を提案しています：

1. バッチ化された等長写像の構成:
   核心となる革新は、等長写像回路を構築するための新しい古典的アルゴリズムです。Malvettiらが行ったように、各$s$個の状態に対して非サブスペース量子ビットをゼロにするために個別の多制御Xゲートを適用するのではなく、著者らは状態をサイズ $m$ のバッチにグループ化します（ここで $m$ は利用可能な非サブスペースレジスタに収まる最大の2のべき乗、すなわち $m \le n - \lceil \log(s) \rceil$）。

   • 各バッチについて、アルゴリズムは、非サブスペースレジスタが異なる位置に単一の $|1\rangle$ を持つ形式（例：$|k\rangle_s |e_0\rangle_r, \dots, |k+m-1\rangle_s |e_{m-1}\rangle_r$）へと状態を変換します。
   • その後、**部分ユニタリ反復（Partial Unary Iteration: PUI）**回路を適用することで、バッチ全体の非サブスペースレジスタを同時にゼロにします。

2. 部分ユニタリ反復（PUI）回路:
   著者らは、アドレスレジスタの全空間ではなく、特定の区間 $[l, r]$ を反復する2種類のPUI回路を導入しています：

   • 制限付きPUI（Restricted PUI）: ユニタリ操作がターゲット区間 $[l, r]$ 内の状態に対してのみ適用されることを保証します。
   • 無制限PUI（Unrestricted PUI）: アドレス値が $r$ より大きい状態に対しても非自明なユニタリを適用することを許容します。この緩和により、Toffoliカウントが大幅に減少します。「不要な」高次アドレス値への影響は、古典的に追跡され、後続のステップやバッチで修正されます。

3. 密な状態準備との結合最適化:
   著者らは、等長写像のコストと密な状態準備のコストのトレードオフを分析しています。彼らは、密な準備から特定のサブタスクを等長写像へ「アウトソーシング」することを提案しています：

   • 符号修正（Sign Fixes）: 密な準備の後に角度レジスタを逆計算（uncompute）する代わりに（これには符号修正のための追加のToffoliが必要になります）、制限付きPUIを用いて符号情報を等長写像に直接エンコードします。
   • 実数状態（Real States）: 純粋に実数の係数を持つターゲット状態の場合、密な準備の位相エンコーディングステップを完全に削除し、それを等長写像内で処理することで、密な準備のToffoliコストを最大3分の1程度削減できる可能性があります。

主な貢献

• 改善された等長写像アルゴリズム: 等長写像回路を、最悪計算コストが以下で抑えられるように構築する新しい古典的アルゴリズム（Algorithm 1）を提案しています：
  $$\left\lceil \frac{s}{m} \right\rceil \left( 2m + \frac{\log(\tilde{s}/m)}{2} - 3 \right) + \log(\tilde{s}^2/m)$$
  ここで $\tilde{s} = 2^{\lceil \log(s) \rceil}$ です。これは、Malvettiらによる最先端の手法と比較して、およそ $\log(s)/2$ の改善を示しています。
• PUIのバリアント: 制限付きおよび無制限の部分ユニタリ反復回路の定義とコスト分析。無制限バージョンは、操作の「漏れ（leakage）」を高次アドレス値に許容することで、より低いToffoliカウントを実現します。これは、バッチ化された等長写像の文脈において管理可能なものです。
• リソース・トレードオフ分析: 疎な状態準備の結合されたToffoliコストと量子ビットコストに関する包括的な分析（表1）。これにより、等長写像を最適化することで、特に実数値の状態において、密な準備のコストを削減するためにアンシラ量子ビットをより良く活用できることが示されています。
• 実装: 回路は Qualtran フレームワークで実装されており、古典的な等長写像探索アルゴリズムは、SIMD加速されたRustコードを用いて最適化されています。

結果

• 理論的境界: 等長写像の最悪Toffoliコストは、$n$ が十分に大きい場合、$O(s \log s)$ から約 $O(s)$ に減少します。具体的には、ランダムな状態を用いた数値ベンチマークにおいて、コストは $n$ の増加に伴い、従来の最良値である約 $s \log s$ から 1 に近づきます。
• 数値ベンチマーク:
  • ランダムな $s$-疎な状態に対して、$s$ あたりのToffoli数は $n$ が増加するにつれて 1 に近づきます（図2、右）。
  • 純粋に実数である状態の場合、結合最適化によって、一般的な複素数状態と比較して総Toffoli数が大幅に減少します（図9）。
  • 古典的アルゴリズムは効率的に動作し、標準的なCPUハードウェア上で $s=10^7$ 個の状態に対する等長写像を約10〜20分で発見します。
• 比較: 提案手法は、量子ビットのオーバーヘッドを同等またはそれ以下に維持しながら、Toffoliカウントにおいて既存の文献（例：[4, 14, 20, 21]）を凌駕しています。

意義と主張
本論文は、Toffoli数および量子ビット数の観点から、最も効率的な疎な状態準備回路を提示していると主張しています。その意義は以下の通りです：

1. ボトルネックの除去: 等長写像のコストを、密な準備と同等のレベルまで低減させることで、アルゴリズム全体をより効率的にします。
2. スケーラビリティ: 手法は量子ビット数 $n$ に対して良好にスケールするため、$s$ が大きいが $s \ll 2^n$ である大規模なフォールトトレラント量子アルゴリズムに適しています。
3. 実用性: 本手法は、既存のフォールトトレラント・リソース推定フレームワーク（Toffoliカウントに焦点を当てたもの）と互換性があり、モジュール化されたソフトウェアフレームワーク（Qualtran）で実装されています。

著者らは将来的な影響について謙虚な姿勢を保っており、現在はToffoli数が標準的な指標であるが、マジック状態生成（培養/蒸留）の進展により、将来的に焦点が実行時間指標へとシフトする可能性があると述べています。また、限られたアンシラリソースを用いて、$s$ に対して劣線形（sub-linear）なToffoliコストが達成可能かという問いも、今後の課題として残しています。