Shor's factorisation algorithm is a combination of classical pre- and post-processing and a quantum period finding (QPF) subroutine which allows an exponential speed up over classical factoring algorithms. We consider the stability of this subroutine when exposed to a discrete error model that acts to perturb the computational trajectory of a quantum computer. Through detailed state vector simulations of an appropriate quantum circuit, we show that the error locations within the circuit itself heavily influences the probability of success of the QPF subroutine. The results also indicate that the naive estimate of required component precision is too conservative.
Shor's factorisation algorithm is a combination of classical pre- and post-processing and a quantum period finding (QPF) subroutine which allows an exponential speed up over classical factoring algorithms. We consider the stability of this subroutine when exposed to a discrete error model that acts to perturb the computational trajectory of a quantum computer. Through detailed state vector simulations of an appropriate quantum circuit, we show that the error locations within the circuit itself heavily influences the probability of success of the QPF subroutine. The results also indicate that the naive estimate of required component precision is too conservative.
The publication in 1994 of Shor's algorithm, which allows factorization 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 estimate what demands must be made of quantum error correction (QEC). Several different quantum circuits implementing the quantum period finding (QPF) subroutine, which lies at the heart of Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits can be interacted. While some architectures posses this property, many promising proposals are best suited to realizing a single line of qubits with nearest neighbor interactions only. This paper will present a circuit suitable for implementing the QPF subroutine for such linear nearest neighbor (LNN) designs. We will then present direct simulation results showing for both the LNN circuit and for a circuit utilizing arbitrary interactions, that the QPF subroutine is very sensitive to a small number of errors in the entire circuit. These results can then be used to briefly examine some of the practical issues to implementing such large scale quantum algorithms.
The publication in 1994 of Shor's algorithm, which allows factorization 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 estimate what demands must be made of quantum error correction (QEC). Several different quantum circuits implementing the quantum period finding (QPF) subroutine, which lies at the heart of Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits can be interacted. While some architectures posses this property, many promising proposals are best suited to realizing a single line of qubits with nearest neighbor interactions only. This paper will present a circuit suitable for implementing the QPF subroutine for such linear nearest neighbor (LNN) designs. We will then present direct simulation results showing for both the LNN circuit and for a circuit utilizing arbitrary interactions, that the QPF subroutine is very sensitive to a small number of errors in the entire circuit. These results can then be used to briefly examine some of the practical issues to implementing such large scale quantum algorithms.
“Shor's Algorithm: Factoring and Cryptanalysis” focuses on Shor's Algorithm, particularly its application to factoring and cryptanalysis. It begins with an overview of Shor's algorithm, detailing the classical extraction of periods from measured values and the quantum gates required for the Quantum Fourier Transform (QFT). Further, this chapter explores the applications and limitations of Shor's algorithm, including its impact on RSA encryption. A literature review follows, discussing Shor's algorithm in the context of quantum computation, its effectiveness on RSA, and the effects of imperfections on its factorization process. The section also includes an experimental study of Shor's algorithm using IBM Q, followed by a practical implementation of factoring numbers N=21 and N=35. Further, it covers resource estimation, quantum simulations, and different types of simulators in IBM Qiskit, including state vector, QASM, Matrix Product State (MPS), and stabilizer simulators, providing insights into their use cases and the limits of classical simulation.
Quantum Shor’s algorithm offers an exponential speedup over classical methods for integer factorization, a central problem to modern cryptography, and the implica- tions of Shor’s algorithm in factoring large numbers. The algorithm leverages on quantum parallelism to compute the period of a modular exponentiation function, employ- ing the Inverse Quantum Fourier Transform (IQFT) to extract periodicity, and classical post-processing to derive the factors. This final report of the Quantum Engineer- ing post-graduate course of the Fundacio Polit ́ enica de ` Catalunya, presents the main findings encountered in the implementation and benchmarking of Schor’s algorithm in real IBM quantum computers. To accomplish this, we created a command line tool made in Python, that allows the integration of the circuits implementing the Shor’s algorithm with the overall set of configuration parameters needed to perform the benchmark. In this report, we first provide an overview of the quantum factoring problem, followed by a detailed description of Shor’s algorithm, and its implementation using the Qiskit Python library. The circuit depth and noise effects are analyzed across different backend types, also different values for the optimization level and approximation degrees are configured when performing the circuit transpilation. As mentioned earlier different backend types were utilized for performance comparison, namely backend class with or without a noise model (AerSim), a fake backend class provided by the Qiskit library (fake provider), and the real quantum hardware (IBM Quantum Processing Units in January- June 2025).The study follows by analyzing the different error mitigation techniques: dynamic decoupling, Pauli twirling, the SABRE Optimization (Stochastic Algorithm for Quantum Boolean Optimization and Routing), and any combination of them. Once the optimum configuration is found, the maximum number that can be reasonably factorized with success is explored. Finally, the main conclusions, findings, and possible future research lines are presented, including the factorization of a N ≈ 1000 if appropriate parameters of the algorithm are selected.
A fundamental problem in factorization by Shor's algorithm [1] is the implementation of the modular exponentiation function. The period of this function is important for determining the individual factors, so its accurate implementation is for successful factorization critical.The imprecision of current quantum computers requires that any quantum circuits should be as simple as possible. Both in terms of the number of qubits used, the number of quantum gates and the depth of the quantum circuit. Therefore, it is necessary to search for an optimal variant for the implementation of the above-mentioned modular exponentiation function.The standard method is to implement individual arithmetic functions [2] which can be combined to achieve the desired modular exponentiation function. This process, however, creates a very complex quantum circuit, so that its measured result (probability distribution) will be so skewed that it will not be possible to reliably obtain the period of sought.Another way is to create a special quantum circuit for one particular modular exponentiation function [3]. Such a circuit is of course simpler than the circuit created by the above universal implementation, but in practice it only makes sense for testing the functionality of the surrounding quantum circuit for period detection.A very interesting possibility for the implementation of arithmetic functions is to use the direct and inverse quantum Fourier transform [4]. For a quantum computer, these transformations are very easy operations, and this interesting feature can then be used to advantage in these various implementations.This contribution will explore these possible approaches and show their advantages and disadvantages through concrete examples.
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 549,755,813,701 = 712,321 × 771,781. We put forward the challenge of factoring, without oversimplification, a non-trivial semiprime larger than this number on any quantum computing device.