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⟩)$?

Question

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?

Answer 1

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

Answer 2

Where every j mapped like:

So:

notice that:

Keep also this in mind:

Answer 3

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.