Overreliance on Classical Computing in Quantum Factorization

Abstract

A 2012 quantum experiment factored 143 after performing some simplifications classically. Further research demonstrated that that experiment arguably performed the quantum factorizations of other numbers too, such as 56153. This paper characterizes the numbers factored by the 2012 experiment, demonstrates that there are infinitely many of these numbers if the Bateman-Horn conjecture is correct, and provides $N_{2000} \approx 7.86 \cdot 10^{2000}$ as an explicit example. Finally, we show that, in asymptotic terms, most of the work in these factorizations was done classically. These quantum factorizations therefore do not seem to indicate progress toward factoring large RSA moduli.