Deutsch–Jozsa Algorithm

Deutsch–Jozsa decides whether a black-box function is constant or balanced in a single query — the first clean, exponential quantum-classical separation.

Queries

1 (quantum) vs up to 2ⁿ⁻¹+1 (classical, exact)

Type

exact, oracle-based

Role

teaching example of phase kickback

What it does

Put the input register in superposition and the output qubit in |−⟩. The oracle writes f(x) as a phase (phase kickback). A final Hadamard layer interferes the amplitudes so that measuring all zeros means 'constant' and anything else means 'balanced' — decided in one query.

Circuit sketch

Steps

• Input register in superposition; ancilla in |−⟩.
• Oracle applies f via phase kickback.
• Hadamard the input register.
• Measure: all-zero ⇒ constant, else balanced.

Where it's used

Mostly pedagogical, but the phase-kickback + interference pattern is the template for Bernstein–Vazirani, Simon, and Grover's oracle.

In code (Qiskit)

qc = QuantumCircuit(4,3)
qc.x(3); qc.h(range(4))   # ancilla in |->, all in superposition
# oracle U_f
qc.h(range(3)); qc.measure(range(3),range(3))