algorithms intermediate · 22 min read · April 22, 2026

Deutsch-Jozsa: The First Quantum Speedup

The Deutsch-Jozsa algorithm separates constant from balanced Boolean functions in a single query, where classical deterministic algorithms need up to 2ⁿ⁻¹ + 1. This tutorial derives the algorithm from first principles, explains phase kickback, and walks through the full Qiskit implementation plus the Deutsch n=1 special case.

Prerequisites: Gates & Circuits track (Tutorials 4-7)

Deutsch-Jozsa is the Hello World of quantum algorithms — and also the first formal proof that quantum computers can do things classical ones fundamentally can’t. It’s not a useful algorithm in any practical sense (the problem it solves doesn’t exist in the wild) but the ideas it introduces — oracles, phase kickback, interference at the output — are the scaffolding of every subsequent algorithm you’ll learn.

If you understand Deutsch-Jozsa deeply, you can understand Grover, Shor, and quantum phase estimation. If you don’t, you’ll be memorizing gate sequences forever.

The problem

You’re given a Boolean function $f: \{0,1\}^n \to \{0,1\}$ as a black box — you can query it, but you can’t peek at its code. You’re promised that $f$ is one of two kinds:

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

Your job: decide which, with as few queries as possible.

Classical bound. With a deterministic classical algorithm, the worst case requires $2^{n-1} + 1$ queries. Here’s why: if you see $2^{n-1}$ queries that all returned $0$, the function could still be balanced (all the remaining $2^{n-1}$ inputs might return $1$) or constant. Only on query $2^{n-1} + 1$ are you forced to see either a $1$ (balanced) or a $2^{n-1} + 1$-th $0$ (constant, since a balanced function can’t have more than $2^{n-1}$ zeros).

Quantum bound. A quantum algorithm solves this with a single query. One. That’s the Deutsch-Jozsa algorithm.

The speedup is exponential in the worst case ($2^{n-1}$ vs 1), though it vanishes under a randomized classical algorithm (any balanced-vs-constant test reaches arbitrarily small error with $O(1)$ random samples). Deutsch-Jozsa is primarily a proof of worst-case deterministic separation between classical and quantum.

The oracle

To feed $f$ into a quantum circuit, you need a reversible version. Classical $f$ is generally not reversible (many-to-one). The standard fix: a unitary $U_f$ acting on $n+1$ qubits that XOR’s the output into a dedicated target qubit:

$$U_f\,|x\rangle|y\rangle \;=\; |x\rangle\,|y \oplus f(x)\rangle.$$

This is reversible because applying $U_f$ twice returns to the original state. It’s a formalism every oracle-based quantum algorithm inherits.

Phase kickback: the trick that makes it work

Here is the one idea you need to internalize. Put the target qubit into the state $|-\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ and watch what happens when $U_f$ acts:

$$U_f\,|x\rangle|-\rangle \;=\; |x\rangle\,\tfrac{1}{\sqrt{2}}(|0 \oplus f(x)\rangle - |1 \oplus f(x)\rangle).$$

If $f(x) = 0$, the target is $\tfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = |-\rangle$ (unchanged). If $f(x) = 1$, it’s $\tfrac{1}{\sqrt{2}}(|1\rangle - |0\rangle) = -|-\rangle$ (negated). Rearrange:

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

The oracle’s output $f(x)$ has been moved from the target qubit into the phase of the input qubit. The target qubit is unchanged; the input qubit picks up a $\pm 1$ phase factor depending on $f(x)$.

This is phase kickback. It converts an oracle “that computes $f$” into one “that marks inputs with $f(x)=1$ by a negative sign” — and that phase pattern is what quantum interference can read.

The Deutsch-Jozsa circuit

Now build the algorithm:

1. Prepare $n$ input qubits in $|0\rangle^{\otimes n}$ and one ancilla in $|1\rangle$.
2. Apply $H$ to every qubit. Inputs become uniform superposition; ancilla becomes $|-\rangle$.

$$|\psi_1\rangle \;=\; \frac{1}{\sqrt{2^n}}\sum_x |x\rangle \otimes |-\rangle.$$

3. Apply the oracle $U_f$. Phase kickback gives:

$$|\psi_2\rangle \;=\; \frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle \otimes |-\rangle.$$

4. Apply $H^{\otimes n}$ to the inputs. This is the quantum Fourier transform over $\mathbb{Z}_2^n$ — it decomposes the sign pattern $(-1)^{f(x)}$ into its Hadamard components. The result:

$$|\psi_3\rangle \;=\; \frac{1}{2^n}\sum_x \sum_y (-1)^{f(x) \oplus x \cdot y}|y\rangle \otimes |-\rangle.$$

5. Measure the inputs in the computational basis.

The punchline

Look at the amplitude of $|0\rangle^{\otimes n}$ (i.e., $y = 0$) in $|\psi_3\rangle$:

$$\alpha_{y=0} \;=\; \frac{1}{2^n}\sum_x (-1)^{f(x)}.$$

• Constant $f = 0$: every term is $+1$, sum is $2^n$, $|\alpha_0|^2 = 1$. Measurement gives $0^n$ with certainty.
• Constant $f = 1$: every term is $-1$, $|\alpha_0|^2 = 1$ (the negative global phase is unobservable). Still $0^n$.
• Balanced $f$: half the terms are $+1$ and half are $-1$, sum is $0$. $|\alpha_0|^2 = 0$. $0^n$ can never appear.

So you measure once. If you get $0^n$, $f$ is constant. If you get anything else, $f$ is balanced. One query. Done.

Deutsch n=1 in OpenQASM

The $n = 1$ special case (Deutsch’s original 1985 algorithm) has four possible functions:

$f(x)$	Kind	Oracle
$f(x) = 0$	Constant	Identity on ancilla
$f(x) = 1$	Constant	X on ancilla
$f(x) = x$	Balanced	CNOT, control = input
$f(x) = \bar{x}$	Balanced	CNOT then X on ancilla

Pick the balanced $f(x) = x$ oracle. Circuit:

OPENQASM 2.0;
include "qelib1.inc";

qreg q[2];   // q[0] = input, q[1] = ancilla
creg c[1];

// Prep: |0⟩|1⟩ then H on both → |+⟩|−⟩
x q[1];
h q[0];
h q[1];

// Oracle for f(x) = x: CNOT from input to ancilla
cx q[0], q[1];

// Final H on input
h q[0];

measure q[0] -> c[0];

Run it: you’ll see 1 on every shot. Swap the cx for nothing (constant $f=0$) or x q[1] (constant $f=1$), and you’ll see 0 every shot.

→ Open this circuit in the playground (pick “Deutsch-Jozsa” from the examples dropdown, or paste the QASM above).

General $n$ in Qiskit

Here’s a clean implementation that takes a user-supplied oracle and runs the algorithm:

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

def deutsch_jozsa_circuit(n: int, oracle: QuantumCircuit) -> QuantumCircuit:
    """DJ circuit. `oracle` acts on n input qubits + 1 ancilla qubit (indexed 0..n-1, n)."""
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)                 # ancilla = |1⟩
    qc.h(range(n + 1))      # H everywhere

    qc.compose(oracle, inplace=True)   # wire in the oracle

    qc.h(range(n))          # H on inputs
    qc.measure(range(n), range(n))
    return qc

# --- Build two oracles for n = 3 ---

def constant_oracle(n: int, value: int) -> QuantumCircuit:
    oc = QuantumCircuit(n + 1)
    if value == 1:
        oc.x(n)
    return oc

def balanced_oracle(n: int, mask: int) -> QuantumCircuit:
    """f(x) = (mask · x) mod 2 — a family of balanced functions parameterized by `mask`."""
    oc = QuantumCircuit(n + 1)
    for q in range(n):
        if (mask >> q) & 1:
            oc.cx(q, n)
    return oc

n = 3
sim = AerSimulator()

for name, oracle in [
    ("constant=0", constant_oracle(n, 0)),
    ("constant=1", constant_oracle(n, 1)),
    ("balanced(mask=0b101)", balanced_oracle(n, 0b101)),
    ("balanced(mask=0b111)", balanced_oracle(n, 0b111)),
]:
    qc = deutsch_jozsa_circuit(n, oracle)
    counts = sim.run(qc, shots=1).result().get_counts()
    outcome = next(iter(counts))
    verdict = "CONSTANT" if outcome == "0" * n else "BALANCED"
    print(f"{name:<22s}  → measured {outcome}  → {verdict}")
# constant=0             → measured 000  → CONSTANT
# constant=1             → measured 000  → CONSTANT
# balanced(mask=0b101)   → measured 101  → BALANCED
# balanced(mask=0b111)   → measured 111  → BALANCED

Notice: when the balanced oracle is $f(x) = s \cdot x$ for some bitmask $s$, the measurement returns exactly $s$. That’s not a coincidence — it’s the seed of the next algorithm you’ll meet (Bernstein-Vazirani), where learning $s$ is the actual goal.

Why the separation isn’t quite as miraculous as it sounds

Two honest caveats:

1. Against a randomized classical algorithm, Deutsch-Jozsa’s speedup evaporates. A classical algorithm that picks $O(1)$ random $x$‘s and checks $f(x)$ will be right with probability $\geq 1 - 2^{-k}$ after $k$ queries. “Exponential speedup” only holds against deterministic classical algorithms with zero error.
2. Oracle access is the whole game. In a real problem, you’d have to write $f$ as code anyway — and if you have the code, you could inspect it directly. The separation is a statement about query complexity in the black-box model, not wall-clock time on any real problem.

So why does anyone teach Deutsch-Jozsa? Because it introduces, cleanly and irrefutably, the three moves that power every subsequent quantum algorithm: oracle + phase kickback + Hadamard interference. Once you see them, you see them everywhere.

The deeper pattern: Hadamard transforms and $\mathbb{Z}_2^n$ Fourier analysis

The final $H^{\otimes n}$ in DJ is the discrete Fourier transform over the group $\mathbb{Z}_2^n$. The algorithm is, structurally:

1. Prepare a uniform superposition over the group $\mathbb{Z}_2^n$.
2. Apply the oracle to introduce a character (a sign pattern) onto the group.
3. Fourier-transform to read out a single Fourier coefficient.

Every algorithm we’ll meet in this track follows the same three-move shape, with different groups and different characters. Simon uses $\mathbb{Z}_2^n$ with a shift character. Shor uses $\mathbb{Z}_N$ with a phase character and the QFT in place of Hadamards. QPE uses $\mathbb{Z}_{2^n}$ with a phase character directly.

Exercises

1. Verify the unitary

The oracle for $f(x) = x$ (the CNOT oracle in Deutsch $n=1$) is a $4 \times 4$ matrix. Write it out and verify $U_f^2 = I$.

Show answer

CNOT with control = qubit 0, target = qubit 1, in the basis $|x,y\rangle$ = $|00\rangle, |01\rangle, |10\rangle, |11\rangle$:

$$U_f = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}.$$

$U_f^2 = I$ follows from CNOT being its own inverse.

2. Hand-trace $n = 2$

Pick the balanced oracle $f(x_0, x_1) = x_0 \oplus x_1$ (i.e., CNOT from $q_0$ to ancilla, then CNOT from $q_1$ to ancilla). Write the state $|\psi_2\rangle$ after the oracle as a superposition over $(x_0, x_1)$ with explicit $\pm$ signs. Predict the measurement outcome.

Show answer

$f(0,0)=0, f(0,1)=1, f(1,0)=1, f(1,1)=0$. After phase kickback, the input register (ignoring ancilla) is

$$\tfrac{1}{2}(|00\rangle - |01\rangle - |10\rangle + |11\rangle).$$

This is $|+-\rangle$ times — wait, factor it: $\tfrac{1}{2}(|0\rangle - |1\rangle)(|0\rangle - |1\rangle) = |--\rangle$.

Apply $H \otimes H$: $|--\rangle \to |11\rangle$. So the measurement returns 11 with certainty. Indeed, the “secret” string is s = 11 (both bits contribute), and DJ spits it out.

3. Build a non-linear balanced oracle

The mask-based oracle only produces balanced functions of the form $f(x) = s \cdot x$. Can you construct a balanced oracle that isn’t linear? (Hint: any balanced function can be encoded as a truth-table oracle using Toffoli-based construction.)

Show sketch

A simple nonlinear balanced function on $n=3$: $f(x) = x_0 \wedge x_1$ (this is balanced because exactly 4 of 8 inputs have $x_0 = x_1 = 1$ … wait, that’s 2 not 4. Let me pick a different one).

$f(x_0, x_1, x_2) = x_0 \oplus (x_1 \wedge x_2)$: evaluate at all 8 inputs; 4 outputs are 0 and 4 are 1. Implement by ccx q[1], q[2], q[n]; cx q[0], q[n];. Test with DJ — any non-$0^n$ outcome confirms balanced.

4. Simulate the query complexity

For $n = 8$, classically it could take up to $2^{n-1} + 1 = 129$ queries to be certain. Write a classical worst-case simulation that finds a function where it takes exactly this many queries. Then run DJ on it and confirm the one-query result.

Hint

Construct a balanced function that agrees with “constant = 0” on the first 128 inputs and outputs 1 on the remaining 128. A deterministic classical algorithm querying in order 0, 1, 2, … sees 128 zeros before finding a 1. DJ still uses 1 query.

What you should take away

• Deutsch-Jozsa separates constant from balanced with one quantum query, where classical deterministic algorithms need $2^{n-1} + 1$.
• Phase kickback converts an oracle that computes $f(x)$ into one that multiplies the input register by $(-1)^{f(x)}$.
• Hadamard-sandwich structure: prepare uniform superposition, oracle, Hadamard back, read out one Fourier coefficient. This pattern repeats in every algorithm in this track.
• The speedup is against deterministic classical algorithms in the query model. Against randomized algorithms the gap shrinks or vanishes.

Next: Bernstein-Vazirani and Simon — the algorithms that take the Deutsch-Jozsa framework and turn it into something you can actually recognize as “learning something.”

---

Weekly dispatch

Quantum, for people who already code.

One serious tutorial per week, plus the industry moves that actually matter. No hype, no hand-waving.

Email Subscribe

Free. Unsubscribe anytime. We will never sell your email.