The Phase Oracle

A standard quantum oracle encodes a function $f:\{0,1\}^n \to \{0,1\}$ by XOR-ing its output into an ancilla qubit:

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

This is perfectly valid, but it leaves the answer dangling in the second register. Quantum algorithms such as Deutsch's and Deutsch–Jozsa need something subtler: the information about $f$ encoded in the phase of the input register so that later interference can reveal a global property in a single query.

Phase kickback

The key move is to prepare the ancilla in the state

$|-\rangle = \tfrac{1}{\sqrt{2}}\bigl(|0\rangle - |1\rangle\bigr)$

before calling the oracle. When $f(x) = 0$ the XOR leaves $|-\rangle$ unchanged. When $f(x) = 1$ the XOR flips the ancilla:

$|0\rangle - |1\rangle \;\xrightarrow{\oplus 1}\; |1\rangle - |0\rangle = -(|0\rangle - |1\rangle).$

In both cases the ancilla finishes in $|-\rangle$ , but when $f(x)=1$ the overall state picks up a factor of $-1$ . Tracing out the ancilla, the net effect on the input register is

$|x\rangle \;\longmapsto\; (-1)^{f(x)}|x\rangle.$

The function's output has kicked back onto the phase of $|x\rangle$ . The ancilla is unentangled and can be discarded; the oracle has become a purely diagonal unitary on the input register:

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

This is the phase oracle.

Why phases matter

A global phase on a single basis state is invisible if you measure immediately — $(-1)^{f(x)}|x\rangle$ and $|x\rangle$ have the same measurement probabilities. The power comes when the input is in superposition: applying $O_f$ to $|+\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ gives

$O_f|+\rangle = \tfrac{1}{\sqrt{2}}\bigl((-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\bigr).$

Whether the two relative signs are the same or opposite determines whether a subsequent Hadamard produces $|0\rangle$ or $|1\rangle$ — a measurable, deterministic signal. That is exactly the interference step in Deutsch's algorithm that we will build in later lessons.

Single-qubit phase oracle

For a single-bit function the phase oracle has a simple direct representation. If $f(0)=0$ and $f(1)=0$ (constant zero) then $O_f = I$ — no phase anywhere. If $f(0)=1$ and $f(1)=1$ (constant one) then $O_f = -I$ , which is a global phase and unobservable. The non-trivial cases are the two balanced functions:

$f(x) = x$ : $O_f|0\rangle = |0\rangle$ , $O_f|1\rangle = -|1\rangle$ — this is the $Z$ gate.
$f(x) = 1-x$ : $O_f|0\rangle = -|0\rangle$ , $O_f|1\rangle = |1\rangle$ — this is $-Z$ , which equals $Z$ up to global phase and is also represented by $Z$ .

Both balanced single-bit functions map onto the $Z$ gate (up to an unobservable global phase).

Try it

Build the phase oracle for $f(x) = x$ on a single qubit. The grader checks the unitary matrix, so the identity circuit will not pass — you must implement a real gate.

Run your code to see the quantum state.