2-Fold Forrelation is in QAC$^0$

技術要約：2-fold Forrelationは$\mathsf{QAC}^0$に属する

問題提起
本論文は、浅い量子回路複雑性における中心的な未解決問題、すなわちパリティ関数が$\mathsf{QAC}^0$（任意の単一量子ゲートと一般化されたトフォリゲートを用いた定数深さ量子回路）に含まれるか否かという問題に取り組んでいる。この問いは、$\mathsf{QAC}^0$が非有界の量子ファンアウト（unbounded quantum fan-out）を実装できるかどうかの判定と同値である。パリティは古典的なクラス$\mathsf{AC}^0$（非有界のファンインを持つAND/OR/NOTゲートを用いた多項式サイズ・定数深さ回路）の外にあることが知られているが、$\mathsf{QAC}^0$が自然な決定問題において$\mathsf{AC}^0$から分離可能であるかどうかは依然として不明である。

著者は、量子およびランダム化クエリ複雑性の間に大きな乖離を示すために導入された約束問題である「2-fold Forrelation」に焦点を当てている。2つの$N$ビット文字列$x, y$（ここで$N=2^m$）が与えられたとき、この問題は、2-fold Forrelationの値$\text{Forr}_N(x, y)$が大きい場合（少なくとも$\delta$）と、小さい場合（最大で$\delta/2$）を区別することを求めるものである。Forrelationの標準的な量子アルゴリズムは、バイナリ形式のアドレス指定位相オラクルを使用するが、これは入力ビットのコヒーレントなインデックス参照を必要とする。しかし、入力がオラクル経由ではなく明示的なワイヤとして提供される回路モデルにおいては、非有界のファンアウトなしにこのインデックス参照を実現することは既知のボトルネックとなっている。

手法
著者は、約束を満たすすべての入力に対して有界誤差で2-fold Forrelationを解く、多項式サイズの定数深さ$\mathsf{QAC}^0$回路を構成する。この構成は、バイナリ・アドレスからワンホット（one-hot）への変換ボトルネック（これは非有界のファンアウトを必要とする）を回避するために、ワンホット表現で直接操作を行う。

手法は、主に以下の2つの段階で進行する：

1. ワンホットForrelationテスト:

   • バイナリ・アドレスをワンホットに変換する代わりに、回路は$N$量子ビットのW状態（$|W_N\rangle$）が$\mathsf{QAC}^0$で正確に準備可能であるという事実を利用する。
   • 入力文字列$x$に対して、回路は位相符号化されたW状態$|W_x\rangle = \frac{1}{\sqrt{N}} \sum_u (-1)^{x_u} |\text{oh}(u)\rangle$を準備する。これは、コヒーレントなルックアップを回避し、入力ビットとW状態レジスタ間の互いに素な制御Zゲートを横断的に用いることで達成される。
   • Walsh–Hadamard干渉パターン（$(-1)^{u \cdot v}$）を実装するために、回路は「ワンホットからバイナリ」へのラベル抽出を行う。正確な対数多項式ファンアウト（既知の$\mathsf{QAC}^0$プリミティブ）を用いて、回路はワンホット・レジスタ $|\text{oh}(u)\rangle$ からバイナリ・ラベル $u$ を補助レジスタへ抽出し、ドット積の位相を計算するための制御Zゲートを適用した後、ラベルを逆計算する。
   • 結果として得られた状態をW状態に射影することで、受容確率は$\text{Forr}_N(x, y)^2 / N$に比例するようになる。

2. 位相状態反復による増幅（Amplification via Phase-State Repetition）:

   • 単一のテストでは成功確率が$N$とともに消失する。一定のギャップを得るためには、$R = \Theta(N/\delta^2)$個のコピーを並列に実行する必要がある。
   • $|W_x\rangle^{\otimes R}$を準備する直接的なアプローチでは、各入力ビットを$R$個のゲートへとファンアウトさせる必要があるが、これは非有界のファンアウトなしには$\mathsf{QAC}^0$では不可能である。
   • 著者は、位相状態反復構成（Grier–Morris–Wuの手法を適応）を採用している。この手法は、もし$C_a$個のコピーがアドレス$a$を占有しているならば、入力ビット$x_a$による総位相寄与は$(-1)^{x_a (C_a \mod 2)}$になるという点に着目している。
   • 回路は、**切り捨てられたパリティ（truncated parity）**関数（ハミングウェイトが対数多項式のカットオフ以下の場合のみパリティを計算するもの）を用いて、占有カウント$C_a$のパリティを計算する。このカットオフを超える確率は無視できるほど小さいため、切り捨てられたパリティは、誤差を無視できる範囲で正しい位相を再現するのに十分である。これにより、回路は単一の入力のみを使用して実質的に$R$個のテストをシミュレートでき、定数深さを維持することができる。

主要な貢献と結果

• 上界: 本論文は、逆対数多項式約束ギャップ（$\delta \ge \text{polylog}^{-c}(N)$）を持つ2-fold Forrelationが$\mathsf{Promise\text{-}BQAC}^0$に属することを証明している。この回路は定数深さであり、サイズは$N$に対して多項式である（ただし、アドレス長 $m = \log N$ に対しては指数関数的である）。
• 分離: 量子の上界と既知の古典的下界（Bansal–Sinha, Tal）を組み合わせることで、著者は以下の決定分離を確立している：
  $$\text{ConstGap2Forr} \in (\mathsf{Promise\text{-}BQAC}^0 \cap \mathsf{Promise\text{-}TC}^0) \setminus \mathsf{Promise\text{-}AC}^0$$
  これは、$\mathsf{QAC}^0$が、両方のモデルが同じ明示的な形式で入力を受け取る場合であっても、定数深さのランダム化$\mathsf{AC}^0$回路に対して指数サイズのサイズを必要とする問題を解けることを示している。
• 技術的新規性: 本研究は、明示的入力モデルにおいてForrelationの解決を妨げる「ファンアウトのボトルネック」が、バイナリ・アドレス指定オラクルを実装しようとするのではなく、ワンホット基底で動作し、かつ切り捨てられたパリティ増幅を利用することによって回避できることを示している。

意義
本論文は、標準的な単一コピー入力モデルの下で、$\mathsf{QAC}^0$と$\mathsf{AC}^0$の間の自然な約束問題の分離を提供している。複製された入力（これは実質的にファンアウトのリソースを供給することになる）に依存した以前の分離や、分布的保証に基づいたものとは異なり、この結果は、標準的なForrelationという典型的な問題に対して、**点別（pointwise）**の分離を提供している。

著者は、自身の結果を、複製された入力を用いて$\mathsf{QAC}^0$と\mathsf{AC}^0}[p]を分離したGrier–Morris–Wuの研究や、単一コピー入力におけるMajorityの高相関性を示したGretta–Gupta–Joshiの研究と比較している。本研究は、Forら（Forrelation）の単一コピー入力を用いて、約束されたすべての入力に対して有界誤差の正当性を達成するという点で、これらを補完するものである。この結果は、$\mathsf{QAC}^0$がパリティ（または非有界ファンアウト）を含んでいるとはまだ断定できないものの、問題の構造がワンホット符号化と切り捨てられたパリティ増幅を許容する場合、特定の相関ベースの問題を解くための十分な能力を備えていることを示唆している。