Deutsch-Jozsa algorithm

The Deutsch-Jozsa algorithm is a deterministic quantum algorithm proposed by David Deutsch and Richard Jozsa in 1992, with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello and Michele Mosca in 1998. Although of little practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. The problem it solves is a black box problem, designed to be easy for a quantum computer and hard for a deterministic classical one, which would need an exponential number of queries. It yields an oracle relative to which the classes EQP and P differ, but because a probabilistic classical computer solves it easily, it gives no separation from BPP.