Building the DJ Oracle

You have seen how the Deutsch–Jozsa algorithm uses a single oracle query to decide whether a Boolean function is constant or balanced. The algorithm works regardless of how the oracle is built — but at some point you have to build one. This lesson shows how to translate a concrete balanced function into a circuit that a quantum computer can execute.

What the oracle must do

Recall the standard oracle construction. Given a function $f : \{0,1\}^n \to \{0,1\}$ , the oracle unitary $U_f$ acts on an $n$ -qubit input register and a 1-qubit ancilla register:

$U_f \,|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle,$

where $\oplus$ denotes addition modulo 2 (XOR). The input $|x\rangle$ is left untouched; the function value $f(x)$ is XOR-ed into the ancilla $|y\rangle$ . Applying $U_f$ twice returns the original state, confirming that the mapping is reversible.

The XOR function on two input bits

For the Deutsch–Jozsa problem with $n = 2$ input bits, the oracle acts on 3 qubits altogether: qubits 0 and 1 form the input register, and qubit 2 is the ancilla. A convenient balanced function to use as an example is

$f(x_0, x_1) = x_0 \oplus x_1.$

You can verify it is balanced by enumeration: the four possible inputs give outputs $f(00)=0$ , $f(01)=1$ , $f(10)=1$ , $f(11)=0$ — exactly two zeros and two ones, confirming the definition of a balanced function.

The oracle for this function must implement

$U_f \,|x_0, x_1, y\rangle = |x_0, x_1,\; y \oplus x_0 \oplus x_1\rangle.$

Building the oracle from CNOT gates

The CNOT gate does exactly one thing: it XOR-flips the target qubit conditioned on the control qubit. Formally, $\text{CNOT}_{c \to t}\,|x_c, x_t\rangle = |x_c, x_t \oplus x_c\rangle$ .

To build $U_f$ for $f = x_0 \oplus x_1$ we need qubit 2 to accumulate both $x_0$ and $x_1$ via XOR. Two CNOTs suffice, applied in sequence:

$\text{CNOT}_{0 \to 2}$ : sends qubit 2 from $y$ to $y \oplus x_0$ .
$\text{CNOT}_{1 \to 2}$ : sends qubit 2 from $y \oplus x_0$ to $y \oplus x_0 \oplus x_1$ .

After both gates the ancilla holds $y \oplus f(x_0, x_1)$ , which is exactly what the oracle specification demands. The two input qubits are unchanged throughout.

Try it

Implement the oracle for $f(x_0, x_1) = x_0 \oplus x_1$ on a 3-qubit circuit. The grader checks the full unitary matrix, so leaving the circuit empty will not pass — you must add the two CNOT gates that write the function value into the ancilla.

Run your code to see the quantum state.