An Efficient Quantum Factoring Algorithm

Speaker: Oded Regev

Date: Friday, October 06, 2023

Time: 2:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: Kiva, G-449

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan , CSAIL MIT

Contact: Felicia Raton, fraton@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@lists.csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: TALK: An Efficient Quantum Factoring Algorithm

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 recent arXiv preprint: https://arxiv.org/abs/2308.06572

Zoom Link
https://mit.zoom.us/j/91806514236

Research Areas:

Impact Areas:

See other events that are part of the CSAIL Security Seminar Series 2023 - 2024.

Created by Megan F Farmer at Thursday, October 05, 2023 at 6:19 PM.