Deutsch-Jozsa Algorithm

The Deutsch-Jozsa algorithm, published in 1992, was the first quantum algorithm to prove an exponential speedup over any possible classical algorithm, though only for a deliberately constructed problem. Given a hidden function that is promised to be either constant (returns the same output for every input) or balanced (returns 0 for exactly half of all inputs and 1 for the other half), a classical algorithm needs up to 2^(n-1) + 1 queries in the worst case to tell which, while the Deutsch-Jozsa algorithm determines the answer with a single query by putting the input register into superposition, applying the function as a quantum oracle, and using interference so that only constant or only balanced functions produce a specific measurement outcome. The algorithm has no known practical application. Its significance is historical and pedagogical: it demonstrated the core mechanism, oracle queries plus interference, that later, genuinely useful algorithms like Grover's and Shor's build on, and it is usually taught alongside the related Bernstein-Vazirani and Simon's algorithms as the standard introduction to quantum query complexity before moving on to Grover's search.