We formulate and numerically simulate the single control qubit Shor algorithm for the case of static imperfections induced by residual couplings between qubits. This allows us to study the accuracy of Shor's algorithm with respect to these imperfections using numerical simulations of realistic quantum computations with up to
nq=18 computational qubits allowing to factor numbers up to
N=205193. We confirm that the algorithm remains operational up to a critical coupling strength
ϵc which drops only polynomially with
log2N. The obtained numerical dependence of
ϵc on
log2N is in a good agreement with the analytical estimates that allows to obtain the scaling for functionality of Shor's algorithm on realistic quantum computers with a large number of qubits.
Ideal quantum algorithms usually assume that quantum computing is performed continuously by a sequence of unitary transformations. However, there always exist idle finite time intervals between consecutive operations in a realistic quantum computing process. During these delays, coherent errors will accumulate from the dynamical phases of the superposed wave functions. Here we explore the sensitivity of Shor's quantum factoring algorithm to such errors. Our results clearly show a severe sensitivity of Shor's factorization algorithm to the presence of delay times between successive unitary transformations. Specifically, in the presence of these coherent errors, the probability of obtaining the correct answer decreases exponentially with the number of qubits of the work register. A particularly simple phase-matching approach is proposed in this paper to avoid or suppress these coherent errors when using Shor's algorithm to factorize integers. The robustness of this phase-matching condition is evaluated analytically and numerically for the factorization of several integers: 4, 15, 21, and 33.
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.
The publication in 1994 of Shor's algorithm, which allows factorisation of composite number N in a time polynomial in its binary length L has been the primary catalyst for the race to construct a functional quantum computer. However, it seems clear that any practical system that may be developed will not be able to perform completely error free quantum gate operations or shield even idle qubits from inevitable error effects. Hence, the practicality of quantum algorithms needs to be investigated to not only determine limitations on such algorithms in a noisy quantum computer, but also to estimate what demands must be made of quantum error correction (QEC). Shor's algorithm is a combination of both classical pre and post-processing, and also a quantum period finding subroutine (QPF) which allows for the exponential speed up of this algorithm on a quantum device. This paper will look at the stability of this quantum subroutine under the effects of several error models. Direct simulation of the entire QPF subroutine required to factorise a given composite number N in the presence of errors shows that the circuit required to implement Shor's algorithm is very sensitive to a small number of errors within the entire calculation. Well designed and efficient error correction codes, quick gate times and very low gate error rates will be essential for any physical realisation of Shor's factoring algorithm.
In Shor's algorithm quantum subroutines occur with the structure $\mathcal{F}\mathcal{U}{\mathcal{F}}^{\ensuremath{-}1}$, where
F is a unitary transform and
U is performing a quantum computation. Examples are quantum adders and subunits of quantum modulo adders. In this paper we show, both analytically and numerically, that if, in analogy to spin echoes,
F and ${\mathcal{F}}^{\ensuremath{-}1}$ can be implemented symmetrically when executing Shor's algorithm on actual, imperfect quantum hardware, such that
F and ${\mathcal{F}}^{\ensuremath{-}1}$ have the same hardware errors, a symmetry boost in the fidelity of the combined $\mathcal{F}\mathcal{U}{\mathcal{F}}^{\ensuremath{-}1}$ quantum operation results when compared to the case in which the errors in
F and ${\mathcal{F}}^{\ensuremath{-}1}$ are independently random. Running the complete gate-by-gate implemented Shor algorithm, we show that the symmetry-induced fidelity boost can be as large as a factor 4. While most of our analytical and numerical results concern the case of over- and under-rotation of controlled rotation gates, in the numerically accessible case of Shor's algorithm with a small number of qubits, we show explicitly that the symmetry boost is robust with respect to more general types of errors. While, expectedly, additional error types reduce the symmetry boost, we show explicitly, by implementing general off-diagonal
SU(N) errors (
N=2,4,8), that the boost factor scales like a Lorentzian in $\ensuremath{\delta}/\ensuremath{\sigma}$, where $\ensuremath{\sigma}$ and $\ensuremath{\delta}$ are the error strengths of the diagonal over- and underrotation errors and the off-diagonal
SU(N) errors, respectively. The Lorentzian shape also shows that, while the boost factor may become small with increasing $\ensuremath{\delta}$, it declines slowly (essentially like a power law) and is never completely erased. We also investigate the effect of diagonal nonunitary errors, which, in analogy to unitary errors, reduce but never erase the symmetry boost. Going beyond the case of small quantum processors, we present analytical scaling results that show that the symmetry boost persists in the practically interesting case of a large number of qubits. We illustrate this result explicitly for the case of Shor factoring of the semiprime RSA-1024, where, analytically, focusing on over- and underrotation errors, we obtain a boost factor of about 10. In addition, we provide a proof of the fidelity product formula, including its range of applicability.
Shor's algorithm (SA) is a quantum algorithm for factoring integers. Since SA has polynomial complexity while the best classical factoring algorithms are sub-exponential, SA is cited as evidence that quantum computers are more powerful than classical computers. SA is critically dependent on the Quantum Fourier Transform (QFT) and it is known that the QFT is sensitive to errors in the quantum state input to it. In this paper, we show that the polynomial scaling of SA is destroyed by input errors to the QFT part of the algorithm. We also show that Quantum Error Correcting Codes (QECC) are not capable of suppressing errors due to operator imprecision and that propagation of operator precision errors is sufficient to severely degrade the effectiveness of SA. Additionally we show that operator imprecision in the error correction circuit for the Calderbank-Shor-Steane QECC is mathematically equivalent to decoherence on every physical qubit in a register. We conclude that, because of the effect of operator precision errors, it is likely that physically realizable quantum computers will be capable of factoring integers no more efficiently than classical computers.