Show that these two expressions for the oracle transformation are equivalent

Question

Suppose $x \in \{0,1\}^n$. The standard way to make a query is with an oracle $O_x$ that given an input $|i,b \rangle $ returns $|i,b \oplus x_i \rangle$. Via the phase kick-back trick, this can be used to make another type of query $O_{x}^{''}$ such that $O_{x}^{''}|i\rangle=(-1)^{x_i}|i\rangle$. This is easily seen by passing to the $|+\rangle, |- \rangle$ basis. How can it be seen that the converse is true i.e. that with a query of the latter type (and perhaps some ancillary qubit or transformation) one can implement a query of the former type?

Answer 1

If we express the action of $O_x$ on the basis $\mid i, \pm \rangle$ instead of $\mid i , b \rangle$

\begin{eqnarray*} O_x \mid i , + \rangle = \mid i , + \rangle\\ O_x \mid i , - \rangle = (-1)^{x_i} \mid i , - \rangle\\ \end{eqnarray*}

Because we say auxiliary qubits must be started and ended with $0$,

\begin{eqnarray*} O_x'' &=& (1 \otimes S_x H) O_x (1 \otimes H S_x) \end{eqnarray*}

where the $1 \otimes H S_x$ conjugation takes care of turning the auxiliary from $0$ to $-$ and back.

Be careful about what $O_x''$ does. It does the desired $(-1)^{x_i}$ only when the ancilla is in $0$ as it is supposed to be. If the auxiliary is in $1$ instead, $O_x''$ acts like the identity.

\begin{eqnarray*} O_x'' \mid i , 0 \rangle &=& (-1)^{x_i} \mid i, 0 \rangle\\ O_x'' \mid i , 1 \rangle &=& \mid i, 1 \rangle\\ \end{eqnarray*}

Solve for $O_x$

\begin{eqnarray*} O_x &=& (1 \otimes H S_x) O_x'' (1 \otimes S_x H) \end{eqnarray*}

See what it does on $\mid i , + \rangle$ and $\mid i, - \rangle$

\begin{eqnarray*} (1 \otimes H S_x) O_x'' (1 \otimes S_x H) \mid i, + \rangle &=& (1 \otimes H S_x) O_x'' \mid i, 1 \rangle\\ &=& (1 \otimes H S_x) \mid i, 1 \rangle\\ &=& \mid i, + \rangle\\ (1 \otimes H S_x) O_x'' (1 \otimes S_x H) \mid i, - \rangle &=& (1 \otimes H S_x) O_x'' \mid i, 0 \rangle\\ &=& (1 \otimes H S_x) (-1)^{x_i} \mid i, 0 \rangle\\ &=& (-1)^{x_i} \mid i , - \rangle\\ \end{eqnarray*}

This matches with what we wanted for $O_x$ in the first two lines.

Edit:

\begin{eqnarray*} O_x \mid i, + \rangle &=& O_x \frac{1}{\sqrt{2}} (\mid i, 0 \rangle + \mid i, 1 \rangle)\\ &=& \frac{1}{\sqrt{2}} (O_x \mid i, 0 \rangle + O_x \mid i, 1 \rangle)\\ &=& \frac{1}{\sqrt{2}} (\mid i, 0+x_i \rangle + O_x \mid i, 1+x_i \rangle)\\ &=& \mid i, + \rangle \end{eqnarray*}

For the last equality, the two summands either swap or they don't depending on $x_i$. Similarly with -

\begin{eqnarray*} O_x \mid i, - \rangle &=& O_x \frac{1}{\sqrt{2}} (\mid i, 0 \rangle - \mid i, 1 \rangle)\\ &=& \frac{1}{\sqrt{2}} (O_x \mid i, 0 \rangle - O_x \mid i, 1 \rangle)\\ &=& \frac{1}{\sqrt{2}} (\mid i, 0+x_i \rangle - O_x \mid i, 1+x_i \rangle)\\ \end{eqnarray*}

so if $x_i=0$ there is no swap of terms and the result is $\mid i, - \rangle$. If $x_i=1$, there is a swap of terms and the result is $- \mid i, - \rangle$. This can be put together by saying $O_x \mid i, - \rangle = (-1)^{x_i} \mid i , - \rangle$

Answer 2

You are given a quantum circuit for $U$ compiled into the H/CNOT/T gateset. Derive a controlled version of $U$ by adding a control qubit $q$, replacing every H with a controlled H, every CNOT with a CCNOT, and every T with a controlled T. In all cases the new control goes on the $q$.

Recompile the modified gates down into the H/CNOT/T gate set. Prepend and append the circuit with a Hadamard on $q$. You now have a circuit that toggles $q$ when a -1 eigenstate of $U$ is input and leaves $q$ alone when a +1 eigenstate of $U$ is input.

In short:

• Circuit $C$ implements $(-1)^{f(x)}$
• Derive controlled $C$ implementing $(-1)^{q \cdot f(x)}$
• Switch control basis from Z to X, achieving $q \mathrel{\oplus} = f(x)$