YoVDO

An Efficient Quantum Factoring Algorithm - Quantum Colloquium

Offered By: Simons Institute via YouTube

Tags

Quantum Computing Courses Cryptography Courses Number Theory Courses Quantum Circuits Courses Circuit Complexity Courses Post-Quantum Cryptography Courses

Course Description

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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 States
Simons 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