A quantum algorithm to estimate the Gowers $U_2$ norm and linearity testing of Boolean functions

C. A. Jothishwaran, Anton Tkachenko, Sugata Gangopadhyay +2

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 Bo…