Area 1:Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 Shor:Factoring Hallgren:Pell's Discrete Log Equation QFT (Quantum Fourier Transform):exponential speedup;slower than expected. Pell's Equation:x2-dy2 =1. Problem:Given d,find solutions (x,y)to the above equation. Classical (best known): -~2vlog d(assuming the generalized Riemann hypothesis) -~d1/4(no assumptions) Quantum*1:poly(log d). *1:S.Hallgren.STOC'02.Journal of the ACM,2007.Area 1: Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 QFT (Quantum Fourier Transform): exponential speedup; slower than expected. Shor: Factoring & Discrete Log • Pell’s Equation: x2 – dy2 = 1. • Problem: Given d, find solutions (x,y) to the above equation. • Classical (best known): – ~ 2 √log d (assuming the generalized Riemann hypothesis) – ~ d1/4 (no assumptions) • Quantum*1 : poly(log d). Hallgren: Pell’s Equation *1: S. Hallgren. STOC’02. Journal of the ACM, 2007