Let $B_{n}$ denote the set of all $n$-bit strings and write $N=2^{n}$. Let $I$ denote the identity operator on $n$ qubits and for $G=\left\{x_{1}, x_{2}, \ldots, x_{k}\right\} \subset B_{n}$ introduce the $n$-qubit operator

$$Q=-H_{n} I_{0} H_{n} I_{G}$$

where $H_{n}=H \otimes \ldots \otimes H$ is the Hadamard operation on each of the $n$ qubits, and $I_{0}$ and $I_{G}$ are given by

$$I_{0}=I-2|00 \ldots 0\rangle\left\langle 00 \ldots 0\left|\quad I_{G}=I-2 \sum_{x \in G}\right| x\right\rangle\langle x|$$

Also introduce the states

$$\left|\psi_{0}\right\rangle=\frac{1}{\sqrt{N}} \sum_{x \in B_{n}}|x\rangle \quad\left|\psi_{G}\right\rangle=\frac{1}{\sqrt{k}} \sum_{x \in G}|x\rangle \quad\left|\psi_{B}\right\rangle=\frac{1}{\sqrt{N-k}} \sum_{x \notin G}|x\rangle$$

Let $\mathcal{P}$ denote the real span of $\left|\psi_{0}\right\rangle$ and $\left|\psi_{G}\right\rangle$.

(a) Show that $Q$ maps $\mathcal{P}$ to itself, and derive a geometrical interpretation of the action of $Q$ on $\mathcal{P}$, stating clearly any results from Euclidean geometry that you use.

(b) Let $f: B_{n} \rightarrow B_{1}$ be the Boolean function such that $f(x)=1$ iff $x \in G$. Suppose that $k=N / 4$. Show that we can obtain an $x \in G$ with certainty by using just one application of the standard quantum oracle $U_{f}$ for $f$ (together with other operations that are independent of $f$ ).