Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let $f$ be an $n$-variable Boolean function and its Walsh spectra is denoted by $W_f(ω)$ at the point $ω\in \{0, 1\}^n$. The Boolean function is available in the form of an oracle. We like to find an $ω$ such that $W_f(ω) \neq 0$ as this will provide one of the linear functions which are correlated to $f$. We show that the quantum algorithm proposed by Deutsch and Jozsa (1992) solves the above mentioned problem in constant time. However, the best known classical algorithm to solve this problem requires exponential time in $n$. We also analyse certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch-Jozsa algorithm performs on them.
Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let f be an n-variable Boolean function and its Walsh spectra is denoted by Wf(ω) at the point ω∈{0,1}n. The Boolean function is available in the form of an oracle. We like to find an ω such that Wf(ω)=0 as this will provide one of the linear functions which are correlated to f. We show that the quantum algorithm proposed by Deutsch and Jozsa (1992) solves the above mentioned problem in constant time. However, the best known classical algorithm to solve this problem requires exponential time in n. We also analyse certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch-Jozsa algorithm performs on them.
Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems, one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let f be an n-variable Boolean function and its Walsh spectra is denoted by Wf(ω) at the point ω ∈ {0, 1}n. The Boolean function is available in the form of an oracle. We like to find a ω such that Wf(ω) ≠ 0 as this will provide one of the linear functions which are correlated to f. We show that the quantum algorithm proposed by Deutsch and Jozsa7 solves this problem in constant time. However, the best known classical algorithm to solve the problem requires exponential time in n. We also analyze certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch–Jozsa algorithm performs on them.
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 Deutsch-Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It was proposed by Deutsch and Jozsa in 1992 with improvements by Cleve, Ekert, Macchiavello, and Mosca in 1998. The Deutsch-Jozsa problem is a promise problem and we can equivalently describe it as a partial function ${\text{DJ}}_{n}^{0}:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ defined as DJn0(x)=1 for ∣x∣=n/2,DJn0(x)=0 for ∣x∣=0,n, and it is undefined for the rest of the cases, where n is even, and ∣x∣ is the Hamming weight of x. The optimal quantum algorithm needs only one query to compute DJn0 but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as DJnk(x)=1 for ∣x∣=n/2,DJnk(x)=0 for ∣x∣ in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity k+1 for computing the generalized Deutsch-Jozsa problem DJnk. It is clear that the case of k=0 is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.
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