Deutsch-Jozsa Algorithm

⚡ Key Takeaways

Deutsch–Jozsa Algorithm: a quantum algorithm that determines whether a black-box function $f:\{0,1\}^n \to \{0,1\}$ is constant or balanced using a single query, where any deterministic classical algorithm may require up to $2^{n-1}+1$ queries. Key result: it provides the first proven exponential separation between exact quantum and exact classical query complexity. Applies to: quantum computing theory, query complexity, oracle separations. Who/when: David Deutsch & Richard Jozsa (1992), refined by Cleve, Ekert, Macchiavello, Mosca (1998).

💡 The Core Insight

A quantum computer can evaluate $f$ on all $2^n$ inputs simultaneously by placing the input register in an equal superposition. But superposition alone is useless — measuring it gives a random input. The genius is to encode $f$ 's answer into the phase of each computational basis state (the "phase kickback" trick), then apply Hadamard gates so that constructive/destructive interference concentrates the answer onto a single measurable outcome. If $f$ is constant, all phases align and the system returns deterministically to $|0\rangle^{\otimes n}$ ; if $f$ is balanced, the amplitude of $|0\rangle^{\otimes n}$ vanishes exactly, so measuring it is impossible.

DefinitionThe Promise Problem

Let $f:\{0,1\}^n \to \{0,1\}$ be a Boolean function accessible only through a quantum oracle $U_f$ . We are promised that $f$ is either:

Constant: $f(x)=c$ for all $x\in\{0,1\}^n$ , with fixed $c\in\{0,1\}$ ; or
Balanced: $|\{x : f(x)=0\}| = |\{x : f(x)=1\}| = 2^{n-1}$ .

The task is to determine which, with certainty, minimizing oracle queries. The oracle acts on $n+1$ qubits as

1

\quad U_f\,|x\rangle|y\rangle = |x\rangle\,|y \oplus f(x)\rangle,

Derivation hint: This is the standard reversible (unitary) embedding of any classical function; $\oplus$ is XOR, ensuring $U_f$ is its own inverse since $U_f^2 = I$ . Here $|x\rangle = |x_1 x_2 \cdots x_n\rangle$ is the $n$ -qubit input register, $|y\rangle$ is the single-qubit target (ancilla) register, and $\oplus$ denotes addition modulo $2$ .

DefinitionThe Hadamard Transform

The single-qubit Hadamard gate $H$ and its $n$ -fold tensor power act as

2

\quad H|x\rangle = \frac{1}{\sqrt{2}}\sum_{z\in\{0,1\}}(-1)^{xz}|z\rangle, \qquad H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}}\sum_{z\in\{0,1\}^n}(-1)^{x\cdot z}|z\rangle,

Derivation hint: Apply the single-qubit rule tensor-wise; the dot product $x\cdot z = \sum_{i=1}^n x_i z_i \pmod 2$ arises because the exponents add across qubits, and the global sign is determined modulo 2. where $x\cdot z = x_1 z_1 \oplus \cdots \oplus x_n z_n$ is the bitwise inner product modulo $2$ .

TheoremDeutsch–Jozsa Theorem

There exists a quantum algorithm that solves the promise problem of distinguishing constant from balanced $f$ with certainty using exactly one query to $U_f$ . Any deterministic classical algorithm solving the same problem with certainty requires, in the worst case, at least $2^{n-1}+1$ queries.

ProofStep-by-step evolution of the quantum state

We track the $(n+1)$ -qubit state through the circuit. Initialize the input register to $|0\rangle^{\otimes n}$ and the ancilla to $|1\rangle$ .

Step 1 — Initial state.

3

\quad |\psi_0\rangle = |0\rangle^{\otimes n}\,|1\rangle.

Derivation hint: Standard convention; the ancilla is set to $|1\rangle$ so that after a Hadamard it becomes the eigenvector $\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)$ needed for phase kickback.

Step 2 — Apply $H^{\otimes n}\otimes H$ . Using equation [2] on each register:

4

\quad |\psi_1\rangle = \frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle \otimes \frac{1}{\sqrt 2}\bigl(|0\rangle - |1\rangle\bigr).

Derivation hint: $H^{\otimes n}|0\rangle^{\otimes n} = 2^{-n/2}\sum_x|x\rangle$ (all signs $+1$ since $0\cdot z=0$ ), and $H|1\rangle = \tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)$ .

Step 3 — Apply the oracle $U_f$ (the phase kickback). Acting on the ancilla state $\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)$ :

5

\quad U_f\,|x\rangle\,\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle) = (-1)^{f(x)}\,|x\rangle\,\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle).

Derivation hint: $|0\oplus f(x)\rangle - |1\oplus f(x)\rangle$ equals $+(|0\rangle-|1\rangle)$ if $f(x)=0$ and $-(|0\rangle-|1\rangle)$ if $f(x)=1$ , which is exactly $(-1)^{f(x)}(|0\rangle-|1\rangle)$ . Therefore the full state becomes

6

\quad |\psi_2\rangle = \frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}(-1)^{f(x)}\,|x\rangle \otimes \frac{1}{\sqrt2}(|0\rangle-|1\rangle).

Derivation hint: The function value $f(x)$ has been transferred from a data register into a global $\pm$ phase on each $|x\rangle$ — the ancilla now factors out and can be ignored.

Step 4 — Apply $H^{\otimes n}$ to the input register. Using equation [2]:

7

\quad |\psi_3\rangle = \frac{1}{2^n}\sum_{x\in\{0,1\}^n}\sum_{z\in\{0,1\}^n}(-1)^{f(x)+x\cdot z}\,|z\rangle.

Derivation hint: Replace each $|x\rangle$ by $2^{-n/2}\sum_z(-1)^{x\cdot z}|z\rangle$ and combine the two prefactors $2^{-n/2}\cdot 2^{-n/2}=2^{-n}$ ; exponents add.

Step 5 — Amplitude of $|0\rangle^{\otimes n}$ . Set $z=0^n$ so $x\cdot z = 0$ :

8

\quad \langle 0^n|\psi_3\rangle = \frac{1}{2^n}\sum_{x\in\{0,1\}^n}(-1)^{f(x)}.

Derivation hint: Only the $z=0^n$ term in equation [7] survives the inner product, and $x\cdot 0^n = 0$ kills the $(-1)^{x\cdot z}$ factor.

Step 6 — Interpret by cases.

If $f$ is constant, $(-1)^{f(x)}=(-1)^c$ for all $x$ , so the sum is $\pm 2^n$ and $|\langle 0^n|\psi_3\rangle| = 1$ . Measurement yields $0^n$ with probability $1$ .
If $f$ is balanced, exactly half the terms are $+1$ and half are $-1$ , so the sum is $0$ and $\langle 0^n|\psi_3\rangle = 0$ . The outcome $0^n$ never occurs.

Decision rule: Measure the input register. If the result is $0^n$ , declare constant; otherwise declare balanced. This uses exactly one oracle query. $\blacksquare$

Classical lower bound. A deterministic classical algorithm sees one value of $f$ per query. If it has queried $2^{n-1}$ inputs and all returned the same value, $f$ could still be constant or balanced (a balanced function can agree with a constant one on the first half). Only by querying one more — a $(2^{n-1}+1)$ -th input — can it be certain. Hence $2^{n-1}+1$ queries are necessary in the worst case.

∎

Figure

Deutsch–Jozsa circuit: superposition, phase kickback, interference

```svg

```

DD

David Deutsch

b. 1953

David Deutsch, a British physicist at the University of Oxford, is widely regarded as a founding father of quantum computation. In his 1985 paper he formalized the universal quantum computer (the quantum Turing machine) and posed the original single-bit problem now bearing his name. The $n$ -bit generalization came in his 1992 collaboration with Richard Jozsa, a mathematical physicist. Deutsch's broader motivation was philosophical: he championed the many-worlds interpretation of quantum mechanics, arguing that quantum parallelism is literal evidence of a multiverse. His work transformed quantum computing from a curiosity into a discipline with provable complexity-theoretic payoffs.

🧠 Intuition

Think of $f$ as $2^n$ coins, each showing heads ( $+1$ ) or tails ( $-1$ ) according to $(-1)^{f(x)}$ . Classically you can only flip over and look at the coins one at a time. The quantum trick is to place all coins on a perfectly balanced see-saw (the equal superposition) and ask a single global question: "do all the coins push in the same direction?"

Constant $f$ : every coin shows the same face, so they all push together — the see-saw tilts decisively to the " $0^n$ " side. You read that tilt in one shot.
Balanced $f$ : exactly half show heads and half show tails — their pushes cancel perfectly, the see-saw stays level at " $0^n$ ," and that outcome can never register.

The Hadamard gates are the see-saw: they convert the phase pattern (which you cannot measure directly) into an amplitude pattern (which you can). Interference does the averaging for free, in parallel, which is why no classical "look one coin at a time" strategy can compete.

Examplen = 1: the original Deutsch problem

Given: $n=1$ , so $f:\{0,1\}\to\{0,1\}$ . There are four such functions. Constant ones: $f\equiv 0$ , $f\equiv 1$ . Balanced ones: $f(x)=x$ (identity), $f(x)=1\oplus x$ (NOT).

Take $f(x)=x$ (balanced). Step 1: Initial state $|0\rangle|1\rangle$ . Step 2: After $H\otimes H$ :

\tfrac12(|0\rangle+|1\rangle)(|0\rangle-|1\rangle).

Step 3: Phase kickback gives factor $(-1)^{f(x)}=(-1)^x$ :

\tfrac{1}{\sqrt2}\bigl((-1)^0|0\rangle+(-1)^1|1\rangle\bigr)\otimes\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle) = \tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)\otimes(\ldots).

Step 4: Apply $H$ to input: $H\,\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle) = |1\rangle$ . Step 5: Amplitude of $|0\rangle$ is $0$ , amplitude of $|1\rangle$ is $1$ .

Boxed answer: Measurement yields $1\neq 0$ with probability $1$ ⇒ algorithm correctly declares balanced using 1 query. (Classical worst case here: $2$ queries.)

Examplen = 2: a balanced function via the amplitude formula

Given: $n=2$ , define $f(x_1 x_2) = x_1 \oplus x_2$ . Check the promise: $f(00)=0,\,f(01)=1,\,f(10)=1,\,f(11)=0$ → two zeros, two ones ⇒ balanced.

Compute the all-zeros amplitude using equation [8]:

\langle 00|\psi_3\rangle = \frac{1}{2^2}\sum_{x\in\{0,1\}^2}(-1)^{f(x)} = \frac14\Bigl[(-1)^0+(-1)^1+(-1)^1+(-1)^0\Bigr] = \frac14[1-1-1+1] = 0.

So $|00\rangle$ has zero amplitude — consistent with balanced. To find which outcome appears, use the general amplitude of $|z\rangle$ from equation [7]:

c_z = \frac{1}{4}\sum_x (-1)^{f(x)+x\cdot z}.

For $z=11$ : $x\cdot z = x_1\oplus x_2 = f(x)$ , so $f(x)+x\cdot z = 2f(x)\equiv 0$ , giving $c_{11}=\tfrac14(1+1+1+1)=1$ .

Boxed answer: The measurement deterministically returns $z=11\neq 00$ ⇒ balanced, in 1 query. (Classical worst case for $n=2$ : $2^{1}+1 = 3$ queries.)

⚠️ Common mistake

The algorithm does NOT tell you whether $f$ is balanced if the promise is violated. Deutsch–Jozsa is a promise problem: it assumes $f$ is either exactly constant or exactly balanced. If you feed it an arbitrary function (say, $f=1$ on $3$ of $4$ inputs at $n=2$ ), the all-zeros amplitude is neither $\pm1$ nor $0$ , the measurement is probabilistic, and the output is meaningless. The exponential speedup exists only because the promise drastically restricts the input space.

CounterexampleThe speedup vanishes for randomized classical algorithms

The dramatic exponential gap ( $1$ vs $2^{n-1}+1$ ) is between quantum and deterministic exact classical algorithms. If you allow a bounded-error randomized classical algorithm, the advantage collapses: sample $k$ inputs at random. If $f$ is balanced, the probability that all $k$ agree is $2^{-(k-1)}$ (roughly), so with just $k\approx 10$ random queries you distinguish constant from balanced with error below $0.1\%$ — independent of $n$ . Thus Deutsch–Jozsa shows exponential quantum advantage over exact classical computation, but only a modest constant-factor advantage over probabilistic classical computation. (Genuine exponential advantage over randomized classical algorithms requires later results like Simon's Algorithm.)

connection

Deutsch–Jozsa sits at the head of a family of quantum query algorithms.

It is the $n$ -qubit generalization of the original 1985 single-bit Deutsch's Algorithm, which already showed a $1$ -vs- $2$ query advantage.
The same Hadamard–oracle–Hadamard sandwich and phase-kickback mechanism reappears in the Bernstein–Vazirani Algorithm, which recovers a hidden string $a$ from $f(x)=a\cdot x$ in one query.
It is structurally the prototype of the hidden subgroup framework: Simon's Algorithm extends it to a hidden XOR-mask and achieves provable exponential advantage even over randomized algorithms, directly inspiring the period-finding core of Shor's Algorithm.
The Hadamard transform $H^{\otimes n}$ is the Quantum Fourier Transform over the group $(\mathbb{Z}/2)^n$ , linking Deutsch–Jozsa to Fourier sampling.
Its analysis is the canonical entry point into Quantum Query Complexity and oracle-based separations between complexity classes.

🔬 Where this appears

⏳ History

- 1980–1982 — Paul Benioff and Richard Feynman argue that quantum systems may be hard to simulate classically, hinting at the computational power of quantum mechanics.

- 1985 — David Deutsch publishes "Quantum theory, the Church–Turing principle and the universal quantum computer," defining the quantum Turing machine and posing the original 1-bit Deutsch problem.

- 1992 — Deutsch and Richard Jozsa publish "Rapid solution of problems by quantum computation," generalizing to

n

bits and proving the constant-vs-balanced separation. The original version required two function evaluations and gave an exact answer only in part.

- 1993 — Ethan Bernstein and Umesh Vazirani introduce their related algorithm and formalize quantum complexity classes, sharpening the query-complexity perspective.

- 1994 — Daniel Simon's algorithm and Peter Shor's factoring algorithm appear, showing the Deutsch–Jozsa lineage scales to practically important problems.

- 1998 — Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca publish "Quantum algorithms revisited," streamlining Deutsch–Jozsa to its modern single-query form using the phase-kickback ancilla

|1\rangle

.

- 1998 — Isaac Chuang, Lieven Vandersypen, and collaborators perform early NMR experimental demonstrations of small Deutsch–Jozsa instances.

- 2007 onward — Photonic, ion-trap, and superconducting implementations demonstrate the algorithm on increasing qubit counts, establishing it as a standard hardware benchmark.

open-problem

How "real" is the Deutsch–Jozsa advantage? Several conceptual tensions persist:

Promise dependence. The exponential gap exists only under the constant-or-balanced promise; remove it and the algorithm gives no certified answer. Quantifying advantage for arbitrary (non-promise) decision problems is the subject of ongoing query-complexity research.
Exact vs bounded-error. The exponential separation is against exact deterministic classical computation. Against randomized algorithms the gap is merely constant — so Deutsch–Jozsa does not prove $\mathsf{BPP}\neq\mathsf{BQP}$ . Whether such separation holds relative to no oracle remains open and is tied to deep unresolved questions about $\mathsf{BQP}$ vs the polynomial hierarchy.
Resource accounting. The "single query" hides the cost of building the oracle $U_f$ , which for a real $f$ may itself require exponential classical work; the speedup is a query-complexity statement, not a wall-clock guarantee.
Interpretational debate. Whether quantum parallelism "literally" evaluates all $2^n$ inputs (Deutsch's many-worlds reading) or is merely a useful amplitude bookkeeping device remains philosophically contested, with no experimental test that distinguishes the interpretations.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also