Quantum Algorithms Database
Deutsch-Jozsa Algorithm
The first algorithm to prove a quantum computer could solve a problem exponentially faster than any classical deterministic algorithm.
Year
1992
Inventor(s)
David Deutsch & Richard Jozsa
Speedup Type
Exponential Speedup
Difficulty
★★★☆☆
The Problem
Determining whether a given function is 'constant' (same output for all inputs) or 'balanced' (different outputs for half the inputs).
How It Works
Uses superposition to evaluate the function on all inputs simultaneously, then uses interference so a single measurement reveals whether the function is constant or balanced.
Real-World Impact
Mainly historical and educational — it proved quantum speedup was possible in principle, paving the way for Shor's and Grover's algorithms, though the problem itself has limited practical use.