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


1 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!

  • $\begingroup$ This was very helpful, thank you so much for your time $\endgroup$
    – user918212
    Feb 12, 2020 at 14:46

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.