2018/08/10 by Debajyoti Bera, Subhamoy Maitra, Bera, Debajyoti +3
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata
paper · pdf · doi:10.48550/arxiv.1808.04448
openalex publication_date 2018/08/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.