A function f from n bits to one bit is *constant* if it gives the same answer on every input, and *balanced* if it gives 0 on exactly half of them. Told that f is one or the other, a classical program must, in the worst case, ask about more than half the inputs.

The Deutsch–Jozsa algorithm asks once. The function is given as an *oracle*, a circuit that adds f(x) to an extra qubit. The algorithm:

1. puts every input qubit in superposition with `h`;
2. prepares the extra qubit in |−⟩, so that the oracle kicks f(x) back as the sign (−1)^f(x) on |x⟩;
3. interferes the inputs with `h` again and measures them.

For a constant f every sign is the same, the paths add up on |0…0⟩, and the outcome is all zeros. For a balanced f the paths to |0…0⟩ cancel exactly, so the outcome is never all zeros. One query decides.

The engine checks the outcome distribution exactly: "every time" means probability 1, by proof.