| An Evaluation of Computational Complexity of Shor’s Algorithm on Surface Codes for Factorization | |
|
MSRDG International Journal of Computer Scientific Technology & Electronics Engineering
© 2026 by MSRDG IJCSTEE Journal
Volume 2 Issue 5
Year of Publication: 2026
|
Paper Download Article ID MSRDG-IJCSTEE-V2I5P101 DOI https://doi.org/10.66037/MSRDG-IJCSTEE/V2I5P101 |
|
Abstract: 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. |
|
| Keywords: Shor's algorithm, integer factorization, surface code, fault tolerance, lattice surgery, magic states, resource estimation, computational complexity. | |
