(a) Show how the $n$-qubit state

$$\left|\psi_{n}\right\rangle:=\frac{1}{\sqrt{2^{n}}} \sum_{x \in B_{n}}|x\rangle$$

can be generated from a computational basis state of $\mathbb{C}^{n}$ by the action of Hadamard gates.

(b) Prove that $C Z=(I \otimes H) C N O T_{12}(I \otimes H)$, where $C Z$ denotes the controlled- $Z$ gate. Justify (without any explicit calculations) the following identity:

$$C N O T_{12}=(I \otimes H) C Z(I \otimes H)$$

(c) Consider the following two-qubit circuit:

What is its action on an arbitrary 2-qubit state $|\psi\rangle \otimes|\phi\rangle ?$ In particular, for two given states $|\psi\rangle$ and $|\phi\rangle$, find the states $|\alpha\rangle$ and $|\beta\rangle$ such that

$$U(|\psi\rangle \otimes|\phi\rangle)=|\alpha\rangle \otimes|\beta\rangle .$$

(d) Consider the following quantum circuit diagram

where the measurement is relative to the computational basis and $U$ is the quantum gate from part (c). Note that the second gate in the circuit performs the following controlled operation:

$$|0\rangle|\psi\rangle|\phi\rangle \mapsto|0\rangle|\psi\rangle|\phi\rangle ;|1\rangle|\psi\rangle|\phi\rangle \mapsto|1\rangle U(|\psi\rangle|\phi\rangle) .$$

(i) Give expressions for the joint state of the three qubits after the action of the first Hadamard gate; after the action of the quantum gate $U$; and after the action of the second Hadamard gate.

(ii) Compute the probabilities $p_{0}$ and $p_{1}$ of getting outcome 0 and 1 , respectively, in the measurement.

(iii) How can the above circuit be used to determine (with high probability) whether the two states $|\psi\rangle$ and $|\phi\rangle$ are identical or not? [Assume that you are given arbitrarily many copies of the three input states and that the quantum circuit can be used arbitrarily many times.]