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

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.

Now, I tried to read this article, but found it a bit hard to comprehend.

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.

Help would be appreciated.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.