← Back to papers
An Efficient Quantum Factoring Algorithm
O. Regev·August 12, 2023·DOI: 10.1145/3708471
Computer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
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 certain number-theoretic conjecture. It is currently not clear if the algorithm can lead to improved physical implementations in practice.