Cryptology ePrint Archive: Report 2013/232

Quantum algorithm to check Resiliency of a Boolean function

Kaushik Chakraborty and Subhamoy Maitra

Abstract: In this paper, for the first time, we present quantum algorithms to check the order of resiliency of a Boolean function. We first show that the Deutsch-Jozsa algorithm can be directly used for this purpose. We also point out how the quadratic improvement in query complexity over the Deutsch-Jozsa algorithm can be obtained using the well known Grover's algorithm. While the worst case quantum query complexity to check the resiliency order is exponential, we can cleverly devise a strategy so that the number of measurements are polynomial in number of input variables of the Boolean function. We also point out a subset of $n$-variable Boolean functions for which the algorithm works in polynomial many steps, i.e., we achieve exponential speed-up over best known classical algorithms.

Category / Keywords:

Publication Info: WCC 2013, Bergen, Norway

Date: received 22 Apr 2013

Contact author: subho at isical ac in

Available formats: PDF | BibTeX Citation

Version: 20130429:111809 (All versions of this report)

Discussion forum: Show discussion | Start new discussion