Oracle Separations in the Fourier Hierarchy

技術的要約：フーリエ階層におけるオラクル分離

問題提起
Shi (2005) によって導入されたフーリエ階層 ($FH_k$) は、グローバルなアダマール層（フーリエ深さ）の数に基づいて量子計算を分類するものである。これらの層の間では、回路は基底保存演算（置換および位相付加）を実行するが、新たな重ね合わせを作成することはできない。この階層は $FH_0 \subseteq FH_1 \subseteq FH_2 \subseteq \dots$ と定義される。標準的なクエリモデルにおいて $FH_0 = P$ かつ $FH_1 = BPP$ であり、$FH_2$ は因数分解やサイモンの問題を含むが、追加の層ごとに計算能力が厳密に増加するかどうかは未解決の問いであった。Shiは、すべての $k \ge 0$ に対して $FH_k \subsetneq FH_{k+1}$ であると予想し、その第一歩として隣接するレベル間のオラクル分離を求めた。本研究以前には、$k \ge 2$ のいかなるレベルについても分離は知られていなかった。

手法
著者は、2つの異なるクエリモデルにおいて、すべての定数 $k \ge 2$ に対するオラクル分離を構成することでこの問題を解決する。

1. 位相クエリモデル (Phase-query model): クエリが基底状態に符号を乗算する（$F(x)|x\rangle \to (-1)^{F(x)}|x\rangle$）。
2. 標準クエリモデル (Standard-query model): クエリが答えをレジスタに書き込む（$|y\rangle|b\rangle \to |y\rangle|b \oplus F(y)\rangle$）。

手法の核心は、フーリエ変換とブール関数が交互に現れる関数の連鎖間の相関を測定する、Forrelation問題（特にその $K$ 重の一般化）にある。著者は以下の構造的洞察とツールを利用している：

• 奇数次 vs 偶数次のForrelation: 著者はForrelationの次数 $K$ のパリティ（奇偶）を利用する。$(2k-1)$ 次のForrelation（奇数次）は、計算を深さ $k$ の2つの半分に分割する制御量子ビット干渉テスト（またはSWAPテスト）を用いることで、フーリエ深さ $k+1$ で解けることを示す。逆に、$(2k-2)$ 次のForrelation（偶数次）は深さ $k$ で解ける。
• 深さによる適応性のシミュレーション（位相モデル）: 主要な構造的補題として、位相クエリモデルにおける任意の $q$ 個のクエリを行う $FH_k$ 回路は、$k-1$ ラウンドの適応性と、各ラウンドあたり $q$ 個の並列クエリを持つ量子クエリアルゴリズムによって正確にシミュレートできることを示している。これにより、著者は有界ラウンドアルゴリズムに関する既存の文献（Girish et al., 2024）からの下界を導入することが可能となった。
• フーリエ成長界 (Fourier Growth Bounds): 下界は受容確率のフーリエ重みに依存する。
  • 位相モデルの場合: シミュレーション補題により、問題は $k-1$ ラウンドのアルゴリズムのフーリエ成長を抑えることに帰着される。著者はBansal–Sinhaの基準を適用し、次数 $K = 2k-1$ のとき、深さ $k$ の回路のフーリエ重みの成長が、構造化されたForrelation分布と一様分布を区別するにはあまりに遅いことを示す。
  • 標準モデルの場合: 標準的なクエリは、以前の回答に基づく適応的な分岐を許容するため、ラウンド・シミュレーションが失敗する。著者は新しい手法を開発した。すなわち、各基底保存ブロックを決定木の葉を通じて因数分解することである。これにより、標準クエリ回路に対する直接的なフーリエ成長界が得られるが、これは位相モデルの界よりもわずかに弱く（$k$ に指数的に依存）、分離のために高いForrelation次数（$K = 2k+1$）を必要とする。
• オラクル構成: 分布間のギャップから最悪ケースのオラクル分離へと移行するために、複数のForrelationインスタンスのOR（論理和）を用いた直接積構成を用いて成功確率を増幅させ、その後、ハイブリッド引数と対角化法を用いて、すべての一様 $FH_k$ ファミリーを退け、かつ $FH_{k+1}$ 回路によって決定可能な単一のオラクルファミリー $O$ を構成する。

主要な貢献と結果

1. 隣接レベルの分離（位相モデル）: すべての定数 $k \ge 2$ に対して、 $FH^O_k \subsetneq FH^O_{k+1}$ となるオラクル $O$ が存在する。分離問題は $(2k-1)$ 重のForrelationのORである。これは $O_k(1)$ 個のクエリで深さ $k+1$ で解けるが、最大 $N^{c_k}$ 個（ここで $c_k = \Theta(1/k^2)$）のクエリを行う深さ $k$ の回路では解けない。
2. 隣接レベルの分離（標準モデル）: 同様に、すべての $k \ge 2$ に対して、 $FH^O_{k,std} \subsetneq FH^O_{k+1,std}$ となるオラクル $O$ が存在する。ここでの分離問題は $(2k+1)$ 重のForrelationのORである。標準クエリの適応性により、下界の導出には異なる成長解析が必要となる。
3. クエリモデルの分離: 本論文は、同じフーリエ深さにおいて標準クエリモデルが位相クエリモデルよりも厳密に強力であることを証明する。具体的には、すべての $k \ge 2$ に対して $FH^O_k \subsetneq FH^O_{k,std}$ である。分離問題は $(2k-1)$ 重のForrelationのORであり、これは標準的な深さ $k$ では（中央の回答ビットを読み取ることで）解けるが、位相的な深さ $k$ では解けない。
4. BQPからの分離: 著者は、すべての有界フーリエ深さレベルの和集合が、オラクルに関して $BQP$ に厳密に含まれることを示す。具体的には、次数 $K = \Theta(\log n)$ のForrelationは $BQP$ に属するが、解くために $\approx \frac{1}{4} \log_2 n$ までのフーリエ深さを必要とするため、$\left(\bigcup_k FH_k\right)^O \subsetneq BQP^O$ が成り立つ。
5. 非相対化 (Non-Relativization): 本論文は、隣接レベルの問題が相対化しないことを示している。上記の分離は特定のオラクルに関して成立するが、$FH_k = PSPACE$ となる $PSPACE$ 完全なオラクルが存在する。したがって、相対化しない設定におけるShiの予想を解決するには、非相対化の手法が必要である。

意義と主張
本論文は、すべてのレベル $k \ge 2$ において、すべての標準クエリモデルにおけるShiの「隣接レベル問題」を解決したと主張している。その意義は以下の通りである：

• 構造的特性付け: フーリエ深さとクエリの適応性（具体的には、位相クエリの深さ $k$ が $k-1$ ラウンドの並列クエリと等価であること）の間の精密な関係を確立した。
• 手法の進展: 適応的な標準クエリ回路のフーリエ成長を抑えるための決定木因数分解技術を導入し、非適応的な設定を超えてフーリエ重み法を拡張した。
• 階層の位置付け: フーリエ階層を古典的クラス（$P, BPP, PH$）および完全な量子能力（$BQP$）との関係において位置づけた。これは、第2レベル（$FH_2$）がすでにオラクルに関して多項式階層（PH）を超えている一方で、階層全体は $BQP$ よりも厳密に弱いことを確認している。
• 非相対化された予想への謙虚な姿勢: 著者は、自身の結果が（オラクルを用いない）Shiの非相対化された予想（$FH_k \neq FH_{k+1}$）を解決するものではないことを明言している。なぜなら、崩壊するオラクスの存在は、相対化する手法がこの目的には不十分であることを証明しているからである。

本研究は、フーリエ階層の完全なオラクル理論的全体像を提供し、各レベルにおける厳密性と、量子干渉のためのリソースとしてのフーリエ層の力を明確にしている。