技術要約：対数深さのフェルミオン・サンプリング

問題設定

量子計算と古典計算の間の証明可能な分離は稀であり、サンプリング問題はその条件付き証拠を最も明確に示すものの一つである。フェルミオン・サンプリングとは、非相互作用のフェルミオンを受動的な線形光学系（passive linear optics）を通じて移動させ、その占有数を測定するものである。占有基底入力を用いたダイナミクスは古典的にシミュレート可能であるが、入力が非ガウス型の「マジック」状態である場合、この問題は計算量的に困難になる。

先行研究では、変換がグローバルなHaarランダム受動アンサンブルから抽出される場合、フェルミオン・サンプリングが反集中性（anticoncentration）（出力確率が指数関数的に多くの結果に分散すること）および平均的な場合の困難性（average-case hardness）（典型的なインスタンスにおいて確率を推定することが困難であること）を示すことを確立した。しかし、このグローバルなランダム性は、$O(n)$ の回路深さと $O(n^2)$ 個の2モードゲートを必要とする。中心的な未解決問題は、この線形な深さが本当に必要なのか、あるいはより浅い対数深さの回路で同じ保証を得られるのかという点であった。

手法

著者らは、$n$ 個のモード（$n$ は4の倍数）に作用する特定の回路アンサンブルを分析している。この回路は、4モードのペアリングされたマジック状態の積として準備される。回路は $t$ 層で構成され、各層は独立してモードの一様完全マッチングを選択し、一致したペアに対して独立したHaarランダム2モード受動ゲートを適用する。

分析は、2つの異なる技術的枠組みに基づいている：

1. 衝突ダイナミクスのスペクトル分析:

   • 著者らは、同一の回路による2回の独立したショットが同じ結果をもたらす確率を、一様分布の値で正規化した衝突比（collision ratio）（$R_{n,t}$）を追跡する。
   • **ハウ・双対性（Howe duality）**と置換対称性を用いることで、衝突のダイナミクスを、指数関数的に巨大な多粒子空間から、$O(n)$ 個の状態（具体的には、2つのレプリカにおける二重占有モードの数に基づく $n/2 + 1$ 個のセクター）を持つ可逆マルコフ連鎖へと簡約化する。
   • 衝突の減衰は、この連鎖の固有値によって支配される。決定的なことに、著者らは入力状態がスペクトル重みを決定することを示している。マジック入力の場合、最も遅い緩和モードの重みは定数に抑えられる一方で、第2のモードの重みは $n$ に対して線形に増加する。これにより、支配的な緩和スケールがシフトする。

2. 埋め込みと補間による困難性の低減:

   • 平均的な場合の困難性を証明するために、著者らは、4つのネイティブ層の浅い深さの中に「困難な」インスタンス（事後選択されたユニバーサル計算）を構築する。
   • これらの困難なインスタンスが、「スイッチ」ゲート（恒等写像またはフェルミオン交換）を用いて、相互作用するモードを共にルーティングすることにより、アンサンブルの典型的なランダム・マッチング・スケジュール内に埋め込まれることを示す。
   • **ケイリー・パス（Cayley path）**補間は、Haarランダムゲートと埋め込まれた困難な回路を接続する。Haarエンドポイントの近くでオラクルにクエリを投げ、有理線形計画法デコーダ（Berlekamp-Welch補間のロバストな変種）を使用することで、困難なエンドポイントの確率を復元する。このデコーダは、追加のNPオラクルを必要とせずに、誤った回答の割合を許容できる。

主な貢献と結果

1. 反集中性における鋭い対数閾値

本論文は、対数深さが反集中性に十分であることを確立している。

• 閾値深さ: 衝突比が受動Haarベンチマークの任意の固定倍数 $q > 1$ に達する深さは：
  $$t^*(q) \approx \frac{\log n}{\log(9/4)} \approx 0.855 \log_2 n$$
• 遷移プロファイル: 遷移は鋭く、明示的な極限プロファイル $R_{n,t}/R_{Haar}(n) \to e^{3z/2}$ （ここで $z = n(4/9)^t$）を持つ。
• 最適性: 2粒子相関から導かれる下界は、これより大幅に早い深さでは有界な衝突比を達成できないことを証明しており、このアンサンブル内での対数スケーリングの最適性を裏付けている。
• 有限ゲートセット: 著者らは、Haar測度の2コピー・チャネルを正確に再現する192個の2モードゲート（$U(2)$ の部分群）の有限アルファベットを特定した。したがって、すべての衝突および反集中性の結果は、この離散ゲートセットに対してもそのまま成立する。

2. 確率推定の平均的な場合の困難性

本論文は、この浅い深さのアンサンブルにおいて、出力確率の推定が平均的に困難であることを証明している。

• 困難性の結果: 実RAMモデルにおいて、少なくとも $3/4 + \gamma$ の割合のインスタンスに対して、固定された半充填出力の確率を加法的誤差 $2^{-O(n \log_2 n)}$ で推定することは、#P困難である。
• メカニズム: 証明は、グラフ状態の測定パターンとフェルミオン型I融合を用いた、最悪ケースの#P困難な計算をランダムなスケジュールに埋め込む。ランダム・マッチングの混合特性により、この埋め込みは高い確率で成功する。
• 堅牢性: この簡約化は、ノイズのある、あるいは誤ったオラクルの応答を処理する有理線形計画法デコーダを使用しており、同様の簡約化でしばしば必要とされるNPオラクルを必要としない。

3. 決定論的ルーティング・バリアント

著者らは、固定された**ベネッシュ・ルーティング・プレフィックス（Beneš routing prefix）**に続くランダム・マッチング層を備えたハイブリッド・アンサンブルを提案している。このバリアントは、すべての困難なインスタンスと出力が埋め込まれることを保証し（失敗確率 $\eta = 0$）、純粋なランダム・マッチング・ケースで必要とされるパディングや漸近的な失敗境界を排除する。

意義と主張

本論文は、フェルミオン・サンプリングの困難性に線形深さが必要かどうかという未解決問題を解決したと主張している。対数深さ（$O(\log n)$）および $O(n \log n)$ 個のゲートが、反集中性と平均的な場合の困難性の両方に十分であることを示すことで、本研究は、フェルミオン系における量子優位性の実証に向けたリソース要件を大幅に引き下げている。

従来の作業との主な相違点は以下の通りである：

• 入力依存のメカニズム: 分析は、マジック入力が最も遅い緩和モードをどのように抑制するかを明示的に追跡している。これは、回路のランダム性に関する一般的な境界が見落としているメカニズムである。
• 正確な有限アルファベット: 192個のゲート・アルファベットによる衝突法則の保持は、連続的なHaarランダム性に依存する以前の結果とは異なり、実装のための具体的な離散ゲートセットを提供する。
• 精緻化された困難性: 証明された加法的誤差の許容範囲は、標準的なサンプリングから計数への議論に必要な $1/N$ スケールよりも精緻である。著者らは、彼らの簡約化が定数全変動距離のサンプリングではなく、高精度な確率推定を対象としていることを明記しており、定数全変動距離へのサンプリングの困難性については依然として未解決問題であるとしている。

本研究は、入力準備（マジック状態）と回路の深さが、計算の困難性を生成する上で果たす役割を分離し、浅い深さのフェルミオン量子優位性に厳密な理論的基礎を提供している。