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


1 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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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