# 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.