Source-verifiedLevel 3
Deutsch-Jozsa Algorithm
The Deutsch-Jozsa algorithm determines whether a Boolean function is constant or balanced using only one query, providing an exponential speedup over classical deterministic algorithms.
What it means
The Deutsch-Jozsa algorithm (1992) solves the following problem: given a black-box function f:{0,1}^n -> {0,1} that is promised to be either constant (same output for all inputs) or balanced (output 0 for half the inputs, 1 for the other half), determine which case it is.Classically, this requires 2^(n-1)+1 queries in the worst case.The quantum algorithm uses only ONE query by exploiting quantum parallelism and interference.The circuit applies H gates to create superposition, queries the oracle, applies H gates again, and measures.If all measurement results are |0⟩, the function is constant; otherwise, balanced.This was the first algorithm proving quantum speedup.Everyday analogy
Imagine checking if a coin is fair or double-headed: classically you flip multiple times, but the Deutsch-Jozsa algorithm is like a single magical flip that definitively tells you the answer.
Think of it as testing whether a sealed ballot box contains all identical votes or a perfect split -- quantum mechanics lets you check with a single peek.
Common misconceptions
- The Deutsch-Jozsa speedup is over DETERMINISTIC classical algorithms -- probabilistic classical algorithms can solve it efficiently with bounded error.
- The algorithm does NOT tell you WHAT the function computes -- only whether it is constant or balanced.
Key takeaways
- Determines constant vs balanced with just one oracle query (exponential speedup over classical deterministic).
- First algorithm demonstrating provable quantum advantage.
- Uses superposition, phase kickback, and interference as key quantum techniques.
Check your understanding
How many oracle queries does the Deutsch-Jozsa algorithm require?
- A.n
- B.2^n
- C.1
- D.log(n)
Show the answer
Answer: C. 1
Why: The Deutsch-Jozsa algorithm requires exactly 1 oracle query, compared to 2^(n-1)+1 queries needed classically in the worst case.
Builds on
Primary source: Deutsch & Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. A 439, 553 (1992), doi:10.1098/rspa.1992.0167
Learn it hands-on
This concept is part of a 46-level curriculum with an interactive simulator and Lumen, a tutor whose answers are verified before you see them. Levels 1–5 are free.