An Efficient Quantum Factoring Algorithm

08/12/2023

∙

by   Oded Regev, et al.

∙

0

∙

share

We show that n-bit integers can be factorized by independently running a quantum circuit with Õ(n^3/2) gates for √(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.