The goal in function property testing is to determine whether a black-box Boolean function has a certain property or is $\ensuremath{\epsilon}$-far from having that property. The performance of the algorithm is judged by how many calls need to be made to the black box in order to determine, with high probability, which of the two alternatives is the case. Here we present two quantum algorithms, the first to determine whether the function is linear and the second to determine whether it is symmetric (invariant under permutations of the arguments). Both require order ${\ensuremath{\epsilon}}^{\ensuremath{-}2/3}$ calls to the oracle, which is better than known classical algorithms. In addition, in the case of linearity testing, if the function is linear, the quantum algorithm identifies which linear function it is. The linearity test combines the Bernstein-Vazirani algorithm and amplitude amplification, while the test to determine whether a function is symmetric uses projective measurements and amplitude amplification.
The goal in function property testing is to determine whether a black-box Boolean function has a certain property or is \ensuremathϵ-far from having that property. The performance of the algorithm is judged by how many calls need to be made to the black box in order to determine, with high probability, which of the two alternatives is the case. Here we present two quantum algorithms, the first to determine whether the function is linear and the second to determine whether it is symmetric (invariant under permutations of the arguments). Both require order \ensuremathϵ\ensuremath−2/3 calls to the oracle, which is better than known classical algorithms. In addition, in the case of linearity testing, if the function is linear, the quantum algorithm identifies which linear function it is. The linearity test combines the Bernstein-Vazirani algorithm and amplitude amplification, while the test to determine whether a function is symmetric uses projective measurements and amplitude amplification.
Let a Boolean function be available as a black-box (oracle) and one likes to devise an algorithm to test whether it has certain property or it is ε-far from having that property. The efficiency of the algorithm is judged by the number of calls to the oracle so that one can decide, with high probability, between these two alternatives. The best known quantum algorithm for testing whether a function is linear or ε-far (0<ε<21) from linear functions requires O(ε−32) many calls [Hillery and Andersson, Physical Review A 84, 062329 (2011)]. We show that this can be improved to O(ε−21) by using the Deutsch-Jozsa and the Grover Algorithms.
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.
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 Θ(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. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta Informaticae
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 Θ(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. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta Informaticae
We discuss quantum algorithms, based on the Bernstein-Vazirani algorithm, for finding which variables a Boolean function depends on. There are 2^n possible linear Boolean functions of n variables; given a linear Boolean function, the Bernstein-Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. The same quantum algorithm can also be used to learn which input variables other types of Boolean functions depend on, with a success probability that depends on the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure to futher amplify the success probability, based on another quantum algorithm, the Grover search.
We discuss quantum algorithms based on the Bernstein–Vazirani algorithm for finding which input variables a Boolean function depends on. There are 2 n possible linear Boolean functions of n input variables; given a linear Boolean function, the Bernstein–Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. We show how the same quantum algorithm can also be used to learn which input variables any other type of Boolean function} depends on. The success probability of learning that the function depends on a particular input variable depends on} the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure based on another quantum algorithm, the Grover search, to amplify further the success probability. Finally, we discuss quantum algorithms for learning the exact form of certain quadratic and cubic Boolean functions.