Practical Challenges in Executing Shor’s Algorithm on Existing Quantum Platforms
Paul Bagourd, Julian Jang-Jaccard, Vincent Lenders, Alain Mermoud, Torsten Hoefler, Cornelius Hempel · 2025
Read Practical Challenges in Executing Shor’s Algorithm on Existing Quantum Platforms by Paul Bagourd, Julian Jang-Jaccard, Vincent Lenders, Alain Mermoud, Torsten Hoefler, Cornelius Hempel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-15330.txt.
Introduction
Paul Bagourd and five coauthors run Shor's factoring algorithm on today's cloud quantum computers and report how far it falls short. Shor's algorithm threatens RSA and elliptic curve cryptography, since a big enough quantum machine could factor the keys. Theory says 2048 bit RSA might fall to fewer than a million noisy qubits, but such machines do not exist.
Using public implementations on several cloud platforms, the team probes what key sizes current hardware can realistically factor. A wide gap separates today's machines from cryptographically relevant factoring. Circuits still must be built specifically for each modulus, rather than one general design. Fidelities are unstable, with high error rates that fluctuate from run to run. The study gives practitioners a grounded picture of the present threat level, far below the headline danger.
Catalog record
| CREATOR | Paul Bagourd, Julian Jang-Jaccard, Vincent Lenders, Alain Mermoud, Torsten Hoefler, Cornelius Hempel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-15330
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Practical Challenges in Executing Shor’s Algorithm on Existing Quantum Platforms Paul Bagourd, Julian Jang-Jaccard, Vincent Lenders, Alain Mermoud, Torsten Hoefler, Cornelius Hempel Abstract Quantum computers pose a fundamental threat to widely deployed public-key cryptosystems, such as RSA and ECC, by enabling efficient integer factorization using Shor’s algorithm. Theoretical resource estimates suggest that 2048-bit RSA keys could be broken using Shor’s algorithm with fewer than a million noisy qubits. Although such machines do not yet exist, the availability of smaller, cloud-accessible quantum processors and open-source implementations of Shor’s algorithm raises the question of what key sizes can realistically be factored with today’s platforms. In this work, we experimentally investigate Shor’s algorithm on several cloud-based quantum computers using publicly available implementations. Our results reveal a substantial gap between the capabilities of current quantum hardware and the requirements for factoring cryptographically relevant integers. In particular, we observe that circuit constructions still need to be highly specific for each modulus, and machine fidelities are unstable with high and fluctuating error rates. Although our findings indicate that the present state of quantum computing poses no immediate or near-term threat to modern cryptography, a combination of breakthroughs in hardware and algorithmic advances could rapidly change this picture. Continuous monitoring and proactive preparation are therefore essential to stay ahead of emerging quantum threats. Keywords: cryptography, prime factorization, public key, quantum computing, Shor’s algorithm 1 Introduction Quantum computers have the potential to transform computing by efficiently solving certain problems that are intractable for classical machines. Shor’s algorithm [ 1 , 2 ] is particularly notable for its ability to factor large integers in polynomial time, outperforming the best-known classical methods. At the core of Shor’s algorithm is the Quantum Fourier Transform (QFT), which enables key subroutines to be implemented exponentially faster than their classical counterparts. This capability threatens widely used public-key cryptographic protocols, such as RSA and also ECC [ 3 ] , whose security is based on the presumed hardness of integer factorization or related number-theoretic problems. While theoretical advancements have clarified how quantum computers could eventually compromise such systems, the practical implementation of Shor’s algorithm on existing quantum hardware remains extremely challenging — even for integers far smaller than those used in deployed cryptographic schemes. In the current noisy intermediate-scale quantum (NISQ) [ 4 ] era, quantum devices have limited qubit counts, significant noise, and short coherence times. Understanding what they can and cannot realistically achieve is crucial for assessing the urgency of quantum-safe cryptographic migration. This paper makes three main contributions. First, we review the leading quantum computing approaches that have reached comparable technical readiness levels. We group them into synthetic and natural qubits and discuss their strengths, weaknesses, and key technical barriers. Second, we review the state of experimental implementations of Shor’s algorithm across various quantum computing technologies attempted to date, discussing the significance and limitations of each effort. Third, we report on our own experiments in performing order finding – the core quantum subroutine of Shor’s algorithm – on a publicly available superconducting quantum processor. Using carefully engineered circuits and statistical analysis of Quantum Phase Estimation (QPE) histograms, we characterize the observable quantum signal and identify the point where noise overwhelms the algorithmic structure. We complement these results with an investigation of the challenges encountered when attempting to run comparable circuits on non-superconducting platforms via cloud services. Overall, our findings suggest that, despite substantial progress in both algorithms and hardware, practical quantum attacks on standard cryptographic key sizes remain out of reach on currently accessible quantum platforms. However, the rapid pace of development, coupled with ambitious industrial roadmaps, underscores the need for ongoing evidence-based assessments of quantum capabilities. 2 Understanding Different Quantum Computers Quantum computing is built on qubits as the fundamental units of quantum information. Broadly, qubit implementations can be categorized into two families: synthetic qubits, which are artificially engineered entities designed to effectively realize two-level quantum behavior, and natural qubits, which directly use the intrinsic quantum states of atoms, ions, or photons. Table 1 provides an overview of various key qubit technologies, representative commercial providers, and high-level performance characteristics. Table 1: Quantum computing with different qubit technologies and their characteristics. Synthetic Qubits Natural Qubits Atom-based Light-based Type Superconducting circuits*, Quantum dots, Topological qubits, NV centers in diamonds Trapped-Ion*, Neutral Atom* Photon Examples of Commercial Providers IBM, Google, Rigetti, IQM, Microsoft, Intel, Diraq, Quantum Brilliance IonQ, Quantinuum, AQT, QuEra, Pasqal, planqc, Atom Computing, Infleqtion Xanadu, PsiQuantum, Quandela Overall Processing Speed Fast Slow Fast Qubit Connectivity Low High Low Coherence Times Low High High Cooling Requirement Extreme cryogenics ( \sim 10 mK) Room temperature but often standard cryogenics ( \sim 4 K) Room temperature with detectors requiring standard cryogenics (4 K) Main Advantages Circuits can be designed with the desired topology; highly scalable in some approaches High accuracy and stability; qubits identical by nature; very long coherence times Energy efficient; builds on some telecom-industry matured photonic technologies Main Challenges Qubit uniformity; limited cooling power and wiring; high sensitivity to noise; fast classical-electronics requirements Complex laser-based control that is hard to scale Photon loss and detection; entanglement preparation; often non-deterministic operation slowing clock speeds * indicates the highest TRL modalities at the time of writing 2.1 Quantum Computers with Synthetic Qubits Superconducting qubits, widely used by companies such as IBM, Google, and Rigetti, encode information in oscillating electrical currents in superconducting circuits cooled to millikelvin temperatures. They offer fast gate operations and benefit from mature microwave control and fabrication ecosystems. However, they suffer from relatively short coherence times, variability across the chip, and significant sensitivity to noise, all of which increase the burden on error mitigation and QEC. Quantum dots, which confine electrons in semiconductor nanostructures, are attractive due to their compatiblity with existing semiconductor technology and their potential for high-density integration. Their main challenges include short coherence times, tight fabrication tolerances, and complex control requirements. The availability of ultra-pure silicon-28 as raw material can provide further limitations. Topological qubits, based on exotic quasiparticles such as Majorana fermions, are predicted to exhibit intrinsic robustness against certain types of local noise, thereby reducing error correction overheads in principle. Yet, their experimental realization remains difficult and has not been conclusively demonstrated. NV centers in diamond use electronic or nuclear spin associated with a lattice defect to encode qubit states. They offer long coherence times and can operate at room-temperature, but scaling them to large, controllable registers is difficult, due to the difficulty of precise and reliable manufacturing. Overall, synthetic qubits benefit from strong synergies with microelectronics and integrated circuits, but progress towards large-scale, high-fidelity systems is hindered by noise, parameter dispersion, and packaging constraints that become more severe as system size grows. 2.2 Quantum Computers with Natural Qubits Natural qubit platforms can be further divided into atom-based and light-based approaches. Trapped-ion systems encode qubits in the internal electronic states of ions confined in electromagnetic traps under ultra-high vacuum. They are renowned for their long coherence times and record-low gate error rates, and have been the first platform to demonstrate deterministic quantum gate operations already in 1995. Today, companies such as IonQ and Quantinuum have demonstrated programmable systems with tens of high-fidelity qubits. However, gate operations are relatively slow, and scaling brings challenges due to the complexity