Construct a standard oracle using a phase oracle

Question

Suppose $i \in \{0,1\}^n, b \in \{0,1\}$. Given a phase oracle $U_{f} |i\rangle = (-1)^{f(i)} |i\rangle$ and its controlled version $CU_f$, it is possible to construct a standard oracle $U_f' |i\rangle|b\rangle = |i\rangle|b \oplus f(i)\rangle$?

Answer 1

Yes - put the control bit in the state $H\lvert b\rangle$, with $H$ the Hadamard transform. Then, the controlled-$U_f$ gate will transform $(H\lvert b\rangle)\otimes\lvert i\rangle$ into $(H\lvert b\oplus f(i)\rangle)\otimes\lvert i\rangle$, as can be easily seen by checking the cases $b=0$ and $b=1$ separately.

Thus, the desired action is obtained by applying a Hadamard gate before and after the $CU_f$ gate on the control qubit.)

(A boiled-down version of this which carries the essence of the problem would be to "freeze" $\lvert i\rangle$, and only consider the action on the control qubit or $b$ register: Then, $U$ is either $I$ (for $f(i)=0$) or $Z$ (for $f(i)=1$), and you want to convert it to either $I$ or $X$ - this is exactly what the Hadamard achieves.)