We report on the current state of factoring integers on both digital and analog quantum computers. For digital quantum computers, we study the effect of errors for which one can formally prove that Shor's factoring algorithm fails. For analog quantum computers, we experimentally test three factorisation methods and provide evidence for a scaling performance that is absolutely and asymptotically better than random guessing but still exponential. We conclude with an overview of future perspectives on factoring large integers on quantum computers.
We report on the current state of factoring integers on both digital and analog quantum computers. For digital quantum computers, we study the effect of errors for which one can formally prove that Shor's factoring algorithm fails. For analog quantum computers, we experimentally test three factorisation methods and provide evidence for a scaling performance that is absolutely and asymptotically better than random guessing but still exponential. We conclude with an overview of future perspectives on factoring large integers on quantum computers.
Factoring large integers has long been a computationally difficult problem in classical computing, forming the foundation of widely used encryption methods like RSA. In 1994, Shor’s quantum algorithm introduced a revolutionary method for factoring integers exponentially faster than classical algorithms, laying the groundwork for quantum cryptography. Despite numerous attempts to enhance Shor’s algorithm over the last three decades, significant breakthroughs remained elusive until Regev’s discovery in 2023. Regev introduced a novel, multi-dimensional version of the quantum factoring algorithm, achieving a substantial improvement by reducing the required number of quantum gates to O(n^2 lo gn )(n^(3/2) logn ), compared to Shor’s originalO(n^2 lo gn )original O(n^2 logn ) gate complexity. Although Regev’s approach offers a significant speedup, it comes with increased qubit requirements and relies on an unproven number theory assumption. This paper presents an overview of Regev’s factoring algorithm, including a review of Shor’s work for context, followed by an examination of key recent developments and follow-up research. These include efforts to reduce the qubit count, improve error resilience, generalizegeneralise Regev’s algorithm to related problems, and validate the number theory assumption. This review serves as an accessible entry point for researchers interested in the rapidly evolving field of quantum computing and factoring algorithms.
The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this reduction has proved to be useful for studying SAT solvers, large integers have not been factored via such a reduction. Shor's quantum factoring algorithm factors integers in expected polynomial time. Large-scale fault-tolerant quantum computers capable of implementing Shor's algorithm are not yet available, preventing relevant benchmarking experiments. Recently, several authors have attempted quantum factorizations via reductions to SAT or similar NP-hard problems. While this approach may shed light on algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question its practicality. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware.
The quantum algorithms covered in this chapter, i.e., the Deutsch, Deutsch-Jozsa and Bernstein-Vazirani algorithms, have been chosen for their relative simplicity and theoretical interest. They do not address problems of real practical value, their purpose being to demonstrate, using simple examples, the great potential power of quantum computation relative to the digital case. The most significant breakthrough in quantum computing is Shor's integer factorisation algorithm. Shor's algorithm is beyond the scope of this introductory text, but its significance lies in the fact that it demonstrates the potential to factor large integers efficiently. No efficient digital algorithms for factoring large integers exist, and many current encryption algorithms rely on this being the case. Shor's algorithm therefore threatens current encryption methods, and is responsible for much of the recent accelerated interest in quantum computation.
We present our perspectives on the current status of, integer factoring and discrete logarithm, algorithms underlying the strength of classical public-key cryptography protocols used in key-exchange, encryption and digital signatures. We present an expository overview of the algebraic, number-theoretic and algorithmic principles behind the canonical, powerful algorithms used in the factoring of large, composite RSA modulii. These cover the two main ideas of group order based methods, and quadratic congruence based methods. We provide the resource estimates for the record breaking factoring based on the general number field sieve. Next we present an overview of the algorithmic theory of quantum computation behind, the polynomial time Shor's quantum algorithm for, period finding in hidden subgroup structure problems. This algorithm has played a key role in advancing post-quantum cryptography, and also in the exciting, contemporary developments in quantum computing, networking, sensing, and materials science as a whole. Latest advances in quantum computing rest on a variety of physics, engineering, algorithms, compilation, hardware, software techniques. There are several tradeoffs based on number of qubits, coherence times, control issues, errors and fault tolerance. In this environment, nuances of mathematical ideas, behind every step of the intricate arithmetical and algebraic computations under quantum models plays a significant role. We provide an overview of some of the recent ideas behind such algorithms. We conclude with a recent deep question on the ultimate feasibility of ultra large-scale, error-free, discrete, quantum computations required typically in cryptanalysis.
Quantum computers pose a fundamental threat to widely deployed public-key cryptosystems, such as RSA and ECC, by enabling efficient integer factorization using Shor's algorithm. Theoretical resource estimates suggest that 2048-bit RSA keys could be broken using Shor's algorithm with fewer than a million noisy qubits. Although such machines do not yet exist, the availability of smaller, cloud-accessible quantum processors and open-source implementations of Shor's algorithm raises the question of what key sizes can realistically be factored with today's platforms. In this work, we experimentally investigate Shor's algorithm on several cloud-based quantum computers using publicly available implementations. Our results reveal a substantial gap between the capabilities of current quantum hardware and the requirements for factoring cryptographically relevant integers. In particular, we observe that circuit constructions still need to be highly specific for each modulus, and that machine fidelities are unstable, with high and fluctuating error rates.
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.