5

I am trying to read Nielsen's and Chuang's book on quantum computing and I am having problem understanding Deutsch's algorithm. enter image description here

According to my understanding of the algorithm, the state $|x\rangle$ between the Hadamard gates should not change, however somehow the state of the second qubit affects the first? So from my point of view the measurement after the second Hadamard gate should always be $|0\rangle$. So is $|x\rangle$ after the $U_f$ not the state we used as input? If not then what is the state? Every answer will be appreciated, thanks in advance.

Mariia Mykhailova
  • 9,285
  • 1
  • 13
  • 40
Paul
  • 53
  • 2

1 Answers1

3

This picture can be confusing, since it makes some assumptions that are not clear when you quickly scan through the text.

  1. The picture of the oracle $U_f$ describes its effect on the basis states that go into it, not on arbitrary superposition states. If both $x$ and $y$ are basis states, the oracle will behave exactly as the rectangle says, but the algorithm feeds states in superposition to it, so you need to deduce the effect on a linear combination of basis states as a linear combination of effects on individual basis states.
  2. Since the states fed to the oracle are in superposition, and $|y\rangle = |-\rangle$, phase kickback happens: applying the oracle leaves $|y\rangle$ unchanged and modifies the phase of some of the basis states of $x$ depending on $f(x)$. This allows the final H gate to transform the first qubit into $|0\rangle$ or $|1\rangle$ state depending on the values $f(x)$.

You can read more details on the math behind this picture in this question.

Mariia Mykhailova
  • 9,285
  • 1
  • 13
  • 40