# QFT - Quantum Fourier Transform
For $|a\rangle$ an arbitrary element of the standard basis $\{|0\rangle,...,|N-1\rangle\}$ , QFT can be described as
$
\text{QFT}_{N}|a\rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\bigg(\exp\big( \frac{2\pi i}{N}\big)^a\bigg)^x|x\rangle
$
where $N=2^n$.
This is similar to standard discrete Fourier transform for dimension $2^n$ and $|a\rangle$ viewed as a one hot vector dimension of $2^n$ with 1 in the $a$-th slot.
## Example $n=2$:
computing tensor product of a bit string $a$ where $|0\rangle=e_1$ and $|1\rangle=e_2$ you get this one hot vector e.g., $|10\rangle =|1\rangle\otimes|0\rangle=e_2\otimes e_1=(0,1)\times(1,0)=(0,0,1,0) $
Let $\gamma= e^{\frac{2\pi i}{4}}$ be the 4-th root of unity in the complex field.
$
\text{QFT}_{4}|10\rangle =\frac{1}{\sqrt 4}\bigg(
(\gamma^0)^2|00\rangle+(\gamma^1)^2|01\rangle)+(\gamma^2)^2|10\rangle)+(\gamma^3)^2|11\rangle\bigg)
$
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$ and $a=a_n2^{n-1}+a_{n-1}2^{n-2}+\cdots+a_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:
- integer powers of exponent are equal to 1 so only the fraction part of $a/2^i$ are considered in the exponent.
- $2\pi i \cdot 0.a_na_{n-1}...a_1=2\pi i (\frac{a_n}{2}+\frac{a_{n-1}}{2^2}+\cdots+\frac{a_1}{2^n})$ so $\exp\big(2\pi i (0.a_na_{n-1}...a_1)$ can be computed by composition of rotations of $1\in\mathbb{C}$ by $\frac{2\pi i}{2^k}$ controlled by $a_k$.
Going over all $2^n$ possible binary values of $x_1,...,x_n$ is equivalent to choosing or not choosing each exponent term. We get,
$
\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}
$
Example $n=2$:
$
\begin{align}
&\bigg(|0\rangle+\exp\big(2\pi i (0.a_1)\big)|1\rangle\bigg)\otimes\bigg(|0\rangle+\exp\big(2\pi i (0.a_2a_1)\big)|1\rangle\bigg) = \\
&\bigg(\exp\big(2\pi i (0.a_1)\cdot 0\big)|0\rangle+\exp\big(2\pi i (0.a_1)\cdot 1\big)|1\rangle\bigg)\otimes\bigg(\exp\big(2\pi i (0.a_2a_1)\cdot 0|0\rangle+\exp\big(2\pi i (0.a_2a_1)\cdot 1\big)|1\rangle\bigg) = \\
&=
\exp\big(2\pi i \cdot0.a_1\cdot0\big)\exp\big(2\pi i \cdot 0.a_2a_1\cdot 0\big)\ket0\ket0+\\
& +\exp\big(2\pi i \cdot0.a_1\cdot1\big)\exp\big(2\pi i \cdot 0.a_2a_1\cdot 0\big)\ket0\ket1+\\
& +\exp\big(2\pi i \cdot0.a_1\cdot0\big)\exp\big(2\pi i \cdot 0.a_2a_1\cdot 1\big)\ket1\ket0+\\
& +\exp\big(2\pi i \cdot0.a_1\cdot1\big)\exp\big(2\pi i \cdot 0.a_2a_1\cdot 1\big)\ket1\ket1\\
\end{align}
$
The QFT is computed using [[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
2) 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)$ .
3) The results of the QFT is stored in $|a_1\rangle\otimes\cdots\otimes|a_n\rangle$ where $|a_k\rangle =\frac{1}{\sqrt 2}\bigg(|0\rangle+\exp\big(2\pi i (0.a_ka_{k-1}...a_1)\big)|1\rangle\bigg)$
The complete circuit is as below.
![[Pasted image 20260614152438.png]]
note
- the $\text{QFT}$ result is stored as the tensor of the $a_i