= Solution
Use one target <ancilla qubit> initially in $|0\rangle$. Apply a <CNOT gate> from each data <qubit> $x_j$ to that same target, for $j=1,\ldots,n$. Each <CNOT gate> adds its control bit modulo two without changing the control. After all $n$ gates the target contains the <parity bit> $f(x)=x_1\oplus\cdots\oplus x_n$. Thus \b[the required circuit is the $n$-gate parity fan-in:]
$$
\boxed{W=\prod_{j=1}^{n}\operatorname{CNOT}_{j\to a},\qquad W|x\rangle|0\rangle=|x\rangle|f(x)\rangle.}
$$
This is <parity computation by CNOT gates>. The circuit also satisfies $W|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle$ for either target value, and $W^{-1}=W$ because all these shared-target <CNOT gates> commute and individually square to the identity. The action on general superpositions follows by <linearity>.
Back to article page
