Deutsch–Jozsa Algorithm

Take Deutsch's circuit from Ch. 25 — H, oracle, H, measure — and run it on n qubits instead of one. Nothing about the circuit changes in structure. What changes is the classical comparison: a 1-vs-2 query advantage becomes 1-vs-exponentially-many.

The generalized problem

f: {0,1}ⁿ → {0,1}, promised to be either constant (same output for every input) or balanced (exactly half the inputs give 0, half give 1) — never anything in between. Classically, in the worst case, you might need to check 2ⁿ⁻¹+1 inputs before you're sure: get unlucky and see the same output 2ⁿ⁻¹ times in a row, and you still can't rule out "constant" until one more query either confirms it or reveals a different value.

Why "all-zero or not" is enough

Ch. 22's Hadamard-transform math generalizes exactly: P(measure 0...0) = |(1/N)Σₓ(−1)^f(x)|² . If f is constant, every term in that sum has the same sign, so they add up to ±1 and the probability is exactly 1. If f is balanced, exactly half the terms are +1 and half are −1 — they cancel completely, giving probability exactly 0. There's no overlap between these two cases, ever, which is exactly why a single measurement settles the question with total certainty.

The promise is doing a lot of work

It's worth being honest about what makes this algorithm "easy": the promise that f is either perfectly constant or perfectly balanced, with nothing in between, is doing enormous work. Real-world functions are rarely so cooperative. Deutsch–Jozsa is the cleanest possible demonstration that quantum interference can produce an exponential query-complexity separation, but it's also a famous example of a problem engineered specifically to showcase that gap — Grover's algorithm (Ch. 28) and Shor's algorithm (Ch. 31) tackle problems with real-world motivation and correspondingly messier, harder-won speedups.