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

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.