STOC Conference 2025 Conference Paper
On the Computational Power of QAC0 with Barely Superlinear Ancillae
- Anurag Anshu
- Yangjing Dong
- Fengning Ou
- Penghui Yao
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 can not compute PARITY. In this work we make progress on this longstanding conjecture: we show that any depth- d QAC 0 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 0 . Regarding PARITY, we show that any further improvement on the size of ancillae to n 1+exp(− o ( d )) would imply that PARITY ∉ QAC0. These lower bounds are derived by giving low-degree approximations to QAC 0 circuits. We show that a depth- d QAC 0 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 0 , corresponding to linear size QAC 0 circuits, has approximate degree o ( n ). This is a quantum generalization of the result that LC 0 circuits have approximate degree o ( n ) by Bun, Robin, and Thaler. Our result also implies that QLC 0 ≠ NC 1 .