The Deutsch–Jozsa Algorithm

You are handed a black-box function f — an oracle, an API you can call but not inspect — that maps n input bits to one output bit. You are promised it is one of two kinds: constant (same output for every input) or balanced (output 0 for exactly half the inputs, 1 for the other half). The task: decide which, in as few calls as possible. This chapter builds the smallest version, n = 1, where f maps one bit to one bit. There are exactly four such functions: two constant — f(x)=0 and f(x)=1 — and two balanced — f(x)=x (identity) and f(x)=NOT x. If oracles are new to you, chapter 1 introduces the query model from scratch.

For n = 1, one query is provably not enough. Suppose you query f(0) and get 0. Both the constant function f(x)=0 and the balanced function f(x)=x return 0 there — one data point cannot separate them. Two queries settle it: if f(0) = f(1), constant; otherwise balanced. So classically: 2 queries, and for general n with certainty required, the worst case is 2^(n−1)+1 queries (for n = 3: 2² + 1 = 5, worked through step by step in chapter 1). Deutsch–Jozsa answers with certainty in one query for any n. Fairness note we will return to: a classical randomized program that tolerates a tiny error probability also needs only a handful of queries — the proved exponential gap is specifically about guaranteed correctness.

Quantum gates are reversible, so the oracle keeps the input qubit and XORs its answer into a helper qubit — an ancilla (any extra working qubit). Writing ⊕ for XOR, the oracle maps the pair (x, y) to (x, y ⊕ f(x)). Our two qubits: q0 is the input, q1 the ancilla. The four 1-bit functions become four tiny circuits: f(x)=0 is no gates at all; f(x)=1 is an X (bit-flip) on q1; f(x)=x is a CX — the controlled-NOT, which flips q1 exactly when q0 is 1 (see CNOT).

The algorithm's trick is what state the ancilla is in when the oracle fires. We prepare q1 in the minus state |−> = (|0> − |1>)/√2 — equal weights, opposite signs — by applying X then H (H is the Hadamard gate, sending |0> to (|0>+|1>)/√2 and |1> to (|0>−|1>)/√2). With the ancilla in |−>, XOR-ing f(x) into it does not change its measurement statistics at all; instead it multiplies the amplitude of each input branch x by (−1)^f(x) — a sign, or phase, stamped onto the input register. This is phase kickback, and we will verify it by hand two sections down. The input q0 is placed in |+> = (|0>+|1>)/√2 by an H, so the single oracle call touches both inputs in superposition; a final H on q0 converts the sign pattern into a definite bit. One more housekeeping detail: our simulator measures every qubit at the end (there is no mid-circuit or partial measurement here), so we also apply a final H to the ancilla, turning its |−> into a deterministic |1> — purely to make the full readout clean.

Worked example 1 — the kickback in one line of arithmetic. Apply CX to the state |1> ⊗ |−> — the ⊗ symbol simply glues two single-qubit states into one combined label (q0 in |1> alongside the ancilla in |−>), the state version of writing two bits side by side — writing the pair as (q0, q1) and expanding |−> on the ancilla: the state is (|1,0> − |1,1>)/√2. CX flips q1 because q0 = 1: it swaps the two terms, giving (|1,1> − |1,0>)/√2 = −(|1,0> − |1,1>)/√2. The ancilla is back in |−>, unchanged — but the whole branch acquired a minus sign. For the q0 = 0 branch, CX does nothing and the sign stays +. Net effect: amplitude of branch x gets multiplied by (−1)^f(x), with f(x)=x. The answer to "which function is this?" is now written in signs on the input register — invisible to an immediate measurement, but convertible by H.

Worked example 2 — the full balanced run, all four amplitudes, step by step. Order the four basis states as (q1 q0) = 00, 01, 10, 11 and track their amplitudes. H acts on a qubit's amplitude pair (a₀, a₁) as ((a₀+a₁)/√2, (a₀−a₁)/√2).

1. Start |00>: amplitudes (1, 0, 0, 0).
2. X on q1: state |10>: (0, 0, 1, 0).
3. H on q0 — pairs states differing only in q0: (0, 0, 0.7071, 0.7071).
4. H on q1 — pairs states differing only in q1: (0.5, 0.5, −0.5, −0.5).
5. CX (control q0, target q1) — swaps the two states with q0 = 1, namely 01 and 11: (0.5, −0.5, −0.5, 0.5). Note the sign pattern now sits on q0.
6. H on q0: new(00) = (0.5 + (−0.5))/√2 = 0; new(01) = (0.5 − (−0.5))/√2 = 0.7071; new(10) = (−0.5 + 0.5)/√2 = 0; new(11) = (−0.5 − 0.5)/√2 = −0.7071. State: (0, 0.7071, 0, −0.7071).
7. H on q1: new(01) = (0.7071 + (−0.7071))/√2 = 0; new(11) = (0.7071 − (−0.7071))/√2 = 1.4142/1.4142 = 1. Final state: amplitude 1 on |11>.

Probability of reading 11: 1² = 1, exactly — matching the run. Every other path cancelled. That cancellation-on-demand is interference doing the computing; walking amplitude tables like this is practiced in circuit state, step by step.

What it proves (this is settled theory, not a claim about hardware): in the exact query model, quantum computers solve this promise problem with 1 query while classical certainty costs 2^(n−1)+1 — an exponential separation, and historically the first one (Deutsch 1985 for n=1; Deutsch–Jozsa 1992 in general; the clean phase-kickback formulation we used is due to Cleve, Ekert, Macchiavello and Mosca, 1997).

What it does not prove:

• Not a practical speedup. Allow a classical program a random strategy and a tiny error tolerance, and a few queries suffice (each additional agreeing query makes "constant" overwhelmingly likely). The exponential gap holds only against guaranteed correctness — a fine print that honest accounts always state.
• Not a real-world problem. Nobody is handed promised constant-or-balanced oracles in production. Its value is the mechanism: one query in superposition, answer encoded in phases, interference converting phases into a definite readout.

That mechanism is the reusable part. Bernstein–Vazirani uses the identical circuit skeleton to read an entire hidden bitstring in one query, and the phase-oracle idea returns in Grover search. There is also a full Deutsch–Jozsa algorithm page with larger instances.

The 2-qubit instance — five or six single-qubit gates plus at most one CX — sits comfortably inside what today's public cloud devices run well, and small Deutsch–Jozsa instances are common demo circuits precisely because the ideal outcome is deterministic: any wrong bitstring in the histogram is a direct, legible signature of hardware error. With archetype figures (illustrative only, no vendor implied) of 1% two-qubit gate error and 1% readout error per qubit, the balanced run succeeds in roughly 0.99 × 0.99² ≈ 0.97 of shots — you would see 11 dominate with a few percent of shots leaking elsewhere, rather than the paper-perfect 100%.

Real devices differ in exactly these numbers, and they drift with calibration. Compare measured values on two-qubit fidelity and readout fidelity, browse the QPU index, or run both oracles yourself in the Lab and check the amplitude table from this chapter against the simulator.