# Derivation of QFT product formula

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

• Around here "QFT" usually stands for "Quantum Field Theory." You might want to try this question (and similar questions) at the Quantum Computing Stack Exchange: quantumcomputing.stackexchange.com
– hft
Commented May 8, 2023 at 23:11
• @hft Thank-you, I will bare this in mind for future questions :) Commented May 8, 2023 at 23:13

## 1 Answer

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

Therefore, we perform our sum over each $$y_{l}$$ from right to left to end up with: $$$$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)$$$$ which is what we want.

• I fixed the definition of $U_{FT}$ in my question, feel free to update your answer. Thank-you Commented May 8, 2023 at 23:07