Deutsch–Jozsa: one query instead of many

The first algorithm with a provable gap: is a function constant or balanced?

You will learn to

Explain the oracle model and phase kickback.
Predict the output of Deutsch–Jozsa for a constant and a balanced oracle.
Say honestly why the speed-up is a toy.

You are given a black box computing f: {0,1}ⁿ → {0,1} and promised that f is either constant (same output for every input) or balanced (0 on exactly half the inputs). Classically, you may need 2ⁿ⁻¹ + 1 queries to be sure. Deutsch–Jozsa needs one.

U_{f} ∣ x ⟩ ∣ - ⟩ = (- 1)^{f (x)} ∣ x ⟩ ∣ - ⟩

Phase kickback: with the target in |−⟩, the oracle writes f(x) into the phase of |x⟩ instead of into the target bit. Interference can now read all those phases at once.

H on every input qubit: uniform superposition over all x.
Oracle: phases (−1)^{f(x)}.
H again: the amplitude of |0…0⟩ becomes the average of (−1)^{f(x)}: ±1 if constant, exactly 0 if balanced.
Measure: all zeros means constant, anything else means balanced.

Try it

Balanced oracle on 3 qubits

The oracle is f(x) = x0 ⊕ x2 (two CNOTs onto the target). Simulate: the three input bits are never 000. Replace the two CNOTs by nothing (constant f = 0) and the result is always 000.

OPENQASM 3.0;
include "stdgates.inc";
qubit[4] q;
bit[3] c;
x q[3];
h q[0];
h q[1];
h q[2];
h q[3];
barrier q;
cx q[0], q[3];
cx q[2], q[3];
barrier q;
h q[0];
h q[1];
h q[2];
c[0] = measure q[0];
c[1] = measure q[1];
c[2] = measure q[2];

Open in the IDE Open in the Playground

Be honest about the gap: the classical cost is exponential only if you insist on certainty. A randomised classical algorithm with a few queries is almost always right. Deutsch–Jozsa matters because it is the clearest demonstration of interference doing work, and because its structure returns in Bernstein–Vazirani, Simon and Shor.

Quiz 1 · 10 XP

Why is the target qubit prepared in |−⟩ rather than |0⟩?

Quiz 2 · 10 XP

For a balanced oracle the probability of measuring 0…0 is…

Key takeaway

Deutsch–Jozsa writes f into phases with kickback and reads them all with one round of interference. One query decides constant versus balanced.

Docs: algorithm walkthroughs

Up next: Bernstein–Vazirani: read a hidden string

OPENQASM 3.0; include "stdgates.inc"; qubit[4] q; bit[3] c; x q[3]; h q[0]; h q[1]; h q[2]; h q[3]; barrier q; cx q[0], q[3]; cx q[2], q[3]; barrier q; h q[0]; h q[1]; h q[2]; c[0] = measure q[0]; c[1] = measure q[1]; c[2] = measure q[2];