Non-graded · offline · explore at your own pace
One question instead of many
The Deutsch-Jozsa algorithm (1992) was the first clean proof that a quantum algorithm can answer a promise problem with certainty in one query, where a deterministic classical algorithm can need 2ⁿ⁻¹ + 1 queries. That's an exponential gap in queries, not in wall-clock speed for everyday tasks. The problem itself is artificial, but the technique of superposition, phase, and interference reappears in every major quantum algorithm, including Shor's.
At 50 input bits, a guaranteed classical answer can take over 560 trillion queries. The quantum version still takes one.
01 · The problem
Constant or balanced?
Someone hands you a sealed box, called an oracle, that computes a function f(x). The input x is n bits, and the output is a single bit. You're promised the function is one of two kinds:
Your job: figure out which kind it is, with certainty, using as few queries as possible.
02 · The classical way
Query inputs one at a time
Try it: crack the mystery box classically
Click inputs to query the box. Stop as soon as you're certain. Seeing a 0 and a 1 proves "balanced," but proving "constant" means checking more than half.
03 · The quantum way
Query every input at once, then interfere
The quantum circuit puts all n input qubits into superposition with Hadamards and feeds them to the oracle once. Using a helper qubit in the |−⟩ state, the oracle marks each input with a sign, (−1)f(x). This trick is called phase kickback. A final round of Hadamards makes those signs interfere.
Try it: run Deutsch-Jozsa on the same mystery box
Uses the box from section 02. One query, then a measurement. All zeros means constant; anything else means balanced.
04 · Why it works
The all-zeros amplitude is an average of signs
After the last Hadamards, the amplitude of the all-zeros outcome works out to the average of every sign:
That's interference from page 02 at a larger scale. Wrong answers cancel, right answers reinforce, and a single measurement settles the question.
05 · Why it matters
A toy problem with a serious lesson
Nobody needs to know whether a function is constant or balanced. A classical computer that's allowed a tiny chance of error can also solve it with just a few random queries. Deutsch-Jozsa matters because it showed, cleanly and provably, that the quantum toolkit (superposition, phase, interference) could do something classical computing can't match with certainty.