2026/07/31 by Omar Alrabiah, Srinivasan Arunachalam, Sabee Grewal +1
Physics and Astronomy · Computer Science · #quant-ph #cs.CC
37 pages
arxiv created 2026/07/31 · arxiv updated 2026/08/04
We study the problem of testing low-degree phase states, namely m-qudit quantum states of the form q-m/2 ∑_x ∈ \mathbbFqm ω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 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.