20. Deutsch–Jozsa

20.1Problem definition

Now f: {0,1}ⁿ → {0,1}, promised to be either constant on all 2ⁿ inputs or balanced — exactly 2ⁿ⁻¹ inputs map to 1. Decide which. The problem was posed and solved by Deutsch and Jozsa in 1992 and was the first exponential separation between classical and quantum query complexity: classically you may need to look at 2ⁿ⁻¹+1 inputs, quantum needs one oracle call, with certainty. Like Deutsch's original, it is a promise problem: on functions outside the promise the algorithm's output is meaningless. Keep that asterisk in view for 20.6.

20.2Oracle model

The black box is Uf: |x⟩|y⟩ ↦ |x⟩|y ⊕ f(x)⟩ on n+1 qubits — the same oracle convention as Deutsch, one unitary per query, and exactly one query is granted. As before, feeding the ancilla |−⟩ = (|0⟩−|1⟩)/√2 converts the oracle into a diagonal phase operator (−1)^{f(x)} on the input register: the phase oracle. Nothing about the construction depends on what f computes internally — that is the strength and (20.6) the weakness of the model.

20.3Circuit construction

q0 … q(n-1):  |0> ─H─●─H─M     read 0…0 ⟺ f constant (deterministic)
                  │
q_n:          |1> ─H─Uf──      Uf: |x>|y> ↦ |x>|y ⊕ f(x)>

Hadamards on all n+1 qubits, one oracle call, Hadamards on the n input qubits, measure the inputs. In pseudocode, against the state-vector simulator you already have:

psi = |0…0>|1>
apply H to all n+1 qubits
psi = Uf @ psi              # the single query
apply H to the n input qubits
answer = "constant" if measured(input register) == 0…0 else "balanced"

20.4Interference

Work through the amplitude of the all-zeros outcome. After the oracle and final Hadamards it is (1/2ⁿ)·Σ_x (−1)^{f(x)} — the average of (−1)^{f(x)} over all inputs. If f is constant, every term is +1 or every term is −1: the sum is ±2ⁿ, the amplitude is ±1, and you measure all-zeros with certainty. If f is balanced, exactly half the terms are +1 and half are −1: the sum is 0. All 2ⁿ computational paths interfere to destroy that one outcome — and since the state has norm 1, the probability mass must sit somewhere else, on strings that certify balanced. One query, 2ⁿ constructive/destructive terms, zero probabilities computed numerically.

20.5Complexity

Quantum: 1 query, O(n) Hadamard gates plus the oracle, success probability exactly 1. Classical deterministic: 2ⁿ⁻¹+1 queries in the worst case — query inputs until you see both values (balanced) or have queried 2ⁿ⁻¹+1 equal ones (constant, because a balanced function only has 2ⁿ⁻¹ zeros). Classical randomized: 2 queries suffice for success probability ≈ 3/4, and O(log(1/δ)) queries for error δ — so the exponential gap is against deterministic classical algorithms, and a fair reading puts the honest gap at one query versus a constant number. That is still a separation with a proof; it is just not the headline the 1992 paper suggested.

20.6Limitations of the result

Three limitations, all structural. The promise: real functions are neither constant nor balanced, and off-promise the output is arbitrary — no natural computational task arrives in this form. The oracle: the speedup assumes Uf costs one "unit"; for any specific promised f you might write down, the classical algorithm could inspect its circuit definition instead of querying it. The separation type: it vanishes against randomized classical algorithms (20.5), so the result's lasting value is pedagogical — it introduced the phase-oracle-plus-Hadamards template and the notion of query complexity, which Bernstein–Vazirani and Simon immediately pushed to separations that survive randomization. Treat Deutsch–Jozsa as the field's first exercise, not its first result.