Close

Filter courses

Level
Show courses Show filters
Close

Quantum Algorithms

01 /Applications of a Quantum Computer 02 /Breaking encryption 03 /The classical one-time pad 04 /Grover’s algorithm 05 /Quantum fourier transform 06 /Shor's algorithm 07 /Solving linear equations with quantum computers 08 /Quantum Machine Learning 09 /Simulating chemistry 10 /Distributed quantum computing 11 /Quantum Inspire 12 /Deutsch – Jozsa algorithm

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?

Solution

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.