Factoring some integers using Shor’s algorithm on real quantum hardware
Fábio Gomes dos Santos, Luis Antônio Brasil Kowada, Guilherme da Hora Andrade Fontoura, Vitor Pio Silva, Gabriela Pinheiro, J. V. S. Scursulim, Samuraí Brito
Experimental realizations of Shor’s integer factorization algorithm on NISQ devices often rely on heavy circuit compilation that inadvertently encodes prior knowledge of the solution, bypassing the core challenge of quantum arithmetic. In this work, we present a hardware-execution baseline for the quantum order-finding routine where modular exponentiation is kept explicit as a sequence of controlled modular multiplications. We explicitly acknowledge that our approach relies on strong prior structural knowledge: the moduli are deliberately chosen as products of Fermat primes, and that ensures the multiplication constants \(c_k = A^{2^k} \bmod N\) will reduce to identities or powers of two. However, unlike compiled demonstrations that hardcode the final state, this structural advantage is used strictly as an experimental proxy to make explicit arithmetic feasible on current hardware. Every non-trivial controlled modular multiplication is executed and verified by intermediate checkpoint measurements. We ran the resulting circuits on IBM superconducting devices for \(N \in \{51, 85, 255, 771\}\) . For moduli up to \(N = 255\) , we observed Hellinger fidelities up to 0.946, while for \(N = 771\) we quantitatively characterize the signal degradation caused by increased circuit depth and accumulated hardware noise. By reporting logical and device-compiled resource counts, this methodology provides a reproducible reference point for studying depth-induced degradation in structured instances of order-finding and evaluating future hardware-aware optimizations.
Experimental realizations of Shor’s integer factorization algorithm on NISQ devices often rely on heavy circuit compilation that inadvertently encodes prior knowledge of the solution, bypassing the core challenge of quantum arithmetic. In this work, we present a hardware-execution baseline for the quantum order-finding routine where modular exponentiation is kept explicit as a sequence of controlled modular multiplications. We explicitly acknowledge that our approach relies on strong prior structural knowledge: the moduli are deliberately chosen as products of Fermat primes, and that ensures the multiplication constants (c_k = A^{2^k} \bmod N) will reduce to identities or powers of two. However, unlike compiled demonstrations that hardcode the final state, this structural advantage is used strictly as an experimental proxy to make explicit arithmetic feasible on current hardware. Every non-trivial controlled modular multiplication is executed and verified by intermediate checkpoint measurements. We ran the resulting circuits on IBM superconducting devices for (N \in {51, 85, 255, 771}) . For moduli up to (N = 255) , we observed Hellinger fidelities up to 0.946, while for (N = 771) we quantitatively characterize the signal degradation caused by increased circuit depth and accumulated hardware noise. By reporting logical and device-compiled resource counts, this methodology provides a reproducible reference point for studying depth-induced degradation in structured instances of order-finding and evaluating future hardware-aware optimizations.
Quantum algorithms for integer factorization represent one of the most prominent applications of quantum computation, with far-reaching implications for modern cryptography. While Shor's algorithm provides a polynomial-time solution in the ideal quantum model, its practical implementation is severely constrained by the limitations of current noisy intermediate-scale quantum (NISQ) hardware. These constraints have motivated the exploration of alternative factoring algorithms with different structural and resource trade-offs.
In this work, we present an experimental study of Regev's quantum factoring algorithm, implemented on real quantum hardware, and compare its behavior with that of Shor's algorithm under analogous conditions. Focusing on the case N = 15, we execute both algorithms on the QMIO quantum computer at the Centro de Supercomputacion de Galicia (CESGA) and contrast the results with one of IBM's open-access quantum computers and ideal simulations. This parallel execution enables a low-level comparison of the two algorithms, highlighting how their respective quantum implementations interact with hardware noise, limited circuit depth, and finite sampling.
Our analysis emphasizes the different ways in which Shor's and Regev's algorithms encode arithmetic structure into quantum states through Fourier sampling in one and higher dimensions, respectively, and how these differences manifest in experimental outcomes. Although neither algorithm demonstrates a practical advantage in the small N regime, the results provide insight into their relative robustness and failure modes on contemporary quantum devices. This study illustrates the value of experimental benchmarking of alternative quantum factoring algorithms as a means of understanding the practical implications of algorithmic design choices in the NISQ era.
The literature indicates that the qubit requirements for factoring RSA-2048 remain on the order of 1 million, under commonly assumed architectures and error-correction models, leaving a substantial gap between current resource estimates and near-term practical feasibility. Reducing this requirement to the low-thousand-qubit regime therefore remains an important open research objective. This work proposes a hybrid classical–quantum algorithm that uses a classical modular exponentiation subroutine with a Quantum Number Theoretic Transform (QNTT) circuit to increase the speed and reduce the required quantum resources relative to Shor’s algorithm for integer factorization, which underpins cryptographic systems like RSA and ECC. We evaluate multiple coprime numbers, the result of multiplication of two primes, in both simulation and real quantum hardware, using IBM’s reference Shor implementation as the baseline. Because Shor and proposed Jesse–Victor–Gharabaghi (JVG) use different register sizes for the same coprime N, the reported gate/depth reductions should be interpreted as end-to-end quantum-resource budgets for factoring the same N, rather than a per-qubit or transform-only efficiency claim. In simulation, the JVG algorithm achieved substantial practical reductions in computational resources, decreasing runtime from 174.1 s to 5.4 s, memory usage from 12.5 GB to 0.27 GB, and quantum gate counts by approximately 99%. On quantum hardware, JVG reduced the required runtime from 67.8 s to 2 s, and the quantum gate counts by over 98%. We showed that the proposed algorithm can address the relevant RSA-1024 case scenario, establishing that this method can provide validation for large-scale situations. Furthermore, extrapolation to RSA-2048 indicates that the JVG algorithm significantly outperforms Shor’s approach, requiring a projected quantum runtime of 29 h for ten thousand runs for factorization under identical scaling assumptions. Overall, these results support JVG as a more hardware-compatible and robust noise-tolerant substitute for Shor’s framework, offering a viable research direction toward practical quantum integer factorization on near-term Noisy Intermediate-Scale Quantum (NISQ) devices.
Shor’s algorithm stands as a breakthrough in quantum computing due to its potential to factor large integers exponentially quicker than classical algorithms. However, implementing and evaluating this algorithm on real quantum computer hardware remains exciting due to qubit limitations, gate noise, and hardware constraints. This research presents a comprehensive performance evaluation of Shor’s algorithm using simulated quantum backends provided by Qiskit. A flexible and generic implementation is proposed, allowing dynamic input of integers to be factored, with randomized co-prime selection and automated circuit generation. The algorithm is tested on various semiprime numbers, such as 15, 21, and 35, using IBM’s Aer simulator. A major contribution of this work is the circuit-level analysis conducted both before and after transpilation. Metrics such as gate counts, circuit depth, and simulator runtime are extracted to assess scalability and resource requirements. High-resolution plots of the pre-transpiled circuits are saved to visualize algorithmic complexity, while post-transpilation metrics inform future quantum hardware feasibility. The output measurement distributions are analyzed to estimate periodicity and derive correct factors. The proposed implementation is compared with existing fixed-instance Shor demonstrations to highlight its flexibility and extensibility. Experimental results show consistent success in factor retrieval and provide valuable insight into circuit growth and complexity under realistic constraints. This analysis lays the groundwork for future adaptation to NISQ hardware and contributes to understanding Shor’s algorithm from both computational and architectural perspectives.
Shor's quantum factoring algorithm threatens RSA and elliptic-curve cryptography, yet the operational limits of noisy intermediate-scale quantum (NISQ) hardware for complete Shor implementations remain poorly characterized. This paper presents the first systematic experimental evaluation of the full QFT-based Shor period-finding circuit — with base a and period r pre-selected classically but the complete inverse-QFT structure fully preserved on hardware — across nine semiprimes ranging from 4 to 12 bits, executed on IBM 156-qubit Heron-class processors. All nine instances were factored successfully, including the first reported 8–12-bit superconducting results: N = 205 (61.5%) through N = 3427 (73.4%). The central finding is that QFT peak separability (ΔK) dominates success probability (R2= 0.94), while transpilation overhead is essentially irrelevant (R2= 0.06). Period r = 4 emerges as a noise-robust configuration at 8–12-bit scale, with ΔK ≥ 8 defining the practical NISQ threshold. Six quantitative design rules enable systematic instance pre-screening, with implications for post-quantum cryptography migration timelines discussed.
This work presents a classical simulation framework for circuit components associated with the modular-exponentiation and order-finding stages of Shor’s factoring algorithm. The study examines five experimental cases and combines reversible state evolution, a dual-uint64 representation, Numba just-in-time execution, sparse grouping of phase amplitudes, and Fourier analysis. Its principal contribution is an occupancy-aware Fourier procedure that evaluates singleton groups analytically and applies the conventional fast Fourier transform only to groups containing multiple occupied phase positions. For the instance N = 4,028,033, this procedure reduced the number of FFT calls from 60,970 to 4,566 and decreased the measured Fourier-processing time from 197.68 seconds to 18.11 seconds, a reduction of 90.84%. All five selected cases satisfied the seven adopted validation criteria. The work concerns computational optimization of a classical simulation pipeline; it does not claim execution on quantum hardware, quantum computational advantage, or a new factoring algorithm. The experimental dataset supporting this study is publicly available through Harvard Dataverse: https://doi.org/10.7910/DVN/OOYKSC.
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 that machine fidelities are unstable, with high and fluctuating error rates.