香港中文大学：An Introduction to Quantum Computing in Theoretical Computer Science

Quantum Computing in Theoretical Computer Science Shengyu Zhang CSE Dept.CUHK

Shengyu Zhang CSE Dept. @ CUHK

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

a brief intro to theoretical computer science Computation:a sequence of elementary instructions. More than knowing the existence,but a step-by-step way to find it

A brief intro to theoretical computer science • Computation: a sequence of elementary instructions. • More than knowing the existence, but a step-by-step way to find it

Efficiency Efficient Computation: -Algorithm:design fast algorithms Computational complexity:classify problems according to their computational difficulty ◆Structural Measured by resources like time,space,randomness, counting,... ·Interactive Concrete models:Decision Tree.Communication Complexity,Circuit

Efficiency • Efficient Computation: – Algorithm: design fast algorithms – Computational complexity: classify problems according to their computational difficulty • Structural – Measured by resources like time, space, randomness, counting,… • Interactive • Concrete models: Decision Tree, Communication Complexity, Circuit

Connections to other sciences Import:Use of concepts and techniques from Math:discrete math,analysis,algebra,topology -Physics ● Export: Solve TCS questions appearing naturally in Statistical Physics,Chemistry,Molecular Biology,Social Science,Economics,Computer Information Science, Concepts such as completeness; Problems such as P vs.NP One of the seven $1M Millennium Problems*1 *1:http://www.claymath.org/millennium/P_vs_NP/

Connections to other sciences • Import: Use of concepts and techniques from – Math: discrete math, analysis, algebra, topology – Physics • Export: – Solve TCS questions appearing naturally in • Statistical Physics, Chemistry, Molecular Biology, Social Science, Economics, Computer & Information Science, – Concepts such as completeness; – Problems such as P vs. NP • One of the seven $1M Millennium Problems*1 *1: http://www.claymath.org/millennium/P_vs_NP/

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