mjhjmtu

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^''|irangle=(-1)^x_i|irangle$. 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?

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

begineqnarray*
O_x mid i , + rangle = mid i , + rangle\
O_x mid i , - rangle = (-1)^x_i mid i , - rangle\
endeqnarray*

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

begineqnarray*
O_x'' &=& (1 otimes S_x H) O_x (1 otimes H S_x)
endeqnarray*

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.

begineqnarray*
O_x'' mid i , 0 rangle &=& (-1)^x_i mid i, 0 rangle\
O_x'' mid i , 1 rangle &=& mid i, 1 rangle\
endeqnarray*

Solve for $O_x$

begineqnarray*
O_x &=& (1 otimes H S_x) O_x'' (1 otimes S_x H)
endeqnarray*

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

begineqnarray*
(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\
endeqnarray*

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

Edit:

begineqnarray*
O_x mid i, + rangle &=& O_x frac1sqrt2 (mid i, 0 rangle + mid i, 1 rangle)\
&=& frac1sqrt2 (O_x mid i, 0 rangle + O_x mid i, 1 rangle)\
&=& frac1sqrt2 (mid i, 0+x_i rangle + O_x mid i, 1+x_i rangle)\
&=& mid i, + rangle
endeqnarray*

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

begineqnarray*
O_x mid i, - rangle &=& O_x frac1sqrt2 (mid i, 0 rangle - mid i, 1 rangle)\
&=& frac1sqrt2 (O_x mid i, 0 rangle - O_x mid i, 1 rangle)\
&=& frac1sqrt2 (mid i, 0+x_i rangle - O_x mid i, 1+x_i rangle)\
endeqnarray*

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$

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 mathreloplus = f(x)$