Deutsch–Jozsa
Deutsch–Jozsa decides, in one oracle query, whether a hidden function is constant (same output everywhere) or balanced (outputs 1 on exactly half its inputs) — a task that costs a deterministic classical algorithm up to 2^(n-1)+1 queries. The honest fine print: the promise is artificial, and a randomised classical algorithm answers with near-certainty in a handful of queries. Its real value is pedagogical — it is the cleanest demonstration of interference doing useful work.
| Task | Best classical | Quantum |
|---|---|---|
| Exact answer, deterministic | 2^(n-1) + 1 queries | 1 query |
| Error below 2^-(k-1), randomised | k queries | 1 query |
What problem does it solve?
You are given a black-box function f that maps n bits to one bit — think of an API you can call but not inspect. You hold a promise: f is either constant (returns the same bit for every input) or balanced (returns 1 for exactly half of all 2^n inputs). The task is to decide which, using as few calls as possible.
The promise matters. Without it, the problem is ill-posed — a function that is almost constant but not quite would defeat any small number of queries, quantum or classical.
How well can a classical computer do?
A deterministic algorithm can be unlucky: after seeing 2^(n-1) identical outputs, the function could still be either constant or balanced, so the worst case is 2^(n-1) + 1 queries — exponential in n.
But be honest about randomisation. Query a few random inputs: if any two outputs differ, the function is balanced, full stop. If k outputs all agree, the chance a balanced function survived that test is about 2^-(k-1). Ten queries gets the error below one in five hundred. So the exponential separation only exists if you demand a guaranteed exact answer — a distinction that rarely matters in practice.
How does the quantum circuit decide in one query?
The circuit puts an ancilla qubit in the state |−⟩ (X then H), puts the input register into an equal superposition of all 2^n inputs, and calls the oracle once. Because the ancilla is in |−⟩, XOR-ing f(x) into it flips the sign of each branch where f(x) = 1 — this is phase kickback. The function's outputs are now stored in the signs of the amplitudes, not in any bit you could read directly.
The final Hadamards make those signs interfere. The amplitude of the all-zeros outcome becomes the average of all the signs: ±1 if f is constant (every path reinforces), exactly 0 if balanced (paths cancel pairwise). Measure the input register: all zeros means constant; anything else means balanced. One query, a deterministic verdict.
Note what did not happen: the circuit did not "compute all answers at once" and hand them to you. It evaluated f once on a superposition, and interference collapsed 2^n function values into a single global property — the only thing this circuit can tell you.
What it does not prove
Deutsch–Jozsa is not evidence that quantum computers beat classical ones at anything practical.
- The constant-or-balanced promise is artificial; no known real workload has this shape.
- The advantage is only over deterministic, exact classical algorithms. Allow a randomised algorithm a tiny error probability and the classical cost collapses to a handful of queries.
- The oracle is a circuit someone had to build — and whoever built it already knew the answer.
Its importance is as a template. The pattern — Hadamards, phase kickback, Hadamards, read a global property — reappears in Bernstein–Vazirani and, in evolved form, in Grover's search.
What does this look like on real hardware?
Small Deutsch–Jozsa instances (2–6 qubits) run cleanly on every current platform — the circuit is shallow, and after transpilation a simple oracle costs only a few native gates. It is a common first-light test when bringing up a device.
Be clear about what a clean run demonstrates: gate and readout quality, nothing more. This circuit simulates classically in microseconds — try it in the Lab, then see how real devices are scored on the QPU index.