  QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of
arbitrary arity. QAC$^0$ circuits are QAC circuits of constant depth, and are
quantum analogues of AC$^0$ circuits. We prove the following:
  $\bullet$ For all $d \ge 7$ and $\varepsilon>0$ there is a depth-$d$ QAC
circuit of size $\exp(\mathrm{poly}(n^{1/d}) \log(n/\varepsilon))$ that
approximates the $n$-qubit parity function to within error $\varepsilon$ on
worst-case quantum inputs. Previously it was unknown whether QAC circuits of
sublogarithmic depth could approximate parity regardless of size.
  $\bullet$ We introduce a class of "mostly classical" QAC circuits, including
a major component of our circuit from the above upper bound, and prove a tight
lower bound on the size of low-depth, mostly classical QAC circuits that
approximate this component.
  $\bullet$ Arbitrary depth-$d$ QAC circuits require at least $\Omega(n/d)$
multi-qubit gates to achieve a $1/2 + \exp(-o(n/d))$ approximation of parity.
When $d = \Theta(\log n)$ this nearly matches an easy $O(n)$ size upper bound
for computing parity exactly.
  $\bullet$ QAC circuits with at most two layers of multi-qubit gates cannot
achieve a $1/2 + \exp(-o(n))$ approximation of parity, even non-cleanly.
Previously it was known only that such circuits could not cleanly compute
parity exactly for sufficiently large $n$.
  The proofs use a new normal form for quantum circuits which may be of
independent interest, and are based on reductions to the problem of
constructing certain generalizations of the cat state which we name "nekomata"
after an analogous cat y\=okai.
