An Efficient Quantum Factoring Algorithm

We show that n-bit integers can be factorized by independently running a quantum circuit with \tilde{O}(n^{3/2}) gates for \sqrt{n}+4 times, and then using polynomial-time classical post-processing. In contrast, Shor's algorithm requires circuits with \tilde{O}(n^2) gates. The correctness of our algorithm relies on a number-theoretic heuristic assumption reminiscent of those used in subexponential classical factorization algorithms. It is currently not clear if the algorithm can lead to improved physical implementations in practice. No background in quantum computation will be assumed. Based on the recent arXiv preprint: https://arxiv.org/abs/2308.06572