Quantum Algorithms for Autocorrelation Spectrum
share
In this paper we design quantum algorithms for studying the autocorrelation spectrum of a Boolean function and its individual coefficients. 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 xor a). The Walsh spectrum is a related concept that is well-studied primarily due to its connection to the quantum circuit for the Deutsch-Jozsa problem but the autocorrelation spectrum has not received similar attention that we attempt to deliver in this paper. We propose efficient probabilistic algorithms for several problems regarding the autocorrelation spectrum. First and foremost, we give an algorithm that samples from the Walsh spectrum of any derivative of f(); the derivative of a Boolean function is an extension of autocorrelation to correlation among multiple values of f(). Using a relation between the 1st-order derivative and the autocorrelation coefficients, we design an algorithm to sample the input points according to squares of the autocorrelation coefficients. Then we given a different set of algorithms for estimating the square of a particular coefficient or cumulative sum of their squares. Our last algorithm combines the technique of amplitude estimation and amplification in a novel manner to find points with high values of autocorrelation coefficients.`
READ FULL TEXT