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

Daniel Grier, Jackson Morris, Kewen Wu

${\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 sma…