Shor's Algorithm Using Efficient Approximate Quantum Fourier Transform
Kento Oonishi, Noboru Kunihiro · IEEE Transactions on Quantum Engineering · 2023
Shor's algorithm solves the integer factoring and discrete logarithm problems in polynomial time. Therefore, the evaluation of Shor's algorithm is essential for evaluating the security of currently used public-key cryptosystems because the integer factoring and discrete logarithm problems are crucial for the security of these cryptosystems. In this article, a new approximate quantum Fourier transform is proposed, and it is applied to Rines and Chuang's implementation. The proposed implementation requires one-third the number of$T$gates of the original. Moreover, it requires one-fourth the$T$-depth of the original. Finally, a$T$-scheduling method for running the circuit with the smallest KQ is presented.