Application of Grover's algorithm to check non-resiliency of a Boolean function

摘要

In this paper, we explore quantum algorithms to check the resiliency property of a Boolean function (in particular, when it is non-resilient). First we explain that Deutsch-Jozsa algorithm can be immediately used for this purpose. We further analyse how the quadratic improvement in query complexity can be obtained using Grover's technique. While the worst case quantum query complexity to check the resiliency order is exponential in the number of input variables of the Boolean function, in our strategy one requires polynomially many measurements only. We also describe a subset of n-variable Boolean functions for which the algorithm works in polynomially many steps, i.e., we can achieve an exponential speed-up over best known classical algorithms.