Same question, but the input is n bits wide: does one query still beat the classical worst case?
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 now maps n bits to one bit, and it's promised to be either constant (same output for all 2n inputs) or balanced (exactly half output 0, half output 1). Nothing in between is allowed. Classically, a deterministic algorithm that has to be certain needs to check 2n−1+1 inputs in the worst case: see 2n−1 identical answers in a row and it's still conceivable the very next one flips, so balanced can only be ruled out one query past the halfway point. That worst case is exponential in n.
The quantum algorithm is exactly topic 08's circuit with the single query qubit widened to n qubits, run once. The same phase-kickback trick writes (−1)f(x) onto every branch |x⟩ of an n-qubit superposition simultaneously. One call to f, but it touches all 2n inputs at once, each in superposition. The final layer of Hadamards is what makes that phase pattern visible: it's an interferometer with 2n paths all recombining at the all-zero output. If f is constant, every path carries the same sign and they reinforce completely: probability 1 at all-zero. If f is balanced, exactly half the paths are + and half are −, and they cancel exactly, not approximately: probability of measuring all-zero drops to precisely 0. One measurement, one call to f, a certain answer either way.
Start in |0⟩⊗n|1⟩, apply H⊗(n+1), apply Uf, then H⊗n to the first n qubits. Phase kickback (topic 08) puts (−1)f(x) on each branch |x⟩ during the query, so just before the final Hadamard layer the first register holds (up to the untouched ancilla factor):
(1/√2ⁿ) Σₓ (−1)^f(x) |x⟩
The n-fold Hadamard transform sends |x⟩ ↦ (1/√2ⁿ) Σz (−1)x·z|z⟩ (x·z = bitwise dot product mod 2). Reading off the amplitude of the all-zero string z=0, where every (−1)x·z term is 1 regardless of x: gives:
amplitude(|0⟩ⁿ) = (1/2ⁿ) Σₓ (−1)^f(x)
If f is constant, every term in the sum has the same sign, so the amplitude has magnitude 1 and the all-zero string is measured with probability exactly 1. If f is balanced, exactly 2n−1 terms are +1 and 2n−1 are −1. They cancel to exactly zero, not approximately. Verified numerically at n=4 (16 inputs): both constant functions measure the all-zero string with probability 1.000000; 20 independently random balanced functions all measure it with probability <10⁻⁹ (floating-point zero). Deutsch & Jozsa, Proc. R. Soc. Lond. A 439, 553 (1992); the one-query exact version used here follows Cleve, Ekert, Macchiavello & Mosca, Proc. R. Soc. Lond. A 454, 339 (1998).
The first proven exponential query gap, with an honest asterisk 1 quantum query against 2n−1+1 classical ones is a genuine, provable exponential separation, for this exact promise problem, in the query model, where "work" is counted in calls to f. It is not evidence that quantum computers are exponentially faster at everything, and it is not by itself a proof that BQP is strictly bigger than P (the same honest line drawn on quantum mechanics vs. computing about oracle separations). What it does prove, completely, is that the phase-kickback-then-interference mechanism from topic 08 scales, and topic 10 is where that mechanism first does something with real algorithmic consequence: finding a hidden period.
Check yourself
Why does a balanced function give a hard zero at the all-zero outcome in Deutsch-Jozsa?
The final Hadamards act as an interferometer. A constant function gives every path the same sign, so they add to certainty; a balanced one gives exactly half of each sign, so they cancel to exactly zero.