A classical detective, promised a coin is either double-headed or perfectly fair, might have to flip it thousands of times before ruling out a run of lucky heads. A quantum detective, handed the same promise, glances once and knows for certain. That is the Deutsch–Jozsa algorithm — the Deutsch algorithm grown from one input bit to n — and it was the first problem ever shown to need exponentially fewer questions on a quantum computer than on any deterministic classical one. Same black box, same promise; one quantum query settles what could cost a classical machine over half a million queries.

The whole trick is interference. Instead of reading the function value on one input, the algorithm arranges for every input's value to fold together so that a single global property — is f the same everywhere, or split down the middle? — decides one clean measurement outcome.

The promise

You are given a function f:\{0,1\}^n \to \{0,1\} as a black-box oracle, together with a promise: f is one of exactly two kinds.

• Constant — it returns the same bit on all 2^n inputs (all 0, or all 1).
• Balanced — it returns 0 on exactly half the inputs and 1 on the other half.

Your job is only to decide which — constant or balanced — not to learn the whole function. The promise is what makes the problem crisp: you never have to worry about a function that is "mostly 0 with a couple of 1s," because you are guaranteed it is one of these two extremes.

Why classical determinism is expensive

Suppose you must be certain, using a deterministic classical strategy. Each query reveals one value f(x). Imagine the first 2^{n-1} queries you make all come back the same, say all 0. Are you done? No — the function could be constant, or it could be balanced with every one of its 0s handed to you first and all its 1s still hidden. Both remain possible. You need to look at one more input to break the tie.

So the deterministic worst case is 2^{n-1}+1 queries: half of all inputs, plus one. For n = 20 that is 524{,}289 calls — just to be sure. The quantum algorithm below needs one, for any n, with certainty.

The circuit

Deutsch–Jozsa is four moves on one bundled n-qubit register (plus a single ancilla qubit that supplies the phase). Hadamard everything, query the oracle once, Hadamard the register again, and measure. Step through it:

The ancilla starts in |-\rangle = \tfrac{1}{\sqrt2}(|0\rangle - |1\rangle). When the bit-oracle XORs f(x) into it, |-\rangle is an eigenstate that comes back unchanged except for a global (-1)^{f(x)} — that is phase kickback, and it is what turns the oracle into an effective phase oracle |x\rangle \mapsto (-1)^{f(x)}|x\rangle on the register. From here we can forget the ancilla and track the register alone.

The one amplitude that decides everything

Start the register in |0\dots0\rangle and apply H^{\otimes n} to reach the uniform superposition:

One oracle query stamps the phase (-1)^{f(x)} on each term, giving \tfrac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle. Now apply H^{\otimes n} again. Using H^{\otimes n}|x\rangle = \tfrac{1}{\sqrt{2^n}}\sum_y (-1)^{x\cdot y}|y\rangle, the amplitude that lands on the all-zeros outcome |0\dots0\rangle (where x\cdot 0 = 0, so every sign is +1) is simply the average of all the stamped signs:

This one number tells the whole story:

• Constant f: every term has the same sign, so the sum is \pm 2^n and the amplitude is \pm 1. The state is entirely |0\dots0\rangle — you measure all-zeros with probability 1.
• Balanced f: exactly half the signs are +1 and half are -1, so they cancel perfectly and the amplitude is 0. You will never see all-zeros — the measurement must give some nonzero string.

So the rule is: all-zeros ⟺ constant; any nonzero result ⟺ balanced. Pure interference does the sorting, in a single query.

Worked example 1: n=2, constant vs balanced

Take n=2, so 2^n = 4 inputs 00,01,10,11. After H^{\otimes 2}|00\rangle the register is \tfrac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle).

Constant f\equiv 0: every phase is (-1)^0 = +1, so the state is unchanged. Applying H^{\otimes 2} a second time inverts the first one and returns |00\rangle exactly:

Balanced f(x_1x_2)=x_1 (i.e. f(00)=f(01)=0, f(10)=f(11)=1): the query flips the sign of the two inputs beginning with 1:

The constant case reads 00; the balanced case reads 10 — nonzero. One query each, and the two are told apart with certainty.

Worked example 2: the all-zeros amplitude collapses to 0

You do not have to run the whole circuit to predict the balanced case — just evaluate the deciding amplitude \tfrac{1}{2^n}\sum_x (-1)^{f(x)}. Reuse the balanced f(x_1x_2)=x_1 from above and list the four signs:

The two +1s and two -1s annihilate: the all-zeros amplitude is zero, confirming you can never measure 00 for this f. Contrast the constant f\equiv 1, where every sign is -1:

an amplitude of magnitude 1 — all-zeros with certainty. Every balanced function, whatever its pattern, hits the same perfect cancellation; every constant function saturates the amplitude to \pm1. That gap between 0 and 1 is the entire algorithm.