Let $B_{n}$ denote the set of all $n$-bit strings. Suppose we are given a 2-qubit quantum gate $I_{x_{0}}$ which is promised to be of the form

$$I_{x_{0}}|x\rangle=\left\{\begin{array}{rr} |x\rangle & x \neq x_{0} \\ -|x\rangle & x=x_{0} \end{array}\right.$$

but the 2-bit string $x_{0}$ is unknown to us. We wish to determine $x_{0}$ with the least number of queries to $I_{x_{0}}$. Define $A=I-2|\psi\rangle\langle\psi|$, where $I$ is the identity operator and $|\psi\rangle=\frac{1}{2} \sum_{x \in B_{2}}|x\rangle$.

(a) Is $A$ unitary? Justify your answer.

(b) Compute the action of $I_{x_{0}}$ on $|\psi\rangle$, and the action of $|\psi\rangle\langle\psi|$ on $\left|x_{0}\right\rangle$, in each case expressing your answer in terms of $|\psi\rangle$ and $\left|x_{0}\right\rangle$. Hence or otherwise show that $x_{0}$ may be determined with certainty using only one application of the gate $I_{x_{0}}$, together with any other gates that are independent of $x_{0}$.

(c) Let $f_{x_{0}}: B_{2} \rightarrow B_{1}$ be the function having value 0 for all $x \neq x_{0}$ and having value 1 for $x=x_{0}$. It is known that a single use of $I_{x_{0}}$ can be implemented with a single query to a quantum oracle for the function $f_{x_{0}}$. But suppose instead that we have a classical oracle for $f_{x_{0}}$, i.e. a black box which, on input $x$, outputs the value of $f_{x_{0}}(x)$. Can we determine $x_{0}$ with certainty using a single query to the classical oracle? Justify your answer.