技術要約：適応性がすべてである：単一コピー測定のみを用いた最適なスタビライザー学習

1. 問題提起

スタビライザー状態は、量子誤り訂正、フォールトトレラント計算、および効率的な古典シミュレーションの基礎となる。中心的な運用上の問いは、未知の $n$ 量子ビット・スタビライザー状態を、実験データからいかに効率的に同定できるかである。

先行研究は、測定戦略に応じてサンプル複雑性に大きな差があることを示した：

• 2コピー・ベルサンプリング： Montanaro [9] は、ペアに対する結合ベル測定を用いることで、$\Theta(n)$ 個のコピーがあればスタビライザー状態を学習できることを示した。これは情報理論的に最適である。
• 非適応的単一コピー測定： 文献 [10] は、測定が単一コピーに限定され、かつ（過去の出力に依存しない）非適応的な測定手法である場合、サンプル複雑性が $\Omega(n^2)$ に跳ね上がることを示した。

本研究が取り組む未解決の問いは、適応的単一コピー測定（現在のコピーの測定基底を、過去の出力に基づいて選択する手法）を用いることで、複数のコピーへのコヒーレントなアクセスを必要とせずに、この二次的なギャップを埋め、最適な $\Theta(n)$ スケーリングを達成できるか、という点である。

2. 手法

コアアルゴリズム：適応的スタビライザー学習

著者らは、$\Theta(n)$ 個の単一コピー適応測定のみを用いて、任意の $n$ 量子ビット・スタビライザー状態を学習する多項式時間アルゴリズム（Algorithm 1）を提案している。このアルゴリズムは、未知の状態を計算基底状態へと漸次的に変換するための古典的フィードバックに依拠している。

主要メカニズム：

1. 初期化： 恒等クリフォード回路 $C = I$ から開始する。目標は、$C|\psi\rangle = |z\rangle$（ここで $|z\rangle$ は計算基底状態）となるようなクリフォード $C$ を見つけることである。
2. 反復ラウンド： 各ラウンドにおいて、現在の変換された状態 $C|\psi\rangle$ の2つの独立したコピーを計算基底で測定し、出力 $x$ と $y$ を得る。
3. 差分サンプリング： ビットごとの差分 $u = x + y$ を計算する。スタビライザー状態の場合、もし $u \neq 0$ であれば、このベクトルは計算基底において対角ではないスタビライザー生成子の $X$ 成分を特定する。
4. 適応的更新：
   • アルゴリズムは、$u_i = 1$ となるピボット指数 $i$ を特定する。
   • 特定されたスタビライザーを、形式 $(e_i, v')$ へと写す CNOT ベースのクリフォード演算 $F_u$ を適用する。
   • 決定的な点として、$F_u$ は、既存の $Z$ 型スタビライザーがピボット量子ビット $i$ 上で自明に作用するように $i$ が選択されているため、既に見出されたすべての対角（$Z$ 型）スタビライザーを保存する。
   • 新しいスタビライザーを $Z$ 型に変換するために、ランダムな局所補正（$H_i$ または $H_i S_i$）を適用する。
5. 終了： このプロセスを繰り返し、既知の対角スタビライザー部分空間の次元を単調に増加させる。次元が $n$ に達すると、状態は計算基底状態となり、最終的な測定によって完全に決定される。元の状態は $|\psi\rangle = C^\dagger |z\rangle$ として回収される。

拡張

本論文では、この適応的メカニズムを以下の3つの追加シナリオに拡張している：

• 耐性学習（Tolerant Learning）： 混合状態または非スタビライザー入力 $\rho$ に対して、最も近いスタビライザー状態を、忠実度 $F_{\text{stab}}(\rho) > \sqrt{2/3}$ の条件下で学習する。アルゴリズムは候補リストを生成し、古典シャドウを用いて忠実度を推定する。
• 耐性テスト（Tolerant Testing）： スタビライザー状態への忠実度が $\ge 1-\epsilon_1$ である状態と、$\le 1-\epsilon_2$ である状態を区別する。
• メモリ支援型テスト： $k$ 量子ビットのコヒーレント量子メモリを用いてテストを行い、単一コピー（$k=0$）と2コピー（$k=n$）のレジームを補間する。
• 低スタビライザー・ヌリティ（Low Stabilizer Nullity）： スタビライザー・ヌリティ $r$ を持つ純粋状態（スタビライザー部分空間の次元が $n-r$ である状態。これには、限定された数の非クリフォードゲートによって準備された状態が含まれる）の学習。

3. 主要な貢献と結果

A. 最適な単一コピー学習

主要な結果は、適応性が単一コピー学習と2コピー学習の間のギャップを完全に埋めることを証明したことである。

• 定理 II.1： 未知の $n$ 量子ビット・スタビライザー状態は、適応的な単一コピー測定のみを用い、$N = O(n + \log(1/\delta))$ 個のコピーを用いて確率 $1-\delta$ で学習できる。
• 複雑性： アルゴリズムは、ラウンド数 $T = O(n + \sqrt{n \log(1/\delta)} + \log(1/\delta))$ に対して、多項式時間 $O(n T^2)$ で動作する。
• 最適性： これは結合測定に対して既知の $\Theta(n)$ 下限と一致しており、この設定においてコヒーレントな複数コピーへのアクセスは、最適なサンプル複雑性を達成するために必要ではないことを証明している。

B. 耐性学習とテスト

• 耐性学習 (Theorem III.1)： 入力 $\rho$ が $F_{\textabox}(\rho) \ge f_0 > \sqrt{2/3}$ を満たすとき、アルゴリズムは $O(n + \xi^{-2}\log(1/\delta))$ 個のコピーを用いて、最適値から忠実度 $\xi$ 以内のスタビライザー状態を出力する。
• 耐性テスト (Theorem IV.1)： 著者らは、スタビライザー状態への忠実度が $\ge 1-\epsilon_1$ である状態と $\le 1-\epsilon_2$ である状態を、サンプル複雑度 $O(n + \frac{\epsilon_2}{(\epsilon_2-\epsilon_1)^2} \log(1/\delta))$ で区別する多項式時間テスターを提供する。これは、単一コピー測定による効率的な耐性テストの実現可能性に関する未解決問題を解決するものである。
• 下限： 本論文は、純粋な入力に対して $\Omega(n + \frac{\epsilon_2}{(\epsilon_2-\epsilon_1)^2})$ 個のコピーが必要であることを確立しており、提案されたテスターの最適性を裏付けている。

C. メモリ・サンプル間のトレードオフ

• 定理 V.1： $k$ 量子ビットの量子メモリを用いたスタビライザーテストにおいて、最適なサンプル複雑度は $\Theta(n - k + 1/\epsilon)$ である。
• 示唆： サブリニアなサンプル複雑度（$\Theta(n)$ より優れたもの）を達成するには、ほぼ全状態（$k \approx n$）を保持しなければならない。$k=0$ の場合、複雑度は $\Theta(n)$ であり、$k=n$ の場合、$\Theta(1)$ に低下する。

D. 低ヌリティ状態の学習

• 定理 VI.1： スタビライザー・ヌリティ $r$ を持つ状態（$t$ 個の T ゲートを含む $t$-ドープされた状態を含む）は、$O(2^r(n + \log(1/\delta)) + 2^r \epsilon^{-2}(r + \log(1/\delta)))$ 個のコピーを用いて学習できる。
• メカニズム： 適応的な圧縮は $2^r$ 倍の係数で減速する。なぜなら、有効なスタビライザー方向を明らかにする差分サンプルは $2^{-O(r)}$ の割合しかないからである。しかし、「無害な」サンプルは、既存の対角構造を破壊することはない。

4. 重要性と主張

本論文は、古典的な適応性だけで、サンプル最適となるスタビライザー学習が可能であると主張しており、コヒーレントな複数コピーへのアクセスを不要にしている。これは以下の理由から重要な発見である：

1. ギャップの解消： 非適応的な単一コピー学習（$\Omega(n^2)$）と2コピー・ベルサンプリング（$\Theta(n)$）の間の二次的な分離は、非適応的な制限によるアーティファクトであり、単一コピー測定の根本的な限界ではないことを示している。
2. 実験的実現可能性： アルゴリズムは、単一コピーに対するクリフォード演算とその後の計算基底測定のみを必要とするため、コヒーレントな複数コピーの保持が困難な現在の実験的制約と高い親和性を持つ。
3. 構造的洞察： 本研究は、スタビライザー学習が「自然な構造化設定」であることを強調している。測定結果は二重の役割を果たす：データを供給すると同時に、状態を簡略化しつつ以前に発見された構造を保持するような変換を特定する。
4. より広い文脈： 著者らは、適応性が（ボゾン・ガウス型トモグラフィーやスタビライザー学習のような）特定の構造化されたタスクには役立つものの、トレース距離における一般的な混合状態のトモグラフィーに対して漸近的な優位性をもたらすわけではないことを指摘している。本研究は、適応性が有益となる境界線を明確にしている。

本論文は、低ヌリティ状態に対する $2^r$ への乗法的依存を、加法的依存にできるか、また、サンプル複雑度の主要項の定数を減少させて結合測定の境界に一致させられるか、といったオープンな問題を挙げて締めくくられている。