Quantum vectorial Boolean function Algorithm

Abstract

We shall study the problem Input :A computable vectorial Boolean function

That is either with mask, i.e.

Output: Distinguish between the two eases, and in the second case produce S. To solve this problem exactly or with high probability, for every such f , a classical (probabilistic) computer needs to evaluate f an exponential number of times.  However, this problem can be solved with high probability, by a quantum algorithm with only quantum evaluation of f .