The Deutsch–Jozsa Algorithm

The Deutsch–Jozsa algorithm (Deutsch & Jozsa, 1992) was the first quantum algorithm to exhibit an exact exponential separation between quantum and classical deterministic query complexity. It solves a contrived but clean promise problem on a black-box Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ in one query to $f$, where any deterministic classical algorithm needs $2^{n-1}+1$ queries in the worst case.

The algorithm is mostly of pedagogical and historical importance — the problem is artificial and randomized classical algorithms solve it in $O(1)$ queries with arbitrarily small error — but it is the canonical first exposure to phase kickback, the Hadamard transform, and quantum parallelism. It is the parent of the Bernstein–Vazirani, Simon, and (ultimately) Shor algorithms.

For broader quantum-computing background see the qcfront project; for the complexity-theoretic frame ($\mathsf{P}$, $\mathsf{BPP}$, $\mathsf{BQP}$, query complexity) see math/complexity-theory.md (classical side) and misc/quantum-complexity-theory.md (quantum side, including the query / circuit / QTM models used to make the "one query" claim below precise). For the general anatomy of oracle-based quantum algorithms (how the classical $f$ becomes the unitary $U_f$ below), see misc/quantum-algorithms.md.

1. The Problem

Let $f:\{0,1{\}}^n\to \{0,1\}$ be given as an oracle (black box). We are promised that $f$ is one of the following:

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

The task: decide which case we are in, with certainty, using as few oracle queries as possible.

Inputs not satisfying the promise (e.g. $f$ that is $1$ on a third of the inputs) are outside the problem; the algorithm's behavior on them is unconstrained.

1.1 Classical query complexity

A deterministic classical algorithm must, in the worst case, query $f$ on $2^{n-1}+1$ inputs: after $2^{n-1}$ queries returning all $0$s the function could still be either constant-$0$ or balanced (with all $1$s on the unseen inputs); one more query decides it. So deterministic classical complexity is $\Theta (2^n)$.

Randomized classical complexity is trivial: query $f$ on $k$ uniformly random inputs. If $f$ is constant, all answers agree; if $f$ is balanced, the probability that all $k$ agree is $2^{1-k}$. So $k=O(1)$ queries suffice for any constant error $\epsilon >0$. This is the sense in which the Deutsch–Jozsa "exponential speedup" is fragile — it disappears the moment one allows bounded error.

2. Quantum Preliminaries

We work with qubits — unit vectors in ${\mathbb{C}}^2$ — and tensor products thereof.

2.1 The Hadamard gate

The single-qubit Hadamard is the unitary

$$H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),H|0⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩),H|1⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩).$$

Compactly, for $x\in \{0,1\}$:

$$H|x⟩=\frac{1}{\sqrt{2}}\sum _{y\in \{0,1\}}(-1{)}^{xy}|y⟩.$$

Applied to all $n$ qubits in parallel (the Hadamard transform $H^{\otimes n}$), this generalizes to

$$\boxed{H^{\otimes n}|x⟩=\frac{1}{\sqrt{2^n}}\sum _{y\in \{0,1{\}}^n}(-1{)}^{x\cdot y}|y⟩,x\cdot y\equiv \underset{i=1}{\overset{n}{⨁}}{x}_i{y}_i(\mathrm{mod}2).}$$

In particular $H^{\otimes n}|0{⟩}^{\otimes n}=2^{-n/2}{\sum }_x|x⟩$, the uniform superposition over all $n$-bit strings. And $H$ is its own inverse: $H^2=1$.

2.2 The oracle

The classical function $f$ is supplied as a quantum oracle — a unitary

$$U_f:|x⟩|y⟩⟼|x⟩|y\oplus f(x)⟩,x\in \{0,1{\}}^n,y\in \{0,1\},$$

on $n+1$ qubits, with $\oplus$ the bitwise XOR. This is the standard reversible embedding of an arbitrary Boolean function into a unitary. We charge one query per use of $U_f$.

2.3 Phase kickback

Initialize the ancilla qubit in $|-⟩\equiv H|1⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$. Then

$$U_f|x⟩|-⟩=\frac{1}{\sqrt{2}}(|x⟩|0\oplus f(x)⟩-|x⟩|1\oplus f(x)⟩)=(-1{)}^{f(x)}|x⟩|-⟩.$$

Two cases:

• $f(x)=0$: the bracket is $|0⟩-|1⟩$, so the global sign is $+1$.
• $f(x)=1$: the bracket is $|1⟩-|0⟩=-(|0⟩-|1⟩)$, so the global sign is $-1$.

The value of $f(x)$ has been moved from the value of the ancilla into a relative phase on the data register. This trick — phase kickback — is the engine of essentially every quantum query algorithm.

3. The Algorithm

The circuit has three stages:

|0⟩^⊗n  ── H^⊗n ──┐                ┌── H^⊗n ── measure
                  │      U_f       │
|1⟩    ── H ─────┘                └── (discarded)

Step by step:

1. Initialize $n+1$ qubits in $|0{⟩}^{\otimes n}|1⟩$.
2. Hadamard everything: apply $H^{\otimes n}\otimes H$ to obtain $$|{\psi }_1⟩=\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}|x⟩\otimes |-⟩.$$
3. Query the oracle once. By phase kickback, $$|{\psi }_2⟩=U_f|{\psi }_1⟩=\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}(-1{)}^{f(x)}|x⟩\otimes |-⟩.$$
4. Hadamard the data register again: $$|{\psi }_3⟩=(H^{\otimes n}\otimes 1)|{\psi }_2⟩=\frac{1}{2^n}\sum _{x,y\in \{0,1{\}}^n}(-1{)}^{f(x)+x\cdot y}|y⟩\otimes |-⟩.$$
5. Measure the data register in the computational basis. Output: "constant" iff the outcome is the all-zeros string $0^n$, else "balanced".

4. Why It Works

Read off the amplitude of $|y⟩$ in $|{\psi }_3⟩$:

$${\alpha }_y=\frac{1}{2^n}\sum _{x\in \{0,1{\}}^n}(-1{)}^{f(x)+x\cdot y}.$$

Specialize to $y=0^n$, where $x\cdot y=0$ for every $x$:

$${\alpha }_{0^n}=\frac{1}{2^n}\sum _{x\in \{0,1{\}}^n}(-1{)}^{f(x)}.$$

Now use the promise:

• $f$ constant. Every $(-1{)}^{f(x)}$ has the same sign, so ${\alpha }_{0^n}=\pm 1$, and hence $|{\alpha }_{0^n}{|}^2=1$. Measurement returns $0^n$ with probability $1$.
• $f$ balanced. Exactly $2^{n-1}$ of the $(-1{)}^{f(x)}$ are $+1$ and exactly $2^{n-1}$ are $-1$. They cancel: ${\alpha }_{0^n}=0$. Measurement returns $0^n$ with probability $0$.

So the rule "constant iff outcome is $0^n$" is exact — no error probability, no repetition needed. One query, one shot, certain answer.

A useful way to think about step 4: the Hadamard transform interferes the $2^n$ branches of the superposition. Constructive interference at $|0^n⟩$ requires the phases $(-1{)}^{f(x)}$ to agree (constant case); destructive interference there requires balanced cancellation. Quantum parallelism plus interference is the essential ingredient — neither alone would do it.

5. Worked Example: $n=1$ (Deutsch's Algorithm)

The original Deutsch (1985) algorithm is the $n=1$ special case. There are four functions $f:\{0,1\}\to \{0,1\}$:

Equivalently, decide $f(0)\oplus f(1)$ (= 0 for constant, 1 for balanced) using one query.

Tracing through with $|{\psi }_0⟩=|0⟩|1⟩$:

$$|{\psi }_1⟩=\frac{1}{2}(|0⟩+|1⟩)(|0⟩-|1⟩),$$

$$|{\psi }_2⟩=\frac{1}{2}((-1{)}^{f(0)}|0⟩+(-1{)}^{f(1)}|1⟩)(|0⟩-|1⟩).$$

After the final Hadamard on the data qubit, the data-register amplitude on $|0⟩$ is $\frac{1}{2}((-1{)}^{f(0)}+(-1{)}^{f(1)})$, which is $\pm 1$ if $f(0)=f(1)$ and $0$ if not. Measure: outcome $0\iff$ constant, outcome $1\iff$ balanced.

6. Query Complexity Comparison

So the separation is exponential vs. constant against deterministic classical, but only constant vs. constant against bounded-error randomized classical. This is why Deutsch–Jozsa is rightly called a milestone (first exact super-polynomial quantum-vs-deterministic separation) but rarely called a practical speedup.

The first quantum algorithm to give a super-polynomial separation against bounded-error randomized classical query complexity is Simon's algorithm (1994), which Shor then converted into the polynomial-time factoring algorithm.

7. Historical and Theoretical Significance

• First exponential quantum separation (against deterministic classical). Established that quantum computation could outperform classical in some provable sense, opening the field.
• Phase-kickback template. The pattern "encode classical bits as $\pm 1$ phases via $|-⟩$ ancilla, then interfere with $H^{\otimes n}$" recurs in Bernstein–Vazirani (1993), Simon (1994), and the quantum Fourier transform core of Shor (1994).
• Promise problems matter. The artificial constant-vs-balanced promise is what makes a deterministic separation possible; without the promise, decision problems on $\{0,1{\}}^n$ are subject to entirely different lower bounds.
• Limits. Deutsch–Jozsa puts a contrived problem in $\mathsf{EQP}$ (exact quantum polynomial time) but not provably outside $\mathsf{P}$ (it's outside deterministic query complexity, which is a much weaker statement). Whether $\mathsf{BQP}⊊\mathsf{P}$, $\mathsf{BPP}⊊\mathsf{BQP}$, etc. remain open.

References

• D. Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. R. Soc. A 400, 97 (1985) — the $n=1$ case.
• D. Deutsch and R. Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. A 439, 553 (1992) — the general $n$ case.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge, 2010), §1.4.3 — standard textbook treatment.