# How to show that the QFT satisfies $\frac1{\sqrt N}\sum_j\prod_le^{2\pi i j_l k/2^l}|j_1...j_n⟩=\bigotimes_l \frac1{\sqrt2}(|0⟩+e^{2\pi i k/2^l}|1⟩)$?

I'm reading Ronald de Wolf's lecture notes, and in chapter 4.5 he writes that

$$\frac{1}{\sqrt N}\sum\limits_{j=0}^{N-1}\prod\limits_{l=1}^{n}e^{2\pi i j_l k / 2^l}|j_1...j_n\rangle = \bigotimes\limits_{l=1}^{n} \frac{1}{\sqrt 2}\left(|0\rangle + e^{2\pi i k/2^l} |1\rangle\right).$$

Now it is not clear to me how we arrive from the left hand side to the right hand side. Can someone give a hint?

• You might want to check out section 5.1 of Nielsen and Chuang's "Quantum Computation and Quantum Information" (there are pdf's circulating freely if you just google it) Jan 19 at 19:10
• – glS
Jan 21 at 14:00

We can transform the second expression as follows

\begin{align} \bigotimes_{l=1}^{n} \frac{1}{\sqrt 2}\left(|0\rangle + e^{2\pi i k/2^l} |1\rangle\right) &=\frac{1}{\sqrt{2^n}}\bigotimes_{l=1}^{n}\left(e^{2\pi i\cdot 0 \cdot k/2^l}|0\rangle + e^{2\pi i\cdot 1 \cdot k/2^l} |1\rangle\right)\tag1\\ &=\frac{1}{\sqrt{2^n}}\bigotimes_{l=1}^{n}\sum_{m=0}^1e^{2\pi i\cdot m \cdot k/2^l}|m\rangle\tag2\\ &=\frac{1}{\sqrt{2^n}}\sum_{j_1=0}^1\sum_{j_2=0}^1\dots\sum_{j_n=0}^1 \bigotimes_{l=1}^{n}e^{2\pi i\cdot j_l \cdot k/2^l}|j_l\rangle\tag3\\ &=\frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n-1}\bigotimes_{l=1}^{n}e^{2\pi i\cdot j_l \cdot k/2^l}|j_l\rangle\tag4\\ &=\frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n-1}\prod_{l=1}^{n}e^{2\pi i\cdot j_l \cdot k/2^l}\bigotimes_{l=1}^{n}|j_l\rangle\tag5\\ &=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\prod_{l=1}^{n}e^{2\pi i j_l k / 2^l}|j_1...j_n\rangle\tag6 \end{align}

where $$(3)$$ follows from the distributive law and in $$(4)$$ we combine $$n$$ binary variables $$j_l=0,1$$ into one variable $$j=0\dots 2^n-1$$ with $$j_l$$ refering to the $$l$$th bit of $$j$$.

Each of the $$N = 2^n$$ terms on the left-hand side is determined by the unique choice of $$j_1$$, $$j_2$$, $$\dots$$, $$j_n$$ in $$\{0, 1\}$$. Similarly, each term on the right-hand side as we write out the tensor product is determined by the choice of single one of $$|0>$$ or $$\exp (2 \, \pi \, i \, k \, / \, 2^l) \,|1>$$ that we make from each parenthesis pair -- quite similar to writing out $$(a_1 + b_1) (a_2 + b_2) \cdots (a_n + b_n)$$. The last step is to observe that $$|0>$$ is just $$\exp (2 \, \pi \, i \, j_l \, k \, / \, 2^l) \,|0>$$ with $$j_l$$ set to $$0$$, and $$\exp (2 \, \pi \, i \, k \, / \, 2^l) \,|1>$$ is likewise $$\exp (2 \, \pi \, i \, j_l \, k \, / \, 2^l) \,|1>$$ with $$j_l$$ set to $$1$$. Hope this helps.

Where every j mapped like:

So:

notice that:

Keep also this in mind: