# How to intuitively interpret the QFT of a state?

According to wikipedia,

In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform.

Given the ubiquitousness of QFT in quantum algorithms, I was wondering what the intuitive meaning of the QFT of a state is?

The discrete Fourier transform acts on a vector $$(x_0, ..., x_{N-1})$$ and maps it to the vector $$(y_0, ..., y_{N-1})$$ according to the formula

$$y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_N^{jk}$$

where $$\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$$.

Similarly, the quantum Fourier transform acts on a quantum state $$\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$$ and maps it to the quantum state $$\vert Y\rangle = \sum_{k=0}^{N-1} y_k \vert k \rangle$$ according to the formula

$$y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_N^{jk}$$

with $$\omega_N^{jk}$$ defined as above. Note that only the amplitudes of the state were affected by this transformation.

This can also be expressed as the map:

$$\vert j \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk} \vert k \rangle$$

Or the unitary matrix:

$$U_{QFT} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \sum_{k=0}^{N-1} \omega_N^{jk} \vert k \rangle \langle j \vert$$

The quantum Fourier transform (QFT) transforms between two bases, the computational (Z) basis, and the Fourier basis. The H-gate is the single-qubit QFT, and it transforms between the Z-basis states $$|0\rangle$$ and $$|1\rangle$$ to the X-basis states $$|{+}\rangle$$ and $$|{-}\rangle$$. In the same way, all multi-qubit states in the computational basis have corresponding states in the Fourier basis. The QFT is simply the function that transforms between these bases.

$$|\text{State in Computational Basis}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{State in Fourier Basis}\rangle$$

$$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$