In 1994 Peter Shor discovered efficient quantum computer algorithms for factoring integers and computing discrete logarithms -- problems that are conjectured not to be efficiently solvable using ordinary classical computers. These algorithms are the most well-known among several examples that suggest that quantum information has a profound effect on the general notion of computational difficulty. Quantum computational complexity studies this topic in a variety of settings that model not only quantum computations, but also the verification of quantum proofs, quantum interactions of various types, and their relationships to analogous classical concepts.

In this talk, which will be divided into two parts, I will introduce the basic notions of quantum computational complexity and survey some of the main results in this area. The talk will focus on three fundamental notions in quantum computational complexity: polynomial-time quantum computations, the efficient verification of quantum proofs, and quantum interactive proof systems.