Is a coin-flip function constant or does it actually depend on the input: in one look, not two?
These three are historically where quantum computing stopped being only physics. Each solves a promise problem: the input is guaranteed to have one of a small number of structures, and the algorithm's job is to find out which, and each does it with a query-complexity gap over any classical algorithm that can be proven outright, not benchmarked. None of them do anything commercially useful on their own; their importance is that they are the first proofs, small and completely worked, of the exact mechanism (phase kickback, then interference) that later algorithms on this site (Shor's, Grover's) scale up to problems that matter. The honest caveat, stated once here because it applies to all three: these are separations against an oracle (a black box promised to compute f, queried as a whole) not proofs that quantum computers are faster at every real problem. That is a real, provable gap in the query-complexity model, not a lesser one, but it is a different claim from separating complexity classes like P and BQP outright, which remains open.
f is a function on a single bit, f:{0,1}→{0,1}, and it's either constant (f(0)=f(1)) or balanced (f(0)≠f(1)). There are exactly four 1-bit functions: f(x)=0 and f(x)=1 are the two constant ones, and f(x)=x (the identity) and f(x)=1⊕x (NOT) are the two balanced ones, so "constant vs balanced" covers every case. Classically, telling them apart with certainty needs both f(0) and f(1). One query only ever tells you one value, and one value is consistent with either kind. Deutsch's algorithm answers with a single call to f, and the trick it introduces is used by nearly everything downstream on this page.
Phase kickback. The oracle is normally written to act on two registers (a query register x and an answer register y) as |x⟩|y⟩ → |x⟩|y⊕f(x)⟩: it XORs f(x) into y, leaving x alone. But prepare the answer register in the state (|0⟩−|1⟩)/√2 first, and something different happens: XOR-ing f(x) into that particular state either leaves it completely unchanged (f(x)=0) or flips its overall sign (f(x)=1), and a state that is only ever unchanged or globally negated is, up to that sign, the same state. The information about f(x) doesn't land in the answer register at all. It lands as a phase, (−1)^f(x), attached to the query register instead: the one register the oracle was "supposed" to leave alone.
A single amplitude's phase is invisible to any measurement on its own. What makes it visible is interference: querying both inputs at once, in superposition, then running a second Hadamard that turns the phase difference between the |0⟩ and |1⟩ branches into which outcome the query qubit measures. Constant f gives the two branches the same phase, they interfere back to exactly |0⟩. Balanced f gives them opposite phases, they interfere to exactly |1⟩. One call, one bit of global structure, read off with certainty.
Start in |0⟩|1⟩ and apply H to both qubits:
(H⊗H)|0⟩|1⟩ = [ (|0⟩+|1⟩)/√2 ] ⊗ [ (|0⟩−|1⟩)/√2 ]
Apply Uf: |x⟩|y⟩ → |x⟩|y⊕f(x)⟩. On the second factor, y⊕f(x) leaves (|0⟩−|1⟩)/√2 unchanged if f(x)=0 and negates it if f(x)=1: exactly the phase-kickback identity Uf|x⟩(|0⟩−|1⟩)/√2 = (−1)f(x)|x⟩(|0⟩−|1⟩)/√2. Applied to the superposition above:
1/√2 [ (−1)^f(0)|0⟩ + (−1)^f(1)|1⟩ ] ⊗ (|0⟩−|1⟩)/√2
Factor out the global phase (−1)f(0) (unobservable) and let the query register read 1/√2 [ |0⟩ + (−1)f(0)⊕f(1)|1⟩ ]. Apply H to it: H(|0⟩+|1⟩)/√2 = |0⟩ if the exponent is 0; H(|0⟩−|1⟩)/√2 = |1⟩ if it is 1. Since f(0)⊕f(1)=0 exactly when f is constant:
measure query qubit: 0 ⟺ f constant 1 ⟺ f balanced
deterministically, with probability exactly 1 either way. Verified numerically for all four possible 1-bit functions (both constant, both balanced): measured-outcome probability is exactly 1.0000 for the correct label and 0.0000 for the other in every case. Deutsch, Proc. R. Soc. Lond. A 400, 97 (1985) posed the problem and gave a probabilistic algorithm; the deterministic, single-query version shown here is due to Cleve, Ekert, Macchiavello & Mosca, Proc. R. Soc. Lond. A 454, 339 (1998), the same refinement topic 09 credits for its own one-query exact case.
The mechanism, not the problem Nobody has a real use for "is this 1-bit function constant": the value of Deutsch's algorithm is that phase kickback plus interference, proven here in its smallest possible case, is the exact engine inside Shor's algorithm and Grover's. Topic 09 scales the same trick from one bit to n; topic 10 scales it again into the period-finding structure Shor's algorithm generalises with the Fourier transform.
Check yourself
In Deutsch's algorithm the answer register starts in (|0> minus |1>)/sqrt 2. Where does the information about f(x) end up?
Phase kickback: XOR-ing f(x) into that particular state either leaves it alone or flips its sign, so the information lands as a phase on the query register. The ancilla is never read.