Deutsch–Jozsa
The Deutsch–Jozsa algorithm tells you, with one question to a black box, whether a hidden function is constant (the same output for every input) or balanced (1 for exactly half the inputs). A normal computer that must be exactly sure can need up to 2^(n-1)+1 questions. The fine print: the setup is made up, and a normal computer that guesses at random is almost always right after a few questions. Its real value is teaching. It is the cleanest example 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. It takes n bits in and gives one bit out. Think of a website you can call but can't look inside. You are also given a promise. Either f is constant, meaning it gives the same bit for every input. Or it is balanced, meaning it gives 1 for exactly half of all 2^n inputs. Your task is to tell which, using as few calls as possible.
For example, with n = 2 there are 2 × 2 = 4 inputs: 00, 01, 10 and 11. A balanced function answers 1 for exactly 2 of them.
The promise matters. Without it, the problem makes no sense. A function that is almost constant, but not quite, would fool any small number of questions. That is true for quantum and normal computers alike.
How well can a normal computer do?
A normal computer that must be exactly sure can get unlucky. Say it sees 2^(n-1) outputs that all match. That is half the inputs. The function could still be constant or balanced. So in the worst case it needs 2^(n-1) + 1 questions. That number doubles each time you add a bit.
But be honest about guessing at random. Ask about a few random inputs. If any two answers differ, the function is balanced, full stop. If k answers all agree, the chance a balanced function slipped through is about 2^-(k-1).
Let's work it out for ten questions. The chance is 2^-9, which is 1 ÷ 512. That is below one in five hundred. So the huge gap only exists if you demand an answer that is guaranteed exact. In practice that rarely matters.
How does the quantum circuit decide in one query?
Here is what the circuit does, step by step.
- It puts a helper qubit, the ancilla, in the state
|−⟩. It does this with an X gate, then an H gate. - It puts the input qubits into an equal superposition of all
2^ninputs. - It calls the oracle once.
The oracle adds f(x) into the ancilla using XOR (addition where 1 + 1 = 0). Because the ancilla is in |−⟩, something odd happens. The ancilla doesn't change. Instead, the sign flips on each input where f(x) = 1. This is called phase kickback. The function's outputs are now stored in the signs of the amplitudes (the numbers that set how likely each answer is). They are not in any bit you could read directly.
The final Hadamard gates make those signs interfere, which means add up or cancel. The amplitude of the all-zeros answer becomes the average of all the signs. If f is constant, every sign is the same, so the average is +1 or −1. If it is balanced, half are +1 and half are −1. They cancel in pairs and the average is exactly 0.
Let's check with 4 inputs. Constant: (1 + 1 + 1 + 1) ÷ 4 = 1. Balanced: (1 + 1 − 1 − 1) ÷ 4 = 0.
So measure the inputs. All zeros means constant. Anything else means balanced. One question gives a sure answer.
Think of noise-canceling headphones. If the two sounds match, they get louder. If they are opposite, you hear silence. You only learn "loud or silent," not the details of each sound.
Notice what did not happen. The circuit did not "compute all answers at once" and hand them to you. It ran f once on a superposition. Then interference squeezed 2^n outputs into one overall fact. That one fact is all this circuit can tell you.
What doesn't it prove?
Deutsch–Jozsa does not show that quantum computers beat normal ones at anything practical.
- The constant-or-balanced promise is made up. No known real task looks like this.
- The gain is only over normal methods that must be exactly sure. Let a normal method guess at random with a tiny chance of error, and its cost drops to a handful of questions.
- The oracle is a circuit someone had to build. Whoever built it already knew the answer.
Its importance is as a pattern: Hadamards, phase kickback, Hadamards, then read one overall fact. That pattern shows up again in Bernstein–Vazirani. A grown-up version of it drives Grover's search.
What does this look like on real hardware?
Small Deutsch–Jozsa runs (2–6 qubits) work cleanly on every current platform. The circuit has few layers. After transpilation (rewriting into the chip's own gates), a simple oracle costs only a few gates. It is a common first test when a new device is switched on.
Be clear about what a clean run shows. It shows the quality of the gates and readout, nothing more. A normal computer can simulate this circuit in millionths of a second. Try it in the Lab. Then see how real devices are scored on the QPU index.