✦Deutsch–Jozsa algorithm

Detect constant versus balanced Boolean functions under a promise.

1. Core idea

Prepare a uniform input superposition, use a phase oracle for f, apply Hadamards again, and measure. For a constant function, the all-zero output has probability one. For a balanced function, that amplitude vanishes. The oracle is a supplied reversible subroutine, not a free classical lookup.

2. Mathematical foundation

The notation describes a precise relationship among states, transformations or probabilities. Identify each symbol, check the dimensions of the objects, and distinguish amplitudes from the probabilities produced by a measurement.

3. Worked example

4. Reasoning flow

1. Prepare two input qubits with H gates.
2. Apply a balanced phase oracle for f(x)=x₀⊕x₁.
3. Apply H to recombine the phase-marked paths.
4. Measure the input; 00 is excluded for balanced functions.
5. Compare with the constant-oracle case.

Qiskit implementation

Run this standalone Python script with Qiskit installed. It uses exact statevector simulation rather than noisy hardware shots.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector
# Two-input balanced function f(x)=x0 XOR x1.
# Phase oracle: (-1)^f(x) implemented with Z on each input.
qc = QuantumCircuit(2)
qc.h([0, 1])                 # prepare uniform input amplitudes
qc.z([0, 1])                 # balanced phase oracle
qc.h([0, 1])                 # interfere the signed amplitudes
print(qc.draw())
print(Statevector.from_instruction(qc).probabilities_dict())
# Expected: '11' with probability 1; never '00'.

5. Check your understanding

6. What to watch out for

Ideal-state calculations assume perfect gates and measurements. When assessing an algorithm, separate its mathematical guarantee from the cost of building oracles, preparing inputs, repeating experiments and correcting physical noise.