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. Factoring:Given an n-bit number,factor it (into product of two numbers). The reverse problem of Multiplication,which is very easy. Classical (best known):~O(2m1/3) Quantum*1:~O(n2) *1:P.Shor.STOC'93,SIAM Journal on Computing,1997.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 • Factoring: Given an n-bit number, factor it (into product of two numbers). – The reverse problem of Multiplication, which is very easy. • Classical (best known) : ~ O(2n^1/3) • Quantum*1 : ~ O(n2 ) *1: P. Shor. STOC’93, SIAM Journal on Computing, 1997