Deutsch's algorithm is the simplest quantum algorithm that demonstrates a quantum speedup over any classical algorithm. It determines whether a binary function $f:\{0,1\} \to \{0,1\}$ is constant (same output for both inputs) or balanced (different outputs for the two inputs) using only a single quantum query, whereas any classical algorithm requires two.
The function $f$ is accessed via a quantum oracle $U_f$ which implements $\lvert x\rangle\lvert y\rangle \mapsto \lvert x\rangle\lvert y \oplus f(x)\rangle$. Classically, determining the type of $f$ requires evaluating both $f(0)$ and $f(1)$. Deutsch's algorithm determines it with one query to $U_f$.
The circuit uses two qubits, initialized to $\lvert 0\rangle\lvert 1\rangle$. Hadamard gates are applied to both, then the oracle $U_f$ is queried, then a Hadamard is applied to the first qubit, and finally the first qubit is measured.
$$\lvert 0\rangle\lvert 1\rangle \xrightarrow{H\otimes H} \lvert +\rangle\lvert -\rangle \xrightarrow{U_f} \pm(-1)^{f(0)}\lvert f(0)\oplus f(1)\rangle\lvert -\rangle \xrightarrow{H\otimes I}$$
If the first qubit measures $\lvert 0\rangle$, then $f(0) \oplus f(1) = 0$ and $f$ is constant. If it measures $\lvert 1\rangle$, then $f(0) \oplus f(1) = 1$ and $f$ is balanced. The answer is determined with certainty from a single measurement.
The key mechanism is phase kickback: the ancilla qubit in state $\lvert -\rangle$ causes the oracle to write the output $f(x)$ as a phase $(-1)^{f(x)}$ on the first register, rather than flipping any bit. After the second Hadamard gate, this phase difference constructively or destructively interferes to reveal whether $f$ is constant or balanced. Phase kickback is a central subroutine in many more powerful quantum algorithms including Deutsch-Jozsa algorithm, Bernstein-Vazirani, and Grover's algorithm.