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
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Gangopadhyay, Sugata; Pasalic, Enes; Stănică, 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 ...
Medina, Luis A.; Parker, Matthew G.; Riera, Constanza; Stănică, Pantelimon (Springer, 2019-07);In this paper we define a new transform on (generalized) Boolean functions, which generalizes the Walsh-Hadamard, nega-Hadamard, 2k-Hadamard, consta-Hadamard and all HN-transforms. We describe the behavior of what we call ...
Mesnager, Sihem; Riera, Constanza; Stănică, Pantelimon (Springer, 2019);In this paper we investigate generalized Boolean functions whose spectrum is flat with respect to a set of Walsh-Hadamard transforms defined using various complex primitive roots of 1. We also study some differential ...