Deutsch-Jozsa

The Deutsch-Jozsa algorithm (1992) was the first demonstrated example of a quantum algorithm that is exponentially faster than the best classical algorithm — and it’s simple enough to explain in a single lesson. It’s a toy problem, yes. But it’s the proof that quantum speedup is real.

The problem

You’re given a function $f: \{0, 1\}^n \to \{0, 1\}$. You don’t know what $f$ is, but you’re promised that it’s either:

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

Your job: decide which. You can only access $f$ through a “query” — you give it an $x$ and it tells you $f(x)$.

The classical lower bound

How many queries do you need, in the worst case, to be certain? If you’ve queried $f$ on $2^{n-1}$ inputs and they were all 0, you still can’t be sure — maybe it’s constant 0, or maybe it’s balanced and all the 1s are in the unsampled inputs. You need to query one more to be sure.

So the classical worst-case cost is $2^{n-1} + 1$ queries. That’s exponential in $n$: for $n = 30$ bits, you’d need over half a billion queries.

The quantum algorithm

One query. That’s the full quantum cost, regardless of $n$.

Here’s the circuit (in the phase-kickback form, which is a little cleaner):

1. Initialize $n$ qubits in $|0\rangle^{\otimes n}$.
2. Apply $H$ to each qubit: uniform superposition $\frac{1}{\sqrt{2^n}}\sum_{x} |x\rangle$.
3. Apply the phase oracle: $|x\rangle \mapsto (-1)^{f(x)}|x\rangle$. This is “one query,” in the sense that $f$ is evaluated in superposition.
4. Apply $H$ to each qubit again.
5. Measure all qubits.

Result: If $f$ is constant, you measure $|0\rangle^{\otimes n}$ with probability 1. If $f$ is balanced, you measure anything other than $|0\rangle^{\otimes n}$ with probability 1.

So a single run of the circuit, followed by checking whether the measurement was all-zeros, decides the question with certainty.

Try it

Pick each of the five functions in turn. Notice:

• For the constant functions, the final probability distribution is concentrated at $|00\rangle$.
• For the balanced functions, the final probability at $|00\rangle$ is exactly zero — some other basis state picks it up.

A single measurement is enough to distinguish the two cases.

Why it works

The H-gates create a uniform superposition, the oracle stamps each basis state with $(-1)^{f(x)}$, and the final layer of H-gates converts this phase pattern into a position pattern via interference. The key identity is:

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

and then the final H layer amounts to a Fourier-like transform: the amplitude at $|0\rangle^{\otimes n}$ after everything is $\frac{1}{2^n}\sum_x (-1)^{f(x)}$. This sum is either $\pm 1$ (if $f$ is constant) or $0$ (if $f$ is balanced, because half the terms cancel the other half).

So:

• Constant $f$: $P(|0\rangle^{\otimes n}) = 1$.
• Balanced $f$: $P(|0\rangle^{\otimes n}) = 0$.

The Hadamard gates set up interference; the oracle imposes a phase pattern; the final Hadamards cash in the interference to read the answer.

What this proves — and what it doesn’t

Deutsch-Jozsa proves a promise problem can be solved exponentially faster on a quantum computer than on a classical one, if you require zero error probability. If you relax the requirement and allow a small probability of error, classical randomized algorithms can solve it in constant time (try a few random inputs; if they differ, it’s balanced; otherwise it’s very probably constant).

So Deutsch-Jozsa is a demonstration, not a breakthrough. The real breakthroughs are Shor’s algorithm (exponential speedup for factoring, with no classical equivalent even with randomness) and Grover’s search (quadratic speedup for unstructured search). We’ll see both this module.

What’s next

The next two algorithms in Module 7 — Bernstein-Vazirani and Simon’s — are variants of the same “phase-kickback + Hadamard interference” recipe, applied to slightly different promise problems. Then we get to the real headliners: Grover’s search and Shor’s factoring.