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

arXiv:2509.00417

An exploration of the noise sensitivity of the Shor's algorithm

Fusheng Yang, Zhipeng Liang, Zhengzhong Yi, Xuan Wang

Published Aug 30, 2025• 0 citations
arXivHTMLPDF

Abstract

Quantum algorithms face significant challenges due to qubit susceptibility to environmental noise, and quantum error correction typically requires prohibitive resource overhead. This paper proposes that quantum algorithms may possess inherent noise resilience characteristics that could reduce implementation barriers. We investigate Shor's algorithm by applying circuit-level noise models directly to the original algorithm circuit. Our findings reveal that Shor's algorithm demonstrates superior fault tolerance under Z noise compared to X and Y noise. Focusing on the modular exponentiation circuit which is the core component of the algorithm, we conduct fault-tolerant position statistics on circuits with bit lengths from 4 to 9. The results show that under Z noise, fault-tolerant positions grow with the same quartic polynomial order as potential error positions as the problem scale increases. In contrast, fault tolerance under X and Y noise exhibits a strong dependence on the composite number N and the parameter a. Based on these findings, we develop an extrapolation method predicting that the minimum probability of a correct output of the modular exponentiation circuit to factor 2048 bit integers under biased noise is approximately 1.417*{10}^{-17}.

DOI
10.48550/arxiv.2509.00417

Related papers

The Impact of Quantum Noise on Shor's Algorithm and Its Cryptographic Applications

Wael M. F. Abdel-Rehim

Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.

•May 12, 2025•2 citations

Enhanced Security Algorithm for Integer Factorization in Quantum Computing: Optimizing Shor’s Algorithm

Rashmi Kuksal, Sumit Chaudhary, Ashish Bhatt

With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.

International Conference on Innovative Mechanisms for Industry Applications•Oct 1, 2026•0 citations

A Novel Hybrid Quantum Framework for Assessing Noise Effects on Performance of Shor’s Algorithm

Mst. Nishita Aktar, Joynob Akter, Kh. Mustafizur Rahman +4 more

This experimental study introduces a hybrid quantum-classical framework aiming to improve the noise robustness of Shor’s algorithm. By incorporating a novel hybrid logic gate into the modular exponentiation phase, the framework stabilizes qubit interactions and decreases decoherence in a noisy environment simulated by IBM Qiskit. Performance evaluation is accomplished by fidelity and entropy analysis across varied noise levels. Comparative benchmarking with conventional techniques, including Shor’s code, Bacon-Shor code, dynamical decoupling, and zero noise extrapolation, demonstrates that the proposed hybrid gate achieves higher fidelity (0.90) and lower entropy (0.33), while preserving minimal resource overhead. These findings highlight the framework’s effectiveness as a hardware-independent, scalable solution for Noisy Intermediate-Scale Quantum (NISQ) devices. Instead, the study offers an approach toward a scalable, error-resilient model to avoid exaggerating scalability. Despite its promising outcomes, study is presently limited to simulations and a single noise model. Future work will explore implementation on real quantum hardware and extend the framework to incorporate a broader range of noise profiles, contributing to the evolution of fault-tolerant quantum computation.

Journal of Quantum Information Science•Jan 1, 2025•0 citations

Practical fault tolerance for quantum circuits

John David Kubiatowicz, Mark Whitney

Due to very high projected error rates, large scale quantum computers will require substantial fault tolerance just to maintain a minimum level of reliability. We present tools to better analyze the performance of large, fault tolerant quantum computer designs. We find that current uses of quantum error correction are overly conservative in mitigating the impact of gate errors and negligent of other error sources in quantum data communication and memory. We have developed circuit layout heuristics to generate detailed designs in trapped ion quantum computing technology. From these designs, we can extract much more accurate error models for a given application, including all gate, movement and idle errors on qubits. Using these extracted models, our flexible error simulation environment determines the overall failure probability of the design. Included in this simulation environment is a bit-parallel Monte Carlo technique that is 10 times faster than previous fault propagation simulations. This allows us to evaluate the reliability of designs that are an order of magnitude larger, in the same amount of time. Using this analysis framework to verify reliability, we have developed a linear programming-based optimization for error correction which decreases overall circuit resources by an order of magnitude. In some cases, our optimization actually improves overall system reliability by removing error correction. We combine this optimization with judicious quantum error correcting code selection to provide efficient designs for large quantum arithmetic kernels used in Shor's factorization algorithm. We show our optimized designs perform 2x to 100x better than previous works in terms of probabilistic area-delay product. Additionally, the area of our layout of a 1024-bit factoring using Shor's algorithm is 64cm2, a substantial improvement compared to the 0.9m2 state-of-the-art design from prior work. A design size reduction by this amount will make fabricating such an application feasible much sooner.

•Jan 1, 2009•15 citations

Performance Limits of Fault-Tolerant Quantum Error Correction Schemes

Lorenzo Valentini, Diego Forlivesi, Marco Chiani

Quantum error correction (QEC) is essential for realizing scalable quantum computation. However, when evaluating its benefits, most analyses assume idealized components, overlooking the imperfections inherent in realistic fault-tolerant (FT) implementations. In this paper, we investigate the performance of QEC schemes taking into account that quantum gates and measurements are themselves error-prone. We derive bounds for the failure probability of Shor-style FT-QEC schemes using limited structural information, such as the number of flag qubits and quantum gates. Our analysis separates and quantifies two key contributors to the failure rate: decoding errors and residual errors arising from circuit-level faults. The derived bounds highlight fundamental limitations in Shor-style FT-QEC performance and quantify how circuit imperfections degrade error correction capabilities, under the assumption of depolarizing noise.

quant-pharXiv:2605.24501•IEEE Journal on Selected Areas in Communications•May 26, 2026•0 citations

Demonstrating quantum error mitigation on logical qubits

Aosai Zhang, Haipeng Xie, Yu Gao +32 more

A long-standing challenge in quantum computing is developing technologies to overcome the inevitable noise in qubits. To enable meaningful applications in the early stages of fault-tolerant quantum computing, devising methods to suppress post-correction logical failures is becoming increasingly crucial. In this work, we propose and experimentally demonstrate the application of zero-noise extrapolation, a practical quantum error mitigation technique, to error correction circuits on superconducting processors. By amplifying the noise on physical qubits, the circuits yield outcomes that exhibit a predictable dependence on noise strength, following a polynomial function determined by the code distance. This property enables the effective application of polynomial extrapolation to mitigate logical errors. Our experiments demonstrate a universal reduction in logical errors across various quantum circuits, including fault-tolerant circuits of repetition and surface codes. We observe a favorable performance in multi-round error correction circuits, indicating that this method remains effective when the circuit depth increases. These results advance the frontier of quantum error suppression technologies, opening a practical way to achieve reliable quantum computing in the early fault-tolerant era. Quantum error mitigation refers to techniques that reduce, rather than correct, errors in quantum computing. Here the authors demonstrate zero-noise extrapolation applied to quantum error correction circuits on superconducting processors, effectively reducing logical errors and advancing early fault-tolerant quantum computing.

arXiv:2501.09079•Nature Communications•Dec 24, 2025•42 citations
Quantum algorithms face significant challenges due to qubit susceptibility to environmental noise, and quantum error correction typically requires prohibitive resource overhead. This paper proposes that quantum algorithms may possess inherent noise resilience characteristics that could reduce implementation barriers. We investigate Shor's algorithm by applying circuit-level noise models directly to the original algorithm circuit. Our findings reveal that Shor's algorithm demonstrates superior fault tolerance under Z noise compared to X and Y noise. Focusing on the modular exponentiation circuit which is the core component of the algorithm, we conduct fault-tolerant position statistics on circuits with bit lengths from 4 to 9. The results show that under Z noise, fault-tolerant positions grow with the same quartic polynomial order as potential error positions as the problem scale increases. In contrast, fault tolerance under X and Y noise exhibits a strong dependence on the composite number N and the parameter a. Based on these findings, we develop an extrapolation method predicting that the minimum probability of a correct output of the modular exponentiation circuit to factor 2048 bit integers under biased noise is approximately 1.417*{10}^{-17}.
Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.
With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.
This experimental study introduces a hybrid quantum-classical framework aiming to improve the noise robustness of Shor’s algorithm. By incorporating a novel hybrid logic gate into the modular exponentiation phase, the framework stabilizes qubit interactions and decreases decoherence in a noisy environment simulated by IBM Qiskit. Performance evaluation is accomplished by fidelity and entropy analysis across varied noise levels. Comparative benchmarking with conventional techniques, including Shor’s code, Bacon-Shor code, dynamical decoupling, and zero noise extrapolation, demonstrates that the proposed hybrid gate achieves higher fidelity (0.90) and lower entropy (0.33), while preserving minimal resource overhead. These findings highlight the framework’s effectiveness as a hardware-independent, scalable solution for Noisy Intermediate-Scale Quantum (NISQ) devices. Instead, the study offers an approach toward a scalable, error-resilient model to avoid exaggerating scalability. Despite its promising outcomes, study is presently limited to simulations and a single noise model. Future work will explore implementation on real quantum hardware and extend the framework to incorporate a broader range of noise profiles, contributing to the evolution of fault-tolerant quantum computation.
Due to very high projected error rates, large scale quantum computers will require substantial fault tolerance just to maintain a minimum level of reliability. We present tools to better analyze the performance of large, fault tolerant quantum computer designs. We find that current uses of quantum error correction are overly conservative in mitigating the impact of gate errors and negligent of other error sources in quantum data communication and memory. We have developed circuit layout heuristics to generate detailed designs in trapped ion quantum computing technology. From these designs, we can extract much more accurate error models for a given application, including all gate, movement and idle errors on qubits. Using these extracted models, our flexible error simulation environment determines the overall failure probability of the design. Included in this simulation environment is a bit-parallel Monte Carlo technique that is 10 times faster than previous fault propagation simulations. This allows us to evaluate the reliability of designs that are an order of magnitude larger, in the same amount of time. Using this analysis framework to verify reliability, we have developed a linear programming-based optimization for error correction which decreases overall circuit resources by an order of magnitude. In some cases, our optimization actually improves overall system reliability by removing error correction. We combine this optimization with judicious quantum error correcting code selection to provide efficient designs for large quantum arithmetic kernels used in Shor's factorization algorithm. We show our optimized designs perform 2x to 100x better than previous works in terms of probabilistic area-delay product. Additionally, the area of our layout of a 1024-bit factoring using Shor's algorithm is 64cm2, a substantial improvement compared to the 0.9m2 state-of-the-art design from prior work. A design size reduction by this amount will make fabricating such an application feasible much sooner.
Quantum error correction (QEC) is essential for realizing scalable quantum computation. However, when evaluating its benefits, most analyses assume idealized components, overlooking the imperfections inherent in realistic fault-tolerant (FT) implementations. In this paper, we investigate the performance of QEC schemes taking into account that quantum gates and measurements are themselves error-prone. We derive bounds for the failure probability of Shor-style FT-QEC schemes using limited structural information, such as the number of flag qubits and quantum gates. Our analysis separates and quantifies two key contributors to the failure rate: decoding errors and residual errors arising from circuit-level faults. The derived bounds highlight fundamental limitations in Shor-style FT-QEC performance and quantify how circuit imperfections degrade error correction capabilities, under the assumption of depolarizing noise.
A long-standing challenge in quantum computing is developing technologies to overcome the inevitable noise in qubits. To enable meaningful applications in the early stages of fault-tolerant quantum computing, devising methods to suppress post-correction logical failures is becoming increasingly crucial. In this work, we propose and experimentally demonstrate the application of zero-noise extrapolation, a practical quantum error mitigation technique, to error correction circuits on superconducting processors. By amplifying the noise on physical qubits, the circuits yield outcomes that exhibit a predictable dependence on noise strength, following a polynomial function determined by the code distance. This property enables the effective application of polynomial extrapolation to mitigate logical errors. Our experiments demonstrate a universal reduction in logical errors across various quantum circuits, including fault-tolerant circuits of repetition and surface codes. We observe a favorable performance in multi-round error correction circuits, indicating that this method remains effective when the circuit depth increases. These results advance the frontier of quantum error suppression technologies, opening a practical way to achieve reliable quantum computing in the early fault-tolerant era. Quantum error mitigation refers to techniques that reduce, rather than correct, errors in quantum computing. Here the authors demonstrate zero-noise extrapolation applied to quantum error correction circuits on superconducting processors, effectively reducing logical errors and advancing early fault-tolerant quantum computing.