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

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?

• Hi Cheryl, I see that you study Nielsen and Chuang book. However according to questions you posted, I see that you are somewhat confused by basics concepts in QC. Therefore, I would recommend to start with some lighter literature, for example documentation on IBM Quantum is good place where to start if you want to understand QC well Aug 20 at 6:35
• @MartinVesely Thanks so much for the advice!!! I will look into the documentation on IBM Quantum :) Aug 20 at 13:07

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.

• Very nice explanation! +1 Aug 20 at 6:28

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