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. The correctness of the 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.

Categories: quant-ph cs.CC

An Efficient Quantum Factoring Algorithm