  The circuit class $\mathsf{QAC}^0$ 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 $\mathsf{QAC}^0$ 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 $\mathsf{QAC}^0$
circuits, which can be viewed as the quantum analogue of the Fourier spectrum
of classical $\mathsf{AC}^0$ circuits. We conjecture that the Pauli spectrum of
$\mathsf{QAC}^0$ circuits satisfies low-degree concentration, in analogy to the
famous Linial, Nisan, Mansour theorem on the low-degree Fourier concentration
of $\mathsf{AC}^0$ circuits. If true, this conjecture immediately implies that
polynomial-size $\mathsf{QAC}^0$ circuits cannot compute parity.
  We prove this conjecture for the class of depth-$d$, polynomial-size
$\mathsf{QAC}^0$ 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 $(\frac{1}{2} +
2^{-\Omega(n^{1/d})})$-fraction of inputs, and
  - the $n$-bit majority function on more than $(1 -
1/\mathrm{poly}(n))$-fraction of inputs.
  Additionally we show that this class of $\mathsf{QAC}^0$ circuits with
limited auxiliary qubits can be learned with quasipolynomial sample complexity,
giving the first learning result for $\mathsf{QAC}^0$ circuits.
  More broadly, our results add evidence that "Pauli-analytic" techniques can
be a powerful tool in studying quantum circuits.
