On the Computational Power of QAC0 with Barely Superlinear Ancillae

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 Moore as a quantum counterpart of AC 0 , along with the conjecture that QAC 0 circuits cannot compute PARITY. In this work, we make progress on this long-standing conjecture: we show that any depth-𝑑 QAC 0 circuit requires 𝑛 1+3 -𝑑 ancillae to compute a function with approximate degree Θ(𝑛), which includes PARITY, MAJORITY and MOD 𝑘 . We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first lower bound on the super-linear sized QAC 0 . Regarding PARITY, we show that any further improvement on the size of ancillae to 𝑛 1+exp(-𝑜 (𝑑) ) would imply that PARITY ∉ QAC 0 . These lower bounds are derived by giving low-degree approximations to QAC 0 circuits. We show that a depth-𝑑 QAC 0 circuit with 𝑎 ancillae, when applied to low-degree operators, has a degree (𝑛 + 𝑎) 1-3 -𝑑 polynomial approximation in the spectral norm. This implies that the class QLC 0 , corresponding to linear size QAC 0 circuits, has an approximate degree 𝑜(𝑛). This is a quantum generalization of the result that LC 0 circuits have an approximate degree 𝑜(𝑛) by Bun, Kothari, and Thaler. Our result also implies that QLC 0 ≠ NC 1 .