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(n1/(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⁰/|T1/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.