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/