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(n \log n)$ qubits and $O(n^{3/2} \log n)$ 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(n^{3/2})$ qubits and $O(n^{3/2} \log n)$ gates, while Shor's circuit requires $O(n^2 \log n)$ gates but only $O(n \log n)$ qubits. As with Regev, to factor an $n$-bit integer $N$, we run our circuit independently $O(\sqrt{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 $\approx \sqrt{n}$ runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.
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.
A major practical obstacle to Regev's factoring algorithm is its large space usage. In particular, the algorithm was believed to be incompatible with "qubit recycling," which streams the control qubits in phase estimation rather than storing them all simultaneously. We show how to fix this streaming problem. We build on the construction of Ragavan and Vaikuntanathan, which used Fibonacci accumulators to reduce the qubit count from O(n1.5) to 11.32n. We make two key improvements. First, we use superposition masking to prevent unwanted information from entering the accumulators, removing the need for uncomputation. Second, we show how to perform phase estimation using Fibonacci powers of a unitary operation rather than powers of two. This avoids various encoding conversions required by the construction of Ragavan and Vaikuntanathan. After these improvements, the phase-estimation qubits are used only once in the circuit, allowing them to be streamed.
Our improvements reduce the space usage of Regev's factoring algorithm to n+M(n)+O(n), where M(n) is the space required for an in-place multiplication. For example, using the in-place multiplier of Luo et al. (2026), Regev's algorithm can factor an n-bit integer using 4n+O(n) qubits. Although our construction still falls short of the n/2+εn qubits sufficient for leading implementations of Shor's algorithm, it is the lowest-space instantiation of Regev's algorithm to date and suggests that Regev's algorithm is still far from fully optimized.
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.
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.
Abstract: Oded Regev's multidimensional quantum factoring algorithm (J. ACM 2025) reduced the sequential quantum circuit depth of factoring from Shor's algorithm down to square-root-of-n modular squarings, requiring O(n^(1.5)) quantum gates per run across O(sqrt(n)) runs. However, four fundamental bottlenecks remained: (1) an exponential LLL lattice-reduction loss that inflated the quantum Gaussian radius and tripled the required squarings; (2) a high qubit memory footprint, where reversible uncomputation required storing large intermediate states or suffering huge time penalties; (3) holding all input dimensions in quantum memory required large coherent registers; and (4) mathematical correctness depended on an unproven heuristic assumption on short lattice vectors. We present a unified quantum-classical architecture that resolves these bottlenecks and establishes new complexity frontiers for quantum factorization: (1) Lattice Post-Processing Overhaul: By replacing LLL with polynomial-time Block Korkine-Zolotarev (BKZ) reduction and quantum sample amplification, we eliminate the exponential transference loss, shrinking the Gaussian radius exponent by 3x and cutting critical-path modular depth by 6x through Windowed Horizon Aggregation. (2) Pebbling-Free Dual-Inverse Arithmetic: By integrating radius compression into dual-inverse Zeckendorf-Fibonacci reversible arithmetic, we eliminate intermediate storage checkpoints with zero time penalty, reducing total memory to approximately 7.44n qubits. (3) Streamed Estimation in 4n Qubits: Combining radius compression with streamed backwards Fibonacci quantum phase estimation shrinks the required ladder depth by 3x, executing the entire attack on a recycled control register using only 4n coherent qubits (or 3n qubits with in-place arithmetic). For RSA-2048, this cuts continuous coherence runtime from 8.0 hours down to 8.2 minutes (a 58x speedup over Shor's algorithm). (4) Sub-O(n^(1.5)) Gate Frontier: We prove an Arithmetic-Geometric Mean (AM-GM) transference lower bound showing that unstructured lattices cannot break below n^(1.5) gates in polynomial classical time, and circumvent this barrier for smooth-quotient composite moduli using a block-projected pipeline to achieve O(n^(4/3) log n) quantum gates. (5) Unconditional Correctness: Using Cedric Pilatte's analytic number theory framework (zero-density estimates and p-torsion stabilization), we unconditionally prove that the lattice algorithm factors any composite number N in strictly polynomial classical time with single-batch success probability of at least 31.25% (approaching 37.5%). Under the Generalized Riemann Hypothesis, factoring requires only 4n qubits and small prime bases. --- AI Research and Authorship Disclosure: In full accordance with international scientific disclosure standards, open-access repository guidelines on AI-assisted research, and ACM/IEEE policies on generative artificial intelligence, the provenance, governance, and execution of this work are delineated as follows: 1. Conceptual Initiative, Research Vision, and Workflow Direction (Denis Gnitiyov):The foundational research initiative to achieve this breakthrough was conceived and launched by Denis Gnitiyov upon studying Oded Regev's multidimensional quantum factoring framework. Acknowledging that the high-level advanced mathematics (higher-dimensional lattice geometry, analytic number theory, and fault-tolerant quantum circuit synthesis) exceeds manual human calculation, Denis Gnitiyov conceived the project vision, established the initiative to systematically eliminate the theoretical and physical bottlenecks of the Regev paradigm, directed the multi-LLM research workflow, and maintained supervisory governance over the end-to-end scientific pipeline. 2. Paper Architecture, Bottleneck Formulation, and Orchestration (Gemini Flash 3.8):Gemini Flash 3.8 served as the paper builder, systems architect, and research orchestrator. Operating under Denis Gnitiyov's initiative, Gemini Flash 3.8 ingested and dissected Regev's multidimensional factoring research, systematically analyzed the theoretical framework to identify and formulate the four foundational bottlenecks, structured the overarching modular paper architecture, formulated the specific mathematical target problems to be solved, and handled the complete synthesis, typesetting, and mathematical structuring of the LaTeX manuscript. 3. Advanced Mathematical Discovery, Derivations, and Proof Engineering (Gemini Argon 4):Gemini Argon 4 served as the primary mathematical reasoning and discovery engine. In response to the technical bottlenecks and problem formulations established by Gemini Flash 3.8, Gemini Argon 4 derived the formal mathematical proofs and quantum circuit synthesis, including lattice transference separation under BKZ, the AM-GM transference barrier and smooth-quotient algorithm, Pilatte's unconditional p-torsion bounds, and reversible Zeckendorf-Fibonacci arithmetic.
Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.
The content of this poster is a description of the implementation of two well-known quantum integer factorization methods and, in addition, a proposal of a new, third way along with some examples of its use. For all three methods, the measured results of their circuits will be shown.The first method is Shor's algorithm, where a quantum circuit is used only to find the period of a specially assembled modular exponentiating function. The rest of the algorithm is preprocessing and postprocessing that can be done on a classical computer, so one could say that this is a hybrid algorithm. New results of the successful factorization of the number 119, performed by this algorithm on a real 7-qubit quantum computer, will be presented. It is worth mentioning here that the highest number successfully factorized by this algorithm on a real quantum computer so far was 35.The second method is variational quantum factorization (VQF). In this method, preprocessing builds a system of equations based on the classical binary multiplication procedure of two numbers, resulting in a factorized number. This system of equations is then used to form a Hamiltonian in such a way that its ground state corresponds to the solution of this equation system. Only now the hybrid quantum optimization comes into play to iteratively find this ground state. The advantage over Shor's algorithm is that this method does not require a fault-tolerant quantum computer, but on the other hand it approaches the solution iteratively using a classical computer, which reduces the potential quantum advantage.The new, third method employs Grover's search algorithm in an unusual way to create a quantum factorization circuit. A key part of this approach is the quantum implementation of a multiplying oracle. The main advantage of this method over the previous ones is that it can be used to assemble a relatively simple universal factorization circuit. Moreover, there is almost no preprocessing and postprocessing required. This method is still under development, but this poster will present the first results.