Shor's Algorithm Using Efficient Approximate Quantum Fourier Transform

Abstract

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 of the $T$-depth of the original. Finally, a $T$-scheduling method for running the circuit with the smallest KQ (where K is the number of logical qubits and Q is the circuit depth) is presented.

Keywords

• Approximate quantum Fourier transform
• controlled modular multiplication
• Shor's algorithm