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$ – Norbert Schuch Feb 16 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 ancillas 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 ancilla 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 ancilla 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$

  • $\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$ – Norbert Schuch Feb 16 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 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 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 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 at 11:11
  • $\begingroup$ And also: control basis Z is $|+\rangle,|-\rangle$ and X is $|0\rangle,|1\rangle$? $\endgroup$ – Karl Feb 17 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$ – Craig Gidney Feb 17 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.