In short

Deutsch-Jozsa (1992) is the n-bit generalisation of Deutsch's algorithm. You are given a function f: \{0,1\}^n \to \{0,1\} promised to be either constant (same value on every input) or balanced (exactly half the inputs map to 0 and half to 1). A deterministic classical algorithm may need up to 2^{n-1}+1 queries in the worst case to decide which. A quantum algorithm needs exactly one query, regardless of n. The recipe is short: Hadamard everything, query the oracle, Hadamard everything, measure the input register. If the outcome is |00\ldots 0\rangle, f is constant; otherwise, f is balanced — no ambiguity. This is the first known algorithm with an exponential quantum-classical separation, though the problem itself is contrived. The technique — phase kickback plus Hadamard interference — is the real contribution, and it scales up into Bernstein-Vazirani, Simon, and Shor.

Imagine you have been handed a function f that takes 20-bit inputs and produces one output bit. There are 2^{20} \approx 10^6 possible inputs. You are told, on good authority, that f is either constant — it returns the same bit on every input — or balanced — exactly half of the 10^6 inputs return 0 and the other half return 1. Your job is to determine which.

You start querying f. The first query returns 0. You query again — also 0. Again — 0. After 500{,}000 queries you have seen nothing but 0s. Is f constant? You do not know: it might be, or it might be a balanced function that happens to send the first half a million inputs to 0 and the second half a million to 1. The next query could be 1, and the answer is immediately "balanced". Or the next query could be 0, and you still do not know. To be certain, classically, you may need to query 2^{19} + 1 = 524{,}289 inputs.

A quantum computer with access to f via an oracle does the job in one query. One. Regardless of how big n is — 20, 2000, 2{,}000{,}000. This is the exponential query-complexity separation the Deutsch-Jozsa algorithm (David Deutsch and Richard Jozsa, 1992) was built to demonstrate.

The problem is admittedly contrived — a uniform promise, no practical application — and in the classical randomised model the separation collapses (you can get the right answer with very high probability in only a few random queries). So Deutsch-Jozsa does not, on its own, prove anything directly useful. But it does demonstrate, for the first time in the history of quantum computing, that quantum mechanics can produce an exponential separation for a natural-sounding problem. And the technique — Hadamard the input, phase-kickback the oracle, Hadamard again, measure — is the template for every quantum algorithm that followed. Bernstein-Vazirani, Simon, Shor, and Grover are all variations on this one shape.

The problem, stated carefully

Given a function f: \{0,1\}^n \to \{0,1\}, with the promise that f is either:

Decide which. You are not required to determine c in the constant case or to find which inputs go where in the balanced case — only to distinguish the two possibilities.

Why the promise matters: a function that is neither constant nor balanced (say, outputs 0 on 60\% of inputs and 1 on 40\%) is not allowed as input to the algorithm. The algorithm's behaviour on such a function is not defined. This is what makes Deutsch-Jozsa a promise problem — the input is guaranteed to satisfy one of two possibilities, and the algorithm only needs to tell them apart.

The classical lower bound — 2^{n-1}+1 queries in the worst case

Before seeing the quantum algorithm, pin down the classical baseline.

Claim. Any deterministic classical algorithm that solves Deutsch-Jozsa with certainty must, in the worst case, query f on at least 2^{n-1}+1 different inputs.

Proof sketch. Suppose you have queried f on 2^{n-1} distinct inputs and received all the same output b. Can you conclude anything? Not with certainty. Two possibilities remain consistent with your data:

  1. f is constant with value b — every unqueried input will also return b.
  2. f is balanced, with the 2^{n-1} inputs you queried all happening to lie in the "output b" half, and the other 2^{n-1} inputs all outputting 1 - b.

Until you make one more query — the (2^{n-1}+1)-th — you cannot rule out either possibility. If that extra query returns b, then f cannot be balanced (because a balanced function has exactly 2^{n-1} inputs returning b; if you have seen 2^{n-1}+1 of them, that is too many). If the extra query returns 1-b, then f cannot be constant. Either way, you are now certain.

Why the worst case is sharp: the adversary can always arrange for the first 2^{n-1} queries to return the same value, whether the function is truly constant or secretly balanced. You cannot get lucky, because "luck" requires knowing which inputs to query, and the adversary controls the function. So 2^{n-1}+1 queries is both necessary and sufficient — there is a matching upper-bound algorithm: query 2^{n-1}+1 distinct inputs and check whether they are all the same.

For n = 20, this is 524{,}289 queries. For n = 30, roughly a billion. Classical determinism cannot do better. Classical randomisation can — a few random queries suffice to get the right answer with high probability, and we will see below that this is why the "exponential separation" is specifically a separation against deterministic classical algorithms, not a complete dismissal of classical methods.

Classical lower bound for Deutsch-JozsaA bar chart showing classical versus quantum query count as a function of n. Classical bars grow exponentially as 2 to the n minus 1 plus 1; the quantum bar stays at 1 throughout. Values plotted for n = 2, 4, 6, 8, 10.number of input bits nqueries (log scale)n=2n=4n=6n=8n=10393312951311111classical (deterministic)quantum
Classical deterministic worst-case queries grow as $2^{n-1}+1$ — roughly half of all inputs. Quantum stays flat at $1$ query regardless of $n$. This is the exponential gap.

The algorithm — four lines

The quantum algorithm uses n "input" qubits (call this register X) and one "target" qubit. The oracle is the standard reversible encoding:

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

where x is an n-bit string, y is a single bit, and \oplus is XOR. This is the same oracle model as Deutsch's algorithm — just with an n-bit input instead of one bit.

The full algorithm:

  1. Initialise the input register to |0\rangle^{\otimes n} and the target to |1\rangle.
  2. Hadamard every qubit: apply H^{\otimes n} to the input register and H to the target.
  3. Query the oracle: apply U_f once.
  4. Hadamard the input register again: apply H^{\otimes n} to it. (The target is left alone — you will not measure it.)
  5. Measure the input register in the computational basis. Call the outcome y \in \{0,1\}^n.

Decision rule. If y = 0^n = 00\ldots 0, declare f constant. Otherwise, declare f balanced.

That is the entire algorithm. Four circuit layers and one measurement. You will now see why it works.

The Deutsch-Jozsa circuitA quantum circuit with n parallel input wires labelled ket 0, plus one target wire labelled ket 1. A Hadamard gate H is applied to each input wire, and a Hadamard is also applied to the target. Then a box labelled U_f spans all n plus one wires. Then Hadamards are applied to the input wires only (not the target). Then a meter symbol measures each input wire.|0⟩|0⟩|0⟩|1⟩⋮⋮⋮HHHHU_fHHHH^⊗n + Horacle (1 query)H^⊗nmeasure input
The Deutsch-Jozsa circuit. Hadamards on every qubit before the oracle; oracle query once; Hadamards on the input register after; measure the input register. The target is not measured.

Why it works — the walk-through

Track the state through each step. This is the core of the analysis.

After step 1 — initialisation. The state is |0\rangle^{\otimes n}|1\rangle.

After step 2 — Hadamards everywhere. Hadamard on |0\rangle gives |+\rangle, and an n-fold tensor of |+\rangle can be written as an equal superposition over all 2^n input strings:

H^{\otimes n}|0\rangle^{\otimes n} \;=\; \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle.

Hadamard on |1\rangle gives |-\rangle. So the joint state is

\frac{1}{\sqrt{2^n}} \sum_{x} |x\rangle \otimes |-\rangle.

Why this is the magic starting configuration: the input register is now in an equal superposition over every possible input to f, and the target is in |-\rangle — the eigenstate that makes phase kickback happen when the oracle queries it.

After step 3 — oracle query. You saw in the phase-kickback chapter that U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle, because |-\rangle is an eigenstate of the XOR-flip operation with eigenvalue (-1)^{f(x)} depending on whether the oracle fires. Applying this to every term in the superposition:

U_f\,\frac{1}{\sqrt{2^n}} \sum_{x} |x\rangle|-\rangle \;=\; \frac{1}{\sqrt{2^n}} \sum_{x} (-1)^{f(x)}|x\rangle \otimes |-\rangle.

The oracle has written the entire function f into the phase pattern of the input register: every basis state |x\rangle now carries a \pm 1 factor in front of it, with the sign determined by f(x). After one oracle query, the input register holds all 2^n function values — as phases.

Why this does not violate information limits: you have not learned the values of f yet. A measurement of the input register at this stage would give a random x and tell you nothing about f (each |x\rangle has the same probability 1/2^n because |{(-1)^{f(x)}}|^2 = 1). The sign information is real but hidden; it takes the next Hadamard to convert it into something measurable.

After step 4 — Hadamards on the input register. Apply H^{\otimes n} to the phase-encoded state. The key identity — proved in the Hadamard chapter — is that for any n-bit string x,

H^{\otimes n}|x\rangle \;=\; \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle,

where x \cdot y = x_1 y_1 + x_2 y_2 + \cdots + x_n y_n \pmod 2 is the bitwise inner product mod 2.

Apply this to each term in the sum:

H^{\otimes n}\,\frac{1}{\sqrt{2^n}} \sum_{x} (-1)^{f(x)}|x\rangle \;=\; \frac{1}{2^n} \sum_{x,y} (-1)^{f(x) + x \cdot y} |y\rangle.

Regroup by the outcome y:

=\; \sum_{y} \left[\frac{1}{2^n}\sum_{x} (-1)^{f(x) + x \cdot y}\right] |y\rangle.

The amplitude of a specific measurement outcome |y\rangle is the bracketed expression:

\alpha_y \;=\; \frac{1}{2^n}\sum_{x} (-1)^{f(x) + x \cdot y}.

Why this sum is the whole algorithm: the algorithm's entire power is captured in this formula. It says the amplitude of outcome y is an average (with signs) of all 2^n function values, weighted by the parity of the inner product x \cdot y. The Hadamard transforms the phase pattern into an interference pattern, and the outcome probabilities are what that interference produces.

Step 5 — measurement. The probability of measuring a specific y is |\alpha_y|^2. Focus on y = 0^n = 00\ldots 0. Then x \cdot y = 0 for every x, so (-1)^{x \cdot y} = 1 always:

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

This is where the constant-vs-balanced distinction lands.

If f is constant, (-1)^{f(x)} is the same value \pm 1 for every x. The sum is \pm 2^n, and the amplitude is \pm 1. The probability of measuring |0^n\rangle is |\pm 1|^2 = 1. You are certain to see all zeros.

If f is balanced, half of the 2^n terms contribute +1 and the other half contribute -1. The sum is 0. The amplitude is 0. The probability of measuring |0^n\rangle is exactly 0. You will never see all zeros; the outcome is some other y \ne 0^n.

That is the punch line. The |0^n\rangle outcome is a perfect indicator: it occurs with certainty if constant, and never if balanced. One oracle query, one measurement, one certain answer.

The interference pattern at the |0…0⟩ outcomeTwo bar-chart style panels. Left panel, constant f: four bars all at the same height, labelled 2 to the n over 2 to the n. They add constructively to give amplitude plus or minus 1 on outcome ket 0 to the n. Right panel, balanced f: four bars alternating plus and minus the same height, adding to zero amplitude on outcome ket 0 to the n.constant f — constructive+1+1+1+1sum = 2^n → |α|² = 1every term adds, amplitude 1outcome |0…0⟩ is certainbalanced f — destructive+1−1+1−1sum = 0 → |α|² = 0+1s and −1s cancel exactlyoutcome |0…0⟩ never happens
The amplitude of the $|0^n\rangle$ outcome is the average of $(-1)^{f(x)}$ over all inputs. For constant $f$, every term is the same sign and they add constructively to $\pm 1$. For balanced $f$, half are $+1$ and half are $-1$ and they cancel to $0$. Interference is the mechanism; the oracle is queried only once.

The worked examples

Example 1: $n = 2$, constant $f(x) = 0$

Take n = 2, so there are 4 inputs: 00, 01, 10, 11. Let f(x) = 0 for every x — a constant function.

Step 1 — initialise. The state is |00\rangle|1\rangle.

Step 2 — Hadamards everywhere. H^{\otimes 2}|00\rangle = \tfrac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle), and H|1\rangle = |-\rangle. Joint state:

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

Step 3 — oracle query. Since f(x) = 0 for every x, (-1)^{f(x)} = +1 for every x. The oracle does effectively nothing:

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

Why the oracle is a no-op here: for constant-zero f, the XOR with f(x) = 0 flips no bits, so the target state |-\rangle passes through unchanged and picks up no sign on any branch. For constant-one f, every branch would pick up -1, giving an overall global phase of -1 — which is invisible, so the analysis is the same.

Step 4 — Hadamard the input register. Apply H^{\otimes 2} to the equal superposition. You have already computed that H^{\otimes 2} on the equal superposition is |00\rangle: a Hadamard applied to the |+\rangle^{\otimes n} state returns to |0\rangle^{\otimes n}. So the input register is now |00\rangle exactly.

\text{Input register} = |00\rangle = |0^n\rangle.

Step 5 — measurement. The input register is |00\rangle with probability 1. You measure, you see 00, you declare f constant. Correct.

Deutsch-Jozsa n=2 constantA bar chart with four bars for outcomes 00, 01, 10, 11. The 00 bar reaches up to probability 1; the other three bars are at zero. Annotation: constant f, always measures all zeros.000110111.00outcome on input registerp = 1constant f ⇒measure |00⟩ with certainty
For constant $f$ at $n=2$, the input register lands on $|00\rangle$ with probability $1$. The $|0^n\rangle$ outcome is the unique signature of a constant function.

What this shows. The constant case is the simplest: the oracle does nothing to the phase pattern (or stamps a global phase, which is invisible), so the second round of Hadamards just undoes the first round, returning the input register to |0^n\rangle. A measurement returns all zeros with certainty.

Example 2: $n = 2$, balanced $f(x_1 x_2) = x_1 \oplus x_2$ (parity)

Take n = 2 and f(x_1 x_2) = x_1 \oplus x_2 — the parity function. This is balanced because two of the four inputs (00, 11) return 0 and the other two (01, 10) return 1.

Step 1 — initialise. State is |00\rangle|1\rangle.

Step 2 — Hadamards. Same as before:

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

Step 3 — oracle query. Now f gives different values: f(00) = 0, f(01) = 1, f(10) = 1, f(11) = 0. The phase kickback multiplies each |x\rangle by (-1)^{f(x)}:

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

Why the pattern has two plus and two minus: the parity function outputs 0 for even-parity inputs (00 and 11) and 1 for odd-parity inputs (01 and 10). That produces exactly the plus-plus-minus-minus pattern above, with plus on even-parity strings and minus on odd-parity strings.

Step 4 — Hadamard the input register. Apply H^{\otimes 2} to the phase-encoded state. Use the identity H^{\otimes 2}|x\rangle = \tfrac{1}{2}\sum_{y}(-1)^{x\cdot y}|y\rangle term by term, and sum:

H^{\otimes 2}\,\tfrac{1}{2}\bigl(|00\rangle - |01\rangle - |10\rangle + |11\rangle\bigr) \;=\; \tfrac{1}{4}\sum_{y} \underbrace{\bigl[(-1)^{00\cdot y} - (-1)^{01\cdot y} - (-1)^{10\cdot y} + (-1)^{11\cdot y}\bigr]}_{A_y}|y\rangle.

Compute A_y for each y \in \{00, 01, 10, 11\}:

  • y = 00: A_{00} = 1 - 1 - 1 + 1 = 0.
  • y = 01: A_{01} = 1 - (-1) - 1 + (-1) = 0.
  • y = 10: A_{10} = 1 - 1 - (-1) + (-1) = 0.
  • y = 11: A_{11} = 1 - (-1) - (-1) + 1 = 4.

So the amplitude of |00\rangle is 0, of |01\rangle is 0, of |10\rangle is 0, and of |11\rangle is 4/4 = 1. The input register is |11\rangle with probability 1.

Step 5 — measurement. Measure, see 11 \ne 00, declare f balanced. Correct.

Deutsch-Jozsa n=2 balanced parityA bar chart with four bars for outcomes 00, 01, 10, 11. The 11 bar reaches up to probability 1; the others are zero. Annotation: balanced f (parity), outcome never 00.000110111.00outcome on input registerp = 1balanced f (parity) ⇒|00⟩ never measured
For $f(x) = x_1 \oplus x_2$ (parity, balanced) at $n=2$, the input register lands on $|11\rangle$ with certainty. The outcome is not $|00\rangle$, which is the signal that $f$ is balanced — the specific non-zero outcome depends on which balanced function it is.

What this shows. For this particular balanced function (parity), the outcome is specifically |11\rangle. A different balanced function would give a different non-zero outcome. You cannot reconstruct which balanced function f is — the algorithm is not a function-identification algorithm — but you can tell it apart from any constant function, in one query, with certainty. The interference pattern on the |00\rangle outcome is the single bit of information the algorithm returns.

Common confusions

Going deeper

You have the algorithm, the proof, and the worked examples. The rest of this section unpacks three more layers: the formal query-complexity gap (deterministic vs randomised classical), the algorithmic family that Deutsch-Jozsa sits at the start of (Bernstein-Vazirani, Simon, Shor), and an honest assessment of what the exponential separation does and does not prove about quantum computing.

Exact query complexity — the formal theorem

Deterministic classical. The minimum number of queries needed to solve Deutsch-Jozsa with certainty is exactly 2^{n-1}+1 in the worst case. Both directions: the upper bound is the trivial algorithm (query that many distinct inputs and check if they are all the same); the lower bound is the adversary argument sketched earlier. This is a tight result.

Randomised classical. With bounded error \epsilon, you can solve Deutsch-Jozsa with O(\log(1/\epsilon)) queries — a constant, independent of n. The argument is a simple probability calculation: query k random inputs; if all give the same value, decide "constant"; otherwise "balanced." For a balanced f, the probability of all-same is 2 \cdot 2^{-k}, so k = \log_2(2/\epsilon) queries suffice to achieve error \epsilon. For constant f, you are always correct.

Quantum. Exactly 1 query, with zero error — the Deutsch-Jozsa algorithm you just saw.

The exponential separation is therefore specifically against deterministic classical, not against randomised classical. This is a subtle but important point: for a long time in the 1990s, researchers debated whether Deutsch-Jozsa's gap had "real" content or was a deterministic-vs-randomised artefact. The answer is that the gap is genuine in the deterministic model, and the real payoff for quantum computing comes from later algorithms (Simon, Shor) whose gaps hold even against randomised classical computation.

The Deutsch-Jozsa → Bernstein-Vazirani → Simon → Shor progression

Deutsch-Jozsa is the first member of a family of oracle algorithms that get progressively more interesting.

Bernstein-Vazirani (1993). The oracle computes f(x) = s \cdot x \pmod 2 for a hidden n-bit string s — an inner-product function. The goal: find s. Classically: n queries (one to learn each bit). Quantumly: exactly one query, using the same Hadamard-oracle-Hadamard structure as Deutsch-Jozsa. Linear speedup, but a concrete algorithmic win — you actually learn something useful (the string s).

Simon (1994). The oracle promises there is a hidden n-bit period s such that f(x) = f(y) iff x \oplus y \in \{0, s\} — a "periodic" function on the Boolean hypercube. The goal: find s. Classically: \Omega(2^{n/2}) queries. Quantumly: O(n) queries, giving an exponential separation even against randomised classical algorithms. Simon's algorithm was the first algorithm with a genuine exponential separation in the randomised model and inspired Shor's approach.

Shor (1994). Shor's factoring algorithm uses quantum phase estimation on a modular-multiplication oracle to find the order of an element modulo N — a classically hard sub-problem equivalent to factoring. Exponential separation against randomised classical, genuinely useful (breaks RSA).

The progression shows the same Hadamard-oracle-interference shape getting applied to more sophisticated problems, with the separation becoming more robust and the problem becoming more consequential at each step. Deutsch-Jozsa is the pedagogical entry point.

The honest assessment — what the exponential separation does and does not prove

Deutsch-Jozsa proves: there exists a computational problem (decide constant vs balanced under a promise) for which quantum algorithms have an exponential deterministic-query advantage over classical algorithms.

Deutsch-Jozsa does not prove:

What Deutsch-Jozsa does demonstrate, beyond the narrow deterministic separation, is the general shape of quantum algorithms: prepare a superposition (Hadamards), query an oracle once, apply another transformation (Hadamards), measure. This shape scales to Bernstein-Vazirani, Simon, and ultimately Shor. Every quantum algorithm that achieves a superpolynomial speedup uses some version of this template — and Deutsch-Jozsa is where the template was first written down.

Pedagogy vs practice — why Deutsch-Jozsa is in every textbook

Despite having no practical application, Deutsch-Jozsa is the most-taught quantum algorithm at the introductory level. The reason: it is the smallest algorithm that demonstrates all of the quintessentially quantum moves at once. Superposition (Hadamards), oracle query, phase kickback, interference, and measurement — all five ingredients, arranged in the simplest possible way, with a clean proof. Every other quantum algorithm you will learn later — Grover, Shor, quantum walk, amplitude estimation — builds on at least one of these moves and typically all of them. Deutsch-Jozsa is the "hello world" of the quantum algorithm zoo.

Indian context — early algorithm research at IIT and TIFR

Quantum-algorithm research in India began in earnest in the 1990s, with groups at TIFR Mumbai, IIT Madras, IIT Kanpur, and IISc Bangalore. Some of the most influential recent work on oracle algorithms by Indian researchers has been on quantum walks and amplitude-amplification generalisations — successors of the Deutsch-Jozsa template. Ashwin Nayak (IIT-alumnus, now at Waterloo) has contributed to the formal lower-bound theory that shows exactly how much classical and quantum query complexity can differ; his work on communication complexity and the quantum adversary method is part of the formal foundation on which the Deutsch-Jozsa-style separations are proved. When Indian students learn Deutsch-Jozsa today in an undergraduate QC course, they are entering a research tradition that India has contributed to since the algorithm's early years.

Where this leads next

References

  1. Deutsch and Jozsa, Rapid solution of problems by quantum computation (1992) — the original paper. Proc. R. Soc. A 439, 553.
  2. Wikipedia, Deutsch-Jozsa algorithm — the standard encyclopaedic treatment with worked n=2 example.
  3. John Preskill, Lecture Notes on Quantum Computation, Ch. 6 (quantum algorithms) — theory.caltech.edu/~preskill/ph229.
  4. Nielsen and Chuang, Quantum Computation and Quantum Information, §1.4.3 (Deutsch-Jozsa) — Cambridge University Press.
  5. Cleve, Ekert, Macchiavello, Mosca, Quantum algorithms revisited (1998) — unified treatment of Deutsch-Jozsa, Bernstein-Vazirani, Simon, and Shor. arXiv:quant-ph/9708016.
  6. Qiskit Textbook, Deutsch-Jozsa algorithm — runnable Python implementation with small-n examples.