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(n^{1.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(\sqrt{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(\sqrt{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.
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.
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: 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.
Decomposing finite Abelian black-box groups into cyclic factors is a basic problem in quantum computation. We give a quantum algorithm for decomposing finite Abelian black-box groups by adapting the quantum sampling and classical lattice-reduction method of Regev's factoring algorithm. The algorithm computes an invariant-factor decomposition and corresponding cyclic generators with high probability. For a group G of order at most 2^n with unique encodings and reversible group-operation cost T_op = Omega(sqrt(n)), our algorithm uses O(sqrt(n)) quantum circuits, each with O~(n T_op) gates and executed at most O(n) times.
For comparison, we consider the Cheung-Mosca algorithm, which decomposes the Sylow p-subgroups separately. We also consider the common-modulus implementation of the extended Cheung-Mosca algorithm. Our algorithm reduces the sum of the circuit gate counts from O~(n^2 T_op) to O~(n^(3/2) T_op). The total quantum time bound reduces from O~(n^3 T_op) to O~(n^(5/2) T_op), and the quantum space bound reduces from O(n^2) to O(n) qubits. The classical computation uses polynomially many bit operations and group-operation queries.
These improvements rely on two technical ingredients. We prove that the integer relation lattices used in our algorithm admit, with high probability, integral bases whose vectors have Euclidean norm at most exp(O(sqrt(n))). We preserve the circuit-size advantage of Regev's algorithm for group decomposition by incorporating all O(n) sampled generators while keeping the lattice-reduction dimension at O(sqrt(n)).
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 This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on one of the most important breakthroughs in quantum computing: the quantum phase estimation (QPE) algorithm and its application to Shor’s factoring algorithm. The lesson begins with the phase estimation problem, Solving this problem efficiently is a cornerstone of many quantum algorithms. Spectral Theorem and Mathematical Foundations The discussion starts with the spectral theorem from linear algebra. In the context of this lesson, it is applied to unitary matrices, which can be diagonalized in an orthonormal eigenbasis. This property makes it possible to extract phase information using interference effects and controlled unitary operations. Later, the same mathematical framework extends to Hermitian operators, which are central to quantum mechanics and Hamiltonian simulation. Quantum Phase Estimation (QPE) The Quantum Phase Estimation algorithm combines: Controlled unitary operations Superposition and interference The Quantum Fourier Transform (QFT) The QFT plays a crucial role by transforming phase information encoded in amplitudes into measurable computational basis states. Importantly, the QFT can be implemented efficiently with a quantum circuit whose complexity scales polynomially with the number of qubits. From Phase Estimation to Shor’s Algorithm By applying QPE to a specific modular exponentiation operator, one obtains Shor’s algorithm, an efficient quantum algorithm for integer factorization. Shor’s algorithm demonstrates an exponential speedup over the best-known classical factoring algorithms and has profound implications for cryptography, particularly for RSA-based systems. Significance This lesson illustrates a major milestone in quantum computing: It connects abstract linear algebra (spectral theorem) to concrete algorithmic advantage. It shows how quantum interference enables extraction of hidden periodicity. It demonstrates a real-world cryptographic impact through efficient factorization. Through hands-on experimentation on IBM Q, theoretical concepts are translated into working quantum circuits, reinforcing the deep relationship between mathematics, algorithm design, and quantum computational power.