Unconditionally separating noisy QNC⁰ from bounded polynomial threshold circuits of constant depth

We study classes of constant-depth circuits with gates that compute restricted polynomial threshold functions, recently introduced by Kum23 as a family that strictly generalizes AC⁰. Denoting these circuit families bPTFC⁰k for bounded polynomial threshold circuits parameterized by an integer-valued degree-bound k, we prove three hardness results separating these classes from constant-depth quantum circuits (QNC⁰). 2em - We prove that the parity halving problem WKS+19, which QNC⁰ over qubits can solve with certainty, remains average-case hard for polynomial size bPTFC⁰k circuits for all k=O (n^1/ (5d) ). 2em - We construct a new family of relation problems based on computing mod\ p for each prime p>2, and prove a separation of QNC⁰ circuits over higher dimensional quantum systems (`qupits') against bPTFC⁰k circuits for the same degree-bound parameter as above. 2em - We prove that both foregoing results are noise-robust under the local stochastic noise model, by introducing fault-tolerant implementations of non-Clifford QNC⁰/|T^1/p> circuits, that use logical magic states as advice. bPTFC⁰k circuits can compute certain classes of Polynomial Threshold Functions (PTFs), which in turn serve as a natural model for neural networks and exhibit enhanced expressivity and computational capabilities. Furthermore, for large enough values of k, bPTFC⁰k contains TC⁰ as a subclass. The main challenges we overcome include establishing classical average-case lower bounds, designing non-local games with quantum-classical gaps in winning probabilities and developing noise-resilient non-Clifford quantum circuits necessary to extend beyond qubits to higher dimensions.