Scaling Up: Deutsch–Jozsa

Deutsch's original algorithm solved a one-bit problem: is a function $f:\{0,1\}\to\{0,1\}$ constant or balanced? The Deutsch–Jozsa algorithm, developed by David Deutsch and Richard Jozsa in 1992, lifts that result to $n$ input bits — and the quantum advantage becomes exponential.

The generalized problem

We have a black-box function $f:\{0,1\}^n \to \{0,1\}$ that is promised to be either:

Constant: $f(x) = 0$ for all $x$ , or $f(x) = 1$ for all $x$ .
Balanced: $f(x) = 0$ for exactly half of the $2^n$ inputs, and $1$ for the other half.

Classically, in the worst case you must evaluate $f$ at $2^{n-1}+1$ different inputs before you can be certain of the answer — the first half of the inputs could all return the same value, and only the $(2^{n-1}+1)$ -th query guarantees a conclusion. The Deutsch–Jozsa algorithm answers the question with a single oracle query, regardless of $n$ .

The circuit

The algorithm uses $n$ input qubits (initialized to $|0\rangle$ ) and one ancilla qubit (initialized to $|1\rangle$ ). The steps are:

Apply $H$ to the ancilla to prepare it in $|-\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ .
Apply $H^{\otimes n}$ to all $n$ input qubits, creating the uniform superposition $\tfrac{1}{\sqrt{2^n}}\sum_{x \in \{0,1\}^n}|x\rangle$ .
Query the oracle $U_f$ once.
Apply $H^{\otimes n}$ to the input qubits again.
Measure the input qubits.

If the measurement yields $|0\rangle^{\otimes n}$ (all zeros), the function is constant; any other outcome means it is balanced.

Why it works

After the second layer of Hadamards, the amplitude for the all-zeros outcome $|0\rangle^{\otimes n}$ is

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

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

The first Hadamard layer spreads the input over all $2^n$ basis states at once (quantum parallelism), the oracle imprints the function value as a phase via the $|-\rangle$ ancilla (phase kickback), and the second Hadamard layer converts that global phase pattern back into a measurable amplitude difference. Interference does all the work in a single pass.

Classical vs quantum query complexity

| Strategy | Queries in worst case | |----------------|-----------------------| | Classical | $2^{n-1}+1$ | | Deutsch–Jozsa | $1$ |

This $2^{n-1}$ vs $1$ separation is exact: there is no classical algorithm that can solve the promised problem with fewer than $2^{n-1}+1$ queries in the worst case, and the quantum algorithm never needs more than one. For $n = 270$ , classical worst-case requires $2^{269} \approx 10^{81}$ queries — more than the estimated $\sim 10^{80}$ atoms in the observable universe; the quantum algorithm still uses exactly one.

Deutsch–Jozsa is often called a "toy" algorithm because the promise (constant or balanced) makes the problem somewhat artificial. Its real value is didactic: it is the cleanest demonstration that quantum parallelism combined with interference can yield an exponential query advantage, and many deeper algorithms — Bernstein–Vazirani, Simon's algorithm, Shor's — inherit exactly this structure.