HN-transforms, which have been proposed as generalizations of Hadamard transforms, are constructed by tensoring Hadamard and nega-Hadamard kernels in any order. We show that all the 2~n possible HN-spectra of a Boolean function in n variables, each containing 2~n elements (i.e., in total 2~(2n) values in transformed domain) can be computed in O(2~(2n)) time (more specific with little less than 2~(2n+1) arithmetic operations). We propose a generalization of Deutsch-Jozsa algorithm, by employing HN-transforms, which can be used to distinguish different classes of Boolean functions over and above what is possible by the traditional Deutsch-Jozsa algorithm.
展开▼
