mathsf{QAC}⁰ Contains mathsf{TC}⁰ (with Many Copies of the Input)

mathsf{QAC}⁰ 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}⁰ lower bounds to mathsf{QAC}⁰ have failed. We give one possible explanation of this: mathsf{QAC}⁰ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation mathsf{QAC}^{0notsubsetmathsf}{AC}⁰[p] for decision problems, which also resolves for the first time whether mathsf{AC}⁰ could be more powerful than mathsf{QAC}⁰. Moreover, we prove that mathsf{QAC}⁰ circuits can compute a wide range of Boolean functions if given multiple copies of the input: mathsf{TC}⁰ subseteq mathsf{QAC}⁰ circ mathsf{NC}⁰. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.