Improved bounds on stabilizer extent and Clifford rank

技術要約：スタビライザーの広がり（Extent）およびクリフォード階数（Clifford Rank）に関する改善された境界

問題設定
本論文は、量子状態（または演算子）の「スタビライザー階数（stabilizer rank）」と「スタビライザーの広がり（stabilizer extent、またはクリフォード係数ノルム）」の間の定量的関係を扱っている。スタビライザー階数 $\chi(|\psi\rangle)$ は、状態 $|\psi\rangle$ を厳密に分解するために必要な最小のスタビライザー状態の数を測定するものである。スタビライザーの広がり $\xi(|\psi\rangle)$ は、そのような分解における係数の二乗和の最小値を測定する。

ゴッテスマン＝クニル（Gottesman-Knill）の定理は、スタビライザー状態上のクリフォード回路が古典的にシミュレート可能であることを確立しているが、一般的な量子計算には「マジック（magic）」のリソースが必要となる。シミュレーションアルゴリズムは、しばしば非スタビライザー状態をスタビライザー状態へと分解することに依存している。これらのアルゴリズムの効率はスタビライザーの広がりに依存する。なぜなら、小さな係数は効率的なサンプリング（疎化）を可能にするからである。しかし、スタビライザー階数が小さい状態であっても、分解において大きな係数が打ち消し合うことで、理論的に大きな広がりを持つ可能性がある。

中心となる問題は、スタビライザー階数に対する境界が、スタビライザーの広がりをどの程度強く制約するかを決定することである。具体的には、スタビライザー階数 $k$ の状態は、スタビライザー忠実度（最も近いスタビライザー状態とのオーバーラップ）が $2^{-k/C}$（ここで $C$ は定数）によって下限付けられるはずであるという、Mehraban–Tahmasbi [MT25] による定量的予想を調査している。先行研究である Kalra–S-Sinha [KS26] では、ランク $k$ の状態に対して $\xi(|\psi\rangle) \le 2^{O(k \log k)}$ という広がりの上限を確立した。著者らは、この境界を改善し、ランクと忠実度のスケーリングに関する予想を解決することを目的としている。

手法
著者らは、スタビライザー符号空間へのランダム投影と、符号のオーバーラップに基づくクラスタリング引数を組み合わせた新しいアプローチを採用している。

1. 符号の統合によるクラスタリング： 著者らは、状態 $|\psi\rangle$ を $k$ 個のスタビライザー状態に分解することから始める。彼らは「クラスター」を、共通のスタビライザー符号空間に含まれるこれら状態のサブセットとして定義する。Lemma 3.2 を用いて、もし二つの符号空間が大きなオーバーラップ（射影の演算子ノルムで測定される）を持つならば、それらをより大きな次元を持つ共通の符号空間へと統合できることを示す。
2. 二分法（Dichotomy）： クラスタリングのプロセスは、二分法（Lemma 3.3）をもたらす。すなわち、低次元の符号空間が元のスタビライザー項の相当数を包含しているか、あるいは項がほぼ直交するクラスターへと分裂するかである。
   • ケース1（低次元の包含）： 次元 $d$ の符号空間が $r$ 個の項を含む場合、著者らは、任意の $d$ 次元のスタビライザー符号内の状態は、係数の和が $\sqrt{d}$ で抑えられる分解を持つという事実を利用する。
   • ケース2（近直交性）： クラスターがほぼ直交している場合、それらの間の打ち消し合いは限定的である。著者らは、各クラスターの寄与を合算することで広がりを抑えることができる。
3. ランダム投影によるブロック除去： クラスター内の項を扱うために、著者らはランダムなパウリ投影を利用する。符号の制約を満たすランダムなパウリ演算子の固有空間へ投影することで、残りの項のスタビライザーとしての性質を（スカラー倍を除いて）保持しつつ、 $r$ 個のスタビライザー項のブロックを排除することができる。これにより、問題のサイズを帰納的に減少させることが可能となる。
4. クリフォード演算子への拡張： 演算子に対しては、正規化されたチョイ写像（Choi map）を用いてこのフレームワークを適応させる。著者らは、エンタングルメント欠損（entanglement deficit）（最大もつれから不足している ebit の数）という概念を導入する。パウリ投影がこの欠損にどのように影響するか（最大で1増加する）を追跡することで、中間状態を最大もつれスタビライザー状態（これはクリフォードユニタリに対応する）へと分解するコストを制御する。

主要な貢献と結果

1. 改善されたスタビライザー階数–広がり境界 (Theorem 1.1)：
   著者らは、スタビライザー階数 $\chi(|v\rangle) \le k$ である任意の $n$ 量子ビットベクトル $|v\rangle$ に対して、スタビライザーの広がりが以下のように抑えられることを証明した：
   $$\xi(|v\rangle) \le 2^{O(\sqrt{k} \log(k+1))} \|v\|^2$$
   これは、Kalra–Sinha [KS26] による従来の $2^{O(k \log k)}$ という境界に対し、指数の部分で平方根の因子分だけ改善されている。

2. 定量的予想の解決：
   この新しい境界は、スタビライザー忠実度の下限 $FS(|\psi\rangle) \ge 2^{-O(\sqrt{k} \log(k+1))}$ を意味する。これは [MT25] の定量的予想（$2^{-k/C}$ を示唆していたもの）を解決し、指数のスケーリングを平方根の因子分改善したものである。

3. クリフォード階数–係数ノルム境界 (Theorem 1.2)：
   演算に対しても同様の境界が確立されている。クリフォード階数 $\chi_C(A) \le k$ である演算子 $A$ について、二乗クリフォード係数ノルムは以下を満たす：
   $$\Lambda_C(A)^2 \le 2^{O(\sqrt{k} \log(k+1))} 2^{-n} \|A\|_F^2$$

4. 近似スタビライザー階数の下限：
   これらの境界を非スタビライザー状態のテンソル冪に適用することで、近似スタビライザー階数の下限が得られる。任意の固定された非スタビライザー量子ビット状態 $|\phi\rangle$ に対して、その近似スタビライザー階数は以下の通りとなる：
   $$\chi_\delta(|\phi\rangle^{\otimes n}) = \Omega_\phi(n^2 / \log n)$$
   これは、$T$ 状態に関する [MT24] の最良の既知の下限を、任意の非スタビライザー量子ビット状態へと一般化したものである。

5. ブール関数の古典的表現：
   クリフォード階数の境界は、二次位相（quadratic phases）を用いた $n$ ビット AND 関数の厳密な表現に対する下限を導く。必要な二次位相の数 $Q(n)$ は、以下を満たす：
   $$Q(n) = \Omega(n^2 / \log n)$$
   これは、従来の線形下限を改善するものである。

6. 擬似ランダム性と学習：

   • 擬似ランダム性： これらの結果は、近似スタビライザー／クリフォード階数が $O((\log n)^2 / \log \log n)$ であるような、擬似ランダムな状態およびユニタリアンサンブルルの存在を否定する。これは [KS26] における $O(\log n / \log \log n)$ という閾値を改善している。
   • トモグラフィー： 著者らは、スタビライザー階数が高々 $k$ である状態の、時間およびコピー複雑度が $\text{poly}(n) 2^{O(\sqrt{k} \log k)}$ であるトモグラフィーアルゴリズムを導出している。これは [KS26] に基づく最良のアルゴリズムと比較して、指数部においてほぼ平方根の改善を示している。

意義と主張
論文は、導出された境界が、量子状態や演算子の構造的複雑さ（階数）とその係数ノルム（広がり）の間のより強い結びつきを提供すると主張している。広がりをタイトにすることで、著者らは、低スタビライザー階数を持つ状態がスタビライザー状態と極めて小さなオーバーラップを持つことはできないことを示し、それによって、複雑さを隠蔽しうる「打ち消し」の効果を制限している。

その意義は以下の点にある：

• 理論的解決： 定量的予想 [MT25] を、よりタイトな境界をもって解決したこと。
• 一般化： マジック状態のテンソル冪に関する下限を、特定の状態（$|T\rangle$ など）から、すべての非スタビライラー量子ビット状態へと拡張したこと。
• アルゴリズムの改善： 低ランクの状態およびユニタリの学習およびトモグラフィーの複雑性において、指数部でほぼ平方根の改善を実現したこと。
• 古典的複雑性： 二次位相のランクに関する、AND 関数のほぼ二次的な下限を確立し、古典的表現理論における最新の知見を更新したこと。

著者らは、自らの境界 $2^{O(\sqrt{k} \log k)}$ は、並行して行われている研究 [Dut26]（$2^{O(k)}$ を達成）よりも強力であるが、指数が $O(\sqrt{k})$ まで削減可能か、あるいは広がりがランクに対して多項式的に抑えられるのかについては、まだ分かっていないと述べている。現在の境界における対数的な損失は、符号空間を統合する際の次元コストに起因しており、より強力なクラスタリング境界があれば、この因子を取り除ける可能性があると示唆している。