$\mathsf{ QAC}^0$ is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical $\mathsf{ AC}^0$ lower bounds to $\mathsf{ QAC}^0$ have failed. We give one possible explanation of this: $\mathsf{ QAC}^0$ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation $\mathsf{ QAC}^0\not\subset\mathsf{ AC}^0[p]$ for decision problems, which also resolves for the first time whether $\mathsf{ AC}^0$ could be more powerful than $\mathsf{ QAC}^0$. Moreover, we prove that $\mathsf{ QAC}^0$ circuits can compute a wide range of Boolean functions if given multiple copies of the input: $\mathsf{ TC}^0 \subseteq \mathsf{ QAC}^0 \circ \mathsf{ NC}^0$. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.
Categories: cs.CC quant-ph