0
$\begingroup$

I have a question on the following quantum circuit implementing Deutsch’s algorithm enter image description here

enter image description here

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?

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Aug 20 at 6:35
  • 1
    $\begingroup$ @MartinVesely Thanks so much for the advice!!! I will look into the documentation on IBM Quantum :) $\endgroup$
    – Alexia.
    Aug 20 at 13:07
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Very nice explanation! +1 $\endgroup$ Aug 20 at 6:28
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.