Algorithm Zoo · Search
Deutsch-Jozsa
First described: Deutsch, Jozsa, 1992
The problem
Determine whether a Boolean function f : {0,1}^n → {0,1} is constant or balanced (promised one of the two).
Pedagogical: the first quantum algorithm with provable exponential separation in the oracle model. Determines constant vs balanced in one query; classically deterministic requires 2^{n-1} + 1 queries.
Best classical
Deterministic: 2^{n-1}+1 queries. Randomized: O(1) queries (just sample).
Quantum complexity
1 query.
Our verdict
Historically essential — the first proof a quantum computer could outpace a classical one. Practically useless: nobody has a deterministic-vs-balanced promise problem in their workload. Teach it as the entry point to the rest.
When to use it
- Teaching.
When not to use it
- Anything practical — the problem doesn't arise in practice.
Classical baseline
Randomized classical algorithm: pick a random x, evaluate f(x), repeat ~10 times. Statistical separation is overwhelming. The 'exponential separation' is deterministic-only.
Hardware cost
n+1 qubits, one oracle query, depth O(n).
Key papers
- Rapid solutions of problems by quantum computation ↗
Deutsch, Jozsa · 1992 · Proc. Royal Society A
Deep-dive tutorials
Last verified: 2026-05-24