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?

  • $\begingroup$ 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. $\endgroup$ Feb 16 '19 at 19:34

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.


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

  • 1
    $\begingroup$ 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! $\endgroup$ Feb 16 '19 at 19:34
  • $\begingroup$ 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$. $\endgroup$
    – Karl
    Feb 17 '19 at 11:06
  • $\begingroup$ 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. $\endgroup$
    – Karl
    Feb 17 '19 at 17:29
  • $\begingroup$ 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. $\endgroup$
    – AHusain
    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)$
  • $\begingroup$ Hi and thanks for your reply. Do you think the result is achievable also without using controlled $U$? $\endgroup$
    – Karl
    Feb 17 '19 at 11:11
  • $\begingroup$ And also: control basis Z is $|+\rangle,|-\rangle$ and X is $|0\rangle,|1\rangle$? $\endgroup$
    – Karl
    Feb 17 '19 at 13:07
  • 1
    $\begingroup$ @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. $\endgroup$ Feb 17 '19 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.