Quantum Complexity Theory

3 credits · Graduate

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