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

Quantum Information Processing

Resource analysis of quantum computing with noisy qubits for Shor’s factoring algorithms

Jinyoung Ha, Jonghyun Lee, Jun Heo

Published Jan 20, 2022• 25 citations
Publisher

Abstract

Abstract We decompose two implementations of Shor’s algorithm for prime factorization into universal gate units at the logical level and predict the number of physical qubits and execution time when surface codes are used. Logical qubit encoding using a rotated surface code and logical qubits with all-to-all connectivity are assumed. We express the number of physical qubits and execution time in terms of the bit length of the number to be factorized and error rate of the physical quantum gate. We confirm the relationship between the number of qubits and the execution time by analyzing two algorithms using various bit lengths and physical gate error rates .

DOI
10.1007/s11128-021-03398-1

Related papers

Resource analysis and modifications of quantum computing with noisy qubits for elliptic curve discrete logarithms

Jinyoung Ha, Jonghyun Lee, Jun Heo

We estimate the number of physical qubits and execution time by decomposing an implementation of Shor's algorithm for elliptic curve discrete logarithms into universal gate units at the logical level when surface codes are used. We herein also present modified quantum circuits for elliptic curve discrete logarithms and compare our results with those of the original quantum circuit implementations at the physical level. Through the analysis, we show that the use of more logical qubits in quantum algorithms does not always lead to the use of more physical qubits. We assumed using rotated surface code and logical qubits with all-to-all connectivity. The number of physical qubits and execution time are expressed in terms of bit length, physical gate error rate, and probability of algorithm failure. In addition, we compare our results with the number of physical qubits and execution time of Shor's factoring algorithm to assess the risk of attack by quantum computers in RSA and elliptic curve cryptography.

Scientific Reports•Feb 16, 2024•4 citations

An Evaluation of Computational Complexity of Shor’s Algorithm on Surface Codes for Factorization

Pradeep M

Shor's algorithm factors an n-bit integer in time polynomial in n, which would break RSA. Its asymptotic gate complexity, however, says little about what a real machine must provide, because the dominant cost is the overhead of quantum error correction. This report evaluates the computational complexity of Shor's algorithm in three layers: the logical algorithm (gate count, depth and qubits of order finding and modular exponentiation), the surface-code layer (code distance, logical error suppression, lattice surgery and magic-state production) and the physical resource layer (qubits and wall-clock time). We present a compact analytic resource model, calibrated to the published Gidney-Ekerå estimate for RSA-2048, and use it to study scaling with key size, physical error rate and reaction time. For RSA-2048 the model gives about 2.6 billion Toffoli gates, roughly 6,200 logical qubits, a code distance near 29 and about 20 million physical qubits for a runtime of about seven hours at a 0.1% physical error rate. Resource requirements grow as n3 in gates and runtime, while physical-qubit overhead is dominated by the code distance, which rises steeply as the physical error rate approaches the threshold. We also summarize how algorithmic and code improvements through 2026 have reduced published estimates by orders of magnitude.

MSRDG International Journal of Computer Scientific Technology & Electronics Engineering•Oct 31, 2026•0 citations

ARCHITECTURE-DEPENDENT EXECUTION TIME OF SHOR'S ALGORITHM

Rodney Van Meter, Kohei M. Itoh, Thaddeus D. Ladd

We show how the execution time of algorithms on quantum computers depends on the architecture of the quantum computer, the choice of algorithms (including subroutines such as arithmetic), and the ``clock speed'' of the quantum computer. The primary architectural features of interest are the ability to execute multiple gates concurrently, the number of application-level qubits available, and the interconnection network of qubits. We analyze Shor's algorithm for factoring large numbers in this context. Our results show that, if arbitrary interconnection of qubits is possible, a machine with an application-level clock speed of as low as one-third of a (possibly encoded) gate per second could factor a 576-bit number in under one month, potentially outperforming a large network of classical computers. For nearest-neighbor-only architectures, a clock speed of around twenty-seven gates per second is required.

arXiv:quant-ph/0507023•International Symposium on Mesoscopic Superconductivity and Spintronics (MS+S)•Oct 1, 2008•29 citations

Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits

Madelyn Cain, Qian Xu, Robbie King +6 more

Quantum computers have the potential to perform computational tasks beyond the reach of classical machines. A prominent example is Shor's algorithm for integer factorization and discrete logarithms, which is of both fundamental importance and practical relevance to cryptography. However, due to the high overhead of quantum error correction, optimized resource estimates for cryptographically relevant instances of Shor's algorithm require millions of physical qubits. Here, by leveraging advances in high-rate quantum error-correcting codes, efficient logical instruction sets, and circuit design, we show that Shor's algorithm can be executed at cryptographically relevant scales with as few as 10,000 reconfigurable atomic qubits. Increasing the number of physical qubits improves time efficiency by enabling greater parallelism; under plausible assumptions, the runtime for discrete logarithms on the P-256 elliptic curve could be just a few days for a system with 26,000 physical qubits, while the runtime for factoring RSA-2048 integers is one to two orders of magnitude longer. Recent neutral-atom experiments have demonstrated universal fault-tolerant operations below the error-correction threshold, computation on arrays of hundreds of qubits, and trapping arrays with more than 6,000 highly coherent qubits. Although substantial engineering challenges remain, our theoretical analysis indicates that an appropriately designed neutral-atom architecture could support quantum computation at cryptographically relevant scales. More broadly, these results highlight the capability of neutral atoms for fault-tolerant quantum computing with wide-ranging scientific and technological applications.

quant-pharXiv:2603.28627•Mar 31, 2026•160 citations

Shor’s algorithm does not factor large integers in the presence of noise

Jin‐Yi Cai

Abstract We consider Shor’s quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form pq when the noise exceeds a vanishingly small level in terms of n —the number of bits of the integer to be factored, where p and q are from a well-defined set of primes of positive density. We further prove that with probability 1 − o (1) over random prime pairs ( p, q ), Shor’s factoring algorithm does not factor numbers of the form pq , with the same level of random noise present.

arXiv:2306.10072•Science China Information Sciences•Jun 18, 2024•27 citations

How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

Craig Gidney, Martin Ekerå

We significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields on a quantum computer by combining techniques from Shor 1994, Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Ekerå-Håstad 2017, Ekerå 2017, Ekerå 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of 10 − 3 , a surface code cycle time of 1 microsecond, and a reaction time of 10 microseconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction's spacetime volume is a hundredfold less than comparable estimates from earlier works (Van Meter et al. 2009, Jones et al. 2010, Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses 3 n + 0.002 n lg ⁡ n logical qubits, 0.3 n 3 + 0.0005 n 3 lg ⁡ n Toffolis, and 500 n 2 + n 2 lg ⁡ n measurement depth to factor n -bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.

arXiv:1905.09749•Quantum•Apr 15, 2021•1,131 citations
Abstract We decompose two implementations of Shor’s algorithm for prime factorization into universal gate units at the logical level and predict the number of physical qubits and execution time when surface codes are used. Logical qubit encoding using a rotated surface code and logical qubits with all-to-all connectivity are assumed. We express the number of physical qubits and execution time in terms of the bit length of the number to be factorized and error rate of the physical quantum gate. We confirm the relationship between the number of qubits and the execution time by analyzing two algorithms using various bit lengths and physical gate error rates .
We estimate the number of physical qubits and execution time by decomposing an implementation of Shor's algorithm for elliptic curve discrete logarithms into universal gate units at the logical level when surface codes are used. We herein also present modified quantum circuits for elliptic curve discrete logarithms and compare our results with those of the original quantum circuit implementations at the physical level. Through the analysis, we show that the use of more logical qubits in quantum algorithms does not always lead to the use of more physical qubits. We assumed using rotated surface code and logical qubits with all-to-all connectivity. The number of physical qubits and execution time are expressed in terms of bit length, physical gate error rate, and probability of algorithm failure. In addition, we compare our results with the number of physical qubits and execution time of Shor's factoring algorithm to assess the risk of attack by quantum computers in RSA and elliptic curve cryptography.
Shor's algorithm factors an n-bit integer in time polynomial in n, which would break RSA. Its asymptotic gate complexity, however, says little about what a real machine must provide, because the dominant cost is the overhead of quantum error correction. This report evaluates the computational complexity of Shor's algorithm in three layers: the logical algorithm (gate count, depth and qubits of order finding and modular exponentiation), the surface-code layer (code distance, logical error suppression, lattice surgery and magic-state production) and the physical resource layer (qubits and wall-clock time). We present a compact analytic resource model, calibrated to the published Gidney-Ekerå estimate for RSA-2048, and use it to study scaling with key size, physical error rate and reaction time. For RSA-2048 the model gives about 2.6 billion Toffoli gates, roughly 6,200 logical qubits, a code distance near 29 and about 20 million physical qubits for a runtime of about seven hours at a 0.1% physical error rate. Resource requirements grow as n3 in gates and runtime, while physical-qubit overhead is dominated by the code distance, which rises steeply as the physical error rate approaches the threshold. We also summarize how algorithmic and code improvements through 2026 have reduced published estimates by orders of magnitude.
We show how the execution time of algorithms on quantum computers depends on the architecture of the quantum computer, the choice of algorithms (including subroutines such as arithmetic), and the ``clock speed'' of the quantum computer. The primary architectural features of interest are the ability to execute multiple gates concurrently, the number of application-level qubits available, and the interconnection network of qubits. We analyze Shor's algorithm for factoring large numbers in this context. Our results show that, if arbitrary interconnection of qubits is possible, a machine with an application-level clock speed of as low as one-third of a (possibly encoded) gate per second could factor a 576-bit number in under one month, potentially outperforming a large network of classical computers. For nearest-neighbor-only architectures, a clock speed of around twenty-seven gates per second is required.
Quantum computers have the potential to perform computational tasks beyond the reach of classical machines. A prominent example is Shor's algorithm for integer factorization and discrete logarithms, which is of both fundamental importance and practical relevance to cryptography. However, due to the high overhead of quantum error correction, optimized resource estimates for cryptographically relevant instances of Shor's algorithm require millions of physical qubits. Here, by leveraging advances in high-rate quantum error-correcting codes, efficient logical instruction sets, and circuit design, we show that Shor's algorithm can be executed at cryptographically relevant scales with as few as 10,000 reconfigurable atomic qubits. Increasing the number of physical qubits improves time efficiency by enabling greater parallelism; under plausible assumptions, the runtime for discrete logarithms on the P-256 elliptic curve could be just a few days for a system with 26,000 physical qubits, while the runtime for factoring RSA-2048 integers is one to two orders of magnitude longer. Recent neutral-atom experiments have demonstrated universal fault-tolerant operations below the error-correction threshold, computation on arrays of hundreds of qubits, and trapping arrays with more than 6,000 highly coherent qubits. Although substantial engineering challenges remain, our theoretical analysis indicates that an appropriately designed neutral-atom architecture could support quantum computation at cryptographically relevant scales. More broadly, these results highlight the capability of neutral atoms for fault-tolerant quantum computing with wide-ranging scientific and technological applications.
Abstract We consider Shor’s quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form pq when the noise exceeds a vanishingly small level in terms of n —the number of bits of the integer to be factored, where p and q are from a well-defined set of primes of positive density. We further prove that with probability 1 − o (1) over random prime pairs ( p, q ), Shor’s factoring algorithm does not factor numbers of the form pq , with the same level of random noise present.
We significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields on a quantum computer by combining techniques from Shor 1994, Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Ekerå-Håstad 2017, Ekerå 2017, Ekerå 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of 10 − 3 , a surface code cycle time of 1 microsecond, and a reaction time of 10 microseconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction's spacetime volume is a hundredfold less than comparable estimates from earlier works (Van Meter et al. 2009, Jones et al. 2010, Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses 3 n + 0.002 n lg ⁡ n logical qubits, 0.3 n 3 + 0.0005 n 3 lg ⁡ n Toffolis, and 500 n 2 + n 2 lg ⁡ n measurement depth to factor n -bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.