Understanding Steps in Deutsch's Algorithm

Question

I am currently working my way through the book Quantum Computation and Quantum Information by Chuang and Nielsen. So far it has been a joy to read, however I am hung up on a couple aspects of quantum parallelism and Deutsch's algorithm that I cannot understand as they are described in the text. My two questions are as follows.

---

First, in concern with quantum parallelism, suppose we are given the function $f(x): \{0, 1\} \rightarrow \{0, 1\}$, and the unitary map $$ U_f:|x, y\rangle \rightarrow |x, y\oplus f(x)\rangle $$ Now suppose we feed $U_f$ the input $|+\rangle |0\rangle$. Then as output we obtain the interesting state $$ \frac{1}{\sqrt{2}}(|0, f(0)\rangle + |1, f(1) \rangle) $$ which clearly exhibits quantum parallelism as $f(0)$ and $f(1)$ are simultaneously evaluated. What I am unclear on is exactly how to arrive at the above output state via computation: how do you compute $|0 \oplus f(|+\rangle)\rangle$, or just $f(|+\rangle)$? And how does this computation lead to our output state? What if we had more than one qubit in our input register such as the state $|++\rangle$, how would you compute $f(|++\rangle)$?

---

My next question follows from the first. In the text, the authors say: applying $U_f$ (as defined above) to the state $|x\rangle \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ gives the state $$ (-1)^{f(x)}|x\rangle \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) $$ How was this result obtained (what computation is needed to obtain it?), where did the term $(-1)^{f(x)}$ come from?

As a consequence of this, they say that inputting the state $|+-\rangle$ into $U_f$ leaves us with the two possibilities of $\pm |+-\rangle$ if $f(0)=f(1)$ or $\pm |--\rangle$ if $f(0) \not= f(1)$. Similarly this doesn't make sense, how can I carry out the computation to show this?

Thank you all for the time and help, I will upvote partial answers (anwering one of the above questions for example).

Answer 1

To answer your first question, the quantum oracles are defined by their effect on the basis states $|0\rangle$ and $|1\rangle$, and if the oracle has to be computed on a superposition of basis states, its effects are expressed using the fact that the oracle is a linear transformation. This means that you never compute $f(|+\rangle)$; instead, to compute the result of applying $U_f$ to a state $|+\rangle|0\rangle$, you'd perform the following steps:

$$U_f|+\rangle|0\rangle = U_f \frac{1}{\sqrt2}(|00\rangle + |10\rangle) = \frac{1}{\sqrt2}(U_f|00\rangle + U_f|10\rangle) = \frac{1}{\sqrt{2}}(|0, f(0)\rangle + |1, f(1) \rangle)$$

---

Your next question can be answered using exactly the same logic: take the input state, represent it as a linear combination of basis states, apply the oracle to each basis state separately and look at the result to write it more concisely. Thus, if $x$ is a basis state 0 or 1, you'll get

$$U_f|x\rangle \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = \frac{1}{\sqrt{2}}(U_f|x,0\rangle - U_f|x,1\rangle) =$$ $$ = \frac{1}{\sqrt{2}}(|x,f(x)\rangle - |x,1 \oplus f(x)\rangle) = |x\rangle\frac{1}{\sqrt{2}}(|f(x)\rangle - |1 \oplus f(x)\rangle)$$

Now you consider options:

• if $f(x) = 0$, the state of the second qubit is $\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = |-\rangle$,
• if $f(x) = 1$, the state of the second qubit is $\frac{1}{\sqrt{2}}(|1\rangle - |0\rangle) = -|-\rangle$

which finally you can write shorter as $(-1)^{f(x)}|x\rangle \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

---

The same math applies to the final portion of your question, when $U_f$ is applied to a $|+\rangle|-\rangle$ state. For educational purposes I would recommend you do go through the steps yourself - you should have all the tool for that now!