Suppose I have an oracle $U_f$ that maps $|x\rangle \mapsto (-1)^{f(x)}|x\rangle$ where $f : \{0,\dots,N\} \to \{0,1\}$ is such that $f(0)=0$. I want to show that I can implement the oracle $|x\rangle|b\rangle \mapsto |x\rangle|b \oplus f(x)\rangle$ using just one application of $U_f$.

I figured a way to do this but by using a controlled version of $U_f$. The following circuit does the trick:


However what if I don't have access to the controlled version of $U_f$? Can I still do it? Does the fact that $f(0)=0$ help here?


1 Answer 1


Make a temporary ancillary copy conditional on the control, and apply the operation to the copy. This only applies the varying -1 factors if the control is ON, not OFF, which gives the necessary phase kickback.


enter image description here

The $f(0) = 0$ requirement is avoided by classically computing $f(0)$ and applying a $Z$ to the control if it's 1 instead of 0.

  • $\begingroup$ Thanks! It's all clear now! $\endgroup$ Commented Sep 3, 2022 at 23:21

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.