0
$\begingroup$

I am really, really beginner to QP. But for some reason, I am studying about Deutsch-Jozsa algorithm, and I have found this article which really helped me with understanding the pipeline of the algorithm.

There's an example that applies $f(x) = x$ to the algorithm, and I nearly understood it. (Honestly, I cannot sure)

So, I tried to apply $f(x)$ = 1 (constant) to the algorithm, but I have a problem. Here's my (wrong) solution to solve it.

  1. Prepare two qubits ― $(1, 1)$ (I'll notate like this since I'm not used to bra-ket notation)
  2. Operate Hadamard transformation to qubits that I prepared:

$$ (\frac{1}{\sqrt{2}}0 - \frac{1}{\sqrt{2}}1)(\frac{1}{\sqrt{2}}0 - \frac{1}{\sqrt{2}}1) = \frac{1}{2}(00-01-10+11) $$

  1. Apply $U_f$ to each qubit that maps $(x, y)$ to $(x, y + f(x))$. (In this case, as this answer mentions, $U_f$ can be simplified as NOT-gate on second qubit.): $$ \frac{1}{2}(01-00-11+10) $$

  2. Send output from Step 3 through Hadamard gate again:

$$\scriptsize \frac{1}{2}((\frac{1}{\sqrt{2}}0 + \frac{1}{\sqrt{2}}1)(\frac{1}{\sqrt{2}}0 - \frac{1}{\sqrt{2}}1)-(\frac{1}{\sqrt{2}}0 + \frac{1}{\sqrt{2}}1)(\frac{1}{\sqrt{2}}0 + \frac{1}{\sqrt{2}}1)-(\frac{1}{\sqrt{2}}0 - \frac{1}{\sqrt{2}}1)(\frac{1}{\sqrt{2}}0 - \frac{1}{\sqrt{2}}1)+(\frac{1}{\sqrt{2}}0 - \frac{1}{\sqrt{2}}1)(\frac{1}{\sqrt{2}}0 + \frac{1}{\sqrt{2}}1)) $$

$$ = \frac{1}{2}(\frac{1}{2}(00-01+10-11)-\frac{1}{2}(00+01+10+11)-\frac{1}{2}(00-01-10+11)+\frac{1}{2}(00+01-10-11)) $$

$$ = \frac{1}{4}(00-01+10-11-00-01-10-11-00+01+10-11+00+01-10-11) $$

$$ = \frac{1}{4}(-11-11-11-11) $$

$$ = -11 ? $$

This result is obviously wrong (..or it isn't?), because the final result is negative, and also a bit to measure (a first bit) is one, even if the function $f(x) = 1$ is constant, and it should be zero.

This solution seems to work well to other functions, e.g. the result of $f(x) = 0$ was $(0, 0)$, and $f(x) = \bar{x}$ was $(1, 0)$.

Where did I went wrong?

$\endgroup$
1
$\begingroup$

In Deutsch's algorithm you prepare the qubits in the $|01\rangle$ state, not $|11\rangle$. Because the initial condition is incorrect, everything follows will produce a different result. The correct steps should be:

  1. Prepare two qubits $(\color{red}{0}, 1)$
  2. Hadamard: $$ \left( \frac1{\sqrt2} 0 \color{red}+ \frac1{\sqrt2} 1 \right)\left( \frac1{\sqrt2} 0 - \frac1{\sqrt2} 1 \right) = \frac12\left(00 -01 \color{red}+10\color{red}-11\right) $$
  3. Apply $U_f$: $$ \frac12\left(01 -00 \color{red}+11\color{red}-10\right) $$
  4. Hadamard: \begin{align} & \frac14\bigl( (0+1)(0-1)-(0+1)(0+1) \color{red}+ (0-1)(0-1) \color{red}- (0-1)(0+1) \bigr) \\ &= \frac14 \bigl( 00-01+10-11-00-01-10-11 \color{red}+00 \color{red}-01 \color{red}- 10 \color{red}+ 11 \color{red}- 00\color{red}- 01 \color{red}+ 10 \color{red}+ 11 \bigr) \\ &= \frac14 \bigl( -4\cdot\color{red}01 \bigr) \\ &= -\color{red}01 \end{align}

So the first bit is indeed zero, showing that $f(x)$ is a constant. The negative sign is just a phase which can be ignored.

$\endgroup$
  • $\begingroup$ Oh, so shameful- I thought first two qubits should be (f(0), f(1)). Thank you very much! $\endgroup$ – suhdonghwi Mar 9 '17 at 22:41
  • $\begingroup$ @Gear The point of the Deutsch-Jozsa is to find out the behavior of $f(x)$ (constant or balancing) by only calling $f(x)$ only once. If we are given $f(0), f(1)$ in the beginning, there is no need to run the algorithm — we already know the answer! :) $\endgroup$ – kennytm Mar 10 '17 at 6:13

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.