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