  Non-linearity of a Boolean function indicates how far it is from any linear
function. Despite there being several strong results about identifying a linear
function and distinguishing one from a sufficiently non-linear function, we
found a surprising lack of work on computing the non-linearity of a function.
The non-linearity is related to the Walsh coefficient with the largest absolute
value; however, the naive attempt of picking the maximum after constructing a
Walsh spectrum requires $\Theta(2^n)$ queries to an $n$-bit function. We
improve the scenario by designing highly efficient quantum and randomised
algorithms to approximate the non-linearity allowing additive error, denoted
$\lambda$, with query complexities that depend polynomially on $\lambda$. We
prove lower bounds to show that these are not very far from the optimal ones.
The number of queries made by our randomised algorithm is linear in $n$,
already an exponential improvement, and the number of queries made by our
quantum algorithm is surprisingly independent of $n$. Our randomised algorithm
uses a Goldreich-Levin style of navigating all Walsh coefficients and our
quantum algorithm uses a clever combination of Deutsch-Jozsa, amplitude
amplification and amplitude estimation to improve upon the existing quantum
versions of the Goldreich-Levin technique.
