Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Exact Analyses of Computational Time for Factoring in Quantum Computers

Noboru Kunihiro

Published Jan 1, 2005• 13 citations
Publisher

Abstract

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. key words: Shor’s factoring algorithm, quantum circuit, practical running time 1.

DOI
10.1093/ietfec/e88-a.1.105

Related papers

Efficient networks for quantum factoring

David Beckman, Amalavoyal N. Chari, Devabhaktuni Srikrishna +1 more

We consider how to optimize memory use and computation time in operating a quantum computer. In particular, we estimate the number of memory quantum bits (qubits) and the number of operations required to perform factorization, using the algorithm suggested by Shor [in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society, Los Alamitos, CA, 1994), p. 124]. A K-bit number can be factored in time of order ${\mathit{K}}^{3}$ using a machine capable of storing 5K+1 qubits. Evaluation of the modular exponential function (the bottleneck of Shor's algorithm) could be achieved with about 72${\mathit{K}}^{3}$ elementary quantum gates; implementation using a linear ion trap would require about 396${\mathit{K}}^{3}$ laser pulses. A proof-of-principle demonstration of quantum factoring (factorization of 15) could be performed with only 6 trapped ions and 38 laser pulses. Though the ion trap may never be a useful computer, it will be a powerful device for exploring experimentally the properties of entangled quantum states. \textcopyright{} 1996 The American Physical Society.

arXiv:quant-ph/9602016•Physical Review A•Aug 1, 1996•308 citations

Circuit for Shor's algorithm using 2n+3 qubits

Stéphane Beauregard

We try to minimize the number of qubits needed to factor an integer of n bits using Shor's algorithm on a quantum computer. We introduce a circuit which uses 2n+3 qubits and O(n^3 lg(n)) elementary quantum gates in a depth of O(n^3) to implement the factorization algorithm. The circuit is computable in polynomial time on a classical computer and is completely general as it does not rely on any property of the number to be factored.

arXiv:quant-ph/0205095•Quantum Information and Computation•Mar 1, 2003•299 citations

Shor's Factoring Algorithm and Modular Exponentiation Operators

Robert Singleton

We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.

arXiv:2306.09122•Quanta•Sep 15, 2023•15 citations

Performance Analysis of Shor's Algorithm for Integer Factorization Using Quantum and Classical Approaches

T. Thamaraimanalan, Bhupendra Singh, M. Mohankumar +1 more

Factoring large numbers poses a significant chal-lenge in contemporary cryptography and security practices. Shor's algorithm presents a remarkable advancement over clas- sical methods by providing exponential acceleration in factoring large numbers, presenting a possible risk to traditional cryptography methods. The algorithm relies on the Quantum Fourier Transform (QFT) and modular exponentiation principles to efficiently ascertain the period (x) of a given large number (N). Upon determining the period using classical methods, the prime factors of the large number can be easily computed. To eval- uate the algorithm's efficiency and scalability, both simulation- based experiments and theoretical analyses are conducted. The algorithm is simulated utilizing the Qiskit back end to estimate resources, including Clifford gates, T gates, T depth, Full depth, and qubits, across a range of large numbers.

International Conference on Advanced Computing and Communication Systems (ICACCS)•Mar 14, 2024•11 citations

Streamlining Shor's algorithm for potential hardware savings

Yunseong Nam, R. Blümel

We constructed a virtual quantum computer by running a complete, scaling, quantum-gate--by--quantum-gate implementation of Shor's algorithm on a 128-core classical cluster computer. In mode A [quantum period finding (PF) only, supplied with classical results for the modular exponentiation (ME) part of Shor's algorithm], factoring semiprimes up to $N=557\phantom{\rule{0.16em}{0ex}}993$ with up to $n=39$ qubits, we confirm earlier, smaller-$n$ results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large-$n$ implementations of quantum computers.

Physical Review A•Jun 26, 2013•7 citations

Circuit implementation of Shor's algorithm for the factorization of small integers in Qiskit

Iheb Eddine Gharbi, Amor Gueddana, Hichem Eleuch +1 more

To factor an integer N into a product of two other numbers N1 and N2, Shor’s algorithm uses the Quantum Fourier Transform on n qubits, denoted QFTn, to determine the period r of a Modular Exponentiation Function (MEF), which is later used to compute a factor of N. In this work, we present Shor’s algorithm for factoring an integer of n qubits and illustrate an example with n=4. We implement our algorithm using Qiskit and IBM quantum computers, which also can be adapted on other quantum computing platforms with minor adjustments. We discuss the IBM quantum computer limitations for running our circuit and show the impact of device imperfections on the factored result.

Quantum Communications and Quantum Imaging•Aug 13, 2024•3 citations
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. key words: Shor’s factoring algorithm, quantum circuit, practical running time 1.
We consider how to optimize memory use and computation time in operating a quantum computer. In particular, we estimate the number of memory quantum bits (qubits) and the number of operations required to perform factorization, using the algorithm suggested by Shor [in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society, Los Alamitos, CA, 1994), p. 124]. A K-bit number can be factored in time of order K3{\mathit{K}}^{3}K3 using a machine capable of storing 5K+1 qubits. Evaluation of the modular exponential function (the bottleneck of Shor's algorithm) could be achieved with about 72K3{\mathit{K}}^{3}K3 elementary quantum gates; implementation using a linear ion trap would require about 396K3{\mathit{K}}^{3}K3 laser pulses. A proof-of-principle demonstration of quantum factoring (factorization of 15) could be performed with only 6 trapped ions and 38 laser pulses. Though the ion trap may never be a useful computer, it will be a powerful device for exploring experimentally the properties of entangled quantum states. \textcopyright{} 1996 The American Physical Society.
We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.
Factoring large numbers poses a significant chal-lenge in contemporary cryptography and security practices. Shor's algorithm presents a remarkable advancement over clas- sical methods by providing exponential acceleration in factoring large numbers, presenting a possible risk to traditional cryptography methods. The algorithm relies on the Quantum Fourier Transform (QFT) and modular exponentiation principles to efficiently ascertain the period (x) of a given large number (N). Upon determining the period using classical methods, the prime factors of the large number can be easily computed. To eval- uate the algorithm's efficiency and scalability, both simulation- based experiments and theoretical analyses are conducted. The algorithm is simulated utilizing the Qiskit back end to estimate resources, including Clifford gates, T gates, T depth, Full depth, and qubits, across a range of large numbers.
We constructed a virtual quantum computer by running a complete, scaling, quantum-gate--by--quantum-gate implementation of Shor's algorithm on a 128-core classical cluster computer. In mode A [quantum period finding (PF) only, supplied with classical results for the modular exponentiation (ME) part of Shor's algorithm], factoring semiprimes up to N=557993N=557\phantom{\rule{0.16em}{0ex}}993N=557993 with up to n=39n=39n=39 qubits, we confirm earlier, smaller-nnn results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large-nnn implementations of quantum computers.
To factor an integer N into a product of two other numbers N1 and N2, Shor’s algorithm uses the Quantum Fourier Transform on n qubits, denoted QFTn, to determine the period r of a Modular Exponentiation Function (MEF), which is later used to compute a factor of N. In this work, we present Shor’s algorithm for factoring an integer of n qubits and illustrate an example with n=4. We implement our algorithm using Qiskit and IBM quantum computers, which also can be adapted on other quantum computing platforms with minor adjustments. We discuss the IBM quantum computer limitations for running our circuit and show the impact of device imperfections on the factored result.