2
$\begingroup$

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.

$\endgroup$
1

0

Your Answer

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