The Deutsch-Jozsa algorithm is a quantum algorithm, proposed by David Deutsch and Richard Jozsa in 1992. It was one of first examples of a quantum algorithm, which is a class of algorithms designed for execution on Quantum computers and have the potential to be more efficient than conventional, classical, algorithms by taking advantage of the quantum superposition and entanglement principles.
In Deutsch-Jozsa problem, we are given a black box computing a 0-1 valued function f(x1, x2, ..., xn). The black box takes n bits x1, x2, ..., xn and outputs the value f(x1, x2, ..., xn). We know that the function in the black box is either constant (0 on all inputs or 1 on all inputs) or balanced (returns 1 for half the domain and 0 for the other half). The task is to determine whether f is constant or balanced.
For a conventional deterministic algorithm, 2n-1 evaluations of f will be required in the worst case. For a conventional randomized algorithm, a constant number of evaluation suffices to produce the correct answer with a high probability but 2n-1 evaluations are still required if we want an answer that is always correct. The Deutsch-Jozsa quantum algorithm produces an answer that is always correct with just 1 evaluation of f.
The algorithm is as follows. First, do Hadamard transformations on n 0s, forming all possible inputs, and a single 1, which will be the answer qubit. Next, run the function once; this XORs the result with the answer qubit. Finally, do Hadamards on the n inputs again, and measure the answer qubit. If it is 0, the function is constant, otherwise the function is balanced.
The algorithm builds on an earlier 1985 work by David Deutsch which gave a similar algorithm for the special case when the function f(x1) has one 0-1 valued variable instead of n. It preceded other quantum algorithms such as Shor's algorithm and Grover's algorithm.
This is partially based on the public domain information found here: Deutsch-Jozsa algorithm at NIST.
References
- David Deutsch, Richard Jozsa. Rapid solutions of problems by quantum computation. Proceedings of the Royal Society of London, Series A, vol. 439, pp. 553, 1992.
- Michael A. Nielsen and Isaac L. Chuang, "Quantum Computation and Quantum Information", pages 34-36.