Quantum Algorithms for Gowers Norm Estimation, Polynomial Testing, and Arithmetic Progression Counting over Finite Abelian Groups
Author:
Preprint
Abstract
We propose a family of quantum algorithms for estimating Gowers uniformity norms $ U^k $ over finite abelian groups and demonstrate their applications to testing polynomial structure and counting arithmetic progressions. Building on recent work for estimating the $ U^2 $-norm over $ \mathbb{F}_2^n $, we generalize the construction to arbitrary finite fields and abelian groups for higher values of $ k $. Our algorithms prepare quantum states encoding finite differences and apply Fourier sampling to estimate uniformity norms, enabling efficient detection of structural correlations. As a key application, we show that for certain degrees $ d = 4, 5, 6 $ and under appropriate conditions on the underlying field, there exist quasipolynomial-time quantum algorithms that distinguish whether a bounded function $ f(x) $ is a degree-$ d $ phase polynomial or far from any such structure. These algorithms leverage recent inverse theorems for Gowers norms, together with amplitude estimation, to reveal higher-order algebraic correlations. We also develop a quantum method for estimating the number of 3-term arithmetic progressions in Boolean functions $ f : \mathbb{F}_p^n \to \{0,1\} $, based on estimating the $ U^2 $-norm. Though not as query-efficient as Grover-based counting, our approach provides a structure-sensitive alternative aligned with additive combinatorics. Finally, we demonstrate that our techniques remain valid under certain quantum noise models, due to the shift-invariance of Gowers norms. This enables noise-resilient implementations within the NISQ regime and suggests that Gowers-norm-based quantum algorithms may serve as robust primitives for quantum property testing, learning, and pseudorandomness.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Classical and Quantum Algorithms for Characters of the Symmetric GroupPRX Quantum, 2025
- Quantum Algorithms for Representation-Theoretic MultiplicitiesPhysical Review Letters, 2025
- The complexity of NISQNature Communications, 2023
- A quantum engineer's guide to superconducting qubitsApplied Physics Reviews, 2019
- Trapped-ion quantum computing: Progress and challengesApplied Physics Reviews, 2019
- The Inverse Conjecture for the Gowers Norm over Finite Fields in Low CharacteristicAnnals of Combinatorics, 2011
- 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
- Power of One Bit of Quantum InformationPhysical Review Letters, 1998
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993