On the Computational Power of QAC0 with Barely Superlinear Ancillae

Anurag Anshu, Yangjing Dong, Fengning Ou +1

${\mathrm{QAC}}^0$ is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by…