The Deutsch-Jozsa Algorithm

The Deutsch-Jozsa problem is defined as follows. Fix $n \ge 1$. You are given oracle access to a Boolean function

with the promise that $f$ is either constant (i.e. $f(x)$ is the same value for every $x$) or balanced (i.e. $f(x) = 0$ for exactly half of the $2^n$ inputs and $f(x)=1$ for the other half). The task is to determine which case holds. Oracle access means you cannot inspect the internal description of $f$; you may only query it, classically by evaluating $f(x)$ for a chosen $x$, or quantum-mechanically by applying a unitary $U_f$ that implements $f$ reversibly. The quantum oracle is the unitary

acting on an $n$-qubit query register $|x\rangle$ and a 1-qubit target register $|y\rangle$. This is the natural reversible implementation of $f$: it is a permutation of basis states, hence unitary, and it reduces to ordinary evaluation of $f$ when $|x\rangle,|y\rangle$ are computational basis states. Crucially, $U_f$ can be applied to a superposition of inputs $x$, evaluating $f$ at all $2^n$ points "simultaneously" in the sense of linear superposition — though, as we will see, this alone does not let you read off all the values; the payoff comes only through interference. The key mechanism, inherited directly from The Deutsch Algorithm, is phase kickback. If the target qubit is prepared in the state $|-\rangle = \frac{1}{\sqrt2}(|0\rangle - |1\rangle)$, then

The target register is left completely unchanged, but the query register $|x\rangle$ picks up a phase of $(-1)^{f(x)}$. Applying $U_f$ to a superposition over all $x$ therefore imprints the entire truth table of $f$ into relative phases across the $2^n$-dimensional query register, using only one call to the oracle. The Deutsch-Jozsa algorithm's remaining job is purely classical linear algebra: use the $n$-qubit Hadamard transform to convert this phase pattern into a measurement outcome that reveals whether $f$ was constant or balanced.

The circuit uses $n+1$ qubits: an $n$-qubit query register initialized to $|0\rangle^{\otimes n}$, and a single target qubit initialized to $|1\rangle$ (so that after a Hadamard it becomes $|-\rangle$).

Step 1 — Initialize. Prepare the state $|0\rangle^{\otimes n} \otimes |1\rangle$.

Step 2 — Superpose. Apply Hadamard $H$ to every qubit. The query register becomes a uniform superposition over all $2^n$ strings, and the target becomes $|-\rangle$:

Step 3 — Query the oracle once. Apply $U_f$. By phase kickback, each basis term $|x\rangle|-\rangle$ picks up phase $(-1)^{f(x)}$ and the target is untouched:

Step 4 — Un-superpose the query register. Apply $H^{\otimes n}$ to the query register only. Using the identity $H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}}\sum_z (-1)^{x\cdot z}|z\rangle$ (the Hadamard Transform on $n$ qubits, where $x\cdot z$ is bitwise inner product mod 2), the amplitude of each basis state $|z\rangle$ becomes

Step 5 — Measure the query register. Measure all $n$ query qubits in the computational basis. If the outcome is $z = 0^n$, output "constant"; otherwise output "balanced." ``` Algorithm DEUTSCH-JOZSA(oracle U_f, n) // U_f acts as |x>|y> -> |x>|y XOR f(x)>, x in {0,1}^n allocate query register q[1..n], each initialized to |0> allocate target qubit t, initialized to |1> for i = 1 to n: apply H to q[i] apply H to t // t is now |-> = (|0>-|1>)/sqrt(2) apply U_f to (q[1..n], t) // single oracle call; phase kickback // t returns to |-> unchanged, // q picks up phase (-1)^f(x) per branch for i = 1 to n: apply H to q[i] // undo the initial superposition z = MEASURE(q[1..n]) // z in {0,1}^n if z == 0^n: return "f is CONSTANT" else: return "f is BALANCED" ``` The target qubit is never measured; it served only as a scratchpad to route phase into the query register. Note the single call to $U_f$ — everything else is single-qubit gates and measurement, both cheap and classical to simulate in isolation.

Query complexity. The algorithm makes exactly one call to $U_f$, regardless of $n$. Every other step is a layer of single-qubit Hadamard gates ($O(n)$ of them) and a final measurement. Total gate complexity is $O(n)$, and query complexity is $1$. Contrast this with the classical deterministic query complexity. Deterministically, an adversary can answer $f(x_1) = f(x_2) = \dots = f(x_{2^{n-1}}) = 0$ for any $2^{n-1}$ queries you choose, consistent with $f$ being either the all-zero constant function or some balanced function that happens to be $0$ on exactly those points. Only the $(2^{n-1}+1)$-th query can force a decision: if it also returns 0, $f$ must be constant (since a balanced function cannot be 0 on more than half its inputs); if it returns 1, $f$ is balanced. So $2^{n-1}+1$ queries are necessary and sufficient classically — deterministic query complexity is $\Theta(2^n)$. A randomized classical algorithm does much better on average: sample a few random points, and if they ever disagree, declare "balanced" (correct with certainty); if they agree $k$ times, guess "constant" with error probability at most $2^{-(k-1)}$, so $O(1)$ queries suffice for any fixed bounded error. The genuinely exponential separation is against deterministic, zero-error classical algorithms; against randomized classical algorithms with bounded error, the quantum advantage is "$1$ exact query vs. $O(1)$ probabilistic queries" — still a real advantage (exactness, and a strictly smaller constant), but not itself exponential. The historically clean statement is: exact quantum query complexity is $1$; exact (zero-error) classical deterministic query complexity is $2^{n-1}+1$.

Correctness proof. We show the amplitude $\alpha_{0^n}$ of the all-zeros outcome equals $\pm1$ when $f$ is constant, and equals exactly $0$ when $f$ is balanced; since amplitudes must have squared magnitudes summing to 1, this fully determines the measurement statistics. From Step 4, the amplitude of basis state $|z\rangle$ in the query register after the second Hadamard layer is

Set $z = 0^n$. Then $x \cdot z = 0$ for every $x$, so

Case 1: $f$ constant. Every term $(-1)^{f(x)}$ equals the same value $c \in \{+1,-1\}$, so the sum has $2^n$ identical terms and $\alpha_{0^n} = \frac{1}{2^n}\cdot 2^n \cdot c = c = \pm 1$. Since amplitudes have magnitude at most 1 and total squared magnitude 1, this forces $\alpha_{0^n} = \pm 1$ and every other amplitude is exactly 0. Measuring the query register yields $z = 0^n$ with probability $|\alpha_{0^n}|^2 = 1$ — certainty. Case 2: $f$ balanced. Exactly $2^{n-1}$ of the terms $(-1)^{f(x)}$ equal $+1$ (where $f(x)=0$) and exactly $2^{n-1}$ equal $-1$ (where $f(x)=1$). The sum is $2^{n-1} - 2^{n-1} = 0$, so $\alpha_{0^n} = 0$. Measuring the query register yields $z = 0^n$ with probability $0$ — it is impossible, so any observed outcome is some $z \ne 0^n$, correctly signaling "balanced." Both cases are exact — no bounded-error rounding, no probability of failure. The algorithm is a zero-error (Las Vegas-with-certainty, in fact Monte-Carlo-with-zero-error) quantum procedure: it always terminates and always answers correctly, given that the promise holds.

Why interference, not parallelism, does the work. It is tempting to say the speedup comes from "evaluating $f$ at all $2^n$ points at once." That framing is misleading: after the oracle call, the state $|\psi_2\rangle$ does encode all $2^n$ values of $f$ in relative phase, but no measurement of $|\psi_2\rangle$ directly in the computational basis would reveal that global structure — it would just return a uniformly random $x$. The real work is done by the second Hadamard layer, which performs a global linear combination (a Walsh–Hadamard transform) of all $2^n$ phases simultaneously, concentrating them constructively at $z=0^n$ exactly when they are all equal (constant case) and causing perfect destructive cancellation at $z=0^n$ exactly when half are $+1$ and half are $-1$ (balanced case). This constructive/destructive interference pattern, not raw parallel evaluation, is what a classical computer cannot cheaply replicate: reproducing $\alpha_z$ for even one $z$ classically requires summing $2^n$ terms.

Tradeoffs and caveats, honestly stated.

• The advantage is only proven relative to the black-box model, where the only permitted access to $f$ is through queries. If $f$ is given by an explicit formula or circuit, classical algorithms may exploit that structure and the separation can vanish.
• The promise (that $f$ is constant or balanced, no other case) is essential to the algorithm's logic; if $f$ is neither, the "constant vs. balanced" output is meaningless, though the algorithm still runs and still outputs something.
• The exponential separation is against deterministic exact classical algorithms specifically. Bounded-error randomized classical algorithms solve the promise problem with $O(1)$ queries, so the practically fair comparison (bounded-error quantum vs. bounded-error classical) shows only a constant-factor advantage, not an exponential one. The Deutsch-Jozsa algorithm's real historical significance is conceptual: it is a clean existence proof that quantum query algorithms can beat classical exact algorithms by an exponential factor, opening the door to later problems (Simon's problem, and ultimately Shor's factoring algorithm) where the bounded-error separation is also exponential.

Take $n = 3$ and the balanced function defined on $x = x_2x_1x_0$ (3-bit strings) by

(ignore $x_2$; this is a valid balanced function since exactly half of the 8 inputs give $x_0\oplus x_1 = 0$).

After Step 2 (Hadamards on all 4 qubits), the query register is a uniform superposition over all 8 strings with amplitude $\frac{1}{\sqrt 8}$ each, tensored with $|-\rangle$ on the target.

After Step 3 (one oracle call, phase kickback), the query register state is

Notice the sign pattern depends only on $x_0 \oplus x_1$, exactly as expected.

After Step 4 (Hadamard transform), compute $\alpha_{000} = \frac{1}{8}\sum_x (-1)^{f(x)}$ using the table: the sum of the last column is $1-1-1+1+1-1-1+1 = 0$. So $\alpha_{000} = 0$, confirming that $z = 000$ is impossible, consistent with $f$ being balanced. A fuller computation shows the surviving nonzero amplitudes are exactly those $z$ orthogonal (mod 2, under dot product) to the "direction" of $f$'s phase pattern; here one finds nonzero amplitude only at $z \in \{011, 100, 111, 000\}$-style patterns determined by $x_0\oplus x_1$'s dependency — concretely $\alpha_z \ne 0$ exactly for $z$ with $z_0 = z_1$ pattern matching the XOR structure (this generalizes the Bernstein–Vazirani phenomenon, foreshadowed below). Measuring might yield, say, $z = 011$: since $z \ne 000$, the algorithm correctly outputs "balanced," using a single call to $U_f$, whereas a deterministic classical strategy could have been fed the answers $f(000){=}0, f(001){=}1$ and would need up to $2^{3-1}+1 = 5$ queries in the worst case to be certain in general. For contrast, take the constant function $g(x) = 1$ for all $x$. Then every entry of the $(-1)^{g(x)}$ column is $-1$, so $\alpha_{000} = \frac{1}{8}(-8) = -1$, forcing all other amplitudes to zero. The measurement returns $z=000$ with certainty, and the algorithm outputs "constant" — correctly, and again from a single query.

The Deutsch-Jozsa algorithm itself solves no problem of direct industrial interest — no real dataset asks "is this function constant or balanced?" Its importance is pedagogical and structural. It is the first and cleanest illustration of the phase kickback plus Hadamard sandwich pattern that recurs throughout quantum algorithm design: prepare a uniform superposition, query an oracle so that function values become relative phases, then apply an inverse transform to convert phase structure into a measurable pattern. This exact skeleton reappears, with modifications, in The Bernstein-Vazirani Algorithm (recovering a hidden string instead of a binary property), in Simon's algorithm (finding a hidden XOR-mask period using a group-theoretic Hadamard trick), and ultimately in the quantum Fourier transform underlying Shor's factoring algorithm, where the "Hadamard sandwich" is replaced by a more general Fourier sandwich over $\mathbb{Z}_N$. In teaching and research, Deutsch-Jozsa is the standard first experiment run on new quantum hardware and new simulators, precisely because its correctness condition ($z=0^n$ iff constant) is trivial to check and its circuit is shallow — a small number of Hadamard layers plus one oracle call — making it a natural benchmark for gate fidelity and small-scale coherence. It also anchors the theoretical subfield of Query Complexity and Quantum Speedups, which classifies computational problems by how many oracle queries quantum versus classical algorithms need, a framework that later produced provably exponential bounded-error separations (Simon's problem) and, eventually, practically consequential ones (integer factoring, discrete logarithms) that threaten current public-key cryptography.

Ask the tutor: How would the algorithm's amplitudes change if the promise were dropped and f were an arbitrary Boolean function?