<p>We propose a family of quantum algorithms for estimating Gowers uniformity norms <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$ U^k $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>U</mi> <mi>k</mi> </msup> </math></EquationSource> </InlineEquation> over finite abelian groups, extending earlier quantum methods for the <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$ U^2 $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>U</mi> <mn>2</mn> </msup> </math></EquationSource> </InlineEquation>-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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$ f: \mathbb {F}_p^n \rightarrow \mathbb {C} $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>f</mi> <mo>:</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>p</mi> <mi>n</mi> </msubsup> <mo stretchy="false">→</mo> <mi mathvariant="double-struck">C</mi> </mrow> </math></EquationSource> </InlineEquation> is a low-degree phase polynomial or is far from any such structure. We show that whenever an inverse theorem for the <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$ U^{d+1} $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>U</mi> <mrow> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> </math></EquationSource> </InlineEquation>-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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$ U^4 $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>U</mi> <mn>4</mn> </msup> </math></EquationSource> </InlineEquation>-norm over <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$ \mathbb {F}_p^n $</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>p</mi> <mi>n</mi> </msubsup> </math></EquationSource> </InlineEquation>, we obtain quasipolynomial-time quantum algorithms for detecting cubic phase polynomials. For higher-order norms such as <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$ U^5 $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>U</mi> <mn>5</mn> </msup> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$ U^6 $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>U</mi> <mn>6</mn> </msup> </math></EquationSource> </InlineEquation> over <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$ \mathbb {F}_2^n $</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi mathvariant="double-struck">F</mi> <mn>2</mn> <mi>n</mi> </msubsup> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$ U^2 $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>U</mi> <mn>2</mn> </msup> </math></EquationSource> </InlineEquation>-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.</p>

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

期刊论文
出版模式：

开放获取
发表日期：

2026年4月13日

查看全文

En-Jui Kuo

摘要

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} \to 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.