No low-degree tests for quantum states

We study the problem of testing low-degree phase states, namely m-qudit quantum states of the form q^-m/2 sum_{x in mathbb{F}_q^m} omega^f(x) |x>, where f is a degree-d polynomial. In contrast to the classical setting, where low-degree polynomials admit highly efficient classical testers, it is not known whether analogous quantum tests exist. We show that no such quantum low-degree test exists: any tester requires Omega\(binom{lfloor m/2rfloor}{lfloor (d-1\)/2 rfloor}) copies to determine whether a given state is a degree-d phase state or is far from every such state. Our results follow from a general framework that relates quantum testing of codeword phase states to classical decoding properties of the dual code, which allows us to leverage known bounds on the tolerance of high-rate Reed--Muller codes to random errors.