We provide two improvements to Regev’s 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 modular 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. Additionally, we show how to generalize our reversible exponentiation technique beyond the Fibonacci numbers to obtain constant-factor improvements in the number of qubits and/or gates. 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.
