Testing Boolean Functions Properties

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 parame- ter. 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 con- sider 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 com- plexity for this problem is Θ(2n) 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/ε2). Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case.