Let $B_{n}$ denote the set of all $n$-bit strings. For any Boolean function on 2 bits $f: B_{2} \rightarrow B_{1}$ consider the linear operation on 3 qubits defined by

$$U_{f}|x\rangle|y\rangle=|x\rangle|y \oplus f(x)\rangle$$

for all $x \in B_{2}, y \in B_{1}$ and $\oplus$ denoting addition of bits modulo 2 . Here the first register is a 2-qubit register and the second is a 1-qubit register. We are able to apply only the 1-qubit Pauli $X$ and Hadamard $H$ gates to any desired qubits, as well as the 3 -qubit gate $U_{f}$ to any three qubits. We can also perform measurements in the computational basis.

(a) Describe how we can construct the state

$$|f\rangle=\frac{1}{2} \sum_{x \in B_{2}}(-1)^{f(x)}|x\rangle$$

starting from the standard 3-qubit state $|0\rangle|0\rangle|0\rangle$.

(b) Suppose now that the gate $U_{f}$ is given to us but $f$ is not specified. However $f$ is promised to be one of two following cases:

(i) $f$ is a constant function (i.e. $f(x)=0$ for all $x$, or $f(x)=1$ for all $x$ ),

(ii) for any 2-bit string $x=b_{1} b_{2}$ we have $f\left(b_{1} b_{2}\right)=b_{1} \oplus b_{2}$ (with $\oplus$ as above).

Show how we may determine with certainty which of the two cases (i) or (ii) applies, using only a single application of $U_{f}$.