5
$\begingroup$

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?

  • 0
    Also you're still using `\mid` instead of `|`, as Michael pointed out in [this question](http://math.stackexchange.com/questions/181402). `\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.2012-08-13

1 Answers 1

2

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$.