episciences.org_8500_1642656409
1642656409
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Fundamenta Informaticae
1875-8681
11
18
2021
Volume 182, Issue 4
Testing Boolean Functions Properties
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.
11
18
2021
8500
arXiv:2109.06763
10.3233/FI-2021-2076
https://fi.episciences.org/8500