Efficient Quantum Algorithm for the Parity Problem of a Certain Function

Based on a particular mathematical structure of a certain function f(x) under our attention, we present a novel quantum algorithm. The algorithm allows one to determine the property of a certain function. In our study, it is f(x) = f(−x). Therefore, there would be a question here, “How fast can we succeed in this?” All we need to do is only the evaluation of a single quantum state | 0 , 0 , … , 0 , 1 ⏞ N〉 (N ≥ 2). Only using that with a little amount of information, we can derive the global property f(x) = f(−x). Our quantum algorithm overcomes a classical counterpart by a factor of the order of 2^N.