= Solution
A two-query network begins in $|0\rangle_x|0\rangle_y$, calls $U_f$, flips the input with $X_x$, calls $U_f$ again, and measures the answer wire in Z. The successive states are
$$
|0,0\rangle\longmapsto|0,f(0)\rangle
\longmapsto|1,f(0)\rangle
\longmapsto|1,f(0)\oplus f(1)\rangle.
$$
The measured answer is zero for constant functions and one for balanced functions. The circuit is drawn in <4/b/i>.
Explicit <Boolean quantum oracle>[oracle] circuits follow from the form $f(x)=a\oplus bx$:
$$
\boxed{U_f=(I\otimes X^a)\operatorname{CNOT}_{x\to y}^{\,b}.}
$$
Thus the four circuits, respectively for the truth tables in <5/b/i>, are the identity on both wires; a NOT on the answer wire; a <CNOT gate>[CNOT] from input to answer; and a <CNOT gate>[CNOT] together with an answer NOT. The latter commute, so their order is immaterial. These circuits leave the input wire unchanged and <exclusive or>[XOR] precisely $f(x)$ into the answer.
Back to article page
