Deutsch-Jozsa algorithm
From Wikipedia, the free encyclopedia
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, designed for execution on a quantum computer, that have the potential to be more efficient than classical algorithms by taking advantage of quantum superposition and entanglement.
In the Deutsch-Jozsa problem, we are given a black box quantum computer that implements a single function f(x1, x2, ..., xn) that takes n binary bits x1, x2, ..., xn and returns the binary value f(x1, x2, ..., xn). We know that the function is either constant (0 on all inputs or 1 on all inputs) or balanced (returns 1 for half of the input domain and 0 for the other half); the task then is to determine which it is (constant or balanced) by applying inputs to the black box and observing its output.
For a conventional deterministic algorithm, 2n-1 + 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 + 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 a Hadamard transform on a quantum register of n 0s, forming all possible inputs, and a single 1, which will be the answer qubit. Next, run the function once. This is done by using the n input qubits as input of the function of a Function-Controlled NOT gate that works on the answer qubit. Finally, do Hadamards on the n inputs again, and measure them. If they are in a state of all zeroes, it's now certain the function is constant, otherwise you know the function to be balanced. The algorithm is deterministic, always producing the correct answer with 100% certainty. Interestingly, the state of the answer qubit remains unchanged and the real answer of the algorithm is stored in the input qubits.
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.
[edit] References
This is partially based on the public domain information found here: Deutsch-Jozsa algorithm at NIST.
- 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.
