${\mathsf{QAC}}^0$ Contains ${\mathsf{TC}}^0$ (with Many Copies of the Input)

Abstract

${\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.