Deutsch–Jozsa Algorithm

The Deutsch–Jozsa algorithm is the first quantum algorithm that is unconditionally faster than every classical one — provably, exactly, with no caveats about average cases or bounded error. It answers a single yes/no question about a black-box Boolean function $f:\{0,1\}^n\to\{0,1\}$ that comes with a promise: $f$ is either constant (the same value on all $2^n$ inputs) or balanced (value $0$ on exactly half the inputs, $1$ on the other half). A deterministic classical machine, in the worst case, must open the box $2^{n-1}+1$ times before it can be certain which case holds; the quantum algorithm opens it once. That gap — one query versus more than half of an exponentially large table — is the whole point. The circuit is almost embarrassingly short. Prepare $n$ input qubits in $|0\rangle$ and one ancilla in $|1\rangle$ , apply a Hadamard to every qubit, call the oracle $U_f$ once, apply Hadamards again to the $n$ input qubits, and measure them. Everything hangs on two tricks stacked on top of quantum parallelism. The ancilla, put into $|-\rangle$ , converts the oracle's bit-flip $|y\rangle\mapsto|y\oplus f(x)\rangle$ into a pure phase $(-1)^{f(x)}$ on each branch — phase kickback. The final Hadamard layer is the Fourier transform over $\mathbb{Z}_2^n$ , and it reads out whether that phase pattern has a nonzero average — precisely the constant-versus-balanced distinction in disguise. Deutsch–Jozsa is where a student first sees that the power of a quantum computer is not that it evaluates $f$ on all inputs at once — a classical parallel machine could imagine that too — but that it can make the unwanted answers interfere destructively and cancel. It is the direct ancestor of Bernstein–Vazirani, Simon's algorithm, and, through them, Shor's factoring algorithm and the abelian hidden-subgroup framework.

Key takeaways

The Deutsch–Jozsa algorithm decides whether a promised function $f:\{0,1\}^n\to\{0,1\}$ is constant or balanced using exactly one query to a quantum oracle.
Any deterministic classical algorithm needs $2^{n-1}+1$ queries in the worst case, so the separation is exponential in the exact (zero-error) query model.
The engine has three parts: a Hadamard layer builds the uniform superposition, phase kickback turns $f(x)$ into a sign $(-1)^{f(x)}$ , and a second Hadamard layer interferes the signs.
Measuring the input register yields the all-zeros string $0^n$ with probability $1$ if $f$ is constant, and with probability $0$ if $f$ is balanced — a single-shot, deterministic verdict.
Its importance is structural, not applied: a classical randomized algorithm solves the promise in $O(1)$ queries, so the exponential gap lives only in the exact model.
It is the template — Hadamard, oracle, Hadamard, measure — reused by Bernstein–Vazirani, Simon, and ultimately Shor.
Key idea: put the ancilla in $|-\rangle$ so the oracle stamps each branch with $(-1)^{f(x)}$ ; the final Hadamards send that sign pattern to amplitude $\tfrac{1}{2^n}\sum_x(-1)^{f(x)}$ on $|0\rangle^{\otimes n}$ , which is $\pm1$ for constant $f$ and exactly $0$ for balanced $f$ .

The core insight

Put the ancilla in $|-\rangle$ so the oracle stamps each branch with the phase $(-1)^{f(x)}$ ; the final Hadamard transform sends that sign pattern to amplitude $\tfrac{1}{2^n}\sum_x(-1)^{f(x)}$ on $|0\rangle^{\otimes n}$ , which is $\pm1$ (probability $1$ ) when $f$ is constant and $0$ when $f$ is balanced.

Where this lives today

Deutsch–Jozsa was one of the very first quantum algorithms run on real hardware, and it remains a workhorse benchmark. A two-qubit version was demonstrated on a nuclear-magnetic-resonance processor by Jones and Mosca in 1998 and independently by Chuang and collaborators the same year; ion-trap realizations followed, notably Gulde and colleagues in 2003 on a single trapped calcium ion. Because an instance has a known answer, needs only one oracle call, and can be built with either separable or entangling oracles, small- $n$ versions are ideal low-overhead test circuits: they probe gate fidelity, oracle construction, and — by comparing entangling and non-entangling oracles — whether a device's advantage is genuinely coherent. The algorithm is a standard element of superconducting- and photonic-processor demonstrations and of compiler test suites, because a machine that fails it is failing at interference, the most basic quantum resource. Its conceptual influence is larger still: the Hadamard–oracle–Hadamard–measure skeleton is the template for Bernstein–Vazirani, Simon's algorithm, and the abelian hidden-subgroup problem, and the on-ramp to the quantum Fourier transform and Shor's algorithm in essentially every course in the field.

The physical picture

Think of the oracle as a rubber stamp that inks a $+$ or a $-$ onto each computational-basis branch of a superposition according to $f(x)$ . A constant function stamps every branch with the same sign, leaving the uniform superposition unchanged up to a global phase; running the Hadamard layer backwards then reassembles the state exactly onto $|0\rangle^{\otimes n}$ . A balanced function stamps half the branches $+$ and half $-$ , producing a state that is orthogonal to the uniform superposition, so the amplitude that would have landed on $0^n$ cancels to nothing. The whole algorithm is a machine for asking "are all the signs the same?" in a single query, and the answer is read from one place: the probability of measuring all zeros. The first figure is the circuit itself — five moves, one oracle call — with the state written out at each stage so the phase-kickback step and the Fourier readout are visible in the math, not just asserted.

Figure

The Deutsch–Jozsa circuit: n input qubits begin in the all-zeros state and the ancilla in state 1; Hadamards build a uniform superposition, one oracle call U_f kicks back the phase (−1) raised to f(x), a second Hadamard layer interferes the branches, and measuring the inputs returns the string 0ⁿ with probability 1 when f is constant and never when f is balanced

Why does asking "are the signs all equal?" require only one look? Because the Hadamard layer does not inspect the branches one at a time — it sums them. The amplitude that arrives at $0^n$ is literally the average sign $\tfrac{1}{2^n}\sum_x(-1)^{f(x)}$ , the mean of the function's $\pm1$ encoding over its entire domain. A constant function has average $\pm1$ ; a balanced function has average exactly $0$ . The quantum computer evaluates this global average of $2^n$ terms with a single oracle call, whereas a classical machine that must be certain the average is nonzero has to inspect a strict majority of the table. The second figure makes the readout concrete for $n=3$ : the full probability distribution over the $2^3=8$ measurement outcomes, for a constant function beside a specific balanced one.

Figure

Output distribution for n = 3. A constant f puts all probability on the 000 outcome, P = 1. The balanced majority function spreads probability equally over the four odd-parity strings 001, 010, 100, 111 at P = 0.25 each, and gives exactly zero weight to 000 — the vanishing 000 amplitude is the signature that certifies balanced

The core equations

The oracle is the only thing about $f$ the algorithm may touch, and it is a reversible bit-flip: it XORs $f(x)$ into an output register conditioned on the input $x$ . This is the standard way to make any Boolean function unitary, and it costs one query per application.

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

where: $|x\rangle$ — $n$ -qubit input register, $x\in\{0,1\}^n$ ; $|y\rangle$ — single-qubit output (ancilla) register; $\oplus$ — addition modulo $2$ (XOR); $f$ — the unknown Boolean function, promised constant or balanced. Reading it: $U_f$ leaves the input alone and toggles the output iff $f(x)=1$ , so it is its own inverse and unitary. The pivotal trick is to feed the ancilla the state $|-\rangle$ . It is an eigenstate of the bit-flip with eigenvalue $-1$ , so the oracle's action on it is not to flip a bit but to multiply by a sign that depends on $x$ — the information moves out of the output register and into a phase on the input register.

U_f\,|x\rangle|-\rangle=(-1)^{f(x)}\,|x\rangle|-\rangle,\qquad |-\rangle=\tfrac{1}{\sqrt2}\big(|0\rangle-|1\rangle\big) \qquad (2)

where: $|-\rangle$ — the $-1$ eigenstate of the bit-flip, prepared by $H|1\rangle$ ; $(-1)^{f(x)}$ — the eigenvalue, which becomes a relative phase on branch $|x\rangle$ . Reading it: the ancilla comes out unchanged and factorizes off, so from here on we may ignore it and track only the phased input register. Hadamards on the input register manufacture quantum parallelism: from a single basis state $|0\rangle^{\otimes n}$ they build an equal-weight superposition over every one of the $2^n$ inputs at once.

H^{\otimes n}\,|0\rangle^{\otimes n}=\frac{1}{\sqrt{2^{\,n}}}\sum_{x\in\{0,1\}^n}|x\rangle \qquad (3)

where: $H$ — the Hadamard gate, $H|0\rangle=|+\rangle$ , $H|1\rangle=|-\rangle$ ; $2^n$ — the size of the input domain. Reading it: one layer of $n$ gates produces a superposition with exponentially many terms, the raw material interference will act on. Applied to a general basis state, the same layer is the Walsh–Hadamard transform — the Fourier transform over the group $\mathbb{Z}_2^n$ — spreading $|x\rangle$ over all frequency labels $z$ with the character sign $(-1)^{x\cdot z}$ .

H^{\otimes n}\,|x\rangle=\frac{1}{\sqrt{2^{\,n}}}\sum_{z\in\{0,1\}^n}(-1)^{x\cdot z}\,|z\rangle,\qquad x\cdot z=\bigoplus_{i=1}^{n}x_i z_i \qquad (4)

where: $x\cdot z$ — the bitwise inner product mod $2$ ; $z$ — the output (frequency) label after the transform. Reading it: because $H^{\otimes n}$ is its own inverse, this transform is exactly what will convert the phase pattern back into measurable amplitudes. Composing the three input-register operations — Hadamard, phase kickback, Hadamard — gives the state just before measurement. Its amplitude on outcome $z$ is a Fourier coefficient of the sign function $(-1)^{f}$ .

|\psi_{\text{final}}\rangle=\sum_{z\in\{0,1\}^n}\Big[\,\frac{1}{2^{\,n}}\sum_{x\in\{0,1\}^n}(-1)^{f(x)+x\cdot z}\,\Big]\,|z\rangle \qquad (5)

where: the bracket is the amplitude of outcome $z$ , the $z$ -th Walsh–Hadamard coefficient of $(-1)^{f}$ . Reading it: the algorithm has computed the entire Fourier transform of the sign pattern; measurement samples one coefficient's location. Setting $z=0^n$ kills the second sign ( $x\cdot 0=0$ ), so the all-zeros amplitude is exactly the average sign — and under the promise that average is $\pm1$ or $0$ , giving a clean decision rule.

a_{0^n}=\frac{1}{2^{\,n}}\sum_{x\in\{0,1\}^n}(-1)^{f(x)},\qquad \Pr[\,z=0^n\,]=\big|a_{0^n}\big|^2=\begin{cases}1,& f\ \text{constant}\\[2pt]0,& f\ \text{balanced}\end{cases} \qquad (6)

where: $a_{0^n}$ — amplitude of $|0\rangle^{\otimes n}$ ; $\Pr[z=0^n]$ — probability the $n$ -qubit measurement returns all zeros. Reading it: observing $0^n$ certifies constant; observing any nonzero string certifies balanced. Contrast the query counts. The exact quantum cost is one; the worst-case deterministic classical cost is a strict majority of the table plus one — an exponential gap.

Q_{E}(\text{DJ})=1,\qquad D_{\text{cl}}(\text{DJ})=2^{\,n-1}+1 \qquad (7)

where: $Q_E$ — exact (zero-error) quantum query complexity; $D_{\text{cl}}$ — worst-case deterministic classical query complexity. Reading it: for $n=10$ this is $1$ versus $513$ ; the ratio grows without bound.

Derivation AFull evolution through Hadamard, oracle, and Hadamard

The goal is to carry the joint $(n{+}1)$ -qubit register all the way from the standard input $|0\rangle^{\otimes n}|1\rangle$ through the three unitary layers to the final measurement, and to reduce the whole computation to a single number — the amplitude on $0^n$ — showing that it equals $\pm1$ for a constant function and $0$ for a balanced one. This is the master calculation of the article; the phase-kickback identity and the Walsh–Hadamard sum are its two load-bearing steps, and every later result is a corollary of the state written down here.

Step 1. Initialize the register as $|\psi_0\rangle=|0\rangle^{\otimes n}\otimes|1\rangle$ — the $n$ input qubits in the all-zeros state and the ancilla in $|1\rangle$ . Why: putting the ancilla in $|1\rangle$ rather than $|0\rangle$ is the deliberate choice that a Hadamard will turn into $|-\rangle$ , arming the phase-kickback trick.

Step 2. Apply Hadamards to all $n+1$ qubits: $|\psi_1\rangle=\big(\tfrac{1}{\sqrt{2^n}}\sum_x|x\rangle\big)\otimes|-\rangle$ , using $H^{\otimes n}|0\rangle^{\otimes n}=\tfrac{1}{\sqrt{2^n}}\sum_x|x\rangle$ and $H|1\rangle=|-\rangle$ . Why: one layer builds the uniform superposition over all $2^n$ inputs and simultaneously prepares the ancilla eigenstate — parallelism and the kickback ancilla in a single move.

Step 3. Apply the oracle once. By the eigenvalue relation $U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle$ , it stamps each branch with a sign: $|\psi_2\rangle=\big(\tfrac{1}{\sqrt{2^n}}\sum_x(-1)^{f(x)}|x\rangle\big)\otimes|-\rangle$ . Why: this is the only place $f$ enters, and it enters as a phase on the input register — the ancilla is untouched and factorizes off, so it plays no further role.

Step 4. Apply $H^{\otimes n}$ to the input register, using $H^{\otimes n}|x\rangle=\tfrac{1}{\sqrt{2^n}}\sum_z(-1)^{x\cdot z}|z\rangle$ , and collect the coefficient of each $|z\rangle$ : $|\psi_3\rangle=\tfrac{1}{2^n}\sum_z\big(\sum_x(-1)^{f(x)+x\cdot z}\big)|z\rangle$ . Why: the second Hadamard layer is the Fourier transform that converts the phase pattern into amplitudes where interference — constructive or destructive — becomes visible to a measurement.

Step 5. Read off the all-zeros amplitude by setting $z=0^n$ , so $x\cdot z=0$ for every $x$ : $a_{0^n}=\tfrac{1}{2^n}\sum_x(-1)^{f(x)}$ . Why: the outcome $0^n$ is exactly the DC (average) Fourier component of the sign function, and the promise controls that average precisely.

Step 6. Evaluate the constant case: if $f\equiv c$ then all $2^n$ terms are equal, $a_{0^n}=\tfrac{1}{2^n}\cdot 2^n(-1)^c=(-1)^c$ , so $|a_{0^n}|^2=1$ . Why: identical signs add coherently to full amplitude, so the state reassembles exactly onto $0^n$ and the measurement is deterministic.

Step 7. Evaluate the balanced case: with $2^{n-1}$ inputs mapping to each value, $a_{0^n}=\tfrac{1}{2^n}(2^{n-1}-2^{n-1})=0$ , so $0^n$ never occurs and any observed string proves balanced. Why: equal numbers of $+$ and $-$ signs cancel exactly, the hallmark of destructive interference, and it is total precisely because the promise fixes the counts to be equal. *The normalization $\sum_z|a_z|^2=1$ follows directly from the unitarity of $H^{\otimes n}$ . For the $n=3$ majority instance: $a_{000}=0$ and the four odd-parity strings each carry $|a_z|^2=0.25$ , summing to $1$ .*

Go deeper · Derivation B · 2 minThe classical deterministic lower bound

Derivation BThe classical deterministic lower bound

The goal is to prove that a classical algorithm which must answer with certainty has no shortcut: an adversary can keep both answers alive until the algorithm has inspected a strict majority of the table, forcing $2^{n-1}+1$ queries in the worst case. This is the number the single quantum query beats, and the argument is a clean adversary (or fooling-set) argument that fixes the answers only as it is forced to, never revealing more than the algorithm has earned.

Step 1. Suppose a deterministic algorithm has made $k\le 2^{n-1}$ distinct queries and received identical answers, say all $0$ . Why: if it ever saw two different values it could immediately answer "balanced", so the hard case is a run of equal answers, and we bound how long such a run can be uninformative.

Step 2. A constant completion still exists: extend $f$ to the constant- $0$ function, which agrees with every answer given so far. Why: nothing seen rules out "constant", so the algorithm cannot yet commit to "balanced".

Step 3. A balanced completion also exists: since at most $2^{n-1}$ inputs have been assigned $0$ , set the remaining $2^{n-1}-k$ zeros on unqueried inputs and assign $1$ to the other $2^{n-1}$ , which is a valid balanced function agreeing with all $k$ answers — possible exactly when $k\le 2^{n-1}$ . Why: nothing seen rules out "balanced" either, so with both completions live the algorithm has strictly zero information about which case holds.

Step 4. Therefore after any $k\le 2^{n-1}$ equal answers the algorithm cannot decide and must query again. Why: a correct deterministic algorithm may not guess; while two consistent completions of opposite type remain, any answer it gives is wrong on one of them.

Step 5. One more query settles it: after $2^{n-1}+1$ queries, if all answers agree then no balanced function can match (a balanced $f$ produces each value only $2^{n-1}$ times), so $f$ is constant; and if two answers ever differ, $f$ is balanced. Hence $2^{n-1}+1$ is both necessary and sufficient. Why: crossing the halfway mark by one is exactly the threshold at which a constant and a balanced function can no longer agree, which is what makes the bound tight. *As a sanity check at $n=1$ : $2^{0}+1=2$ queries, meaning a classical algorithm must read both $f(0)$ and $f(1)$ to be certain — which is correct.*

Go deeper · Derivation C · 1 minBernstein–Vazirani as the linear special case

Derivation CBernstein–Vazirani as the linear special case

The goal is to show that the very same circuit, applied to a linear oracle $f(x)=a\cdot x$ , does more than answer one bit — it reads out all $n$ bits of the hidden string $a$ in a single query, deterministically. This is the first hint that the Fourier readout carries far more than a constant-versus-balanced verdict, and it turns the "random nonzero string" of a general balanced function into a precisely engineered outcome via the orthogonality of characters.

Step 1. Take $f(x)=a\cdot x=\bigoplus_i a_i x_i$ for a fixed $a\in\{0,1\}^n$ (this $f$ is balanced whenever $a\neq 0^n$ ), and insert it into the general amplitude, combining the two signs with $a\cdot x\oplus x\cdot z=(a\oplus z)\cdot x$ : $a_z=\tfrac{1}{2^n}\sum_x(-1)^{a\cdot x}(-1)^{x\cdot z}=\tfrac{1}{2^n}\sum_x(-1)^{(a\oplus z)\cdot x}$ . Why: linearity lets the two phase exponents merge into a single character indexed by $a\oplus z$ , which is what makes the sum collapse.

Step 2. Apply character orthogonality on $\mathbb{Z}_2^n$ : $\tfrac{1}{2^n}\sum_x(-1)^{w\cdot x}=\delta_{w,0}$ , so with $w=a\oplus z$ the amplitude is $a_z=\delta_{z,a}$ . Why: a nontrivial character sums to zero over the group and a trivial one sums to $1$ , so all amplitude concentrates on the single label $z=a$ .

Step 3. Conclude $\Pr[z=a]=1$ : one oracle query reveals every bit of $a$ at once, versus $n$ classical queries — one per basis vector $e_i$ — needed to read the bits one at a time. Why: the outcome is not a random balanced-certifying string but the hidden vector itself, an exact $n$ -to- $1$ query saving that generalizes to Simon's exponential separation. *This is the Deutsch–Jozsa circuit specialized by the Walsh–Hadamard orthogonality relation. For example, at $n=2$ with $a=11$ : the circuit output is $z=11$ with probability $1$ .*

Limiting cases

The algorithm has one moving part — the promise on $f$ — and its behaviour at the edges shows exactly where the advantage lives and where it evaporates.

Case	Result	Meaning
$n=1$ (Deutsch)	$a_0=\tfrac{1}{2}\sum_{x\in\{0,1\}}(-1)^{f(x)}$	Reduces to Deutsch's algorithm: one query distinguishes $f(0)=f(1)$ (constant) from $f(0)\neq f(1)$ (balanced).
Constant $f$	$\Pr[\,0^n\,]=\big\|\tfrac{1}{2^n}\sum_x(-1)^{f(x)}\big\|^2=1$	All signs equal, average $\pm1$ ; the state reassembles onto $0^n$ and the measurement is deterministic.
Balanced $f$	$\Pr[\,0^n\,]=\big\|\tfrac{1}{2^n}\sum_x(-1)^{f(x)}\big\|^2=0$	Equal $+$ and $-$ cancel; $0^n$ never appears, so any observed string certifies balanced.
Linear $f(x)=a\cdot x$	$\Pr[\,z=a\,]=1$	Bernstein–Vazirani: the hidden string $a$ is read out whole in one query.
Classical randomized	$\Pr[\text{error after }k{+}1\text{ queries}]\le 2^{-k}$	A few random samples decide the promise with tiny error; the exponential gap is exact-model only.
No promise	$f$ arbitrary	Without constant-or-balanced, one query reads only the average sign, which is no longer decisive.

Common trapDeutsch–Jozsa proves quantum computers beat classical ones in practice

It does not. The exponential separation is real but lives entirely in the exact (zero-error) query model, where the classical machine is forbidden to make any mistake. Allow it a vanishing error probability and the advantage collapses: a classical algorithm that queries $f$ at a handful of random inputs and answers "balanced" the moment it sees two different values is wrong only when a balanced function happens to agree on all sampled points, which occurs with probability at most $2^{-k}$ after $k+1$ samples. So $O(1)$ classical queries solve the promise for any fixed confidence, and there is no super-polynomial bounded-error speedup. The correct lesson of Deutsch–Jozsa is conceptual — it is the first clean proof that quantum interference, not brute parallel evaluation, is the resource — not a claim about practical dominance. The first problem with a genuine exponential bounded-error separation is Simon's, which is what actually pointed the way to Shor.

Worked examples

1 · Tracing the full circuit for n = 2 (fully worked)

Run the algorithm by hand on two qubits for a constant function $f\equiv 1$ and for the balanced parity function $f(x)=x_0\oplus x_1$ . Track every amplitude.

Step 1. Build the superposition. After the input Hadamards the register is $\tfrac{1}{2}\big(|00\rangle+|01\rangle+|10\rangle+|11\rangle\big)$ with the ancilla in $|-\rangle$ ; the four branches carry equal amplitude $\tfrac12$ .

Step 2. Kick back the phase, constant case. For $f\equiv 1$ every branch gets the sign $(-1)^1=-1$ , giving $-\tfrac{1}{2}\big(|00\rangle+|01\rangle+|10\rangle+|11\rangle\big)$ . This is $-1$ times the uniform state, so $H^{\otimes 2}$ returns it to $-|00\rangle$ . Measuring gives $\mathbf{00}$ with probability 1 — the global sign is unobservable, and $0^n$ certifies constant.

Step 3. Kick back the phase, balanced case. For $f(x)=x_0\oplus x_1$ the signs are $+,-,-,+$ on $00,01,10,11$ , giving $\tfrac{1}{2}\big(|00\rangle-|01\rangle-|10\rangle+|11\rangle\big)$ . This factorizes as $|-\rangle\otimes|-\rangle$ , and since $H|-\rangle=|1\rangle$ , the second Hadamard layer sends it to $|11\rangle$ . Measuring gives $\mathbf{11}$ with probability 1 — a nonzero string, certifying balanced.

Step 4. Read the extra structure. The outcome $11$ is not accidental: parity is the linear function $f(x)=a\cdot x$ with $a=11$ , so by the Bernstein–Vazirani reduction the circuit returns $z=a=11$ deterministically. Constant $\to 00$ ; balanced parity $\to 11=a$ ; both in a single query.

2 · A non-linear balanced function, n = 3 (fully worked)

Take the majority function on three bits, $f(x)=1$ iff at least two of the bits are $1$ . It is balanced (four inputs give $1$ ). Find the full measurement distribution and show it certifies balanced.

Step 1. Encode the signs. The values $(-1)^{f(x)}$ over $x=000,\dots,111$ are $+,+,+,-,+,-,-,-$ : the four inputs of weight $\ge 2$ (namely $011,101,110,111$ ) carry $-1$ , the rest carry $+1$ .

Step 2. Check the all-zeros amplitude. $a_{000}=\tfrac{1}{8}\sum_x(-1)^{f(x)}=\tfrac{1}{8}(4-4)=\mathbf{0}$ , so $000$ is never observed — the balanced certificate. This is the destructive interference of Step 7 of the master derivation, realized on a concrete non-linear function.

Step 3. Compute the rest of the spectrum. Evaluating $a_z=\tfrac{1}{8}\sum_x(-1)^{f(x)+x\cdot z}$ for every $z$ gives amplitude $+\tfrac12$ on $z=001,010,100$ , amplitude $-\tfrac12$ on $z=111$ , and $0$ on $z=000,011,101,110$ . The nonzero outcomes are exactly the odd-parity strings.

Step 4. Read the distribution. The measurement lands on one of $\{001,010,100,111\}$ , each with probability $|{\pm}\tfrac12|^2=0.25$ , summing to $1$ . Any of the four proves balanced, but which one is essentially random — unlike the linear case, a general balanced function leaves no further guaranteed structure in the outcome. $P(000)=0$ certifies balanced; the verdict needs one query, where a classical worst case needs $2^{2}+1=5$ .

3 · How large the classical bill gets

Put a number on the separation for $n=10$ and $n=30$ .

Step 1. Quantum cost is fixed at $Q_E=1$ query regardless of $n$ .

Step 2. Classical worst-case cost is $D_{\text{cl}}=2^{n-1}+1$ : for $n=10$ that is $2^{9}+1=\mathbf{513}$ queries, and for $n=30$ it is $2^{29}+1\approx\mathbf{5.4\times10^{8}}$ queries — over half a billion evaluations to be certain, versus one. The gap is exactly $2^{n-1}+1$ to $1$ , and it is unbounded.

Physics of the portrait

The Deutsch–Jozsa algorithm carries two names, but it grew from one radical idea: that the laws of computation are laws of physics, and a machine built on quantum mechanics can therefore do things no classical machine can. That idea, and the first algorithm to prove it, belong to David Deutsch.

Origins · 1 minDavid Deutsch and how this was discovered

David Deutsch

born 1953, Haifa · founder of the quantum algorithm and the universal quantum computer

David Deutsch is the physicist who turned quantum computing from a speculation into a theory. In a 1985 paper he wrote down the universal quantum computer — a quantum generalization of the Turing machine — and argued for a physical Church–Turing principle: every finitely realizable physical system can be simulated by a universal computing machine operating by finite means. To show the model was not merely a re-description of the classical one, he exhibited a problem it could solve faster, the single-bit "Deutsch problem", using interference between the two branches of a superposed query. That original 1985 algorithm was probabilistic — it succeeded only half the time — a blemish reflecting how new the ideas were. In 1992, with the mathematician Richard Jozsa, Deutsch generalized it to $n$ bits and the constant-versus-balanced promise, giving the first exponential quantum–classical separation in the exact query model. The circuit was sharpened to its modern deterministic single-query form by Cleve, Ekert, Macchiavello and Mosca in 1998, who isolated phase kickback as the mechanism. Deutsch's deeper commitment was always to the physics: a lifelong champion of the many-worlds interpretation, he argued that the speedup of quantum algorithms is best understood as computation distributed across the branches of the wavefunction. The line from his 1985 machine runs through Bernstein–Vazirani, Simon, and Shor to the whole field.

History

1985

— Deutsch defines the universal quantum computer and gives the first quantum algorithm for the single-bit problem

1992

— Deutsch and Jozsa generalize to n bits, proving an exact-query exponential separation

1993

— Bernstein and Vazirani found quantum complexity theory on the hidden-linear variant

1994

— Simon lifts the separation to exponential even with bounded error, seeding Shor's algorithm

1998

— Cleve, Ekert, Macchiavello and Mosca recast the algorithm as a single exact query via phase kickback

Going further

Texts. Nielsen and Chuang, Quantum Computation and Quantum Information, §1.4.3–1.4.4 and Box 1.2 (Deutsch and Deutsch–Jozsa) · Kaye, Laflamme and Mosca, An Introduction to Quantum Computing, Ch. 6 · Mermin, Quantum Computer Science, Ch. 2 · Preskill, Lecture Notes for Physics 219, Ch. 6 · Kitaev, Shen and Vyalyi, Classical and Quantum Computation · Watrous, quantum-complexity lecture notes (query model).

Primary sources. Deutsch, Quantum theory, the Church–Turing principle and the universal quantum computer, Proc. R. Soc. Lond. A 400, 97 (1985) · Deutsch and Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. Lond. A 439, 553 (1992) · Cleve, Ekert, Macchiavello and Mosca, Quantum algorithms revisited, Proc. R. Soc. Lond. A 454, 339 (1998). Key identities to keep in mind: the phase-kickback relation $U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle$ follows by direct expansion of $|-\rangle$ ; the all-zeros amplitude $a_{0^n}=2^{-n}\sum_x(-1)^{f(x)}$ equals $(-1)^c$ for constant $f$ and $0$ for balanced $f$ ; the deterministic classical bound $2^{n-1}+1$ follows from the adversary argument; the Bernstein–Vazirani reduction rests on character orthogonality $2^{-n}\sum_x(-1)^{(a\oplus z)\cdot x}=\delta_{z,a}$ ; and the $n=3$ majority spectrum gives $a_{000}=0$ with the odd-parity strings at $|a_z|^2=0.25$ each. Every number appearing here — $2^n$ , $2^{n-1}+1$ , probabilities $0$ and $1$ , $0.25$ — is an exact combinatorial or algebraic value, not an empirical constant.

Prerequisites. Quantum Parallelism and the Oracle Model · Deutsch's Algorithm. Leads to. Bernstein–Vazirani Algorithm · Simon's Algorithm · Hidden Subgroup Problem · Quantum Fourier Transform.

Ask the tutor: Ask me to trace the circuit on any oracle you choose — constant, balanced, or linear — and watch the phase kickback and the final Fourier interference decide the answer in a single query.

Why is the promise that f is constant or balanced essential?

The single-query algorithm reads exactly one number about $f$ : the average sign $\tfrac{1}{2^n}\sum_x(-1)^{f(x)}$ , delivered as the amplitude on the all-zeros outcome. For an arbitrary function this average can take many intermediate values, and the all-zeros probability $|a_{0^n}|^2$ then tells you nothing decisive. The promise collapses the possibilities to two extremes — average exactly $\pm1$ (constant) or exactly $0$ (balanced) — so that one bit of information, whether or not $0^n$ was observed, distinguishes them. Remove the promise and you are asking one query to resolve a question that contains more than one bit of information, which no measurement of a single amplitude can do.

What does phase kickback actually do, and what breaks if the ancilla is |0⟩ instead of |−⟩?

Phase kickback exploits the fact that $|-\rangle$ is an eigenstate of the bit-flip: applying $U_f$ , which XORs $f(x)$ into the ancilla, multiplies the branch by the eigenvalue $(-1)^{f(x)}$ and leaves the ancilla unchanged. The information about $f$ is thereby moved from the ancilla's value into a relative phase on the input register, exactly where Hadamard interference can act on it. Prepare the ancilla in $|0\rangle$ instead and the oracle entangles it with $|f(x)\rangle$ in the computational basis, producing no useful relative phase. The final Hadamards then return an uninformative mixture and the constant-versus-balanced distinction is lost — you would learn at most $f$ at one random point, no better than a single classical query.

If a random classical algorithm solves it in a few queries, why do we care about Deutsch–Jozsa at all?

Because the point was never practical speed on this toy problem — it was a proof of principle. Deutsch–Jozsa was the first demonstration that a quantum computer can be provably exponentially faster than any classical one in a clean, fully specified model (exact, deterministic query complexity), and it isolated interference as the mechanism, distinct from mere parallel evaluation. That clarity is what mattered historically: it convinced researchers the model had real power and set the template that Bernstein–Vazirani and Simon refined into a genuine bounded-error separation, which in turn led Shor to factoring. Judged as a practical algorithm it is uninteresting; judged as the hinge between "quantum computers are a curiosity" and "quantum computers can be exponentially better", it is foundational.

Does observing a particular nonzero string z tell me anything beyond "balanced"?

For a general balanced function, no. Any $z\neq 0^n$ certifies balanced, because the all-zeros amplitude vanishes only then, but the specific $z$ you obtain is a random sample from the Fourier support of $(-1)^{f(x)}$ and carries no further guaranteed structure — the $n=3$ majority example scatters the outcome uniformly over four strings. The exception is the linear case $f(x)=a\cdot x$ , where character orthogonality concentrates all amplitude on the single string $z=a$ . There the "random balanced string" becomes a deterministic readout of the hidden vector $a$ , which is exactly the Bernstein–Vazirani algorithm — the same circuit extracting $n$ bits instead of one.

How can one query beat 2ⁿ⁻¹ + 1 — isn't the quantum computer also just evaluating f?

It evaluates $f$ once, in superposition, but the speed does not come from that. If you tried to read out $f(x)$ for all $x$ from the post-oracle state you would fail — measurement gives one random $x$ and one value, no better than classical. The advantage comes entirely from the second Hadamard layer, which makes the $2^n$ phased branches interfere: for a constant function they add coherently onto $0^n$ , for a balanced function they cancel there completely. The machine is not extracting $2^n$ answers, it is computing a single global property — the average sign — by arranging for all the individual answers to interfere. That is why "quantum parallelism" alone is a misleading slogan: parallel evaluation is free and useless without the interference that follows.

How does Deutsch–Jozsa relate to Bernstein–Vazirani, Simon, and Shor?

They are one family, built on the identical skeleton: Hadamard, oracle (via phase kickback), Hadamard, measure. Deutsch–Jozsa asks a one-bit question. Bernstein–Vazirani specializes the oracle to a linear function and reads out the whole hidden string $a$ in one query. Simon's algorithm hides a period $s$ in a two-to-one function and achieves an exponential separation that survives bounded error — the first problem to do so. Simon's structure is what suggested that a Fourier transform over $\mathbb{Z}_N$ rather than $\mathbb{Z}_2^n$ could expose the period of modular exponentiation, which is exactly Shor's factoring algorithm. All four are instances of the abelian hidden-subgroup problem, solved by transforming to the Fourier basis and sampling; Deutsch–Jozsa is the simplest member and the one where the mechanism is most transparent.