Area 1:Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 Shor:Factoring Discrete Log QFT (Quantum Fourier Transform):exponential speedup;slower than expected. Implication of fast algorithm for Factoring Theoretical:Church-Turing thesis Practical:Breaking RSA-based cryptosystemsArea 1: Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 QFT (Quantum Fourier Transform): exponential speedup; slower than expected. Shor: Factoring & Discrete Log • Implication of fast algorithm for Factoring – Theoretical: Church-Turing thesis – Practical: Breaking RSA-based cryptosystems