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

06/30/2020
by   C. A. Jothishwaran, et al.
0

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 ϵ-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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset