Abstract
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 defined as for for , and it is undefined for the rest of the cases, where is even, and is the Hamming weight of . The optimal quantum algorithm needs only one query to compute but the classical deterministic algorithm requires queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as for for in the set , and it is undefined for the rest of the cases, where . In particular, we give and prove an optimal exact quantum query algorithm with complexity for computing the generalized Deutsch-Jozsa problem . It is clear that the case of 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.
- Received 4 February 2018
DOI:https://doi.org/10.1103/PhysRevA.97.062331
©2018 American Physical Society