Deutsch-Jozsa Algorithm

The Deutsch-Jozsa algorithm, published by David Deutsch and Richard Jozsa in 1992, is historically the first quantum algorithm to demonstrate a clear separation between quantum and classical computation. Given a black-box function $f: \{0,1\}^n \to \{0,1\}$ that is promised to be either constant (same output for all inputs) or balanced (outputs 0 for exactly half the inputs and 1 for the other half), the algorithm determines which case holds using exactly one query to $f$. Any deterministic classical algorithm requires $2^{n-1} + 1$ queries in the worst case.

The circuit

The algorithm uses $n$ input qubits and one ancilla qubit:

1. Initialize: $|0\rangle^{\otimes n}|1\rangle$
2. Apply Hadamard gates to all $n+1$ qubits, producing the state $\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle \cdot \frac{|0\rangle - |1\rangle}{\sqrt{2}}$
3. Apply the oracle $U_f$, which maps $|x\rangle|y\rangle \to |x\rangle|y \oplus f(x)\rangle$
4. Apply Hadamard gates to the $n$ input qubits
5. Measure the input qubits

After step 3, the phase kickback effect transforms the state so that each basis state $|x\rangle$ picks up a phase of $(-1)^{f(x)}$. The input register becomes:

$\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}(-1)^{f(x)}|x\rangle$

After applying Hadamard gates in step 4, the amplitude of the all-zeros state $|0^n\rangle$ is:

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

If $f$ is constant, all phases are equal and this amplitude is $\pm 1$, so measuring gives $|0^n\rangle$ with certainty. If $f$ is balanced, the positive and negative phases cancel exactly, giving amplitude 0, so the measurement never yields $|0^n\rangle$.

Complexity comparison

Approach	Queries needed
Deterministic classical	$2^{n-1} + 1$ (worst case)
Randomized classical	$O(1)$ with bounded error
Quantum (Deutsch-Jozsa)	1 (exact, no error)

The quantum advantage here is over deterministic classical algorithms. A randomized classical algorithm can solve the problem with high probability using just a few queries (if the first few queries all return the same value, “constant” is overwhelmingly likely). This makes the Deutsch-Jozsa speedup somewhat academic, but it remains an important proof of concept.

Historical significance

The Deutsch-Jozsa algorithm was the first clear example showing that quantum computers can solve certain problems faster than classical computers. The original 1985 paper by Deutsch considered the single-bit case ($n=1$), and Jozsa extended it to $n$ bits. It directly inspired subsequent oracle-based algorithms including Bernstein-Vazirani and ultimately Grover’s algorithm.

Why it matters for learners

Deutsch-Jozsa is typically the first quantum algorithm taught in courses because it cleanly illustrates three core quantum concepts: superposition (querying all inputs at once), phase kickback (encoding function values into phases), and interference (using Hadamard transforms to make phases constructively or destructively combine). Understanding this algorithm provides the conceptual toolkit for all subsequent oracle-based quantum algorithms.

See also

• Quantum Oracle
• Hadamard Gate
• Bernstein-Vazirani
• Quantum Interference
• Phase Kickback