Question regarding a step in the computation of $QFT_{16} \frac{1}{2} ( \mid 1 \rangle + \mid 5 \rangle + \mid 9 \rangle + \mid 13 \rangle )$

Question

In clas we computed the Quantum Fourier Transformation $QFT_{16} \frac{1}{2} ( \mid 1 \rangle + \mid 5 \rangle + \mid 9 \rangle + \mid 13 \rangle )$. We started with the following computation:

\begin{align} \text{QFT}&_{16}{\frac{1}{2} \left( \mid 1 \rangle + \mid 5 \rangle + \mid 9 \rangle + \mid 13 \rangle \right)} \\ &= \frac{1}{8} \sum_{k=0}^{15} \omega_{16}^{k} \left( 1 + \omega_{16}^{4k} + \omega_{16}^{8k} +\omega_{16}^{12k} \right) \mid k \rangle \\ &= \frac{1}{8} \sum_{k=0}^{15} \omega_{4}^{k} \left( 1 + \omega_{4}^{k} + \omega_{4}^{2k} +\omega_{4}^{3k} \right) \mid k \rangle \end{align}

However, I do not understand the second equation. I know that $\omega_{n}^{2k} = \omega_{n/2}^k$, but I do not understand why $\omega_{16}^{k}$ becomes $\omega_{4}^{k}$. Could you please explain this to me?

Remark: $\omega_n$ denotes the $n$-th root of unity.

Answer 1

We have: $$\omega_n^k=\mathrm{e}^{\frac{2\mathrm{i}\pi k}{n}}$$ As such, for any $p\in\mathbb{N}^*$: $$\omega_n^{pk}=\mathrm{e}^{\frac{2\mathrm{i}\pi pk}{n}}=\mathrm{e}^{\frac{2\mathrm{i}\pi k}{\frac{n}{p}}}=\omega_{\frac{n}{p}}^k$$ Thus, we have: $$\omega_{16}^{4k}=\omega_{\frac{16}{4}}^{k}=\omega_{4}^{k}$$ The same formula can be applied to the two other terms to find the correct result.