We study effects of imperfections induced by residual couplings between qubits on the accuracy of Shor's algorithm using numerical simulations of realistic quantum computations with up to 30 qubits. The factoring of numbers up to
N=943 show that the width of peaks, which frequencies allow to determine the factors, grow exponentially with the number of qubits. However, the algorithm remains operational up to a critical coupling strength
ϵc which drops only polynomially with
log2N. The numerical dependence of
ϵc on
log2N is explained by analytical estimates that allows one 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.
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 factoring algorithm is one of the most anticipated applications of quantum computing. However, the limited capabilities of today's quantum computers only permit a study of Shor's algorithm for very small numbers. Here we show how large GPU-based supercomputers can be used to assess the performance of Shor's algorithm for numbers that are out of reach for current and near-term quantum hardware. First, we study Shor's original factoring algorithm. While theoretical bounds suggest success probabilities of only 3-4 %, we find average success probabilities above 50 %, due to a high frequency of "lucky" cases, defined as successful factorizations despite unmet sufficient conditions. Second, we investigate a powerful post-processing procedure, by which the success probability can be brought arbitrarily close to one, with only a single run of Shor's quantum algorithm. Finally, we study the effectiveness of this post-processing procedure in the presence of typical errors in quantum processing hardware. We find that the quantum factoring algorithm exhibits a particular form of universality and resilience against the different types of errors. The largest semiprime that we have factored by executing Shor's algorithm on a GPU-based supercomputer, without exploiting prior knowledge of the solution, is 549755813701 = 712321 * 771781. We put forward the challenge of factoring, without oversimplification, a non-trivial semiprime larger than this number on any quantum computing device.
Quantum algorithms are computational routines that exploit quantum mechanics to solve problems exponentially faster than the best classical algorithms. Shor's quantum factoring algorithm is a key example and the prime motivator in the international effort to realise a quantum computer. However, due to the large number of resources required, to date, there have been only four small scale demonstrations. Here we address this resource demand and demonstrate a scalable version of Shor's algorithm in which then qubit control register is replaced by a single qubit that is recycled n times: the total number of qubits is one third of that required in the standard protocol. Encoding the work register in higher-dimensional states, we implement a two-photon compiled algorithm to factor N = 21. Significantly, the algorithmic output exhibits structure that is distinguishable from noise, in contrast to previous demonstrations.