= Solution
A constant function has $f(0)=f(1)$, whereas a balanced one has one zero and one one, so $f(0)\ne f(1)$. The four oracles require only the following circuits:
$$
U_0=I,\qquad U_1=I\otimes X,\qquad
U_x=\operatorname{CNOT},\qquad
U_{1\oplus x}=(I\otimes X)\operatorname{CNOT}.
$$
Prepare $|0\rangle|1\rangle$, apply a <Hadamard gate> to each <qubit>, apply the oracle once, apply another <Hadamard gate> to the first <qubit>, and measure that first wire in the <computational basis>. Immediately before the oracle the state is $|+\rangle|-\rangle$. The identity $X|-\rangle=-|-\rangle$ gives <phase kickback>:
$$
|+\rangle|-\rangle\xrightarrow{U_f}
\frac{(-1)^{f(0)}|0\rangle+(-1)^{f(1)}|1\rangle}{\sqrt2}|-\rangle
\xrightarrow{H\otimes I}
\boxed{(-1)^{f(0)}|f(0)\oplus f(1)\rangle|-\rangle.}
$$
The output is certainly zero for constant and one for balanced. In circuit terms the target $X$ contributes only a global sign, and a controlled $X$ with target $|-\rangle$ acts as $Z$ on the control; $HZH=X$ then turns that phase into a measured bit. These identities prove the network for all four explicit oracles. The unused sign contains $f(0)$ only as a global phase, consistent with the full-identification lower bound.
Back to article page
