Fanout Complexity of Symmetric Boolean Functions in $\mathsf{QAC}^0$

技術要約：$\mathsf{QAC}^0$ における対称ブール関数のファンアウト複雑性

問題提起
$\mathsf{QAC}^0$（任意の単一量子ゲートおよび多制御Toffoliゲートを持つ、定数深さ・多項式サイズの量子回路）という複雑性クラスにおける中心的な未解決問題は、それが $\mathsf{FANOUT}_n$ 操作を実装できるかどうかである。古典的回路においてファンアウトは無料であるが、量子回路において、1つの量子ビットから $n$ 個のターゲットへ古典情報をコピーすることは非自明なリソースとなる。$\mathsf{FANOUT}_n$ はアダマール共役の下で $\mathsf{PARITY}_n$ 関数と等価であるため、$\mathsf{QAC}^0 = \mathsf{QAC}^0_f$（ここで $\mathsf{QAC}^0_f := \mathsf{QAC}^0[\mathsf{FANOUT}_n]$）であるかどうかを判定することは、$\mathsf{PARITY}_n \in \mathsf{QAC}^0$ であるかどうかを判定することと同値である。

一般的なケースは未解決のままであるが、ディッケ状態（Dicke-state）の準備に関する最近の研究は、対称関数の計算の困難さが、必要とされるファンアウトゲートのサイズと相関している可能性を示唆した。本論文は、より微細な視点からの問いに取り組む：任意の対称ブール関数 $f$ について、それを $\mathsf{QAC}^0$ 内で計算するために必要なファンアウトサイズはいくらであるか。

手法
著者らは、対称関数のための構造的パラメータとして、**遷移半径（transition radius）**と呼ばれる $\rho(f)$ を導入する。対称関数 $f$ に対して、$\Delta f$ をハミング重み $i$ と $i+1$ の間で関数の値が変化するインデックスの集合とする。遷移半径は次のように定義される：
$$\rho(f) := \max_{i \in \Delta f} \min\{i + 1, n - i\}$$
直感的には、$\rho(f)$ は「最も内側」の遷移が、ハミング重みの区間の端点からどれだけ離れているかを測定するものである。

本論文は、任意の対称関数 $f$ を計算することと、$\mathsf{QAC}^0$ 還元下での $\mathsf{FANOUT}_{\rho(f)}$ の実装との間の正確な等価性を確立する。証明は二方向で行われる：

1. ファンアウトから対称関数へ：
   著者らは、$\rho(f) = k$ である任意の対称関数を計算するために $\mathsf{FANOUT}_k$ が十分であることを示す。そのような関数のすべての遷移は、最初の $k$ または最後の $近似k$ のハミング重みレイヤー内に発生するため、その関数は高々 $2k$ 個の「正確な重み（exact weight）」述語（$\mathsf{EXACT}_j$）の選言（OR）として表現できる。$\mathsf{FANOUT}_k$ を用いることで、回路は入力の $2k$ 個のコピーを並列に生成し、必要な $\mathsf{EXACT}_j$ 述語（これらは $\mathsf{QAC}^0[\mathsf{FANOUT}_k]$ に属することが既知である）を評価し、単一のORゲートで結合することができる。

2. 対称関数からファンアウトへ：
   逆に、もし $\mathsf{QAC}^0$ 回路が、最悪実行確率 $1/2 + 1/\text{polylog}(n)$ で対称関数 $f$ を計算する場合、$\mathsf{FANOUT}_k$ を実装できることを著者らは実証する。

   • 証明では、ハミング重みのスペクトルの中心付近の遷移を孤立させるために、回路を $m = 2k-1$ ビットの入力に制限する。
   • 制限された回路の付随する実数値関数 $g$ を分析する。回路が確率の高い精度で $f$ を計算するという条件は、隣接するハミング重み付近の入力 $x, y$ に対する差分 $|g(x) - g(y)|$ に関する下界を意味する。
   • この差分は、関数の全影響度（total influence）の下界へと翻訳され、これはパーセバルの等式とFact 6を介して、有意な「フーリエ・テイル（Fourier tail）」（高次における質量）を意味する。
   • 著者らは、Gretta, Gupta, および Joshi [GGJ26a] によるフーリエ・テイル還元結果を援用する。これは、十分な高次のフーリエ質量を持つ回路は、$\mathsf{FANOUT}_\ell$ 回路へと変換可能であることを示している。
   • 最後に、導出されたファンアウトサイズ $\ell$ が、定数深さの木を通じて $\mathsf{FANOUT}_k$ を構成するのに十分であることを示す。

主要な結果
主定理は、任意の対称ブール関数 $f$ に対して以下の等価性を確立する：
$$f \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_{\rho(f)} \in \mathsf{QAC}^0$$
より正確には：

1. もし $f$ が確率 $1/2 + 1/\log^c n$ で $\mathsf{QAC}^0$ 回路によって計算可能であれば、$\mathsf{FANOUT}_{\rho(f)}$ は $\mathsf{QAC}^0$ によって実装可能である。
2. もし $\mathsf{FANOUT}_{\rho(f)}$ が $\mathsf{QAC}^0$ 回路によって実装可能であれば、$f$ は $\mathsf{QAC}^0$ 回路によって正確に計算可能である。

系および示唆

• 大きな遷移半径に対する完全性： もし $\rho(f) \ge n^\delta$ （ある定数 $\delta > 0$）であれば、$f$ を計算すること（指定された確率で）は $\mathsf{QAC}^0_f$ 完全である。これは、$\mathsf{FANOUT}_{\rho(f)}$ を定数深さの木で反復することで $\mathsf{FANOUT}_n$ を実装できるためである。この結果は、$\mathsf{PARITY}$、$\mathsf{MAJORITY}$、$\mathsf{THRESHOLD}$、および $\mathsf{MOD}_q$ に関する既知の完全性の結果を統一し、一般化するものである。
• 近似次数と対称性： $f$ の近似次数に関するパトリ（Paturi）の定理（$\widetilde{\deg}(f) = \Theta(\sqrt{n\rho(f)})$）と本結果を組み合わせることで、著者らは $\mathsf{QAC}^0$ 内の関数に対する制約を導出する。具体的には、もし $\mathsf{PARITY}_n \notin \mathsf{QAC}^0$ ならば、近似次数が $\Omega(n^{1/2+\eta})$ である $\mathsf{QAC}^0$ 内のいかなる関数も、非対称でなければならない。なぜなら、そのような次数を持つ対称関数は、多項式オーダーの大きな遷移半径を持ち、$\mathsf{QAC}^0_f$-完全になる（したがって $\mathsf{PARITY}_n$ と等価になる）からである。

意義
本論文は、$\mathsf{QAC}^0$ 内の全対称ブール関数のクラスに対するファンアウト複雑性の完全な特性付けを提供する。これは、遷移半径を正確な閾値として特定することで、対称関数に関するファンアウト問題の「全か無か（all-or-nothing）」の性質を解決するものである。本研究は、特定の関数（$\mathsf{PARITY}$ や $\mathsf{MAJORITY}$ など）に関する既知の結果を特殊なケースとして回収し、さらに、近似的な計算（確率 $1/2 + 1/\text{polylog}(n)$）であっても、大きな遷移半径を持つ関数のファンアウト問題の完全性を引き起こすには十分であることを示すことで、先行研究を強化している。さらに、高次の対称関数に関する $\mathsf{QAC}^0$ の限界について、$\mathsf{PARITY}$ の未解決問題を対称関数の構造的特性に直接結びつける新しい視点を提供している。