I'm trying to understand quantum parallelism ideas leading the Deutsch's algorithm. The circuit in question is
I understand that we end up with $$|\psi_3 \rangle = \pm | f(0) \oplus f(1) \rangle \left[ \frac{|0 \rangle - |1 \rangle }{\sqrt{2} } \right].$$ Then by measuring the first qubit we can determine $f(0) \oplus f(1),$ and the claim is that we have thus determined a global property of $f(x),$ namely $f(0) \oplus f(1),$ using only one evaluation of $f(x)$.
I have three questions:
- Where does that single evaluation of $f(x)$ actually occur? Is it in the construction of $U_f$?
- What is $U_f$ in this case? I realize it depends on $f$, but how can we build it using at most one evaluation of $f$?
- In the circuit above, the $x$ input to $U_f$ is $(|0\rangle + |1 \rangle)/\sqrt{2})$. What does it mean to apply (classical) $f$ to this $x$?
I realize all 3 of these questions are probably tied up somehow.