Zhengwei Xie ; Daowen Qiu ; Guangya Cai ; Jozef Gruska ; Paulo Mateus - Testing Boolean Functions Properties

fi:8500 - Fundamenta Informaticae, November 18, 2021, Volume 182, Issue 4
Testing Boolean Functions PropertiesArticle

Authors: Zhengwei Xie ; Daowen Qiu ; Guangya Cai ; Jozef Gruska ; Paulo Mateus

    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 $\varepsilon$-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 $\varepsilon$-far from $g$, where $\varepsilon$ is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity $O(\frac{1}{\sqrt{\varepsilon}})$. Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is $\Theta(\frac{1}{\varepsilon})$. 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)|=\varepsilon$ and $|C(f,g)|=1$ using six queries, while the classical deterministic query complexity for this problem is $\Theta(2^{n})$ queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus $\varepsilon$-far balanced using $O(\frac{1}{\varepsilon})$ 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/\varepsilon^{2})$. Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case.


    Volume: Volume 182, Issue 4
    Published on: November 18, 2021
    Accepted on: September 22, 2021
    Submitted on: September 19, 2021
    Keywords: Quantum Physics

    Consultation statistics

    This page has been seen 245 times.
    This article's PDF has been downloaded 277 times.