# Understanding Steps in Deutsch's Algorithm

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

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!

• This was very helpful, thank you so much for your time – GEG Feb 12 at 14:46