Skip to main content
The Deutsch-Jozsa algorithm solves a problem that classically requires up to 2^(n−1)+1 queries: given a black-box function f:ⁿ→, determine whether it is constant (same output for all inputs) or balanced (outputs 0 for exactly half the inputs and 1 for the other half). The quantum algorithm answers with certainty using just one query to the oracle. This is one of the earliest examples of an exponential separation between classical and quantum query complexity.

​
Code

​
Step-by-step explanation

Gate definitions
  • x (Pauli-X / NOT): U(pi, 0, pi) — flips |0⟩ ↔ |1⟩.
  • h (Hadamard): U(pi/2, 0, pi) — creates superposition.
  • cx (CNOT): controlled U(pi, 0, pi) — used inside the balanced oracle.
Oracle definitions Both variants define the same three subroutines. Only the oracle function differs:
  • constant(q0, q1) applies x q1, which flips the ancilla unconditionally. This implements f(x) = 1 for all x — a constant function.
  • balanced(q0, q1) applies cx q0, q1, which flips the ancilla only when q0 is |1⟩. This implements f(x) = x — a balanced function that outputs 0 and 1 for equal numbers of inputs.
Initialization Both qubits start in |0⟩ after reset. The ancilla qubit q1 is prepared in the |−⟩ state:
The query qubit q0 is placed in uniform superposition:
Phase kickback When the oracle is applied to the state (|0⟩ + |1⟩)/√2 ⊗ |−⟩, the effect on q0 depends on the function:
  • Constant function: The ancilla flips regardless of q0. The phase factor (−1)^f(x) is the same for both terms in q0’s superposition, introducing a global phase that does not affect the measurement.
  • Balanced function: The CNOT ties the ancilla flip to q0’s value. The relative phase between |0⟩ and |1⟩ in q0’s superposition flips sign, turning (|0⟩ + |1⟩)/√2 into (|0⟩ − |1⟩)/√2.
Final Hadamard on q0 h q0 maps back from the Hadamard basis:
  • If the oracle was constant: q0 → |0⟩
  • If the oracle was balanced: q0 → |1⟩

​
Expected output

Measuring q0 after the final Hadamard gives a deterministic result:
To switch between oracles, only the body of oracle changes — constant(q0, q1) vs balanced(q0, q1). The surrounding circuit structure (initialization, final Hadamard) is identical in both cases.

​
Quantum mechanics concepts

Phase kickback — When a unitary gate U is controlled by an ancilla qubit in the |−⟩ state, phase information about f is “kicked back” from the ancilla onto the control qubit’s amplitudes. This is the core mechanism behind many quantum speedups. Query complexity — The Deutsch-Jozsa problem has classical deterministic query complexity O(2^(n−1)) but quantum query complexity O(1). A single call to the oracle suffices because interference allows the quantum circuit to extract global properties of f rather than evaluating it point by point. Global vs relative phase — A constant oracle introduces only a global phase on q0’s state, which has no physical consequences. A balanced oracle introduces a relative phase between |0⟩ and |1⟩, which the final Hadamard converts into a measurable amplitude difference.