A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The Deutsch-Jozsa algorithm determines whether a Boolean function f:{0,1}^n -> {0,1} is constant (same output for all inputs) or balanced (outputs 0 for exactly half the inputs and 1 for the other half), promised that one of these holds. A classical deterministic algorithm requires 2n-1 + 1 queries in the worst case, but the quantum algorithm uses exactly one query to the function oracle. It was the first algorithm to demonstrate a provable exponential separation between quantum and classical deterministic query complexity, establishing that quantum computers can solve certain problems fundamentally faster.
The Deutsch-Jozsa algorithm is historically important as the first quantum algorithm to demonstrate an exponential separation from classical computation, even though the problem it solves is artificial. You are given a black-box function f:{0,1}^n -> {0,1} with the promise that f is either constant (all outputs are the same) or balanced (exactly half the outputs are 0 and half are 1). Classically, in the worst case, you must evaluate f on 2n-1 + 1 inputs to be certain — you might get unlucky and see the same output for the first 2n-1 queries. The quantum algorithm uses one query.
The circuit works as follows. Prepare n input qubits in |0> and one ancilla qubit in |1>. Apply Hadamard to all n+1 qubits. The input register is now in a uniform superposition over all 2n basis states, and the ancilla is in |-> = (|0> - |1>)/sqrt(2). Apply the oracle Uf, which maps |x>|y> to |x>|y xor f(x)>. Because the ancilla is in |-> , the effect of the oracle is phase kickback: the ancilla stays in |-> and each input state |x> acquires a phase (-1)^f(x). The state is now (1/sqrt(2n)) * sum_x (-1)^f(x) |x> tensor |-> .
Now apply Hadamard to each input qubit. The Hadamard transform maps the state to a sum over all output basis states, where the amplitude of each output state |y> is a sum involving (-1)^f(x) * (-1)x dot y over all x. The amplitude of |0...0> specifically is (1/2n) * sum_x (-1)^f(x). If f is constant, this sum is +/- 1, so the probability of measuring |0...0> is 1. If f is balanced, exactly 2n-1 terms are +1 and 2n-1 are -1, so the sum is zero and the probability of measuring |0...0> is 0. A single measurement therefore determines the answer with certainty.
The key mechanism is interference. The oracle embeds the function's behavior into phases, and the final Hadamard transform recombines these phases. For a constant function, all paths interfere constructively at |0...0>. For a balanced function, they interfere destructively and the amplitude at |0...0> vanishes completely. This pattern — oracle encodes information into phases, followed by interference that concentrates the answer — recurs throughout quantum algorithms. The Deutsch-Jozsa algorithm is the simplest instance of this paradigm. It is worth noting that a probabilistic classical algorithm can solve this problem with O(1) random queries and high confidence, so the exponential advantage is specifically over deterministic classical algorithms. The deeper significance is conceptual: it proves that quantum query complexity can be strictly less than classical.