Let $\mathcal{B}_{n}$ denote the set of all $n$-bit strings and let $\mathcal{H}_{n}$ denote the space of $n$ qubits.

(a) Suppose $f: \mathcal{B}_{2} \rightarrow \mathcal{B}_{1}$ has the property that $f\left(x_{0}\right)=1$ for a unique $x_{0} \in \mathcal{B}_{2}$ and suppose we have a quantum oracle $U_{f}$.

(i) Let $\left|\psi_{0}\right\rangle=\frac{1}{2} \sum_{x \in \mathcal{B}_{2}}|x\rangle$ and introduce the operators

$$I_{x_{0}}=I_{2}-2\left|x_{0}\right\rangle\left\langle x_{0}\right| \quad \text { and } \quad J=I_{2}-2\left|\psi_{0}\right\rangle\left\langle\psi_{0}\right|$$

on $\mathcal{H}_{2}$, where $I_{2}$ is the identity operator. Give a geometrical description of the actions of $-J, I_{x_{0}}$ and $Q=-J I_{x_{0}}$ on the 2-dimensional subspace of $\mathcal{H}_{2}$ given by the real span of $\left|x_{0}\right\rangle$ and $\left|\psi_{0}\right\rangle$. [You may assume without proof that the product of two reflections in $\mathbb{R}^{2}$ is a rotation through twice the angle between the mirror lines.]

(ii) Using the results of part (i), or otherwise, show how we may determine $x_{0}$ with certainty, starting with a supply of qubits each in state $|0\rangle$ and using $U_{f}$ only once, together with other quantum operations that are independent of $f$.

(b) Suppose $\mathcal{H}_{n}=A \oplus A^{\perp}$, where $A$ is a fixed linear subspace with orthogonal complement $A^{\perp}$. Let $\Pi_{A}$ denote the projection operator onto $A$ and let $I_{A}=I-2 \Pi_{A}$, where $I$ is the identity operator on $\mathcal{H}_{n}$.

(i) Show that any $|\xi\rangle \in \mathcal{H}_{n}$ can be written as $|\xi\rangle=\sin \theta|\alpha\rangle+\cos \theta|\beta\rangle$, where $\theta \in[0, \pi / 2]$, and $|\alpha\rangle \in A$ and $|\beta\rangle \in A^{\perp}$ are normalised.

(ii) Let $I_{\xi}=I-2|\xi\rangle\langle\xi|$ and $Q=-I_{\xi} I_{A}$. Show that $Q|\alpha\rangle=-\sin 2 \theta|\beta\rangle+\cos 2 \theta|\alpha\rangle$.

(iii) Now assume, in addition, that $Q|\beta\rangle=\cos 2 \theta|\beta\rangle+\sin 2 \theta|\alpha\rangle$ and that $|\xi\rangle=$ $U|0 \ldots 0\rangle$ for some unitary operation $U$. Suppose we can implement the operators $U, U^{\dagger}, I_{A}$ as well as the operation $I-2|0 \ldots 0\rangle\langle 0 \ldots 0|$. In the case $\theta=\pi / 10$, show how the $n$-qubit state $|\alpha\rangle$ may be made exactly from $|0 \ldots 0\rangle$ by a process that succeeds with certainty.