Deutsch – Jozsa algorithm
The Deutsch-Jozsa algorithm is the first example of a quantum algorithm that performs better than the best classical algorithm: it provides exponential speed-up. Using this algorithm, it is possible to determine with 100% certainty whether an unknown Boolean function is either constant or balanced, with only one consultation of this function.
Prerequisite knowledge:
- Ket-notation
- Hadamard transform
- Measurement in {|0>,|1>} basis
The following video contains an explanation of the Deutsch-Jozsa algorithm given by Annick Teepe, Applied Physics MSc student at the TU Delft.
Further thinking:
In the video, we required absolute certainty of both the classical and the quantum computation. If you have already tried k inputs, and have found the same output for all of your tries, what is then the probability that the function actually is constant?
Further reading:
- John Preskill, Quantum Information, Chapter 6.3. California Institute of Technology
- Deutsch, D., & Jozsa, R. (1992). Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439(1907), 553-558.