On the Pauli Spectrum of QAC0

The circuit class QAC⁰ was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower bounds against such circuits is a longstanding challenge in quantum circuit complexity; in particular, showing that polynomial-size QAC⁰ cannot compute the parity function has remained an open question for over 20 years. In this work, we identify a notion of the Pauli spectrum of QAC⁰ circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical AC⁰ circuits. We conjecture that the Pauli spectrum of QAC⁰ circuits satisfies low-degree concentration, in analogy to the famous Linial, Mansour, Nisan (LMN) theorem on the low-degree Fourier concentration of AC⁰ circuits. If true, this conjecture immediately implies that polynomial-size QAC⁰ circuits cannot compute parity. We prove this conjecture for the class of depth-d, polynomial-size QAC⁰ circuits with at most n^O(1/d) auxiliary qubits. We obtain new circuit lower bounds and learning results as applications: this class of circuits cannot correctly compute the n-bit parity function on more than (1/2 + 2^−Ω(n1/d))-fraction of inputs, and the n-bit majority function on more than (1/2 + O(n^−1/4))-fraction of inputs. Additionally we show that this class of QAC⁰ circuits with limited auxiliary qubits can be learned with quasipolynomial sample complexity, giving the first learning result for QAC⁰ circuits. More broadly, our results add evidence that “Pauli-analytic” techniques can be a powerful tool in studying quantum circuits.