QAC^0 contains TC^0 (with Many Copies of the Input)
Jackson Morris (UC San Diego)
Monday, March 9th, 2026, 2-3pm
Abstract:
QAC0 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
AC0 lower bounds to QAC0 have failed. We give one possible explanation of this: QAC0 circuits are significantly more powerful than their classical counterparts. We show the unconditional separation QAC0⊄AC0[p] for \emph{decision} problems, which also resolves for the first time whether AC0 could be more powerful than QAC0. Moreover, we prove that QAC0 circuits can compute a wide range of Boolean functions if given multiple copies of the input: TC0⊆QAC0∘NC0. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.