Deutsch–Jozsa Algorithm

Overview

Deutsch–Jozsa is the multi-bit generalization of Deutsch’s algorithm.

You’re given oracle access to a function

$$f:\{0,1\}^n\to\{0,1\},$$

with a promise that $f$ is either:

• constant: same output for all inputs, or
• balanced: outputs 0 on exactly half of inputs and 1 on exactly half.

Goal: decide which case holds.

Why it’s interesting:

• Classically, to be sure in the worst case you may need many queries.
• Deutsch–Jozsa solves it with one oracle query (ideal model), by encoding the global property into interference.

Intuition

The algorithm queries the oracle on a uniform superposition of all inputs.

• If $f$ is constant, the oracle applies the same phase to every branch. That global phase does not affect measurement, so the “uniform structure” remains.

• If $f$ is balanced, half the branches get a phase flip and half do not. That pattern causes destructive interference in a very specific place.

After a final mixing step (Hadamards), the measurement outcome is designed to be:

• all zeros if constant,
• anything else if balanced.

This is a clean demonstration of “global property extraction via phase patterns.”

Algorithm Structure

High-level steps:

1. Prepare $n$ input qubits in $|0\rangle^{\otimes n}$ and one target qubit in $|1\rangle$.
2. Apply H to all qubits to create a uniform superposition on the input and $| - \rangle$ on the target.
3. Query the oracle once.
4. Apply H to the input register.
5. Measure the input register:
   • if you get $0^n$, conclude constant;
   • otherwise, conclude balanced.

Formal Description

Oracle

Use the reversible oracle

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

Create the uniform query

After applying H to the $n$ input qubits:

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

Prepare the target as $| - \rangle$ (via H on $|1\rangle$). Then querying $U_f$ produces phase kickback:

$$\frac{1}{\sqrt{2^n}}\sum_x |x\rangle| - \rangle \mapsto \frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle| - \rangle.$$

So the entire function is now a pattern of signs $(-1)^{f(x)}$ across the input superposition.

Why the final Hadamards work

Applying $H^{\otimes n}$ mixes all branches. The amplitude of the $|0^n\rangle$ outcome becomes proportional to the sum of those signs.

• If $f$ is constant, all signs match, the sum is large, and $|0^n\rangle$ appears with certainty.
• If $f$ is balanced, half are +1 and half are −1, the sum cancels, and $|0^n\rangle$ has zero amplitude.

This is interference doing global counting without enumerating outputs one-by-one.

Worked Example

Take $n=2$. The input superposition is over $\{00,01,10,11\}$.

Constant example: $f(x)=0$ for all $x$

Then $(-1)^{f(x)}=+1$ for all branches. After the oracle, the input register is still the uniform superposition. The final $H^{\otimes 2}$ maps that uniform state to $|00\rangle$. So you measure $00$ with certainty.

Balanced example: $f(x)=x_1\oplus x_2$

This function is 0 on two inputs and 1 on two inputs. The oracle applies a sign pattern with two + and two −. The final $H^{\otimes 2}$ causes cancellation specifically at $|00\rangle$. So you will never measure $00$.

Turtle Tip

Common Pitfalls

Quick Check

What’s Next

Deutsch–Jozsa decides a global promise property. Next we study Bernstein–Vazirani, where the oracle hides a specific bitstring and phase kickback lets you recover it in a single query.