# Show that these two expressions for the oracle transformation are equivalent

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?

• Are you sure that this is even possible? I have a vague memory from long ago that is was not clear how to go from a phase to a normal oracle. Feb 16 '19 at 19:34

## 2 Answers

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$$

• How does this explain how to get from a phase oracle $|x\rangle \to (-1)^{f(x)} |x\rangle$ back to a normal oracle? Your $O_x$ is quite different! Feb 16 '19 at 19:34
• Hi. Thanks for your reply. I don't understand how it matches what we expect from $O_x$ because $O_x$ is not supposed to ever multiply $|i\rangle$ by $-1$.
– Karl
Feb 17 '19 at 11:06
• Yes, but what I need instead is $O_x|i,b\rangle=|i,b\oplus x_i \rangle$. The content of your edit is basically the hypothesis.
– Karl
Feb 17 '19 at 17:29
• You can now see the rest of the answer. It was a this is what we want, write down a formula using O_x" and then check that it did the correct behavior on a basis. Feb 17 '19 at 17:36

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)$$
• Hi and thanks for your reply. Do you think the result is achievable also without using controlled $U$?
– Karl
Feb 17 '19 at 11:11
• And also: control basis Z is $|+\rangle,|-\rangle$ and X is $|0\rangle,|1\rangle$?
– Karl
Feb 17 '19 at 13:07
• @Karl You need the control in order to change the unobservable global phase into an observable relative phase. In practice you won't need to literally control every single operation; there's usually more efficient ways. This is just the simplest way to introduce a control. Feb 17 '19 at 18:04