Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Accelerating Multidimensional Quantum Factoring: Sub-O(n^(3/2)) Gate Regimes, 4n-Qubit Streamed Estimation, and Unconditional Correctness

Denis Gnitiyov

Published Oct 17, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.5281/zenodo.23436576

Related papers

Space-Efficient and Noise-Robust Quantum Factoring

Seyoon Ragavan, Vinod Vaikuntanathan

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.

arXiv:2310.00899•Oct 2, 2023•2 citations

Streaming Regev's Quantum Factoring Algorithm

Katherine Van Kirk, Craig Gidney

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.

quant-pharXiv:2610.06733•Oct 6, 2026•0 citations

An Overview of Regev’s Quantum Factoring Algorithm and Its Recent Developments

Rick Lan Chen

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 g⁡n )(n^(3/2) log⁡n ), compared to Shor’s originalO(n^2 lo g⁡n )original O(n^2 log⁡n ) 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.

Applied and Computational Engineering•Nov 28, 2024•1 citation

Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms

Cédric Pilatte

Abstract In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multidimensional version of Shor’s algorithm that requires far fewer quantum gates. His algorithm relies on a number-theoretic conjecture on the elements in $(\mathbb {Z}/N\mathbb {Z})^{\times }$ that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such as zero-density estimates. As a result, we obtain an unconditional proof of correctness of this improved quantum algorithm and of subsequent variants.

arXiv:2404.16450•Forum of Mathematics Pi•Jan 1, 2026•5 citations

Space-Optimized and Experimental Implementations of Regev's Quantum Factoring Algorithm

Wentao Yang, Bao Yan, Muxi Zheng +3 more

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(n^{3/2}) \) to \( O(n^{5/4}) \), and refined strategies achieve \( O(n \log n) \)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.

quant-pharXiv:2511.18198•Nov 25, 2025•0 citations

Deterministic Prime Bases for Regev's Algorithm

Steven Tolbert

Regev's quantum factoring algorithm reduces the number of gates per quantum call, but its correctness for the original deterministic prime bases rests on a number-theoretic assumption. We prove that the first ⌈√n⌉ primes work unconditionally for almost all n-bit composite inputs, including almost all composite inputs surviving trial division by those primes. The algorithm retains Regev's original asymptotic gate count per quantum call. A separate theorem covers balanced RSA moduli under three explicit sampling laws. The exceptional input proportion is Θ(2^{-⌈√n⌉}); a population of this order admits no useful relation at any length. On each remaining input, Regev's algorithm finds a nontrivial divisor with constant probability using ⌈√n⌉+4 quantum calls of O(n^{3/2} log n) gates each. The main geometric lemma extracts a useful relation from an earlier successive minimum, determined by the dimension of a quotient of the relation lattice. Prime-divisor counting then gives useful-relation lengths 2^{(3/2+o(1))√n} for general inputs and 2^{(9/2+o(1))√n} for RSA. Both main theorems and finite RSA useful-vector bounds are formally verified in Lean 4; the formalization is archived at https://doi.org/10.5281/zenodo.23407163.

•Oct 16, 2026•0 citations
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.
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(nlog⁡n)O(n \log n)O(nlogn) qubits and O(n3/2log⁡n)O(n^{3/2} \log n)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)O(n^{3/2})O(n3/2) qubits and O(n3/2log⁡n)O(n^{3/2} \log n)O(n3/2logn) gates, while Shor's circuit requires O(n2log⁡n)O(n^2 \log n)O(n2logn) gates but only O(nlog⁡n)O(n \log n)O(nlogn) qubits. As with Regev, to factor an nnn-bit integer NNN, we run our circuit independently O(n)O(\sqrt{n})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\approx \sqrt{n}≈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)O(n^{1.5})O(n1.5) to 11.32n11.32n11.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)n+M(n)+O(\sqrt{n})n+M(n)+O(n​), where M(n)M(n)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 nnn-bit integer using 4n+O(n)4n+O(\sqrt{n})4n+O(n​) qubits. Although our construction still falls short of the n/2+εnn/2+εnn/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.
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 g⁡n )(n^(3/2) log⁡n ), compared to Shor’s originalO(n^2 lo g⁡n )original O(n^2 log⁡n ) 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 In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multidimensional version of Shor’s algorithm that requires far fewer quantum gates. His algorithm relies on a number-theoretic conjecture on the elements in (Z/NZ)×(\mathbb {Z}/N\mathbb {Z})^{\times }(Z/NZ)× that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such as zero-density estimates. As a result, we obtain an unconditional proof of correctness of this improved quantum algorithm and of subsequent variants.
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) O(n^{3/2}) O(n3/2) to O(n5/4) O(n^{5/4}) O(n5/4), and refined strategies achieve O(nlog⁡n) O(n \log n) 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 N = 35 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.
Regev's quantum factoring algorithm reduces the number of gates per quantum call, but its correctness for the original deterministic prime bases rests on a number-theoretic assumption. We prove that the first ⌈√n⌉ primes work unconditionally for almost all n-bit composite inputs, including almost all composite inputs surviving trial division by those primes. The algorithm retains Regev's original asymptotic gate count per quantum call. A separate theorem covers balanced RSA moduli under three explicit sampling laws. The exceptional input proportion is Θ(2^{-⌈√n⌉}); a population of this order admits no useful relation at any length. On each remaining input, Regev's algorithm finds a nontrivial divisor with constant probability using ⌈√n⌉+4 quantum calls of O(n^{3/2} log n) gates each. The main geometric lemma extracts a useful relation from an earlier successive minimum, determined by the dimension of a quotient of the relation lattice. Prime-divisor counting then gives useful-relation lengths 2^{(3/2+o(1))√n} for general inputs and 2^{(9/2+o(1))√n} for RSA. Both main theorems and finite RSA useful-vector bounds are formally verified in Lean 4; the formalization is archived at https://doi.org/10.5281/zenodo.23407163.