No low-degree tests for quantum states

Abstract

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}\ddot{I}{‰}^{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 $\hat{I}\text{c◯}((\genfrac{}{}{0ex}{}{\lfloor m/2\rfloor }{\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.

37 pages