← Back to papers
A quantum algorithm to estimate the Gowers U2 norm and linearity testing of Boolean functions
C. A. Jothishwaran, Anton Tkachenko, S. Gangopadhyay, Constanza Riera, P. Stănică·June 1, 2020·DOI: 10.1007/s11128-020-02817-z
MathematicsComputer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We propose a quantum algorithm to estimate the Gowers $U_2$ norm of a Boolean function, and extend it into a second algorithm to distinguish between linear Boolean functions and Boolean functions that are $\epsilon$-far from the set of linear Boolean functions, which seems to perform better than the classical BLR algorithm. Finally, we outline an algorithm to estimate Gowers $U_3$ norms of Boolean functions.