Paper 2013/232

Quantum algorithms to check Resiliency, Symmetry and Linearity of a Boolean function

Kaushik Chakraborty, Anupam Chattopadhyay, and Subhamoy Maitra

Abstract

In this paper, we present related quantum algorithms to check the order of resiliency, symmetry and linearity of a Boolean function that is available as a black-box (oracle). First we consider resiliency and show that the Deutsch-Jozsa algorithm can be immediately used for this purpose. We also point out how the quadratic improvement in query complexity can be obtained over the Deutsch-Jozsa algorithm for this purpose using the 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, we require 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. A similar kind of approach can be exploited to check whether a Boolean function is symmetric (respectively linear) or not. Given a Boolean function as an oracle, it is important to devise certain algorithms to test whether it has a specific property or it is $\epsilon$-far from having that property. The efficiency of the algorithm is judged by the number of calls to the oracle so that one can decide, with high probability, between these two alternatives. We show that this can be achieved in $O(\epsilon^{-\frac{1}{2}})$ query complexity. This is obtained by showing that the problem of checking symmetry or linearity can be efficiently reduced to testing whether a Boolean function is constant.

Note: Revised the title and added further materials.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. WCC 2013, Bergen, Norway
Keywords
Boolean FunctionsDeutsch-Jozsa AlgorithmGrover's AlgorithmLinearityMeasurementProperty TestingResiliencySymmetry
Contact author(s)
subho @ isical ac in
History
2014-03-14: revised
2013-04-29: received
See all versions
Short URL
https://ia.cr/2013/232
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/232,
      author = {Kaushik Chakraborty and Anupam Chattopadhyay and Subhamoy Maitra},
      title = {Quantum algorithms to check Resiliency, Symmetry and Linearity of a Boolean function},
      howpublished = {Cryptology ePrint Archive, Paper 2013/232},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/232}},
      url = {https://eprint.iacr.org/2013/232}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.