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

Technical Summary: Fanout Complexity of Symmetric Boolean Functions in QAC0

Problem Statement
The central open question in the complexity class $\mathsf{QAC}^0$ (constant-depth, polynomial-size quantum circuits with arbitrary single-qubit gates and multi-controlled Toffoli gates) is whether it can implement the $\mathsf{FANOUT}_n$ operation. In classical circuits, fanout is free; in quantum circuits, copying classical information from one qubit to $n$ targets is a non-trivial resource. Since $\mathsf{FANOUT}_n$ is equivalent to the $\mathsf{PARITY}_n$ function under Hadamard conjugation, determining if $\mathsf{QAC}^0 = \mathsf{QAC}^0_f$ (where $\mathsf{QAC}^0_f := \mathsf{QAC}^0[\mathsf{FANOUT}_n]$) is equivalent to determining if $\mathsf{PARITY}_n \in \mathsf{QAC}^0$.

While the general case remains open, recent work on Dicke-state preparation suggested a finer-grained perspective: the difficulty of computing symmetric functions might correlate with the size of the fanout gate required. This paper addresses the general question: for an arbitrary symmetric Boolean function $f$, what is the necessary and sufficient fanout size to compute it within $\mathsf{QAC}^0$?

Methodology
The authors introduce a structural parameter for symmetric functions called the transition radius, denoted $\rho(f)$. For a symmetric function $f$, let $\Delta f$ be the set of indices $i$ where the function's value changes between Hamming weights $i$ and $i+1$. The transition radius is defined as:
$$\rho(f) := \max_{i \in \Delta f} \min\{i + 1, n - i\}$$
Intuitively, $\rho(f)$ measures the distance of the "innermost" transition from the nearest endpoint of the Hamming weight interval.

The paper establishes a precise equivalence between computing a symmetric function $f$ and implementing $\mathsf{FANOUT}_{\rho(f)}$ under $\mathsf{QAC}^0$ reductions. The proof proceeds in two directions:

1. From Fanout to Symmetric Functions:
   The authors show that $\mathsf{FANOUT}_k$ suffices to compute any symmetric function with $\rho(f) = k$. Since all transitions of such a function occur within the first $k$ or last $k$ Hamming weight layers, the function can be expressed as a disjunction (OR) of at most $2k$ "exact weight" predicates ($\mathsf{EXACT}_j$). Using $\mathsf{FANOUT}_k$, the circuit can generate $2k$ copies of the input in parallel, evaluate the necessary $\mathsf{EXACT}_j$ predicates (which are known to be in $\mathsf{QAC}^0[\mathsf{FANOUT}_k]$), and combine them with a single OR gate.

2. From Symmetric Functions to Fanout:
   Conversely, the authors demonstrate that if a $\mathsf{QAC}^0$ circuit computes a symmetric function $f$ with $\rho(f) = k$ with worst-case probability at least $1/2 + 1/\text{polylog}(n)$, then $\mathsf{FANOUT}_k$ can be implemented.

   • The proof restricts the circuit to $m = 2k-1$ input bits to isolate a transition at the center of the Hamming weight spectrum.
   • It analyzes the associated real-valued function $g$ of the restricted circuit. The condition that the circuit computes $f$ with high probability implies a lower bound on the difference $|g(x) - g(y)|$ for inputs $x, y$ with adjacent Hamming weights near the transition.
   • This difference translates to a lower bound on the total influence of the function, which, via Parseval's identity and Fact 6, implies a significant "Fourier tail" (mass at high degrees).
   • The authors invoke a Fourier-tail reduction result by Gretta, Gupta, and Joshi [GGJ26a], which states that a circuit with sufficient high-degree Fourier mass can be transformed into a $\mathsf{FANOUT}_\ell$ circuit.
   • Finally, they show that the derived fanout size $\ell$ is sufficient to construct $\mathsf{FANOUT}_k$ via a constant-depth tree.

Key Results
The main theorem establishes the following equivalence for any symmetric Boolean function $f$:
$$f \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_{\rho(f)} \in \mathsf{QAC}^0$$
More precisely:

1. If $f$ can be computed by a $\mathsf{QAC}^0$ circuit with probability $1/2 + 1/\log^c n$, then $\mathsf{FANOUT}_{\rho(f)}$ can be implemented by a $\mathsf{QAC}^0$ circuit.
2. If $\mathsf{FANOUT}_{\rho(f)}$ can be implemented by a $\mathsf{QAC}^0$ circuit, then $f$ can be computed exactly by a $\mathsf{QAC}^0$ circuit.

Corollaries and Implications

• Completeness for Large Transition Radius: If $\rho(f) \ge n^\delta$ for some constant $\delta > 0$, then computing $f$ (with the specified probability) is $\mathsf{QAC}^0_f$-complete. This is because $\mathsf{FANOUT}_{\rho(f)}$ can be iterated in a constant-depth tree to implement $\mathsf{FANOUT}_n$. This result unifies and generalizes previous completeness results for $\mathsf{PARITY}$, $\mathsf{MAJORITY}$, $\mathsf{THRESHOLD}$, and $\mathsf{MOD}_q$.
• Approximate Degree and Symmetry: Combining the main result with Paturi's theorem on the approximate degree ($\widetilde{\deg}(f) = \Theta(\sqrt{n\rho(f)})$), the authors derive a constraint on functions in $\mathsf{QAC}^0$. Specifically, if $\mathsf{PARITY}_n \notin \mathsf{QAC}^0$, then any function in $\mathsf{QAC}^0$ with approximate degree $\Omega(n^{1/2+\eta})$ must be nonsymmetric. This is because a symmetric function with such a degree would have a polynomially large transition radius, making it $\mathsf{QAC}^0_f$-complete (and thus equivalent to $\mathsf{PARITY}_n$).

Significance
The paper provides a complete characterization of the fanout complexity for the entire class of symmetric Boolean functions within $\mathsf{QAC}^0$. It resolves the "all-or-nothing" nature of the fanout question for symmetric functions by identifying the transition radius as the precise threshold. The work recovers known results for specific functions (like $\mathsf{PARITY}$ and $\mathsf{MAJORITY}$) as special cases and strengthens previous results by showing that even approximate computation (with probability $1/2 + 1/\text{polylog}(n)$) is sufficient to trigger the completeness of the fanout problem for functions with large transition radii. Furthermore, it offers a new perspective on the limitations of $\mathsf{QAC}^0$ regarding high-degree symmetric functions, linking the open question of $\mathsf{PARITY}$ directly to the structural properties of symmetric functions.