# Test Deutsch's algorithm with constant function $f(x) = 1$

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?

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)$$
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.
• @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! :) – kennytm Mar 10 '17 at 6:13