{"id":"arxiv/2608.00265","url":"https://arxiv.org/abs/2608.00265","tags":["quant-ph","cs.CC"],"score":0,"title":"No low-degree tests for quantum states","domain":"quant-ph","source":"arxiv","authors":["Omar Alrabiah","Srinivasan Arunachalam","Sabee Grewal","John Wright"],"reviews":0,"subject":"quant-ph","summary":"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} ω^{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 $Ω(\\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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-31","reactions":{}}