Shor's Algorithm Using Efficient Approximate Quantum Fourier Transform
Open Access
- 25 September 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 4, 1-16
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 the $T$ -depth of the original. Finally, a $T$ -scheduling method for running the circuit with the smallest KQ is presented.Keywords
Funding Information
- Japan Society for the Promotion of Science (JP21H03440)
- Japan Science and Technology CREST (JPMJCR2113)
This publication has 27 references indexed in Scilit:
- Experimental realization of Shor's quantum factoring algorithm using qubit recyclingNature Photonics, 2012
- A Θ( √ n)-depth quantum adder on the 2D NTC quantum computer architectureACM Journal on Emerging Technologies in Computing Systems, 2012
- Layered Architecture for Quantum ComputingPhysical Review X, 2012
- DISTRIBUTED QUANTUM COMPUTATION ARCHITECTURE USING SEMICONDUCTOR NANOPHOTONICSInternational Journal of Quantum Information, 2010
- Fast quantum modular exponentiationPhysical Review A, 2005
- Overhead and noise threshold of fault-tolerant quantum error correctionPhysical Review A, 2003
- Use of Elliptic Curves in Cryptography2000
- Approximate quantum Fourier transform and decoherencePhysical Review A, 1996
- Elliptic Curve CryptosystemsMathematics of Computation, 1987
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978