A major obstacle to implementing Shor's quantum number-factoring algorithm is the large size of modular-exponentiation circuits. We reduce this bottleneck by customizing reversible circuits for modular multiplication to individual runs of Shor's algorithm. Our circuit-synthesis procedure exploits spectral properties of multiplication operators and constructs optimized circuits from the traces of the execution of an appropriate greatest-common-divisor algorithm. Empirically, gate counts are reduced by four to five times, and circuit latency is reduced by larger factors.
A major obstacle to implementing Shor's quantum number-factoring algorithm is the large size of modular-exponentiation circuits. We reduce this bottleneck by customizing reversible circuits for modular multiplication to individual runs of Shor's algorithm. Our circuit-synthesis procedure exploits spectral properties of multiplication operators and constructs optimized circuits from the traces of the execution of an appropriate greatest-common-divisor algorithm. Empirically, gate counts are reduced by four to five times, and circuit latency is reduced by larger factors.
Reversible circuits for modular multiplication Cx%M with x<M arise as components of modular exponentiation in Shor's quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific C and M values. In this work, we develop such optimizations in a bottom-up fashion, starting with most convenient C values. When zero-initialized ancilla registers are available, we reduce the search for compact circuits to a shortest-path problem. Some of our modular-multiplication circuits are asymptotically smaller than previous constructions, but worst-case bounds and average sizes remain Θ(n2). In the context of modular exponentiation, we offer several constant-factor improvements, as well as an improvement by a constant additive term that is significant for few-qubit circuits arising in ongoing laboratory experiments with Shor's algorithm.
Reversible circuits for modular multiplication Cx%M with x < M arise as components of modular exponentiation in Shor's quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific C and M values. In this work, we develop such optimizations in a bottom-up fashion, starting with most convenient C values. When zero-initialized ancilla registers are available, we reduce the search for compact circuits to a shortest-path problem. Some of our modular-multiplication circuits are asymptotically smaller than previous constructions, but worst-case bounds and average sizes remain Θ(n2). In the context of modular exponentiation, we offer several constant-factor improvements, as well as an improvement by a constant additive term that is significant for few-qubit circuits arising in ongoing laboratory experiments with Shor's algorithm.
Shor's algorithm for the prime factorization of numbers provides an exponential speedup over the best known classical algorithms. However, nontrivial practical applications have remained out of reach due to experimental limitations. The bottleneck of the experimental realization of the algorithm is the modular exponentiation operation. In this paper, based on a relation between the modular multiplication operator and generalizations of discrete Fourier transforms, we propose a quantum circuit for modular exponentiation. A distinctive feature of our proposal is that our circuit can be entirely implemented in terms of the standard quantum circuit for the discrete Fourier transform and its variants. The gate-complexity of our proposal is O(L3) where L is the number of bits required to store the number being factorized. It is possible that such a proposal may provide easier avenues for near-term generic implementations of Shor's algorithm, in contrast to existing realizations which have often explicitly adapted the circuit to the number being factorized.
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.
We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.
We provide two improvements to Regev's recent quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using O(nlogn) qubits and O(n3/2logn) gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires O(n3/2) qubits and O(n3/2logn) gates, while Shor's circuit requires O(n2logn) gates but only O(nlogn) qubits. As with Regev, to factor an n-bit integer N, we run our circuit independently O(n) times and apply Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling in-place quantum-quantum modular multiplication. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all ≈n runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.