We construct a quantum circuit for Shor's factoring algorithm that uses 2n+2 qubits, where n is the length of the number to be factored. The depth and size of the circuit are O(n^3) and O(n^3\log n), respectively. The number of qubits used in the circuit is less than that in any other quantum circuit ever constructed for Shor's factoring algorithm. Moreover, the size of the circuit is about half the size of Beauregard's quantum circuit for Shor's factoring algorithm, which uses 2n+3 qubits.
Shor's factoring algorithm (SFA), by its ability to efficiently factor large numbers, has the potential to undermine contemporary encryption. At its heart is a process called order finding, which quantum mechanics lets us perform efficiently. SFA thus consists of a \emph{quantum order finding algorithm} (QOFA), bookended by classical routines which, given the order, return the factors. But, with probability up to
1/2, these classical routines fail, and QOFA must be rerun. We modify these routines using elementary results in number theory, improving the likelihood that they return the factors. The resulting quantum factoring algorithm is better than SFA at factoring safe semiprimes, an important class of numbers used in cryptography. With just one call to QOFA, our algorithm almost always factors safe semiprimes. As well as a speed-up, improving efficiency gives our algorithm other, practical advantages: unlike SFA, it does not need a randomly picked input, making it simpler to construct in the lab; and in the (unlikely) case of failure, the same circuit can be rerun, without modification. We consider generalizing this result to other cases, although we do not find a simple extension, and conclude that SFA is still the best algorithm for general numbers (non safe semiprimes, in other words). Even so, we present some simple number theoretic tricks for improving SFA in this case.
“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.