On the Computational Power of QAC0 with Barely Superlinear Ancillae

QAC⁰ 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 Moore [arXiv: 9903046] as a quantum counterpart of AC⁰, along with the conjecture that QAC⁰ circuits can not compute PARITY. In this work we make progress on this longstanding conjecture: we show that any depth-d QAC⁰ circuit requires n^{1+3^-d} ancillae to compute a function with approximate degree Θ(n), which includes PARITY, MAJORITY and MOD_k. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first superlinear lower bound on the super-linear sized QAC⁰. Regarding PARITY, we show that any further improvement on the size of ancillae to n^1+exp(-o(d)) would imply that PARITY notin QAC0. These lower bounds are derived by giving low-degree approximations to QAC⁰ circuits. We show that a depth-d QAC⁰ circuit with a ancillae, when applied to low-degree operators, has a degree (n+a)^{1-3^-d} polynomial approximation in the spectral norm. This implies that the class QLC⁰, corresponding to linear size QAC⁰ circuits, has approximate degree o(n). This is a quantum generalization of the result that LC⁰ circuits have approximate degree o(n) by Bun, Robin, and Thaler [SODA 2019]. Our result also implies that QLC^0neqNC1.