Consider the quantum oracle $U_{f}$ for a function $f: B_{n} \rightarrow B_{n}$ which acts on the state $|x\rangle|y\rangle$ of $2 n$ qubits as follows:

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

The function $f$ is promised to have the following property: there exists a $z \in B_{n}$ such that for any $x, y \in B_{n}$,

$$[f(x)=f(y)] \text { if and only if } x \oplus y \in\left\{0^{n}, z\right\}$$

where $0^{n} \equiv(0,0, \ldots, 0) \in B_{n}$.

(a) What is the nature of the function $f$ for the case in which $z=0^{n}$, and for the case in which $z \neq 0^{n}$ ?

(b) Suppose initially each of the $2 n$ qubits are in the state $|0\rangle$. They are then subject to the following operations:

1. Each of the first $n$ qubits forming an input register are acted on by Hadamard gates;

2. The $2 n$ qubits are then acted on by the quantum oracle $U_{f}$;

3. Next, the qubits in the input register are individually acted on by Hadamard gates.

(i) List the states of the $2 n$ qubits after each of the above operations; the expression for the final state should involve the $n$-bit "dot product" which is defined as follows:

$$a \cdot b=\left(a_{1} b_{1}+a_{2} b_{2}+\ldots+a_{n} b_{n}\right) \bmod 2$$

where $a, b \in B_{n}$ with $a=\left(a_{1}, \ldots, a_{n}\right)$ and $b=\left(b_{1}, \ldots, b_{n}\right)$.

(ii) Justify that if $z=0^{n}$ then for any $y \in B_{n}$ and any $\varphi(x, y) \in\{-1$, $+1\}$, the following identity holds:

$$\| \sum_{x \in B_{n}} \varphi(x, y)|f(x)\rangle\left\|^{2}=\right\| \sum_{x \in B_{n}} \varphi(x, y)|x\rangle \|^{2}$$

(iii) For the case $z=0^{n}$, what is the probability that a measurement of the input register, relative to the computational basis of $\mathbb{C}^{n}$ results in a string $y \in B_{n}$ ?

(iv) For the case $z \neq 0^{n}$, show that the probability that the above-mentioned measurement of the input register results in a string $y \in B_{n}$, is equal to the following:

zero for all strings $y \in B_{n}$ satisfying $y \cdot z=1$, and $2^{-(n-1)}$ for any fixed string $y \in B_{n}$ satisfying $y \cdot z=0$.

[State any identity you may employ. You may use $(x \oplus z) \cdot y=(x \cdot y) \oplus(z \cdot y), \forall x, y, z \in B_{n}$.]