# How to apply QFT to a quantum state in superposition?

Given the following quantum state:

$$\frac{1}{2}(|0000\rangle + |0100\rangle + |1000\rangle + |1100\rangle)$$

How do I apply a QFT (given by the formula below) to that state in superposition?

$$QFT_n|j\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_{N}^{j \times k} |k\rangle$$ where $$N = 2^n$$

QFT on any Superposition (Linear Combination of Basis States) can be applied using Linearity.

$$QFT_n|\psi\rangle = \sum_{k=0}^{2^n-1}a_kQFT_n|k\rangle$$

Hence $$QFT_4|\psi\rangle$$ where $$|\psi\rangle = \frac{1}{2}(|0000\rangle + |0100\rangle + |1000\rangle + |1100\rangle)$$ is $$QFT_4(\frac{1}{2}(|0000\rangle + |0100\rangle + |1000\rangle + |1100\rangle)) \\ = \frac{1}{2}(QFT_4|0000\rangle + QFT_4|0100\rangle + QFT_4|1000\rangle + QFT_4|1100\rangle) \\ = \frac{1}{2}(QFT_4|0\rangle + QFT_4|4\rangle + QFT_4|8\rangle + QFT_4|12\rangle) \\ = \frac{1}{2}(\frac{1}{4}\sum_{k=0}^{15}\omega_N^{k\times 0}|k\rangle + \frac{1}{4}\sum_{k=0}^{15}\omega_N^{k\times 4}|k\rangle + \frac{1}{4}\sum_{k=0}^{15}\omega_N^{k\times 8}|k\rangle + \frac{1}{4}\sum_{k=0}^{15}\omega_N^{k\times 12}|k\rangle ) \\ =\frac{1}{8}\sum_{k=0}^{15}(\omega_N^{k\times 0}+\omega_N^{k\times 4}+\omega_N^{k\times 8}+\omega_N^{k\times 12})|k\rangle$$

Here $$\omega_N = e^{\frac{i2\pi}{2^4}} = e^{\frac{i\pi}{8}}$$, therefore $$\omega_N^0 = 1$$, $$\omega_N^4 = e^{\frac{i\pi}{2}} = i$$, $$\omega_N^8 = e^{i\pi}=-1$$ and $$\omega_N^{12} = e^{\frac{i3\pi}{2}}=-i$$.

Thus $$QFT_4|\psi\rangle$$ is

$$QFT_n|\psi\rangle = \frac{1}{8}\sum_{k=0}^{15}(\omega_k^{k\times 0}+\omega_k^{k\times 4}+\omega_k^{k\times 8}+\omega_k^{k\times 12})|k\rangle \\ = \frac{1}{8}\sum_{k=0}^{15}(1^{k}+i^{k}+(-1)^{k}+(-i)^{k})|k\rangle$$

This sum $$(1^{k}+i^{k}+(-1)^{k}+(-i)^{k})$$ is $$4$$ when $$k$$ divides 4 otherwise its 0.

Thus $$QFT_4|\psi\rangle$$ is

$$QFT_n|\psi\rangle = \frac{1}{8}\sum_{k'=0}^{3}(4)|4k'\rangle \\ = \frac{1}{2}(|0\rangle + |4\rangle + |8\rangle + |12\rangle) \\ = \frac{1}{2}(|0000\rangle + |0100\rangle + |1000\rangle + |1100\rangle)$$

Here I noticed that our initial state is an eigenvector of $$QFT_4$$ with an eigenvalue $$1$$. If I noticed this before I could have directly written the answer.

Nonetheless, I hope this helps.

• Very well explained, thank you!
– user12136
Aug 2 '20 at 19:00