Exponentially Compressed and Garbage-Free Alias Sampling for Polynomial State Preparation

技術要約：多項式状態準備のための指数関数的圧縮およびガベージフリー・エイリアス・サンプリング

問題提起
ブロックエンコーディング、量子化（qubitization）、および量子特異値変換（QSVT）に基づく量子シミュレーションアルゴリズムは、効率的な量子状態準備に大きく依存している。中心的なサブルーチンは、古典的に指定された振幅を持つターゲット状態への、全ゼロ状態 $|0^n\rangle$ のマッピングである。エイリアス・テーブルを事前に計算して利用することで、このような状態をコヒーレントに準備する手法として「エイリアス・サンプリング」が提案されているが、標準的な実装には決定的なスケーラビリティのボトルネックが存在する。$n$ 量子ビットの状態に対して、明示的なエイリアス・テーブルを構築・保存するには、古典および量子リソースが $n$ に対して指数関数的（$\Theta(2^n)$）に必要となり、大規模なシステムへの適用は不可能である。さらに、標準的なコヒーレント・エイリアス・サンプリングは、出力状態がソース・インデックスおよびフラグメント位置を含む補助レジスタ（「ガベージ」）と絡み合った状態になってしまうため、クリーンで独立したターゲット状態の準備を妨げる。

本論文は、振幅がグリッド上で評価された実多項式 $p$（次数は高々 $d$）の値に比例する「多項式状態」の準備に対処する。著者らは、エイリアス・サンプリングを、コストを $n$ および $d$ に対して多項式時間で抑えつつ、同時に絡み合った補助レジスタを除去するように適応できるかどうかを調査している。

手法
提案される解決策は、$N=2^n$ 個のエントリを持つ明示的なエイリアス・テーブルの代わりに、多項式の構造から導出されたコンパクトかつ暗黙的な表現を用いるものである。手法は以下の主要な段階を経て進行する：

1. コンパクトなエイリアス・テーブルの構築:
   すべての $N$ 個のエントリを列挙する代わりに、著者らはインデックスを、ライト（$v_i < Z$）、ヘビー（$v_i > Z$）、およびバランス（$v_i = Z$）のグループに分割することで、「順序付けられたエイリアス・テーブル」を構築する（ここで $Z$ は正規化定数である）。これらのグループをインデックス順に並べることで、累積確率和を用いてテーブルのエントリをオンザフライで計算できる。

• 暗黙的表現: 著者らは、区間上の平方多項式の累積和が、有限差分から導出された $2d+1$ 個の整数係数（$\kappa_k$）を含む閉形式の公式を用いて評価できることを示している。これにより、フルテーブルを構築することなく、可逆な整数演算を用いて任意のテーブル・エントリ（保持閾値およびエイリアス・インデックス）を計算することが可能となる。
• 複雑性: テーブルの古典的な記述には $O(d(n+B))$ ビットが必要となる（ここで $B$ は算術幅）。量子回路は、ゲート数 $\tilde{O}(ndB)$ でこれらをコヒーレントに評価する。

2. ファイバー・ランキングによるガベージフリー準備:
   補助的なガベージ（ソース・インデックス $i$ およびフラグメント位置 $z$）を除去するために、著者らは**ファイバー・ランキング（fiber ranking）**技術を導入する。

• ランキング: 彼らは、各ソース・フラグメント $(i, z)$ を、出力 $y = \pi(i, z)$ 内のユニークな位置 $t$ に写像する全単射（ランキング）を定義する。
• 逆ランキング: ランク $t$ を計算し、その後に逆ランキングを適用することで、元のソース・レジスタ $(i, z)$ を再構成し、それらを $0$ に XOR して戻すことで、事実上ガベージを消去する。
• 一様状態の消去: 残されたランク状態 $t$ は、サイズ $v_y$（ファイバー体積）の範囲内で一様に分布している。著者らは、制御された $v_y$ による逆一様状態準備回路を適用し、ランク・レジスタを $|0\rangle$ に戻すことで、システムをクリーンな状態にする。

3. 決定論的回路の構築:
   プロセス全体は、決定論的な Clifford+T 回路として実装される。この回路は、必要な閾値、ランク、および体積を計算するために、高速な可逆整数演算（乗算、除算、および比較）を利用する。この回路は、ポストセレクションや測定を回避する。

主な貢献

• 指数関数的圧縮: 本論文は、多項式状態に対して、エイリアス・テーブルを $n$ および $d$ に対して多項式のリソースで表現・評価できることを示しており、コストを $\Theta(2^n)$ から $\tilde{O}(ndB)$ へと削減している。これは、多項式の低次元な記述を利用して、累積和とテーブル・エントリを暗黙的に計算することで達成される。
• ガベージフリー準備: 著者らは、コヒーレント・エイリアス・サンプリングによって生成される補助レジスタをアンコンピュート（uncompute）するための新しい技術を開発した。入力フラグメントに連続したランクを割り当て、逆ランキングを用いることで、測定やポストセレクションなしにソース・レジスタを正常にクリアすることに成功した。
• 完全なゲート数: 多項式状態を準備するための決定論的回路が構築されている。総ゲート数は $\tilde{O}(ndB + B^2)$ である（ここで $B = \tilde{O}(dn + d \log(d+1))$）。高精度限界（固定された $n, d$ に対する忠実度 $\epsilon$）において、ゲート数は $O(\log^3(1/\epsilon) \log \log(1/\epsilon))$ とスケーリングする。
• 古典的有用性: コンパクトなエイリアス・テーブルの記述は、古典的なサンプリング・アルゴリズムにも適用可能であり、フルテーブルを構築することなく効率的な古典的サンプリングを可能にする。

結果
本論文は、順序付けられたエイリアス・テーブルの妥当性と、ファイバー・ランキング／アンランキング手順の正当性に関する厳密な証明を提供している。

• 定理 1: 多項式時間で計算可能なコンパクトなエイリアス・テーブルの古典的記述の存在を確立し、$\tilde{O}(ndB)$ ゲートでのコヒーレントな評価を可能にする。
• 定理 2: ターゲットとなる多項式状態が、導出されたゲート数境界を用いて、理想的な状態 $|\psi\rangle \otimes |0\rangle_{aux}$ とのユークリッド距離 $\epsilon$ 以内で、決定論的に結合出力として準備できることを証明する。
• 効率性: 本手法は、$d$ および係数のビット長が $n$ に対して多項式的に制限されている場合、明示的なテーブル手法に対して指数関数的な改善を実現する。

意義
本論文の構成は、エイリアス・サンプリングをクリーンな多項式状態への効率的な経路にすることを主張している。これは、多くの高度な量子シミュレーションアルゴリズムにとって前提条件となるものである。指数関数的なリソースの必要性を排除し、ガベージ・レジスタを消去することで、本手法は、波の伝搬や微分方程式などの、多項式的な初期データを含む問題に対するブロックエンコーディングおよび量子化技術の実用的な適用を可能にする。本研究は、補助レジスタがデータの分布構造に合わせたランキング技術を用いて体系的にアンコンピュートできることを示すことで、サンプリングに基づく初期状態準備の新たな研究方向を切り拓くものである。