Fall 2022 Course Descriptions
CS 150-01S Quantum Complexity Theory
This course is an introduction to the complexity theoretic foundations of quantum computing and centers around the question: “what classes of computational problems are (not) solvable on computational models with quantum mechanical information processing resources?”. We start off with a gentle introduction to quantum mechanics, quantum computing, models of computation and computational complexity. We then proceed to defining quantum complexity classes and their relationship to the complexity zoo. We then move to special topics such as Hamiltonian complexity, noisy intermediate-scale quantum complexity theory, quantum interactive proof systems, bosonic quantum complexity classes, the interface between physics and theoretical computer science, and more, depending on interest. The goal is to bring students to the research frontier.
Prerequisite: Completion of CS 170 and Introduction to Quantum Information Science or equivalent or permission of instructor.