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.
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.
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.
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)).
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 give a bounded-error quantum algorithm that, given a prime p, a divisor q∣(p−1), and an integer 0<n<p, computes n!modp in expected time O(qc+p/q) for some absolute constant c≥1. When p−1 has a divisor of size q≈p1/(2c+1), this gives the exponent c/(2c+1)<1/2. To our knowledge, this is the first algorithm to break the exponent 1/2 barrier for modular factorials under such a divisor promise. The main technical ingredient is a quantum algorithm that reconstructs the relevant Jacobi sum exactly in compact algebraic form, with polynomial dependence on q and logp. We further extend the same asymptotic bound to the computation of n!modp2, uniformly over 0≤n<p2. At n=p−1, this determines the Wilson quotient p(p−1)!+1(modp). We conjecture that the condition q∣(p−1) is a technical limitation of the present method rather than an inherent obstruction, and that a uniform quantum algorithm exists for all primes.
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 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)× 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.