Exact Analyses of Computational Time for Factoring in Quantum Computers
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.1 pp.105-111
- Publication Date
- 2005/01/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietfec/e88-a.1.105
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
- Public Key Cryptography
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Noboru KUNIHIRO, "Exact Analyses of Computational Time for Factoring in Quantum Computers" in IEICE TRANSACTIONS on Fundamentals,
vol. E88-A, no. 1, pp. 105-111, January 2005, doi: 10.1093/ietfec/e88-a.1.105.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.1.105/_p
Copy
@ARTICLE{e88-a_1_105,
author={Noboru KUNIHIRO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Exact Analyses of Computational Time for Factoring in Quantum Computers},
year={2005},
volume={E88-A},
number={1},
pages={105-111},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e88-a.1.105},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - Exact Analyses of Computational Time for Factoring in Quantum Computers
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 105
EP - 111
AU - Noboru KUNIHIRO
PY - 2005
DO - 10.1093/ietfec/e88-a.1.105
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2005
AB - 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.
ER -
English
