Quantum algorithms for Gowers norm estimation, polynomial testing, and arithmetic progression counting over finite abelian groups

Abstract We propose a family of quantum algorithms for estimating Gowers uniformity norms $$ U^k $$ U k over finite abelian groups, extending earlier quantum methods for the $$ U^2 $$ U 2 -norm to arbitrary prime fields and higher-order uniformity norms. Our algorithms prepare quantum states encoding higher-order finite differences and apply Fourier sampling together with amplitude estimation to obtain estimates of Gowers norms. As a central application, we study algebraic property testing problems of distinguishing whether a bounded function $$ f: \mathbb {F}_p^n \rightarrow \mathbb {C} $$ f : F p n → C is a low-degree phase polynomial or is far from any such structure. We show that whenever an inverse theorem for the $$ U^{d+1} $$ U d + 1 -norm is available, our quantum framework yields a corresponding structure-testing algorithm whose query and measurement complexity depends explicitly on the quantitative bounds of that inverse theorem. In particular, using the recent quasipolynomial inverse theorem for the $$ U^4 $$ U 4 -norm over $$ \mathbb {F}_p^n $$ F p n , we obtain quasipolynomial-time quantum algorithms for detecting cubic phase polynomials. For higher-order norms such as $$ U^5 $$ U 5 and $$ U^6 $$ U 6 over $$ \mathbb {F}_2^n $$ F 2 n , the best known inverse theorems provide only tower-type quantitative bounds; accordingly, our detection algorithms remain correct but inherit complexity corresponding to tower-type quantitative bounds. We also present a quantum method for estimating the number of 3-term arithmetic progressions in Boolean functions via the $$ U^2 $$ U 2 -norm. Although not query-optimal compared to Grover-style counting, this approach is sensitive to additive structure and naturally aligned with tools from higher-order Fourier analysis. Finally, we observe that Gowers norms are invariant under certain classes of shift-type noise, implying that our algorithms retain robustness under natural quantum noise models. This suggests that Gowers norm-based quantum procedures may serve as stable primitives for quantum property testing, learning theory, and the analysis of pseudorandomness in the NISQ regime.