Generalized Deutsch-Jozsa problem and the optimal quantum algorithm

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 DJ(n)(o) : {0,1}(n) -> {0, 1} defined as DJ(n)(o)(x) = 1 for vertical bar x vertical bar = n/2, DJ(n)(o) (x) = 0 for vertical bar x vertical bar = 0,n, and it is undefined for the rest of the cases, where n is even, and vertical bar x vertical bar is the Hamming weight of x. The optimal quantum algorithm needs only one query to compute DJ(n)(o) but the classical deterministic algorithm requires 2(n-1) + 1 queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as DJ(n)(k)(x) = 1 for vertical bar x vertical bar = n/2, DJ(n)(k)(x) = 0 for vertical bar x vertical bar in the set {0,1, . . . , k, n - k, n - k +1, . . . , n}, and it is undefined for the rest of the cases, where 0 <= 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 DJ(n)(k). 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.