Quantum algorithms on Walsh transform and Hamming distance for Boolean functions

摘要

Walsh spectrum or Walsh transform is an alternative description of Boolean functions. In this paper, we explore quantum algorithms to approximate the absolute value of Walsh transform W-f at a single point z(0) (i.e., |W-f (z(0))|) for n-variable Boolean functions with probability at least 8/pi(2) using the number of O(1/vertical bar W-f (z(0))vertical bar epsilon) queries, promised that the accuracy is epsilon, while the best known classical algorithm requires O(2(n)) queries. The Hamming distance between Boolean functions is used to study the linearity testing and other important problems. We take advantage of Walsh transform to calculate the Hamming distance between two n-variable Boolean functions f and g using O(1) queries in some cases. Then, we exploit another quantum algorithm which converts computing Hamming distance between two Boolean functions to quantum amplitude estimation (i.e., approximate counting). If Ham(f, g) = t not equal 0, we can approximately compute Ham(f,g) with probability at least 2/3 by combining our algorithm and Approx - Count (f, epsilon) algorithm using the expected number of Theta(root N/([epsilon t] + 1) + root t(N-t)/[epsilon t] + 1) queries, promised that the accuracy is epsilon. Moreover, our algorithm is optimal, while the exact query complexity for the above problem epsilon is Theta(N) and the query complexity with the accuracy epsilon is O(1/epsilon(2) N/(t + 1)) in classical algorithm, where N = 2(n). Finally, we present three exact quantum query algorithms for two promise problems on Hamming distance using O(1) queries, while any classical deterministic algorithm solving the problem uses O(2(n)) queries.