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.
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.
Peter Shor's in 1994 developed a factoring algorithm that can factor a composite number
nin a polynomial time by using a quantum computer in one step of the algorithm. The algorithm may contain a loop that requires calling a quantum computer many times to find the order of selected number
a,a∈Zn. In this paper, the improvement to the Shor's factoring algorithm guarantees the single use of the quantum computer to find the order, where the rest of the algorithm can be implemented by a classical computer. A numerical example for the original and improved version is presented.