(\mathrm{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 [arXiv: 9903046] as a quantum counterpart of (\mathrm{AC}^0), along with the conjecture that (\mathrm{QAC}^0) circuits can not compute PARITY. In this work we make progress on this longstanding conjecture: we show that any depth-(d) (\mathrm{QAC}^0) circuit requires (n^{1+3^{-d}}) ancillae to compute a function with approximate degree (\Theta(n)), which includes PARITY, MAJORITY and (\mathrm{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 (\mathrm{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 (\not\in) QAC0. These lower bounds are derived by giving low-degree approximations to (\mathrm{QAC}^0) circuits. We show that a depth-(d) (\mathrm{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 (\mathrm{QLC}^0), corresponding to linear size (\mathrm{QAC}^0) circuits, has approximate degree (o(n)). This is a quantum generalization of the result that (\mathrm{LC}^0) circuits have approximate degree (o(n)) by Bun, Robin, and Thaler [SODA 2019]. Our result also implies that (\mathrm{QLC}^0\neq\mathrm{NC}^1).