Testing Boolean Functions Properties
Zhengwei Xie, Qiu Daowen, Guangya Cai, Jozef Gruska, Paulo Mateus · Fundamenta Informaticae · 2021
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 [Formula: see text]. Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is [Formula: see text]. 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 n ) queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus ɛ-far balanced using [Formula: see text] 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.