Learning Noise-Robust Stabilizer Structure via Bell Sampling

技術要約：Bellサンプリングによるノイズに強いスタビライザー構造の学習

問題設定
本論文は、ノイズが存在する状況下で量子状態のスタビライザー構造を学習するという課題に取り組んでいる。低マジック（非スタビライザ性）を持つ純粋状態に対しては、Bellサンプリングを用いた効率的な学習アルゴースリズムが存在するが、現実世界のデバイスはノイズを含む状態を生成する。これらのノイズを含む状態は、理想的な純粋状態に対してパウリチャネルが作用したものとしてモデル化される。決定的な問題は、ノイズが既存の混合状態学習アルゴリズムが依存している「強い」スタビライザー対称性（$\sigma_i \rho = \pm \rho$）を破壊することである。フルランクのノイズを含む状態には、一般に、恒等演算子を除いて正確なパウリ・スタビライザーは存在しない。

著者らは、ノイズを含む状態の**弱いスタビライザー（weak stabilizer）**を学習することを提案している。これは、状態と可換なパウリ演算子の集合（$\sigma_i \rho \sigma_i^\dagger = \rho$）として定義される。パウリチャネルの誤差確率が十分に低い場合、ノイズを含む状態の弱いスタビライザーは、基礎となる理想的な純粋状態のスタビライザー群と一致する。目標は、$\epsilon$-近似的な弱いスタビライザー $\tilde{S}$ を学習することであり、ここで $S \subseteq \tilde{S}$ かつ純粋性の損失 $\Delta\gamma(\tilde{S})$ が $\epsilon$ で抑えられることを満たす。

手法
提案される解決策は、Bell差分サンプルを用いてスタビライザー群を反復的に構築するファインダー・ベリファイア（finder–verifier）スキームを採用している。

1. Bellサンプリングと差分サンプリング: アルゴリズムは、Bell基底で2つの状態を測定するBellサンプリングを用いてビット列を生成する。Bell差分サンプル（2つのBellサンプルをXORしたもの）は、状態のパウリ・サポートを探索するために使用される。ノイズフリーの場合、これらのサンプルはスタビライザー群のセントラライザー（中心化群）内に完全に存在する。ノイズがある場合、サンプルはこのサポートの外側に落ちる（「悪いサンプル」となる）ため、群の構造を損なう。
2. ベリファイア（Verifier）: 候補となる群 $\tilde{S}$ の投影純粋度（projected purity） $\gamma_{\tilde{S}}$ を推定するサブルーチンである。極めて重要な点は、ベリファイアが初期化時に単一のBellサンプルセットを抽出し、すべての適応的なクエリに対してそれを再利用することである。提案された群への更新が純粋度の低下を閾値 $\Delta\epsilon^-$ 以下に抑える場合は受理され、もし低下が $\Delta\epsilon^+$ を超える場合は拒否されることを保証する。これにより、ファインダーは新しいサンプルを検証のために必要とすることなく、適応的に更新を提案できる。
3. ファインダー（Finder）: Bell差分サンプルのバッチを処理して、現在の推測 $\tilde{S}$ への更新を提案するサブルーチンである。これは、ポストセレクション（現在の $\tilde{S}$ と可換なサンプルのみを保持する）と、サンプル・スパンの根基（radical）（そのスパンとその中心化群の共通部分）の解析を通じて、悪いサンプルによる汚染に対処する。
4. レジーム別戦略: アルゴリズムは、ノイズ強度 $\lambda$ と目標精度 $\epsilon$ に基づいて戦略を適応させる。
   • クリーン・レジーム（Clean Regime）: ノイズが非常に弱い場合、十分に大きなサイズの単一のバッチには、悪いサンプルが根基を汚染する前に、ターゲットとなる構造をスパンするための十分な「良い」サンプルが含まれている。ファインダーは根基全体を一度に提案する。
   • 中間レジーム（Intermediate Regime）: ノイズが中程度のとき、単一のバッチでは根基全体が有用であることを保証できない。代わりに、ファインダーは根基からランダムな要素を抽出し、それらを個別にベリファイアに提案する。これは実行時間に $2^t$ のオーバーヘッドをもたらすが、サンプル複雑度は多項式に保たれる。
   • ノイジー・レジーム（Noisy Regime）: ノイズが高い場合、根基は過度に汚染されている。アルゴリズムは「トップダウン」のアプローチに立ち戻り、単一のBell差分サンプルを一つずつ提案する。これにより、$2^{2t}$ のオーバーヘッドが発生する。

主な貢献と結果
本論文は、グローバル脱分極ノイズ（および、より厳格な閾値を持つ任意のパウリノイズ）の下での、スタビライザー構造学習における3つの性能レジームを確立している。

1. クリーン・レジーム（多項式時間およびサンプル）:
   • 条件: グローバル脱分極ノイズに対し、$\lambda \lesssim \min\{0.159, \frac{n\epsilon}{4t}\}$ である場合。
   • コスト: サンプルおよび時間複雑度は、ともに $n, t, 1/\epsilon$ に対して多項式である。
   • 意義: これにより、純粋状態学習アルゴリズム（$\lambda=0$ でのみ効率的）と、アグノスティック（agnostic）学習（$\lambda=0$ であっても $t$ に対して指数関数的）との間のギャップを埋める。
2. 中間レジーム（多項式サンプル、指数時間）:
   • 条件: グローバル脱分極ノイズに対し、$\lambda \lesssim 0.159$ （約16%の総誤差確率）である場合。
   • コスト: サンプル複雑度は多項式のままであるが、時間複雑度は $O(2^t \cdot \text{poly}(\cdot))$ となる。
   • 意義: このレジームでは、ノイズがクリーン・レジームで扱うには高すぎる場合でも、古典的な処理時間を犠牲にすることで、多項式のコピー数での学習が可能となる。
3. ノイジー・レジーム（指数時間およびサンプル）:
   • 条件: 任意の $\lambda < 1$ （グローバル脱分極）または $\lambda < 1/2$ （任意のパウリ）の場合。
   • コスト: 時間およびサンプル複雑度は $O(2^{2t} \cdot \text{poly}(\cdot))$ となる。
   • 意義: これは、状態が最大混合状態になる閾値未満であれば、どのようなノイズレベルでも機能する堅牢なフォールバックを提供する。

任意のパウリノイズについては、閾値はより厳格（$O(1/t)$ にスケール）となるが、これら3つのレジーム構造は維持される。

意義と主張
本論文は、ノイズを含む混合状態からスタビライザー構造を学習するための、最初のエフィシェントな（$n$ および $t$ に対して多項式となる）手法を提供すると主張している。

• ギャップの解消: 理論的な空白、すなわち、正確な約束（promise）に基づく学習者（$\lambda=0$ のみ効率的）と、アグノスティック・トモグラフィー（あらゆる $\lambda$ で指数関数的コスト）との間のギャップを埋めている。
• ノイズ耐性: 「強い」スタビライザーではなく「弱い」スタビライザーを対象とすることで、ノイズによって正確なスタビライザーが破壊された状態にも適用可能としている。
• 実用的な関連性: 著者らは、初期のフォールトトレラント・デバイスにおいて、論理状態はパウリノイズ（例：シンドローム測定によるもの）の影響を受ける低マジック状態であると指摘している。スタビライザー構造とその関連する零度（nullity）$\nu$ を学習する能力は、デバイスの非クリフォード成分の診断に役立ち、基礎となる純粋状態の圧縮トモグラフィーを可能にする。
• 限界: 著者らは、導出された閾値（例：$\lambda \approx 0.159$）は、彼らの解析に基づく十分条件であり、必ずしも根本的な下限ではないことを謙虚に述べている。また、理想的な状態を復元するにはノイズチャネルの知識が必要であり、それは今後の課題であるとも述べている。