f is promised to be either constant (same output for every x) or balanced (exactly half the inputs give 0, half give 1) — never anything in between. Classically, ruling that out for certain needs 2ⁿ⁻¹+1 queries in the worst case: you can be unlucky and see the same output that many times in a row before a single differing result finally proves "balanced". Deutsch-Jozsa needs exactly one.
|0⟩ⁿ|1⟩ --H⊗(n+1)--> uniform superposition, ancilla in |−⟩
--U_f--> aₓ → (−1)^f(x) aₓ (phase kickback, no branching)
--H⊗n--> a_y → (1/√N) Σₓ (−1)^(x·y) aₓ
measure the n-qubit register:
a₀…₀ = (1/N) Σₓ (−1)^f(x) → ±1 if f constant (P=1), 0 if f balanced (P=0)
Every amplitude on this page is computed from that real arithmetic, not looked up — the oracle stage literally flips the sign of aₓ for each x where f(x)=1, and the final stage is a genuine Walsh-Hadamard transform (a real sum over all 2ⁿ basis states for every output y), so a balanced f you build yourself will always collapse the y=0 bar to zero, and a constant one will always send it to probability 1.
- Qubits n — the register size; N=2ⁿ possible inputs to f. Classical worst case grows exponentially (2ⁿ⁻¹+1), quantum stays at 1.
- Constant f=0 / f=1 — the oracle never flips any sign (or flips every sign, a harmless global phase) — the final Hadamard exactly undoes the first one.
- Balanced (random) — a uniformly random half of the 2ⁿ inputs is assigned 1, guaranteeing exact balance by construction.
- Balanced (parity) — f(x) is the XOR of a random nonempty subset of the bits of x; any such parity function is exactly balanced over the full hypercube.
Real-world relevance: Deutsch-Jozsa (1992) was the first algorithm to prove an exponential query-count separation between quantum and classical computation for any problem — a purely theoretical promise problem, but the phase-kickback + interference pattern it introduced is the same trick underlying Simon's algorithm, Shor's factoring, and quantum phase estimation.