The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is ɛ-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique.

At first, we study here a particular testing problem: namely whether a given Boolean function f, of n variables, is identical with a given function g or is ɛ-far from g, where ɛ is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity O ( 1 ε ) . Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is Θ ( 1 ε ) . Secondly, we consider the D-J problem from the perspective of functional correlations and let C(f, g) denote the correlation of f and g. We propose an exact quantum algorithm for making distinction between |C(f, g)| = ɛ and |C(f, g)| = 1 using six queries, while the classical deterministic query complexity for this problem is Θ(2ⁿ) queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus ɛ-far balanced using O ( 1 ε ) queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of O(1/ɛ²). Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case.

Search results

Testing Boolean Functions Properties