An Efficient Quantum Factoring Algorithm - Quantum Colloquium
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore an innovative quantum factoring algorithm presented by Oded Regev from NYU in this 1 hour 53 minute Quantum Colloquium talk. Delve into the details of a method that can factorize n-bit integers using a quantum circuit with \tilde{O}(n^{3/2}) gates, run \sqrt{n}+4 times independently, followed by classical post-processing. Compare this approach to Shor's algorithm, which requires circuits with \tilde{O}(n^2) gates. Understand the number-theoretic heuristic assumption underlying the algorithm's correctness, similar to those used in subexponential classical factorization algorithms. Consider the potential implications and limitations of this method for practical physical implementations. The talk includes a panel discussion starting at 1:08:21, providing further insights and perspectives on this cutting-edge research in quantum computing and cryptography.
Syllabus
An Efficient Quantum Factoring Algorithm | Quantum Colloquium
Taught by
Simons Institute
Related Courses
Classical Commitment to Quantum StatesSimons Institute via YouTube Classical Verification of Quantum Computations
Simons Institute via YouTube On the Security of Proofs of Sequential Work in a Post-Quantum World
Paul G. Allen School via YouTube Post-Quantum Cryptography
TheIACR via YouTube Post-Quantum Crypto - Part I
TheIACR via YouTube