Parity and circuit complexity

For a Walsh character of degree $k$,

Thus parity is degree two in our finite example and degree $n$ on the full $n$-variable parity family. This is a spectral calculation, not a circuit lower bound.

A QAC${}^0$ parity obstruction concerns allowed gates, depth, size, and possibly ancillary systems. None of those parameters occurs in Theorem thm:finite. Conversely, no nominated circuit-complexity theorem proves the Hellinger inequality.