Checkpoint: Solve It in One Query

You have now seen every piece of the Deutsch–Jozsa algorithm: oracles, phase kickback, quantum parallelism, and interference. This checkpoint asks you to assemble those pieces into a complete working circuit and watch a quantum computer decide a property of a function in a single query — something no classical algorithm can match.

The problem

A function $f : \{0,1\}^2 \to \{0,1\}$ is hidden inside an oracle. You are promised that $f$ is either constant (same output for every input) or balanced (outputs 0 on exactly half of all inputs and 1 on the other half). Your goal is to decide which, using only one query to the oracle.

Classically, you would need up to $2^{2-1} + 1 = 3$ queries in the worst case. The Deutsch–Jozsa algorithm does it in one.

The circuit structure

The circuit for $n = 2$ uses three qubits: two input qubits ( $q_0, q_1$ ) and one ancilla ( $q_2$ ).

Initialise. Prepare the ancilla in $|1\rangle$ so that a Hadamard turns it into $|-\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ .

Fan out. Apply a Hadamard to every qubit. The input register becomes the uniform superposition over all four two-bit strings:

$H^{\otimes 2}|00\rangle = \frac{1}{2}\bigl(|00\rangle + |01\rangle + |10\rangle + |11\rangle\bigr).$

The ancilla is now $|-\rangle$ , ready to kick back.

Query. Call the oracle $U_f$ exactly once. Because the ancilla is in $|-\rangle$ , the oracle acts as a phase oracle on the input register:

$U_f\,|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle.$

The joint state of the input register after the query is

$\frac{1}{2}\sum_{x \in \{0,1\}^2} (-1)^{f(x)}|x\rangle.$

Interfere. Apply $H^{\otimes 2}$ to the input register. The Hadamard transform maps this sum to a state concentrated on $|00\rangle$ when $f$ is constant and spread away from $|00\rangle$ when $f$ is balanced. Specifically, for the balanced function $f(x_0, x_1) = x_0$ the final state of the input register is $|10\rangle$ with certainty — a direct consequence of destructive interference cancelling all other outcomes.

Measure. Read qubits 0 and 1. Outcome 00 means constant; any other outcome means balanced.

Try it

Complete the circuit below. The oracle for the balanced function $f(x_0, x_1) = x_0$ is already provided as a single CNOT gate — do not remove it. Your job is to add the correct initialisation steps before the oracle and the correct interference step after it, then measure.

Run your code to see the quantum state.

After running, the probability histogram should show 100 and 101 each with probability 0.5 (qubit 0 = 1, qubit 1 = 0, ancilla in $|-\rangle$ , reading from most-significant to least-significant). The ancilla is never measured out of its $|-\rangle$ state, so it contributes equal weight to both outcomes. The input-register marginal is 10 with probability 1 — the non-00 outcome that certifies the function is balanced, decided in a single query.