Oded Regev: An Efficient Quantum Factoring Algorithm (NTWS 195)

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. 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 arXiv preprint: arxiv.org/abs/2308.06572
Link to slides: drive.google.com/file/d/1Rgwx...
Number Theory Web Seminar: www.ntwebseminar.org
Original air date:
Thursday, January 18, 2024 (8am PST, 11am EST, 4pm GMT, 5pm CET, 6pm Israel Standard Time, 9:30pm Indian Standard Time)
Friday, January 19, 2024 (12am CST, 3am AEDT, 5am NZDT)