Learning Random Quantum Circuits and the Emergence of Pseudorandomness

技術要約：ランダム量子回路の学習と擬似ランダム性の出現

問題設定
本論文は、ランダム量子回路の文脈における、学習可能性と擬似ランダム性の間の根本的な相互作用を扱っている。具体的には、固定次元のブリックワーク（レンガ積み）アーキテクチャ上の局所的なランダム量子回路が、擬似ランダム状態（PRS）の閾値に達する前に、その出力状態のコピー（状態アクセス）から効率的に学習可能であるかどうかを調査している。

設定には、深さ $d$ と、$2\ell$ 個の量子ビットに作用する局所ゲート（局所性 $\ell$）を持つ $k$ 次元ブリックワーク回路が含まれる。中心となる問いは、深さと局所性の組み合わせ $\ell d$ が $\ell d = O(\log n)$ を満たすとき、そのような回路を多項式時間で厳密に復元できるかどうかである。この領域は、擬似ランダム状態（PRS）が期待される自然な境界を表しており、先行研究では $\ell d = \omega(\log n)$ であることが示唆されている。

手法
著者らは、状態アクセスモデル（学習者は出力状態 $|\psi_0\rangle = U|0\rangle^{\otimes n}$ のコピーを与えられるが、ユニタリ $U$ 自体へのクエリアクセスは持たない）の下で動作する効率的な学習アルゴリズムを提案している。アルゴリズムは、最終層 $U_d$ から $U_1$ に向かって、回路を一層ずつ後方に遡って復元することで進行する。

核心となる技術的革新は、以前のアプローチが依存していた完全な後方ライトコーン（逆光錐）の再構成というボトルネックを回避する、**局所相関基準（local correlation criterion）**である。主要なステップは以下の通りである：

1. ライトコーンの非交差性（Lightcone Disjointness）: 最終層のサイト $B$ と $C$ に作用するゲート $G$ に対して、もし $G$ が取り除かれた場合に、$B$ とサイト $D$ の後方ライトコーンが互いに素になるようなサイト $D$ を特定する。
2. 相関関数: アルゴリズムは、相関関数 $\text{Corr}_{B:D}(\rho) = \|\rho_{BD} - \rho_B \otimes \rho_D\|_F^2$ を定義する。正しいゲート $G$ が取り除かれる（または反転される）と、結果として得られる状態は $B$ と $D$ において可分になり、相関はゼロになる。誤ったゲートが選択された場合、相関は非ゼロのままとなる。
3. ゲートの特定: 公開されたゲートセットからすべての候補ゲートに対して $B$ と $C$ 上の簡約状態に逆操作を適用することにより、相関をゼロに最小化するものが正しいゲートであると特定する。
4. アンティコンセントレーション（非集中性）解析: 誤ったゲートに対する相関が十分に大きいこと（具体的には $\ge 2^{-O(\ell d)}$）を保証するために、著者らは、Haarランダム・ユニタリ上の低次多項式に関する新しい次元に依存しないアンティコンセントレーション不等式を証明している。

主な貢献

1. 効率的な学習アルゴリズム: 本論文は、局所性 $\ell d = O(\log n)$ である限り、多項式時間 $\text{poly}(n, 2^{\ell d})$ で $k$ 次元ブリックワーク回路を厳密に復元するアルゴリズムを提示している。これは、$\ell d = O(\log n)$ の場合に多項式時間計算量であることを意味する。
2. 次元に依存しないアンティコンセントレーション: 主要な技術的貢献は、ユニタリ群 $U(m)$ 上の多項式に関する新しいCarbery-Wright型の不等式である。行列次元 $m$ に依存する多項式的なスモールボール指数（例：$1/m^2$）を持つ従来の境界とは異なり、この結果は次元に依存しない指数を確立している：
   $$\Pr_{U \sim \mu_{\text{Haar}}} [|P(U)| \le \varepsilon \|P\|_\infty] \le 64m^2 \cdot \varepsilon^{\frac{1}{24\pi d}}$$
   この次元に依存しない指数は、局所的なヒルベルト空間の次元によって複雑さが爆発することなく、局所性が増大するゲートを扱うために極めて重要である。
3. 状態アクセス vs ユニタリアクセス: 本研究は、ユニタリアクセス（任意の入力に対して $U$ をクエリする）よりも厳格に弱いモデルである状態アクセス（$U|0\rangle$ のコピーのみ）のみを用いて、厳密な回路復元が可能であることを示している。これは、状態アクセスでは大きなライトコーンの再構成が必要となり、超多項式時間の計算量に陥ることが多かった先行文献のギャップを解消するものである。

結果

• 定理 1.1: ランダムなゲートセットから選ばれた深さ $d$, $k$ 次元ブリックワーク回路に対して、高い確率で $\text{poly}_k(n, d, \delta^{-1}) 2^{O_k(d\ell)}$ の時間で回路を厳密に復元するアルゴリズムが存在する。
• 定理 1.2: 本論文は、ユニタリ群上の次元に依存しないCarbery-Wright不等式を証明し、Weyl積分公式とRemez型不等式を介して、問題を一変数の極値問題へと帰着させている。
• 相関ギャップ: 著者らは、誤ったゲートの候補に対して、相関 $\text{Corr}_{B:D}$ が高確率で $\Gamma = 2^{-O(\ell d)} \text{poly}(\dots)$ によって下限付けられることを証明しており、これにより学習アルゴリズムが正しいゲートと誤ったゲートを区別できることを保証している。

意義と主張
本論文は、以下のすべてを同時に達成する最初のアルゴリズムを提供すると主張している：

1. $\ell d = O(\log n)$ である限り、局所性が増大する回路に対しても多項式時間の計算量を実現すること。
2. 元の回路のレイアウトとゲートを厳密に復元すること。
3. より現実的な、暗号学的応用において出力状態のみが利用可能な状況である、状態アクセスモデルの下で動作すること。

著者らは、本研究が擬似ランダム性が生じる条件を明確にすることを目的としていると位置づけている。彼らは、$\ell d = O(\log n)$ というスケールが学習が可能な閾値であり、このスケールを超えると（すなわち $\ell d = \omega(\log n)$ のとき）、擬似ランダム性の出現によって効率的な学習が不可能になることを示唆している。これらの結果は、局所的なHaarランダム回路が、対数的な深さ/局所性の閾値を超えている限り、擬似ランダム状態生成器の候補となり得るという仮説を支持している。

本論文は、提案された学習アルゴリズムは指定された領域において効率的であるが、構造化されたアンサンブルや補助的なワークスペースに依存する暗号構成を打破することを主張しているのではなく、むしろ局所的なHaarランダム回路に対する学習の限界を明らかにしていることを明記している。次元に依存しないアンティコンセントレーションの結果は、量子情報理論および複雑性理論にとって独立した関心事となるツールとして強調されている。