nLab Deutsch-Jozsa algorithm

Idea

An early example of a algorithm for which quantum computers are expected to drastically outperform classical computers (cf. quantum algorithm).

Related concepts

• Shor's algorithm

• Grover's algorithm

• quantum complexity theory

• quantum supremacy

References

Due to:

• David Deutsch, Richard Jozsa, Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A 439 1907 (1992) 553-558 [pdf, doi:10.1098/rspa.1992.0167]

Review:

• Renato Portugal, Basic Quantum Algorithms [arXiv:2201.10574]

Implementation in Quipper:

• Safat Siddiqui, Mohammed Jahirul Islam, Omar Shehab, §4.1-2 in: Five Quantum Algorithms Using Quipper [arXiv:1406.4481]

See also:

• Wikipedia, Deutsch-Jozsa algorithm