# Approximating QFT using only sub-additivity and only $O(n\log n)$ quantum gates

In the original QFT, there are $$O(n^2)$$ quantum gates, and it looks like this:

Where the controlled version of $$R_k = \begin{pmatrix} 1 & 0\\ 0 & e^{\frac{2\pi k}{2^k}} \end{pmatrix}$$ is used.

I want to construct an approximate version of QFT on $$\mathbb{Z}_{2^n}$$ using only $$O(n\log n)$$ gates and show it can be used in Shor's factoring algorithm.

I do understand that for some large enough $$k$$, the matrices $$R_k$$ are close to the identity $$I$$, so it's probably okay to drop them for every $$k > m$$ for some $$m$$.
It will result with much less gates, specifically $$O(n + m^2 + mn)$$, gates, so I guess choosing $$m = O(\log n)$$ will be what's needed here.
However, I'm not sure if my reasoning is correct, and I still need to show that the resulting circuit is an approximation of QFT within $$\frac{1}{q(n)}$$ for an arbitrary polynomial $$q(n)$$. I thought using the distance between unitary matrices to bound the distance between $$I$$ and $$R_k$$, and then $$R_1R_2 \cdots R_m$$ and $$R_1R_2 \cdots R_k$$ where $$k > m$$ but I'm not sure how.