When thinking about an oracle in the quantum case, we need to be careful about what it is doing, since only *unitary* operations are allowed. A clever choice is to put the oracle's answer into a *phase*: $$ \vert \mathbf{x}\rangle \mapsto (-1)^{f(\mathbf{x})} \vert \mathbf{x}\rangle. $$ We encode this as a unitary operator, $U_f$, which acts on basis states as $$ \begin{align*} U_f\vert \mathbf{x}\rangle & = (-1)^{f(\mathbf{x})}\vert \mathbf{x}\rangle = \\ & = \begin{cases} -\vert \mathbf{x}\rangle & \mathbf{x} = \mathbf{s}; \\ \vert \mathbf{x}\rangle & \text{otherwise}. \end{cases} \end{align*} $$ Since this acts on a given basis state, and does not change the size of the amplitude, it is immediate that the oracle is unitary. Fixing the size of amplitudes giveth a unitary operator, but it also taketh away; by itself, we cannot use the oracle to increase the probability of measuring the secret combination of our lock! The probability is the amplitude squared, and adding a phase can't change that. Put differently, a change in global phase is unobservable. But there are other clever things we can do with the oracle, as we'll soon see. *Tip*. We could imagine instead recording the magic 8-ball's "yes" or "no" into a new qubit, initialized to state $|0\rangle$: $$ \begin{align*} \vert \mathbf{s}\rangle \vert 0\rangle &\to \vert \mathbf{s}\rangle \vert 1\rangle \\ \vert \mathbf{x}\rangle \vert 0\rangle &\to \vert \mathbf{x}\rangle \vert 0\rangle, \end{align*} $$ where $\mathbf{x} \neq \mathbf{s}$. This can in fact be implemented as a multi-controlled $X$ gate, but we'll stick to the simpler phase oracle in this section. --- ***Exercise A.2.1.*** (a) Show that we can also write the oracle in terms of the identity matrix $I$ and projector $\vert \mathbf{s}\rangle\langle\mathbf{s}\vert$ as follows: $$ U_f = I - 2\vert \mathbf{s}\rangle\langle\mathbf{s}\vert. \tag{1} \label{u_f} $$

Hint.

Two operators are equal if they have the same action on basis states.

Solution.

(a) Let's apply the right-hand side of Eq. $(\ref{u_f})$ to the solution state to begin with: $$ \begin{align*} (I - 2\vert \mathbf{s}\rangle\langle\mathbf{s}\vert ) \vert \mathbf{s}\rangle & = \vert \mathbf{s}\rangle - 2\vert \mathbf{s}\rangle\langle\mathbf{s}\vert \mathbf{s}\rangle = \\ & = -\vert \mathbf{s}\rangle, \end{align*} $$ since $\langle\mathbf{s}|\mathbf{s}\rangle = 1$. This is what we expect $U_f$ to do! If we consider a non-solution $\vert \mathbf{x}\rangle$, with $\langle \mathbf{s}\vert \mathbf{x}\rangle = 0$, we find $$ \begin{align*} (I - 2\vert \mathbf{s}\rangle\langle\mathbf{s}\vert ) \vert \mathbf{x}\rangle & = \vert \mathbf{x}\rangle - 2\vert \mathbf{s}\rangle\langle \mathbf{s}\vert \mathbf{x}\rangle = \\ & = \vert \mathbf{x}\rangle - 2 \cdot 0 = \\ & = \vert \mathbf{x}\rangle. \end{align*} $$ This means that the phase is unchanged. It follows that the right-hand side of Eq. $(\ref{u_f})$ acts on basis states precisely as $U_f$, and hence must be equal. ▢

(b) Verify that $U_f$ is unitary directly from Eq. $(\ref{u_f})$.

Hint.

Note that $(\vert \mathbf{s}\rangle \langle \mathbf{s}\vert )^2 = \vert \mathbf{s}\rangle \langle \mathbf{s}\vert $.

Solution.

(b) First, we note that $U_f^\dagger = U_f$, since $I^\dagger = I$ and $(\vert \mathbf{s}\rangle\langle\mathbf{s}\vert )^\dagger = \vert \mathbf{s}\rangle\langle\mathbf{s}\vert $. Then $$ \begin{align*} U_f U_f^\dagger = U_f^2 & = (I - 2\vert \mathbf{s}\rangle\langle\mathbf{s}\vert )^2 = \\ & = I\cdot I - 4\vert \mathbf{s}\rangle\langle\mathbf{s}\vert + 4 (\vert \mathbf{s}\rangle\langle\mathbf{s}\vert )^2 = \\ & = I, \end{align*} $$ using $(\vert \mathbf{s}\rangle \langle \mathbf{s}\vert )^2 = \vert \mathbf{s}\rangle \langle \mathbf{s}\vert $. So, $U_f$, defined as in Eq. $(\ref{u_f})$, is unitary. ▢

Codercise A.2.1 — The matrix form of the oracle

Codercise A.2.2 — The oracle in the circuit

The oracle

Encoding oracles in unitaries