Quantum algorithms for Gowers norm estimation, polynomial testing, and arithmetic progression counting over finite abelian groups
Author:
Open Access
- 13 April 2026
- journal article
- research article
- Published by Springer Nature in Quantum Information Processing
- Vol. 25 (5) , 141
Abstract
We propose a family of quantum algorithms for estimating Gowers uniformity norms $$ U^k $$ over finite abelian groups, extending earlier quantum methods for the $$ 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} $$ 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} $$ -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 $$ -norm over $$ \mathbb {F}_p^n $$ , we obtain quasipolynomial-time quantum algorithms for detecting cubic phase polynomials. For higher-order norms such as $$ U^5 $$ and $$ U^6 $$ over $$ \mathbb {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 $$ -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.
Keywords
All Related Versions
Funding Information
- National Science and Technology Council (114-2112-M-A49-036-MY3)
- National Yang Ming Chiao Tung University
This publication has 38 references indexed in Scilit:
- The complexity of NISQNature Communications, 2023
- A quantum algorithm to estimate the Gowers $U_2$ norm and linearity testing of Boolean functionsQuantum Information Processing, 2020
- Ergodic Theory and Dynamical Systems in their Interactions with Arithmetics and Combinatorics2018
- The Inverse Conjecture for the Gowers Norm over Finite Fields in Low CharacteristicAnnals of Combinatorics, 2011
- An Inverse Theorem for the Uniformity Seminorms Associated with the Action of ${{\mathbb {F}^{\infty}_{p}}}$Geometric and Functional Analysis, 2010
- AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORMProceedings of the Edinburgh Mathematical Society, 2008
- Strong coupling of a single photon to a superconducting qubit using circuit quantum electrodynamicsNature, 2004
- A new proof of Szemerédi's theoremGeometric and Functional Analysis, 2001
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993
- Linear Representations of Finite Groups1977