Improved Lower Bounds for QAC0

In this work, we establish the strongest known lower bounds against QAC0, while allowing its full power of polynomially many ancillae and gates. Our two main results show that: (1) Depth 3 QAC0 circuits cannot compute PARITY regardless of size, and require at least Ω(exp(√n)) many gates to compute MAJORITY. (2) Depth 2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size. We present new techniques for simulating certain QAC0 circuits classically in AC0 to obtain our depth 3 lower bounds. In these results, we relax the output requirement of the quantum circuit to a single bit (i.e., no restrictions on input preservation/reversible computation), making our depth 2 approximation bound stronger than the previous bounds. This also enables us to draw natural comparisons with classical AC0 circuits, which can compute PARITY exactly in depth 2 using exponential size. Our proof techniques further suggest that, for Boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth 2 QAC0 circuits, regardless of size, cannot exactly synthesize an n-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth 2 exponential size upper bound for approximating nekomata, which is used as a sub-circuit in all known constant depth PARITY upper bounds. Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems.