# QFT - Quantum Fourier Transform
For $|a\rangle$ an arbitrary element of the standard basis $\{|0\rangle,...,|2^n-1\rangle\}$ (seen as a one hot vector dimension of $2^n$ with 1 in the $a$-th slot), QFT can be described as
$
\text{QFT}|a\rangle = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\exp\bigg(2\pi i \frac{ax}{2^n}\bigg)|x\rangle
$
This is similar to standard discrete Fourier transform for dimension $2^n$.
The fact that DFT matrix is unitarian suggest that we can construct $\text{QFT}$ as a quantum circuit.
For specific $x=x_n2^{n-1}+x_{n-1}2^{n-2}+\cdots+x_1 2^0$ , we have
$
\begin{align}
\exp\bigg(2\pi i \frac{ax}{2^n}\bigg)&=\exp\bigg(2\pi i (\frac{ax_n}{2}+\frac{ax_{n-1}}{4}\cdots+\frac{ax_1}{2^n})\bigg)\\
&=\exp\bigg(2\pi i \frac{ax_n}{2}\bigg)\cdots\exp\bigg(2\pi i \frac{ax_1}{2^n}\bigg) \\
&=\exp\big(2\pi i (0.a_1) x_n\big)\cdots\exp\big(2\pi i(0.a_na_{n-1}...a_1) x_1\big) \\
\end{align}
$
note: that integer powers of exponent are equal to 1 so only fractions of $a$ appear in the exponent.
Going over $2^n$ possible binary values of $x_1,...,x_n$ is equivalent to
$
\begin{align}
\text{QFT}|a\rangle &= \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\exp\bigg(2\pi i \frac{ax}{2^n}\bigg)|x\rangle \\
&= \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\Bigg(\exp\bigg(2\pi i (0.a_1) x_n\bigg)\cdots\exp\bigg(2\pi i(0.a_na_{n-1}...a_1) x_1\bigg) \Bigg)|x\rangle \\
&=\frac{1}{\sqrt{2^n}}\bigg(|0\rangle+\exp\big(2\pi i (0.a_1)\big)|1\rangle\bigg)\otimes\cdots\otimes\bigg(|0\rangle+\exp\big(2\pi i (0.a_na_{n-1}...a_1)\big)|1\rangle\bigg)
\end{align}
$
The QFT is computed using [[Controlling a gate (controlled gate)|controlled phase-gate]] $R_k\big(\alpha|0\rangle+\beta|1\rangle, |c\rangle\big)=\begin{cases}\alpha|0\rangle+\exp(2\pi i/2^k)\beta|1\rangle & ,c=1\\\alpha|0\rangle+\beta|1\rangle &, c=0 \end{cases}$ for example to compute $|0\rangle+\exp\big(2\pi i (0.a_na_{n-1}...a_1)|1\rangle$ we compute the following circuit:
$R_n\Bigg(\cdots R_3\bigg(R_{2}\big(H|a_n\rangle,|a_{n-1}\rangle\big), |a_{n-2}\rangle\bigg)\cdots , |a_1\rangle\Bigg)
=|0\rangle+\exp\big(2\pi i (0.a_na_{n-1}...a_1)|1\rangle$
Note that we first compute $H|a_n\rangle$ to generate the super position $\frac{1}{\sqrt 2}(|0\rangle+(-1)^{a_n}|1\rangle)=\frac{1}{\sqrt 2}(|0\rangle+\exp(2\pi i \cdot 0.a_n)|1\rangle)$ .
The complete circuit is as below.
![[Pasted image 20260614152438.png]]
note that the $\text{QFT}$ result is stored as the tensor of the $a_i