Let $\mathcal{B}_{n}$ denote the set of all $n$-bit strings and let $f: \mathcal{B}_{n} \rightarrow \mathcal{B}_{1}$ be a Boolean function which obeys either

(I) $f(x)=0$ for all $x \in \mathcal{B}_{n}$, or

(II) $f(x)=0$ for exactly half of all $x \in \mathcal{B}_{n}$.

Suppose we are given the $n$-qubit state

$$|\xi\rangle=\frac{1}{\sqrt{2^{n}}} \sum_{x \in \mathcal{B}_{n}}(-1)^{f(x)}|x\rangle$$

Show how we may determine with certainty whether $f$ is of case (I) or case (II).

Suppose now that Alice and Bob are separated in space. Alice possesses a quantum oracle for a Boolean function $f_{A}: \mathcal{B}_{n} \rightarrow \mathcal{B}_{1}$ and Bob similarly possess a quantum oracle for a Boolean function $f_{B}: \mathcal{B}_{n} \rightarrow \mathcal{B}_{1}$. These functions are arbitrary, except that either

(1) $f_{A}(x)=f_{B}(x)$ for all $x \in \mathcal{B}_{n}$, or

(2) $f_{A}(x)=f_{B}(x)$ for exactly half of all $x \in \mathcal{B}_{n}$.

Alice and Bob each have available a supply of qubits in state $|0\rangle$ and each can apply local quantum operations (including their own function oracle) to any qubits in their possession. Additionally, they can send qubits to each other.

Show how Bob may decide with certainty which case applies, after he has received $n$ qubits from Alice. [Hint: You may find it helpful to consider the function $h(x)=$ $f_{A}(x) \oplus f_{B}(x)$, where $\oplus$ denotes addition mod 2.]