Exact Analyses of Computational Time for Factoring in Quantum Computers

Noboru KUNIHIRO

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A    No.1    pp.105-111
Publication Date: 2005/01/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.1.105
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Public Key Cryptography
Keyword: 
Shor's factoring algorithm,  quantum circuit,  practical running time,  

Full Text: PDF(115.7KB)>>
Buy this Article



Summary: 
We evaluate the exact number of gates for circuits of Shor's factoring algorithm. We estimate the running time for factoring a large composite such as 576 and 1024 bit numbers by appropriately setting gate operation time. For example, we show that on the condition that each elementary gate is operated within 50 µsec, the running time for factoring 576 bit number is 1 month even if the most effective circuit is adopted. Consequently, we find that if we adopt the long gate operation-time devices or qubit-saving circuits, factorization will not be completed within feasible time on the condition that a new efficient modular exponentiation algorithm will not be proposed. Furthermore, we point out that long gate operation time may become a new problem preventing a realization of quantum computers.