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 $ρ(f)$: computing $f$ and implementing $\mathtt{FANOUT}_{ρ(f)}$ are equivalent under $\mathsf{QAC}^0$ reductions. In particular, if $ρ(f)\ge n^δ$ for some constant $δ>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+Ω(1)}$ must be nonsymmetric.
Fanout Complexity of Symmetric Boolean Functions in QAC0
Whether QAC0 can compute PARITYn remains open. Computing PARITYn is equivalent to implementing FANOUTn under QAC0 reductions. This raises a more general question: for an arbitrary symmetric Boolean function f:{0,1}n→{0,1}, what fanout size is necessary and sufficient for computing f in QAC0? We show that the answer is exactly the transition radius ρ(f): computing f and implementing FANOUTρ(f) are equivalent under QAC0 reductions. In particular, if ρ(f)≥nδ for some constant δ>0, then computing f is QACf0-complete. Combined with Paturi's theorem, our characterization implies that if PARITYn∈/QAC0, then any Boolean function in QAC0 of approximate degree n1/2+Ω(1) must be nonsymmetric.
A Nearly Optimal Lower Bound on the Approximate Degree of AC0
The approximate degree of a Boolean function f:{−1,1}n→{−1,1} is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function f with approximate degree d into a function F on O(n⋅polylog(n)) variables with approximate degree at least D=Ω(n1/3⋅d2/3). In particular, if d=n1−Ω(1), then D is polynomially larger than d. Moreover, if f is computed by a polynomial-size Boolean circuit of constant depth, then so is F. By recursively applying our transformation, for any constant δ>0 we exhibit an AC0 function of approximate degree Ω(n1−δ). This improves over the best previous lower bound of Ω(n2/3) due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of n that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: * For any constant δ>0, an Ω(n1−δ) lower bound on the quantum communication complexity of a function in AC0. * A Boolean function f with approximate degree at least C(f)2−o(1), where C(f) is the certificate complexity of f. This separation is optimal up to the o(1) term in the exponent. * Improved secret sharing schemes with reconstruction procedures in AC0.
We give and prove an optimal exact quantum query algorithm with complexity k+1 for computing the promise problem (i.e., symmetric and partial Boolean function) DJnk defined as: DJnk(x)=1 for ∣x∣=n/2, DJnk(x)=0 for ∣x∣ in the set {0,1,…,k,n−k,n−k+1,…,n}, and it is undefined for the rest cases, where n is even, ∣x∣ is the Hamming weight of x. The case of k=0 is the well-known Deutsch-Jozsa problem. We outline all symmetric (and partial) Boolean functions with degrees 1 and 2, and prove their exact quantum query complexity. Then we prove that any symmetrical (and partial) Boolean function f has exact quantum 1-query complexity if and only if f can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight {⌊n/2⌋,⌈n/2⌉} and Hamming weight in the set {0,n} for all odd n. In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.
A Nearly Optimal Lower Bound on the Approximate Degree of AC0
The approximate degree of a Boolean function f:{−1,1}n→{−1,1} is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function f with approximate degree d into a function F on O(n⋅polylog(n)) variables with approximate degree at least D=Ω(n1/3⋅d2/3). In particular, if d=n1−Ω(1), then D is polynomially larger than d. Moreover, if f is computed by a polynomial-size Boolean circuit of constant depth, then so is F. By recursively applying our transformation, for any constant δ>0 we exhibit an AC0 function of approximate degree Ω(n1−δ). This improves upon the best previous lower bound of Ω(n2/3) due to Aaronson and Shi [ J. ACM, 51 (2004), pp. 595--605] and nearly matches the trivial upper bound of n that holds for any function. Our lower bounds also apply to (quasipolynomial-size) disjunctive normal forms of polylogarithmic width. We describe several applications of these results and provide the following: (i) for any constant δ>0, an Ω(n1−δ) lower bound on the quantum communication complexity of a function in AC0; (ii) a Boolean function f with approximate degree at least C(f)2−o(1), where C(f) is the certificate complexity of f; this separation is optimal up to the o(1) term in the exponent; (iii) improved secret sharing schemes with reconstruction procedures in AC0.
We propose definitions of QAC^0, the quantum analog of the classical class AC^0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC[q], the analog of the class ACC[q] where Mod_q gates are also allowed. We prove that parity or fanout allows us to construct quantum MOD_q gates in constant depth for any q, so QACC[2] = QACC. More generally, we show that for any q,p > 1, MOD_q is equivalent to MOD_p (up to constant depth and polynomial size). This implies that QAC^0 with unbounded fanout gates, denoted QACwf^0, is the same as QACC[q] and QACC for all q. Since \ACC[p] \ne ACC[q] whenever p and q are distinct primes, QACC[q] is strictly more powerful than its classical counterpart, as is QAC^0 when fanout is allowed. This adds to the growing list of quantum complexity classes which are provably more powerful than their classical counterparts. We also develop techniques for proving upper bounds for QACC in terms of related language classes. We define classes of languages closely related to QACC[2] and show that restricted versions of them can be simulated by polynomial-size circuits. With further restrictions, language classes related to QACC[2] operators can be simulated by classical threshold circuits of polynomial size and constant depth.
Polylogarithmic-Weight Dicke States in QAC0 and Arbitrary Symmetric States in QACf0
An n-qubit Dicke state of weight k, is the uniform superposition over all n-bit strings of Hamming weight k. Dicke states are central to quantum algorithms exhibiting speedups, such as Decoded Quantum Interferometry (Jordan et al., \emph{Nature}, 2025). In the NISQ era, quantum hardware is constrained by both depth and locality, motivating the question of which global operations suffice to prepare such states. QAC0, the quantum analogue of AC0, minimally extends local O(1)-depth quantum circuits by allowing arbitrary-width Toffoli (reversible AND) gates.
We show that Dicke states of polylog(n) weight can be prepared in QAC0. This gives the first QAC0 construction of any super-constant-weight n-qubit Dicke state, since previous constructions relied on the much more powerful FANOUTn gate. In general, we show that any weight-k Dicke state can be constructed using FANOUTmin(k,n−k) gates. Combined with recent hardness results, this yields a tight characterization: for k≤n/2, a n-qubit weight-k Dicke state can be prepared in QAC0 if and only if FANOUTk∈ QAC0. We develop a limited-fanout state-synthesis toolkit for QAC0 that yields further constant-depth, poly(n)-ancilla constructions:
1. Every n-qubit symmetric state supported on Hamming weight ≤k can be prepared using FANOUTk gates.
2. Every O(logn)-qubit state can be prepared using quantum random-access memory (QRAMn), which refers to a coherent indexing gate. QRAMn is a potentially weaker resource than FANOUTn and can be implemented in QACf0.
In this work we study the robustness of QAC0 with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for QAC0 circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel W-test of \cite{grier_morris_wu} can be eliminated entirely via a novel application of exact amplitude amplification in the many-copies context. Consequently, we find that QAC0 can \textit{exactly} simulate TC0 with polynomially many copies of the classical input and that for every fixed prime p exact QAC0, EQAC0, can compute total Boolean functions outside of AC0[p].
Second, we ask to what extent the computational power of QAC0 follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that QAC0 is in fact robust to restrictions on which single-qubit gates are permitted: every QAC0 circuit can be approximately implemented by a QAC0 circuit consisting of just generalized Toffoli, S, and Hadamard gates. Moreover, this approximating circuit can be constructed efficiently from a classical description of the original circuit.