# Quantum Information: Deutsch-Jozsa Algorithm

There is a step in the construction of this algorithm which I'm not understanding:

$\displaystyle \left[\sum_x \frac{| x \rangle}{\sqrt{2^n}}\right]\left[\frac{ | 0 \rangle -| 1 \rangle }{\sqrt{2}} \oplus | f(x) \rangle\right]=\sum_x \frac{(-1)^{f(x)} | x \rangle }{\sqrt{2^n}}\left(\frac{| 0 \rangle - |1 \rangle}{\sqrt{2}}\right)$

where $f:\{0,1\}^n \to \{0,1\}$.

I don't see how they are equal, and I believe part of my confusion is on how $\oplus$ work for $2$-qubits. $\oplus$ denotes addition $\!\!\!\!\mod 2$... so does it work in each element separately?

-
You can get the right formating for braces and parentheses enclosing big stuff by using \left and \right in front of them. –  joriki Aug 13 '12 at 21:16
Also you're still using \mid instead of |, as Michael pointed out in this question. \mid is good for the "divides" bar, but not as part of a bra or ket -- as you can see, it produces too much spacing in that case. –  joriki Aug 13 '12 at 21:21

We can best write the step in question as $$\frac{1}{\sqrt{2^{n+1}}} \sum_x|x\rangle\left(|f(x)\rangle - |1 \oplus f(x) \rangle \right) = \frac{1}{\sqrt{2^{n+1}}} \sum_x(-1)^{f(x)}|x\rangle \left(|0\rangle - |1\rangle \right).$$ $f(x)$ is equal to either $0$ or $1$. If $f(x)=0$, then $$|f(x)\rangle - |1 \oplus f(x) \rangle=|0\rangle - |1\oplus 0 \rangle = |0\rangle - |1 \rangle.$$ If $f(x)=1$, then $$|f(x)\rangle - |1 \oplus f(x) \rangle=|1\rangle - |1\oplus 1 \rangle = |1\rangle - |0 \rangle = (-1)\left(|0\rangle - |1 \rangle\right).$$ So, $(-1)^{f(x)}\left(|0\rangle - |1 \rangle\right)$ is another way of writing $|f(x)\rangle - |1 \oplus f(x) \rangle$.