MilestoneTheory & algorithmsConfirmed
Deutsch and Jozsa find a problem quantum computers solve exponentially faster
Dec 8, 1992
David Deutsch and Richard Jozsa describe a quantum algorithm that decides with certainty whether a hidden function is "constant" or "balanced", in exponentially less time than any deterministic classical method. The task is purely mathematical, but it gave an early, clear example of a quantum speedup.
Why it matters
It showed a quantum computer beating any deterministic classical method by an exponential margin, and its simplest version was among the first quantum algorithms run on real hardware, in 1998.
David Deutsch · Richard Jozsa · Oxford
Related
Sources (3)
-
Proceedings of the Royal Society of London A
Rapid solution of problems by quantum computation
“A class of problems is described which can be solved more efficiently by quantum computation than by any classical or stochastic method. The quantum computation solves the problem with certainty in exponentially less time than any classical deterministic computation.”
-
arXiv (Cleve, Ekert, Macchiavello and Mosca)
Quantum Algorithms Revisited
“Deutsch’s original problem was subsequently generalised by Deutsch and Jozsa (1992)”
-
arXiv (Chuang, Vandersypen, Zhou, Leung and Lloyd)
Experimental realization of a quantum algorithm
“We implemented the simplest possible version of the Deutsch-Jozsa (D-J) quantum algorithm[6], which determines whether an unknown function is constant or balanced.”
Each quote above was checked automatically against the original page. Added Oct 15, 2026. Spotted an error? Tell us and we will review it.