Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 58 / 4 / b / ii / Solution

Use one target ancilla qubit initially in $|0⟩$. Apply a CNOT gate from each data qubit $x_j$ to that same target, for $j=1,\dots ,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 the required circuit is the $n$-gate parity fan-in:This is parity computation by CNOT gates. The circuit also satisfies $W|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$ 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.