  In this paper, we propose efficient probabilistic algorithms for several
problems regarding the autocorrelation spectrum. First, we present a quantum
algorithm that samples from the Walsh spectrum of any derivative of $f()$.
Informally, the autocorrelation coefficient of a Boolean function $f()$ at some
point $a$ measures the average correlation among the values $f(x)$ and $f(x
\oplus a)$. The derivative of a Boolean function is an extension of
autocorrelation to correlation among multiple values of $f()$. The Walsh
spectrum is well-studied primarily due to its connection to the quantum circuit
for the Deutsch-Jozsa problem. We extend the idea to "Higher-order
Deutsch-Jozsa" quantum algorithm to obtain points corresponding to large
absolute values in the Walsh spectrum of a certain derivative of $f()$.
Further, we design an algorithm to sample the input points according to squares
of the autocorrelation coefficients. Finally we provide a different set of
algorithms for estimating the square of a particular coefficient or cumulative
sum of their squares.
