Shor’s Algorithm Factoring Demonstrates the Gap to Breaking 2048-Bit RSA with Current Quantum Platforms
Summarize this article with:
Quantum computers represent a potential challenge to current encryption methods, as they offer the possibility of efficiently breaking widely used public-key cryptosystems. Paul Bagourd, Julian Jang-Jaccard, and Vincent Lenders, from armasuisse Science and Technology, along with colleagues including Torsten Hoefler from ETH Zurich and Cornelius Hempel from the Paul Scherrer Institute, now investigate the practical limitations of executing Shor’s algorithm, a key quantum algorithm for breaking these encryption schemes, on existing quantum hardware. Their work experimentally assesses the feasibility of factoring increasingly large numbers using publicly available quantum computers, revealing a significant discrepancy between theoretical predictions and current capabilities.
The team demonstrates that substantial improvements in both hardware stability and algorithmic flexibility are necessary before factoring cryptographically relevant integers becomes a realistic threat, highlighting critical challenges for the development of practical quantum cryptanalysis. Certifying Shor’s Algorithm on Quantum Hardware This research defines a rigorous methodology for verifying that a quantum computer is genuinely performing Shor’s algorithm in a way that could eventually outperform classical factoring algorithms. Scientists aim to demonstrate that the quantum computation is proceeding in a potentially advantageous manner, concentrating on identifying a discernible quantum signal within noisy data to confirm the algorithm’s proper function. The research defines a metric, ∆, representing the excess signal strength above background noise, and proposes a statistical test to determine if the observed signal is statistically significant. The per-run success probability, crucial for evaluation, depends on the alignment of the QPE spectrum with rational numbers and the ability of the classical step to find a factor. Implementing the algorithm on real quantum hardware introduces challenges, impacting runtime due to noise and imperfections, quantified by a penalty exponent, k. Decoherence, the loss of quantum information, significantly affects the QPE output distribution, suppressing fine phase bits and broadening the signal envelope, revealing which phases remain stable despite decoherence. Ultimately, this work emphasizes the need for rigorous certification, highlights the importance of signal strength, acknowledges the challenges posed by decoherence, and underscores the necessity of statistical testing to evaluate the performance of Shor’s algorithm on quantum hardware. Shor’s Algorithm on Noisy Intermediate-Scale Quantum Computers Scientists investigated the feasibility of executing Shor’s algorithm, a potential threat to modern cryptography, on currently available quantum computers. The study focused on experimentally determining the limits of these machines when attempting to factor large integers, a task crucial to the security of systems like RSA and ECC. Researchers employed several cloud-based quantum computers, utilizing publicly accessible implementations of Shor’s algorithm to assess their capabilities, systematically reviewing leading quantum computing approaches and categorizing them into synthetic and natural qubits. Experiments with superconducting qubits involved encoding information in oscillating electrical currents within circuits cooled to extremely low temperatures, achieving fast gate operations while contending with short coherence times and sensitivity to noise. Researchers also explored quantum dots, confining electrons within semiconductor nanostructures, and investigated their potential for high-density integration despite challenges with coherence and fabrication. Further investigation extended to topological qubits, leveraging exotic quasiparticles predicted to offer inherent robustness against noise, and NV centers in diamond, utilizing electronic or nuclear spin for qubit states and offering room-temperature operation. To characterize quantum signal and identify the point where noise overwhelms the algorithm, scientists engineered specific circuits and performed statistical analysis of Quantum Phase Estimation histograms, systematically comparing the performance of these different qubit technologies. Shor’s Algorithm Faces Hardware and Fidelity Limits Scientists investigated Shor’s algorithm on several cloud-based quantum computers using publicly available implementations. The research reveals a substantial gap between the capabilities of current quantum hardware and the requirements for factoring cryptographically relevant integers, despite theoretical predictions. Experiments demonstrate that circuit constructions remain highly specific for each modulus being factored, and machine fidelities are unstable, exhibiting high and fluctuating error rates. The study categorizes quantum computing approaches into synthetic and natural qubits, detailing key technologies and performance characteristics. Superconducting qubits, utilized by companies like IBM and Google, offer fast gate operations but are limited by relatively short coherence times and sensitivity to noise. Researchers observed that quantum dots, while compatible with existing semiconductor technology, also suffer from short coherence times and tight fabrication tolerances. Topological qubits, predicted to offer intrinsic robustness against noise, remain experimentally challenging to realize, and NV centers in diamond, offering long coherence times, face difficulties in scaling to large, controllable registers. Investigations into order finding on a superconducting quantum processor involved carefully engineered circuits and statistical analysis of Quantum Phase Estimation histograms, demonstrating the limitations of current hardware. Shor’s Algorithm on Noisy Quantum Hardware This research experimentally investigates the feasibility of implementing Shor’s algorithm on currently available quantum computers.
The team successfully executed the algorithm on several cloud-based superconducting quantum processors, demonstrating clear evidence of quantum processing for smaller test cases. Results reveal a significant gap between the capabilities of existing hardware and the requirements for factoring cryptographically relevant integers, confirming expectations for noisy intermediate-scale quantum (NISQ) devices. While the team’s code executed successfully on simulators, attempts to run the algorithm on trapped ion and neutral atom systems via cloud services failed due to difficulties in circuit transpilation. This suggests that achieving reliable execution requires hardware-specific circuit design and optimization. Future work will likely focus on developing hardware-aware algorithms and improving the fidelity of quantum gates to overcome these limitations and explore the potential of quantum computation for cryptographic applications. 👉 More information 🗞 Practical Challenges in Executing Shor’s Algorithm on Existing Quantum Platforms 🧠 ArXiv: https://arxiv.org/abs/2512.15330 Tags: