技術要約：浅い回路におけるサンプリングのための無条件の量子優位性

問題提起

本論文は、定数深さの量子回路（$QNC_0$）が、入力に依存しない設定において、有界ファンインを持つ定数深さの古典的回路（$NC_0$）では不可能なサンプリング・タスクを実行できるかという問いに取り組んでいる。

Bravyi、Gosset、およびKoenigによる先行研究では、探索問題（入力を有効な出力へと写像する問題）において、$QNC_0$と$NC_0$の間の無条件の分離が確立されているが、特定の計算入力なしに固定された分布 $D_n$ からサンプルを生成することを目的とする「サンプリング」問題については、課題が残されていた。入力依存の設定では、古典的な困難性は通常、複雑性理論の仮定（例：$P \neq NP$）に依存している。一方、入力に依存しない設定における課題は、限られた数の乱数のみを与えられた古典的回路が、加法的誤差（全変動距離）の範囲内で、浅い量子回路の出力分布を再現できないことを証明することである。

手法

著者らは特定の分布族 $\{D_n\}$ を構築し、以下の3部構成の手法を通じて分離を実証している。

1. GHZアドバイスを用いた量子構成

著者らはまず、$(X, \text{majmod}_p(X) \oplus \text{parity}(X))$ に近い分布からサンプリングする定数深さの量子回路を設計した。ここで、$X$ は一様ランダムなビット列であり、$\text{majmod}_p$ は「Majority mod $p$」関数である。

• 初期アプローチ: 著者らは、GHZ状態（$|GHZ_n\rangle = \frac{1}{\sqrt{2}}(|0^n\rangle + |1^n\rangle)$）に作用する、自己制御型の非ユニタリ回転ゲート $A_\theta$ を利用している。これにより、回路は入力ビットのハミング重みの modulo $p$ と最終出力ビットを相関させることができる。
• ユニタリ・コンパイル: 回路を物理的に実現可能にするため、非ユニタリゲートをマルチ量子ビット・ユニタリゲート $U_{m,\theta}$ に置き換える。著者らは、これらのユニタリが、定数深さを維持しながら、GHZ状態上で高忠実度で非ユニタリ操作を近似できることを証明している。
• 結果: GHZ状態（アドバイスとして扱う）にアクセスできる定数深さの量子回路は、低い全変動距離でターゲット分布からサンプリングできる。

2. GHZアドバイスの除去（Poor Man's GHZ）

外部アドバイスなしでの分離を実現するために、著者らは入力GHZ状態を「Poor Man's GHZ」状態に置き換えている。

• 構成: この状態は、$2n-1$ 個の量子ビット（バイナリツリー構造に基づく）に対して作用する定数深さの回路と、それに続く $n-1$ 個の補助量子ビットの測定によって生成される。
• 適応: 補助量子ビットの測定結果は、残りの状態にパウリ誤差（符号反転）を導入する。これらの誤差を修正すること（これには対数深さが必要となる）の代わりに、著者らはこれらの誤差をターゲット分布の定義の中に吸収させている。
• 新しい分布: 結果として得られる回路は、修正された分布 $(Z, \text{pmmajmod}_p(Z))$ からサンプリングを行う。関数 $\text{pmmajmod}_p$ は、生成に使用されたバイナリツリーの構造に依存する重みを持つビットの加重和である。

3. 古典的下界

著者らは、有界ファンインを持つ定数深さの古典的回路が、ランダム入力の数が制限されている場合、これらの分布からサンプリングできないことを証明している。

• 手法: 著者らは、Violaによるサンプリング困難性の研究の手法を適応させている。この証明は「局所性（locality）」の概念に基づいている。有界ファンインを持つ定数深さの回路は限定的な局所性を持ち、その出力ビットは入力ビットのわずかな部分集合にのみ依存する。
• 統計的テスト: ターゲット分布が非常に低い確率で通過する一方で、局所関数（古典的回路）が高い確率で通過するような統計的テスト（「悪い」文字列の集合）を構築する。
• 鍵となる洞察: 分布 $(X, \text{majmod}_p(X) \oplus \text{parity}(X))$ において、入力の大部分を固定すると、残りのビットのハミング重みは独立な確率変数の和となる。著者らは、局所関数がこれらの和に対するパリティとmajority-mod-$p$ の制約を同時に満たすことはできないことを示している。
• $\text{pmmajmod}_p$ への拡張: アドバイスなしの分布では、ツリーベースの重みにより依存構造がより複雑になる。著者らは、バイナリツリー構造に基づいて出力変数を「フォレスト（forest）」ブロックへと分割する。彼らは、この複雑な依存関係があっても、十分な数の入力ビットを固定すれば独立したブロックが孤立することを示し、同様の下界論理を適用できることを示している。

主な貢献と結果

1. サンプリングにおける無条件の分離: 本論文は、定数深さの古典的回路（有界ファンイン）が、加法的誤差の範囲内であっても再現できない分布から、定数深さの量子回路がサンプリングできるという最初の無条件の証明を提供している。

   • 定理 3: 任意の $\delta < 1$ に対して、分布 $D_n$ が存在し、ある定数深さの量子回路は距離 $\le 1/6 + O(n^{-c})$ でこれをサンプリングできる一方、$n + n^\delta$ 個のランダム入力ビットを持つ任意の古典的回路は、距離 $\le 1/2 - \omega(1/\log n)$ を達成するために $\Omega(\log \log n)$ の深さを必要とする。

2. ランダムネス制約の処理: この分離は、古典的回路がアクセスできるランダム性が制限されている場合（具体的には $n + n^\delta$ ビット）に特に成立する。著者らは、古典的回路が無制限のランダムビットにアクセスできる場合、その分布を自明にシミュレートできることを指摘している。しかし、彼らはまた、量子アドバイスにアクセスできる有界ファンアウトを持つ古典的回路に対しても、分離が存在することを示している。

3. 偏った入力に対する堅牢性: 著者らは、古典的回路が偏ったランダム入力（エントロピー $1/k$ のベルヌーイ変数）を受け取る場合でも、総エントロピーが制限されている限り、下界を拡張している。これは、古典的回路が完全な一様ランダムネスにアクセスできることを前提としているという懸念に対処するものである。

4. 明示的な回路構成: 論文では、標準的なゲートセット（単一量子ビットゲートおよびCNOT）を用いた量子回路の構成を詳述し、それらが一様（uniform）なファミリーであることを証明している。また、「Poor Man's GHZ」状態およびそれに伴うサンプリング分布の具体的な数学的定義も提供している。

意義

本論文は、以下の領域における重要性を主張している：

• 入力に依存しない量子優位性: 本研究は、Bravyi、Gosset、およびKoenigによって提起された、入力に依存しないサンプリングに関する特定の問いに答えており、量子優位性が探索問題や入力依存のタスクに限定されないことを示している。
• 無条件の困難性: 多くのサンプリング困難性の結果（例：ランダム回路サンプリング）が、未解決の複雑性仮定（例：多項式階層の崩壊の否定）に依存しているのに対し、この結果は無条件である。これは、定数深さの古典的回路の構造的な限界にのみ依拠している。
• 状態準備の複雑性: これらの結果は、状態準備の複雑性に影響を与える。$(X, f(X))$ という分布からのサンプリングは、特定の量子状態を準備することと古典的に類似しているため、この分離は、特定の量子状態（およびそれに関連する分布）が、ランダムネスを用いたとしても、浅い古典的回路にとって本質的に準備またはシミュレートが困難であることを示唆している。
• 境界の精緻化: 本研究は、浅い量子回路の能力に関する理解を精緻化するものである。具体的には、浅い古典的回路が（たとえ余剰なランダムネスへのアクセスがあったとしても）再現できない相関（特にパリティとmajority-mod-$p$ に関するもの）を、量子回路が生成できることを示している。

著者らは、自身の下界がランダムビットの数が制限されている場合にのみ適用されることを認めつつも、謙虚な姿勢を保っている。彼らは、無制限のランダムネスを持つ古典的回路への拡張が依然として未解決の問題であることを認めているが、有界ファンアウトの設定においては進展を見せている。