Graduate Student Organization Seminar

Date: October 9, 2019

Time: 4:00PM - 5:00PM

Location: BLOC 628

Speaker: Kristopher Watkins

Title: An Exposition on Peter Shor's Polynomial-Time Factoring Algorithm

Abstract: Shor's Algorithm utilizes a polynomial reduction given by Jeffrey Miller in 1975 to give the Discrete Logarithm Problem and the Factoring Problem membership in BQP. Doing so means that with a quantum computer of approximately 4000 stable qubits, we can break RSA, DHK, ElGamal, and their elliptic curve variants in polynomial time. The focus of the talk will be showing how Phase Estimation and the Quantum Fourier Transform work together to solve this problem, but Jeffrey Miller's reduction in 1975 will also be shown in a simpler way.