Roadmap Intro to theoretical computer science Intro to quantum computing Export of quantum computing Formula Evaluation Solves a classical open question N-Representability problem Addresses the failure of many efforts in quantum chemistry Quantum is natural mathematically -Decision tree complexity -Communication complexity
Roadmap • Intro to theoretical computer science • Intro to quantum computing • Export of quantum computing – Formula Evaluation • Solves a classical open question – N-Representability problem • Addresses the failure of many efforts in quantum chemistry • Quantum is natural mathematically – Decision tree complexity – Communication complexity
Areas in quantum computing ·Quantum algorithms Quantum complexity Quantum cryptography Quantum error correction Quantum information theory Others:Quantum control game theory
Areas in quantum computing • Quantum algorithms • Quantum complexity • Quantum cryptography • Quantum error correction • Quantum information theory • Others: Quantum control / game theory / …
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
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 cryptosystems
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 • Implication of fast algorithm for Factoring – Theoretical: Church-Turing thesis – Practical: Breaking RSA-based cryptosystems
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