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.