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} \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/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.

Quantum Physics (quant-ph); Computational Complexity (cs.CC)

arXiv:2608.00265 [quant-ph]

(or arXiv:2608.00265v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2608.00265 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.