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

技术摘要：$\mathsf{QAC}^0$ 中对称布尔函数的扇出复杂度

问题陈述
关于复杂度类 $\mathsf{QAC}^0$（具有任意单比特门和多控制 Toffoli 门的常深、多项式规模量子电路）的核心开放性问题是，它能否实现 $\mathsf{FANOUT}_n$ 操作。在经典电路中，扇出是免费的；但在量子电路中，将经典信息从一个量子比特复制到 $n$ 个目标量子比特是一个非平凡的资源问题。由于 $\mathsf{FANOUT}_n$ 在 Hadamard 共轭下等价于 $\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 态制备的研究提出了一种更细粒度的视角：计算对称函数的难度可能与所需的扇出门大小相关。本文探讨了一个更广泛的问题：对于任意对称布尔函数 $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)$ 衡量了“最靠近中心”的转移点距离汉明重量区间最近端点的距离。

本文建立了一个精确的等价关系，即在 $\mathsf{QAC}^0$ 归约下，计算对称函数 $f$ 与实现 $\mathsf{FANOUT}_{\rho(f)}$ 之间的关系。证明分为两个方向：

1. 从扇出到对称函数：
   作者表明，$\mathsf{FANOUT}_k$ 足以计算任何满足 $\rho(f) = k$ 的对称函数。由于此类函数的所有转移都发生在最初的 $k$ 个或最后的 $k$ 个汉明重量层内，因此该函数可以表示为至多 $2k$ 个“精确权重”谓词（$\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$（且 $\rho(f) = k$），则可以实现 $\mathsf{FANOUT}_k$。

   • 证明将电路限制在 $m = 2k-1$ 个输入比特上，以隔离汉明重量谱中心附近的转移。
   • 分析该受限电路相关的实值函数 $g$。电路以高概率计算 $f$ 的条件意味着对于具有相邻汉明重量的输入 $x, y$，函数 $g(x)$ 与 $g(y)$ 之间的差值 $|g(x) - g(y)|$ 存在下界。
   • 该差值转化为函数总影响力的下界，通过 Parseval 等式和 Fact 6，这意味着存在显著的“傅里叶尾部”（高阶傅里叶质量）。
   • 作者调用了 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$ 的完备性结果。
• 近似度数与对称性： 结合主定理与 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$ 中整个对称布尔函数类的扇出复杂度进行了完整的刻画。它通过识别转移半径这一精确阈值，解决了对称函数中扇出问题的“全或无”性质。这项工作将针对特定函数（如 $\mathsf{PARITY}$ 和 $\mathsf{MAJORITY}$）的已知结果作为特例进行了恢复，并通过展示即使是近似计算（概率为 $1/2 + 1/\text{polylog}(n)$）也足以触发具有大转移半径函数的扇出问题完备性，从而强化了先前的研究结果。此外，它为 $\mathsf{QAC}^0$ 在处理高阶对称函数方面的局限性提供了新的视角，将 $\mathsf{PARITY}$ 这一开放问题直接与对称函数的结构属性联系起来。