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⊕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.
We have measured the autocorrelations for the Swendsen-Wang and the Wolff cluster update algorithms for the Ising model in two, three, and four dimensions. The data for the Wolff algorithm suggest that the autocorrelations are linearly related to the specific heat, in which case the dynamic critical exponent is
zint,EW=\ensuremath{\alpha}/\ensuremath{\nu}. For the Swendsen-Wang algorithm, scaling the autocorrelations by the average maximum cluster size gives either a constant or a logarithm, which implies that
zint,ESW=\ensuremath{\beta}/\ensuremath{\nu} for the Ising model.