Why would matter if $f(0)$ equals to $f(1)$ in Deutsch’s algorithm?

Question

I have a question on the following quantum circuit implementing Deutsch’s algorithm

Why would matter if $f(0)$ equals to $f(1)$? Are they what changes the phase of the first qubit state from + to -? If so, how does it happen?

Answer 1

The problem that Deutsch’s algorithm solves is answering to the following question:

given a single-bit-input/output $f(x)$, is it $balanced$ or $constant$?

There are only 4 possible functions $f(x)$:

• always $0$: it does not matter the input, the result is always $0$
• always $1$: it does not matter the input, the result is always $1$
• identity: if $x=0$, the result is $0$. if $x=1$, the result is $1$
• invert: if $x=0$, the result is $1$. if $x=1$, the result is $0$

The first two cases, $f(x)$ is constant. In the last two, $f(x)$ is balanced.

For the balanced case, notice that $f(0) \neq f(1)$. This is, the output of $f$ is different, depending on the input $x$. Similarly, for the constant case, the input does not matter, therefore $f(0) = f(1)$.

So, full point of Deutsch’s game is to distinguish $f(0) = f(1)$ and $f(0) \neq f(1)$. The way it does it is by having different phases, using a trick known as phase kickback.

Answer 2

"are they what changes the phase of the first qubit state from + to -?" <- yup that's exactly right! I think the best way to see how that happens is to calculate $|\psi_0\rangle$,$|\psi_1\rangle$,$|\psi_2\rangle$ and $|\psi_3\rangle$ by hand for the four different possibilities of $f$ i.e.

scenario 1: $f(0)=0$ and $f(1)=0$
scenario 2: $f(0)=0$ and $f(1)=1$
scenario 3: $f(0)=1$ and $f(1)=0$
scenario 4: $f(0)=1$ and $f(1)=1$

It may be a bit tricky the first time around, but it's worth taking the time!