Sparse Quantum State Preparation with Sublinear T-Count

技術要約：サブリニアなTカウントを用いた疎な量子状態準備

問題提起
本論文は、Clifford+Tモデルにおける疎な（sparse）量子状態準備のフォールトトレラントなコストを取り扱う。$n$量子ビットの状態は、その計算基底におけるサポート（非ゼロ振幅を持つ項）が最大で$s$個であるとき、$s$-sparseと定義される。一般的な$n$量子ビットの状態準備には、既知の最適Tカウントとして$\Theta(\sqrt{2^n} \log(1/\epsilon) + \log(1/\epsilon))$が存在するが、これまでの疎な状態に関する研究は、希薄度$s$に対する線形依存性に制限されていた。具体的には、近年の研究では、$s$-sparse状態に対して$O(s)$個のTゲートの上限が確立されている。本研究の中心的な問いは、$s$が量子ビット数$n$に対して十分に大きい場合において、$s$-sparse状態を準備するためのTカウントを$s$に対してサブリニア（sublinear）にできるか否かである。

手法
著者らは、状態準備を以下の3つの主要な段階に分解することでこの問題にアプローチしている：

1. ラベル状態準備（Label State Preparation）: $\lceil \log s \rceil$量子ビットのインデックスレジスタ上に密な重ね合わせを準備する。
2. コヒーレント・ローディング（Coherent Loading）: ブール関数を用いて、インデックス$i$を対応する$n$量子ビットデータレジスタ内の基底文字列$x^{(i)}$へと写像する。
3. ラベル消去（Label Erasure）: ラベリング写像の逆操作を適用してインデックスレジスタをアンコンピュート（uncompute）し、データレジスタを目的の状態に残す。

技術的な核心は、サポートされた入力$x^{(i)}$をそのインデックス$i$へと写し戻し、それ以外の入力をゼロへと写す疎なブール関数L: \{0, 1\}^n \to \{0, 1\}^{\lceil \log s \rceilを実装することを含む、「ラベル消去ステップ」の合成にある。著者らは、サポートサイズ$s$に応じて戦略を適応させる、疎なブール関数のための**サポート認識合成定理（support-aware synthesis theorem）**を開発した：

• 小サポート領域 ($s \leq n^{3/2} \log n$): $s$個のサポートされた入力を、単射（injection）を用いて対数サイズのラベルレジスタへと圧縮する。この問題は、$O(\log s)$ビットのブール関数の合成問題へと帰着され、$O(s+n)$個のToffoliゲートで実行可能である。
• 大サポート領域 ($s > n^{3/2} \log n$): 著者らは、プレフィックス長$r$を固定する再帰的アルゴリズムを採用している。各ステップにおいて、アルゴリズムは現在のサポートにおけるアクティブな$r$ビットのプレフィックスを分析する：
  • アクティブなプレフィックスが少ない場合、**プレフィックス圧縮（prefix compression）**を行い、サポートサイズを変更せずに、アクティブなプレフィックスを単射的に再ラベル付けして入力長を短縮する。
  • アクティブなプレフィックスが多い場合、**サポート・ピーリング（support peeling）**を行い、各アクティブなプレフィックスから1つのサポートされた入力を取り除く。この「剥ぎ取られた（peeled）」スライスは安価に実装でき、残りの再帰的なインスタンスは、サポートポイントを大幅に減少させる。
    これら2つの操作のバランスを取ることで、アルゴリズムは$s$に対してサブリニアなスケールとなるToffoliカウントを実現する。

下界（lower bounds）については、2つの異なる手法を用いている：

• 小規模な$s$ ($s = O(n)$): スタビライザー零空間（stabilizer nullity）の議論の拡張。著者らは、W状態 $|W_s\rangle \otimes |0^{n-s}\rangle$ に近い状態に対して、スタビライザー部分群のランクが制限されることを証明し、$\Omega(s)$の線形下界を導いた。
• 大規模な$s$ ($s = \Omega(n)$): [GKW26]のパッキング引数と計数補題を用いた。互いにウェルセパレーテッド（well-separated）な$s$-sparse状態の大きな族を構成し、$t$個のTゲートで準備可能な状態の数を制限することで、$\Omega(\sqrt{ns})$の低界を導出した。

主な貢献と結果

1. サブリニアな上界: 本論文は、誤差$\epsilon$まで任意の$n$量子ビット$s$-sparse状態を、以下のTゲート数で準備できることを確立した：
   $$\tilde{O}\left(\min\left\{s, n^{3/4}\sqrt{s}\right\} + \sqrt{s}\log(1/\epsilon) + \log(1/\epsilon)\right)$$
   これは、サポートが十分に大きい場合（具体的には $s \gtrsim n^{3/2}$ の場合）に、$s$に対してサブリニアな依存性を示す初めての結果である。補助量子ビット（ancilla）の要件は $\tilde{O}(\sqrt{ns})$ である。

2. タイトな下界: 著者らは、$0 < \epsilon \leq 1/6$ および $2 \leq s \leq 2^{n/2}$ において、Tカウントが以下の下界を持つことを証明した：
   $$\Omega(\min\{s, \sqrt{ns}\})$$
   この結果は、小サポート領域（$s = O(n)$）においては線形依存性$s$が避けられないこと、および大サポート領域においては$n$への依存性を完全に取り除くことはできないことを示している。

3. サポート認識合成定理: サポートサイズ$s$を持つ疎なブール関数 $F: \{0, 1\}^n \to \{0, 1\}^b$ を合成するための一般的な定理。Toffoli複雑度は、小規模な$s$では $O(s+n)$ であり、大規模な$s$では $\tilde{O}(n^{3/4}\sqrt{s} + n^{1/4}\sqrt{bs})$ である。著者らは、この結果が状態準備以外にも独立した関心を持ち得ることを述べている。

意義と主張
本論文は、疎な状態準備が$s$に対してサブリニアになり得るかという問いを解決したと主張している。結果は、以前の既知の線形 $O(s)$ の境界は、大きなサポートに対しては固有のものではないこと、すなわち、コストを $\tilde{O}(n^{3/4}\sqrt{s})$ に削減できることを示している。しかし、著者らは自らの上界の最適性については控えめな表現を用いている。彼らは、大サポート領域における上界 $\tilde{O}(n^{3/4}\sqrt{s})$ と下界 $\Omega(\sqrt{ns})$ の間に依然としてギャップが存在することを強調している。

本論文は、クロスオーバーポイントである $s \approx n^{3/2}$ や $n^{3/4}$ という因子が、彼らの特定のアルゴリズムによるアーティファクト（人工的なもの）なのか、あるいはフォールトトレラントな疎な量子状態準備の固有の限界を反映しているのかは不明であると明記している。さらに、小サポート領域におけるブール関数の部分的性質（partial nature）を利用した構成を用いているが、この緩和を大サポートの構成に組み込んでも、現時点では漸近的な境界を改善できないことも指摘しており、部分関数構造のさらなる活用の可能性を未解決の問題として残している。