REVIEW
Fanout Complexity of Symmetric Boolean Functions in $\mathsf{QAC}^0$
Quantum Physics · Submitted 4 Sep 2026 · 16 references
Pith's verdict: Elegant characterization of symmetric function complexity in QAC⁰ in terms of transition radius, but the critical reverse direction leans entirely on an unpublished lemma from [GGJ26a].
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
For any symmetric Boolean function, exact computability in constant-depth quantum circuits reduces to implementing a fanout gate whose size is exactly the function's transition radius.
The reading
What carries the argument
The transition radius ρ(f) = max_{i∈Δ_f} min(i+1,n−i) is the central parameter; it determines the size of the fanout gate needed. The proof from symmetric functions to fanout uses a Fourier nonconcentration argument (Lemma 14) combined with the Fourier-tail reduction of Gretta, Gupta, and Joshi (Fact 15), which converts a circuit with significant Fourier weight above a certain level into a circuit implementing fanout of that level.
Extended reading notes
Core claim
For every symmetric Boolean function f on n bits, let ρ(f) be the transition radius, defined as the maximum over transitions i of min(i+1,n−i). Then f ∈ $QAC^{0}$ (exact computation) if and only if FANOUT_{ρ(f)} ∈ $QAC^{0}$ (exact clean implementation). Moreover, if a $QAC^{0}$ circuit computes f with worst-case probability at least 1/2+1/log^c n for any constant c>0, then FANOUT_{ρ(f)} can be implemented in $QAC^{0}$. This gives a two-way reduction between computing f and implementing a fanout gate of size ρ(f).
Load-bearing premise
The proof that a symmetric function with large transition radius forces fanout implementation relies on the Fourier-tail reduction of [GGJ26a] (Fact 15), a result not yet published in final form. If that reduction contains an error, the central claim would be invalid even if the paper's own Fourier estimates (Lemma 14) are correct.
Editorial extensions
If this is right
- The question of whether PARITY_n ∈ QAC^0 is exactly equivalent to whether FANOUT_{⌈n/2⌉} ∈ QAC^0, recovering a known equivalence as a special case.
- Any symmetric function with ρ(f) ≥ n^δ (for some δ>0) is QAC^0_f-complete when computed with worst-case probability at least 1/2+1/polylog(n); this includes majority, threshold, and exact functions with polynomial parameters.
- If PARITY_n is not in QAC^0, then no symmetric function in QAC^0 can have approximate degree n^{1/2+Ω(1)}; any function with such high approximate degree must be nonsymmetric.
- The characterization provides a unified explanation for previously separate results on exact and approximate computation of specific symmetric functions in QAC^0.
Reading between the lines
- The transition radius might serve as a general measure of 'fanout cost' for non-symmetric functions, though the paper does not explore this extension.
- If QAC^0 does not contain PARITY, then the class of symmetric functions in QAC^0 is precisely those with subpolynomial transition radius, implying a sharp separation between QAC^0 and QAC^0_f on symmetric functions.
- The connection to approximate degree via Paturi's theorem offers a new strategy for proving lower bounds on symmetric functions in QAC^0: high approximate degree forces completeness for QAC^0_f, so if QAC^0 is strictly smaller than QAC^0_f, then such functions cannot be in QAC^0.
Original abstract
Whether $\mathsf{QAC}^0$ can compute $\mathtt{PARITY}_n$ remains open. Computing $\mathtt{PARITY}_n$ is equivalent to implementing $\mathtt{FANOUT}_n$ under $\mathsf{QAC}^0$ reductions. This raises a more general question: for an arbitrary symmetric Boolean function $f:\{0,1\}^n\to\{0,1\}$, what fanout size is necessary and sufficient for computing $f$ in $\mathsf{QAC}^0$? We show that the answer is exactly the transition radius $\rho(f)$: computing $f$ and implementing $\mathtt{FANOUT}_{\rho(f)}$ are equivalent under $\mathsf{QAC}^0$ reductions. In particular, if $\rho(f)\ge n^\delta$ for some constant $\delta>0$, then computing $f$ is $\mathsf{QAC}^0_{\mathrm{f}}$-complete. Combined with Paturi's theorem, our characterization implies that if $\mathtt{PARITY}_n \notin \mathsf{QAC}^0$, then any Boolean function in $\mathsf{QAC}^0$ of approximate degree $n^{1/2+\Omega(1)}$ must be nonsymmetric.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
Whether $\mathsf{QAC}^0$ can compute $\mathtt{PARITY}_n$ remains open. Computing $\mathtt{PARITY}_n$ is equivalent to implementing $\mathtt{FANOUT}_n$ under $\mathsf{QAC}^0$ reductions. This raises a more general question: for an arbitrary symmetric Boolean function $f:\{0,1\}^n\to\{0,1\}$, what fanout size is necessary and sufficient for computing $f$ in $\mathsf{QAC}^0$? We show that the answer is exactly the transition radius $\rho(f)$: computing $f$ and implementing $\mathtt{FANOUT}_{\rho(f)}$ are equivalent under $\mathsf{QAC}^0$ reductions. In particular, if $\rho(f)\ge n^\delta$ for some constant $\delta>0$, then computing $f$ is $\mathsf{QAC}^0_{\mathrm{f}}$-complete. Combined with Paturi's theorem, our characterization implies that if $\mathtt{PARITY}_n \notin \mathsf{QAC}^0$, then any Boolean function in $\mathsf{QAC}^0$ of approximate degree $n^{1/2+\Omega(1)}$ must be nonsymmetric.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Whether $\mathsf{QAC}^0$ can compute $\mathtt{PARITY}_n$ remains open. | gap 0.75 | 0.04 | 0.02 | asserted 0.78 |
| s1 | Computing $\mathtt{PARITY}_n$ is equivalent to implementing $\mathtt{FANOUT}_n$ under $\mathsf{QAC}^0$ reductions. | background 0.85 | 0.16 | 0.05 | asserted 1.00 |
| s2 | This raises a more general question: for an arbitrary symmetric Boolean function $f:\{0,1\}^n\to\{0,1\}$, what fanout size is necessary and sufficient for computing $f$ in $\mathsf{QAC}^0$? | gap 0.65 | 0.06 | 0.04 | unclear 0.78 |
| s3 | We show that the answer is exactly the transition radius $\rho(f)$: computing $f$ and implementing $\mathtt{FANOUT}_{\rho(f)}$ are equivalent under $\mathsf{QAC}^0$ reductions. | result 0.93 | 0.95 | 0.90 | asserted 1.00 |
| s4 | In particular, if $\rho(f)\ge n^\delta$ for some constant $\delta>0$, then computing $f$ is $\mathsf{QAC}^0_{\mathrm{f}}$-complete. | result 0.85 | 0.90 | 0.16 | asserted 1.00 |
| s5 | Combined with Paturi's theorem, our characterization implies that if $\mathtt{PARITY}_n \notin \mathsf{QAC}^0$, then any Boolean function in $\mathsf{QAC}^0$ of approximate degree $n^{1/2+\Omega(1)}$ must be nonsymmetric. | interpretation 0.94 | 0.76 | 0.11 | asserted 0.94 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.