Optimizing Space in Regev's Factoring Algorithm

ePrint Report: Optimizing Space in Regev's Factoring Algorithm

Seyoon Ragavan, Vinod Vaikuntanathan

We improve the space efficiency of Regev's quantum factoring algorithm [Reg23] 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. In contrast, Regev's circuit requires $O(n^{3/2})$ qubits, while Shor's circuit requires $O(n^2)$ gates. As with Regev, to factor an $n$-bit integer $N$, one runs this circuit independently $\approx \sqrt{n}$ times and apply …

algorithm efficiency eprint report factoring log main quantum qubits report result size space