Let $\hat{U}$ and $\hat{D}$ refer to operators which act not only on the query register but on the auxiliary qubit, dropping the $f$ subscript to declutter our notation:

To start with, let's define our new oracle gate $\hat{U}$. It will act in an entirely classical way on bit strings, defined by $$ \hat{U} \vert \mathbf{x}, y\rangle = \vert \mathbf{x}, y \oplus f(\mathbf{x})\rangle. $$ Here, $\oplus$ just means addition modulo $2$, so $1 \oplus 1 = 0$. In the next exercise, you'll use this to implement the phase oracle. --- ***Exercise G.3.1.*** Show that $\hat{U} (\vert \mathbf{x}\rangle \otimes \vert -\rangle) = (-1)^{f(\mathbf{x})}\vert \mathbf{x}\rangle \otimes \vert -\rangle$.

Solution.

First, let's apply $\hat{U}$: $$ \begin{align*} \hat{U} (\vert \mathbf{x}\rangle \otimes \vert-\rangle) & = \frac{\hat{U}\vert \mathbf{x}0\rangle - \hat{U}\vert \mathbf{x}1\rangle}{\sqrt{2}} \\ & = \frac{\vert \mathbf{x}, 0 \oplus f(\mathbf{x})\rangle - \vert \mathbf{x}, 1\oplus f(\mathbf{x})\rangle}{\sqrt{2}}. \end{align*} $$ If $f(\mathbf{x}) = 0$, then $y \oplus f(\mathbf{x}) = y$, and the state is left alone. However, if $f(\mathbf{x}) = 1$, then $1$ and $0$ swap roles. This has the effect of multiplying the state by an overall phase $(-1)$! Thus, we multiply the state by $(-1)^{f(\mathbf{x})}$, so this has the same effect as applying the oracle $U$ (which does not involve the auxiliary qubit) to the query register. ▢

--- We haven't yet explained how to implement $\hat{U}$ at the circuit level. We'll illustrate by considering a simple (and therefore bad!) secret combination for our lock: $\mathbf{s} = \mathbf{1}$, where every element is $1$. In this case, we only want to flip the phase of $\vert \mathbf{x}\rangle$ if every bit has value $1$. This can be achieved very simply using a multi-controlled $X$ gate. This is like the usual CNOT gate, except with multiple control qubits. In the simplest case, it acts on classical basis states (for the combined system of query register and an auxiliary qubit) as follows: $$ \text{C}^{(n)}\text{NOT}\vert \mathbf{x}, y\rangle = \begin{cases} \vert \mathbf{x}\rangle \otimes X\vert y\rangle & \text{ if } \mathbf{x} = \mathbf{1} \\ \vert \mathbf{x}, y\rangle & \text{otherwise.} \end{cases} $$ Here is a picture of the circuit:

The top group of $n$ qubits are the control bits, and the qubit at the bottom is the target. Now, remember that $\vert -\rangle$ is an eigenstate of the Pauli $X$ gate: $$ X \vert -\rangle = \frac{X\vert 0\rangle - X\vert 1\rangle}{\sqrt{2}} = \frac{\vert 1\rangle - \vert 0\rangle}{\sqrt{2}} = -\vert -\rangle. $$ It follows that, for this choice of secret combination, $$ \hat{U}\vert \mathbf{x}, y\rangle = \text{C}^{(n)}\text{NOT}\vert \mathbf{x}, y\rangle. $$ Since these operators agree on basis states, they agree on all states, so the oracle is just the C${}^{(n)}$NOT gate! In the next couple of exercises, you can see how to extend this to other solutions. We can extend this iterated CNOT gate to be controlled on an arbitrary bit string $\mathbf{s}$. Let's call this gate $C^{(\mathbf{s})}X$, so its action is $$ C^{(\mathbf{s})}X\vert \mathbf{x}, y\rangle = \begin{cases} \vert \mathbf{x}\rangle \otimes X\vert y\rangle & \text{ if } \mathbf{x} = \mathbf{s} \\ \vert \mathbf{x}, y\rangle & \text{otherwise.} \end{cases} $$ --- ***Exercise G.3.2.*** Show how to implement an oracle for an arbitrary solution $\mathbf{s}$ using a multi-controlled $X$ gate, and draw the circuit diagram (schematically).

Solution.

To obtain the oracle associated with a solution $\mathbf{s}$, we simply use $C^{(\mathbf{s})}X$ instead of $C^{(n)}X$. Let's check first that this acts correctly on the solution state: $$ \begin{align*} C^{(\mathbf{s})}X(\vert \mathbf{s}\rangle \otimes \vert -\rangle) & = \vert \mathbf{s}\rangle \otimes X\vert -\rangle \\ & = -\vert \mathbf{s}\rangle \otimes \vert -\rangle. \end{align*} $$ On the other hand, if $\mathbf{x}\neq\mathbf{s}$, it does nothing. So in general, $$ C^{(\mathbf{s})}X(\vert \mathbf{x}\rangle \otimes \vert -\rangle) = (U \vert \mathbf{x}\rangle) \otimes \vert -\rangle. $$ The circuit diagram is then

Recall that white nodes mean the control bit is ``0`` rather than ``1``. Here, we have used white and black nodes to indicate an arbitrary control string. ▢

Codercise G.3.1 - Building the oracle with Multi-controlled gates

Codercise G.3.2 - Building the diffusion operator

Codercise G.3.3 - Improving the circuit

Storing the phase

Implementing the phase oracle

Implementing the diffusion operator