Derivation of QFT product formula

Question

If the quantum fourier transform is defined as follows:

$$ U_{FT} |x\rangle = \frac{1}{2^{n/2}} \sum^{2^n-1}_{y=0} e^{2\pi i x y / 2^n} | y \rangle. $$

We can rewrite the exponential term as:

$$ e^{2\pi i x y / 2^n} = \prod^{n-1}_{l=0}e^{2\pi i x y_l/2^{n-l}}. $$

Using the binary decomposition of $y$. This next step I don't follow, how do use these to derive this new equation for $U_{FT}$?

$$ U_{FT} |x \rangle = \frac{1}{2^{n/2}} \prod^{n-1}_{l=0} \left( |0\rangle + e^{2\pi i x /2^{n-l}}|1\rangle \right). $$

Answer 1

By binary decomposition, we define $y\equiv\sum_{l=0}^{n-1} y_l 2^{-l}$, where $|y\rangle=|y_0...y_{n-1}\rangle$. Putting together your definition of the quantum Fourier transform with this binary decomposition gives \begin{equation} U_{FT}|x\rangle=2^{-n/2}\sum_{y=0}^{2^n-1} \prod_{l=0}^{n-1} e^{2 \pi i x y_l/{2^{n-l}}} |y \rangle=2^{-n/2} \sum_{y_0=0}^{1} ...\sum_{y_{n-1}=0}^1 e^{2 \pi i x y_0/{2^{n}}}...e^{2 \pi i x y_{n-1}/{2^1}} |y_0...y_{n-1} \rangle \end{equation}

Therefore, we perform our sum over each $y_{l}$ from right to left to end up with: \begin{equation} 2^{-n/2}(1|0\rangle+e^{2\pi i x /2^n}|1\rangle)...(1|0\rangle+e^{2\pi i x /2^1}|1\rangle) \end{equation} which is what we want.