Quantum Algorithms Related to HN-Transforms of Boolean Functions
MetadataShow full item record
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ᶯ possible HN-spectra of a Boolean function in n variables, each containing 2 ᶯn elements (i.e., in total 2²ᶯ values in transformed domain) can be computed in O(2²ᶯ) time (more specific with little less than 2²ᶯ+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.
The article of record as published may be found at http://link.springer.com/content/pdf/10.1007/978-3-319-55589-8.pdf#page=325
Showing items related by title, author, creator and subject.
Gangopadhyay, Sugata; Pasalic, Enes; Stanica, Pantelimon (2012);In this paper, we consider the spectra of Boolean functions with respect to the action of unitary transforms obtained by taking tensor products of the Hadamard kernel, denoted by H, and the nega–Hadamard kernel, denoted ...
Correlation immunity, avalanche features, and other cryptographic properties of generalized Boolean functions Martinsen, Thor (Monterey, California: Naval Postgraduate School, 2017-09);This dissertation investigates correlation immunity, avalanche features, and the bent cryptographic properties for generalized Boolean functions defined on Vn with values in Zԛ. We extend the concept of correlation immunity ...
Gangopadhyay, Sugata; Gangopadhyay, Aditi Kar; Pollatos, Spyridon; Stănică, Pantelimon (2015-07-31);While performing cryptanalysis, it is of interest to approximate a Boolean function in n variables f : Fn → F2 by affine functions. Usually, it is assumed that all the input vectors to a Boolean function are equiprobable ...