Quantum Algorithms Related to HN-Transforms of Boolean Functions
Loading...
Authors
Gangopadhyay, Sugata
Maitra, Subhamoy
Sinha, Nishant
Stănică, Pantelimon
Subjects
Boolean function
HN-transform
Deutsch-Jozsa algorithm
HN-transform
Deutsch-Jozsa algorithm
Advisors
Date of Issue
2017
Date
Publisher
Springer
Language
Abstract
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.
Type
Article
Description
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
Series/Report No
Department
Applied Mathematics
Organization
Naval Postgraduate School (U.S.)
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
14 p.
Citation
Sugata Gangopadhyay, Subhamoy Maitra, Nishant Sinha and Pantelimon Stănică. "Quantum Algorithms Related to HN-Transforms of Boolean Functions." In Codes, Cryptology and Information Security: Second International Conference, C2SI 2017, Rabat, Morocco, April 10–12, 2017, Proceedings-In Honor of Claude Carlet, vol. 10194, p. 314. Springer, 2017.
Distribution Statement
Rights
This 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.