The Deutsch–Jozsa Algorithm

The Deutsch–Jozsa algorithm, introduced by David Deutsch and Richard Jozsa in 1992, extends Deutsch's one-bit result to $n$ input bits. It decides whether an unknown Boolean function $f : \{0,1\}^n \to \{0,1\}$ is constant or balanced using a single oracle query — while any deterministic classical algorithm needs up to $2^{n-1}+1$ queries in the worst case.

The complete circuit

The algorithm uses $n$ input qubits and one ancilla qubit. All qubits start in $|0\rangle$ .

Step 1 — Initialise the ancilla. Apply $X$ to the ancilla qubit so it begins in $|1\rangle$ .

Step 2 — Create superpositions. Apply a Hadamard to every qubit. The $n$ input qubits enter the uniform superposition $\tfrac{1}{\sqrt{2^n}}\sum_{x}|x\rangle$ ; the ancilla becomes

$|-\rangle = \tfrac{1}{\sqrt{2}}\bigl(|0\rangle - |1\rangle\bigr).$

$U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle.$

The function value is now encoded as a relative phase on the input register; the ancilla is untouched and disentangles.

Step 4 — Interfere. Apply $H^{\otimes n}$ to all input qubits. The amplitude for the all-zeros bitstring $|0\rangle^{\otimes n}$ after this step is

$\frac{1}{2^n}\sum_{x \in \{0,1\}^n}(-1)^{f(x)}.$

When $f$ is constant, every term has the same sign, so all $2^n$ contributions add constructively and the amplitude is $\pm 1$ . When $f$ is balanced, exactly half the terms contribute $+1$ and half $-1$ , so the sum is zero and the all-zeros outcome has probability exactly zero.

Step 5 — Measure. Read the input qubits. Outcome $|0\cdots0\rangle$ means constant; any other outcome means balanced. The answer is deterministic — no probability of error.

The n = 2 case worked out

For $n = 2$ the input register holds qubits 0 and 1, and qubit 2 is the ancilla. Using the balanced oracle $f(x_0, x_1) = x_0 \oplus x_1$ , encoded by two CNOT gates $\text{CNOT}_{0 \to 2}$ followed by $\text{CNOT}_{1 \to 2}$ , the phase kickback gives

= \tfrac{1}{2}\bigl(|00\rangle - |01\rangle - |10\rangle + |11\rangle\bigr).$$ Applying $H \otimes H$ to this state collapses the amplitude entirely onto $|11\rangle$ — both input qubits measure to 1 with certainty, confirming the function is balanced. ## Try it Complete the circuit for $n = 2$ with the balanced oracle $f(x_0, x_1) = x_0 \oplus x_1$. Follow the five steps above: initialise the ancilla, apply Hadamards to all qubits, add the two CNOT oracle gates, apply Hadamards to the input qubits, then measure them. The grader checks the measurement distribution — for a balanced function both input qubits must read 1. <RunnableExample /> After the algorithm completes, the input qubits deterministically show $|11\rangle$: both amplitudes concentrate on that outcome, and the Probabilities panel shows two equal bars for $|110\rangle$ and $|111\rangle$ (the ancilla is in $|-\rangle$ and contributes equal weight to each).