= Solution
Let $a,b$ be as in <5/b/i>. Insert the explicit <Boolean quantum oracle>[oracle] from <5/b/ii> between the two pairs of <Hadamard gates>. The network identities
$$
HXH=Z,\qquad
(H\otimes H)\operatorname{CNOT}_{x\to y}(H\otimes H)
=\operatorname{CNOT}_{y\to x}
$$
turn the entire network into
$$
U_D=(I\otimes Z^a)\operatorname{CNOT}_{y\to x}^{\,b}.
$$
This is the last simplified circuit in <4/b/i>. On the designated input $|0\rangle_x|1\rangle_y$, its reversed control is certainly one, so
$$
\boxed{U_D|0,1\rangle=(-1)^a|b,1\rangle
=(-1)^{f(0)}|f(0)\oplus f(1),1\rangle.}
$$
The <global phase> is unobservable. Measuring the first wire therefore determines the function class with certainty after one <Boolean quantum oracle>[oracle] query, while the second wire returns to $|1\rangle$. These circuit identities are the network form of <quantum phase kickback>: the answer state between the Hadamards is the $X$ <eigenstate> $|-\rangle$, on which an <exclusive or>[XOR] acts as a phase.
Back to article page
