We show that n -bit integers can be factorized by independently running a quantum circuit with \(\tilde{O}(n^{3/2})\) gates for \(\sqrt {n}+4\) times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a certain number-theoretic conjecture. It is currently not clear if the algorithm can lead to improved physical implementations in practice.
We show that n -bit integers can be factorized by independently running a quantum circuit with (\tilde{O}(n^{3/2})) gates for (\sqrt {n}+4) times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a certain number-theoretic conjecture. It is currently not clear if the algorithm can lead to improved physical implementations in practice.
We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). Most notably, we factor n-bit integers of the form P2Q with logQ=Θ(na) for a∈(2/3,1) in space and depth sublinear in n (specifically, O~(logQ)) using O~(n) quantum gates; for these integers, no known classical algorithms exploit the relatively small size of Q to run asymptotically faster than general-purpose factoring algorithms. To our knowledge, this is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem. Our circuit builds on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du, and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of A mod B, in the regime where B is classical and much larger than A. Our circuit for computing the Jacobi symbol generalizes to related problems such as computing the greatest common divisor and modular inverses, and thus could be of independent interest.
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.
Abstract We show that given the order of a single element selected uniformly at random from ZN∗ Z N ∗ , we can with very high probability, and for any integer N, efficiently find the complete factorization of N in polynomial time. This implies that a single run of the quantum part of Shor’s factoring algorithm is usually sufficient. All prime factors of N can then be recovered with negligible computational cost in a classical post-processing step. The classical algorithm required for this step is essentially due to Miller.
A common starting point of traditional quantum algorithm design is the notion of a universal quantum computer with a scalable number of qubits. This convenient abstraction mirrors classical computations manipulating bits. It allows for a device-independent development of algorithmic primitives. Here we argue that an alternative approach centered on the physical setup can yield great benefits. As an example, we consider hybrid qubit-oscillator systems with linear optics operations augmented by certain qubit-controlled Gaussian unitaries. The continuous variable Fourier transform and certain arithmetic operations have native realizations in such systems. We put this to algorithmic use and give a polynomial-time quantum factoring algorithm which uses only one qubit and three oscillators, independent of the number being factored.
One of the most well known mathematically hard problems in number theory is the integer factorization problem, roughly stated that decomposition of a composite number into its prime factors. In modern cryptography, RSA encryption algorithm whose security is based on integer factorization problem is highly practical, widespread and up to date no classical algorithm having polynomial running time for the factorization of large numbers is known. In 1994, Peter Shor proposed an efficient algorithm on quantum computer. In this paper, we mention about the fundamentals of Shor's quantum algorithm illustrating a concrete example.
The integer factorization problem (IFP) underpins the security of RSA, yet becomes efficiently solvable on a quantum computer through Shor's algorithm. Regev's recent high-dimensional variant reduces the circuit size through lattice-based post-processing, but introduces substantial space overhead and lacks practical implementations. Here, we propose a qubit reuse method by intermediate-uncomputation that significantly reduces the space complexity of Regev's algorithm, inspired by reversible computing. Our basic strategy lowers the cost from O(n3/2) to O(n5/4), and refined strategies achieve O(nlogn)which is a space lower bound within this model. Simulations demonstrate the resulting time-space trade-offs and resource scaling. Moreover, we construct and compile quantum circuits that factor N=35, verifying the effectiveness of our method through noisy simulations. A more simplified experimental circuit for Regev's algorithm is executed on a superconducting quantum computer, with lattice-based post-processing successfully retrieving the factors. These results advance the practical feasibility of Regev-style quantum factoring and provide guidance for future theoretical and experimental developments.