Quantum Complexity Theory

Catalog description

Introduction to quantum complexity theory. Topics include: the class BQP and its relation to other complexity classes; quantum query and communication complexity; quantum proof systems, Hamiltonian complexity, and the quantum PCP conjecture; the complexity & verification of quantum sampling experiments; and quantum cryptography.Prerequisites: background in quantum computing and computational complexity theory