Deutsch-Jozsa algorithm
From Free net encyclopedia
←Older revision | Newer revision→
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 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 Hadamard transforms 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 is deterministic, always producing the correct answer with probability one.
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.ru:Алгоритм Дойча — Джоза