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.