量子计算与计算复杂度（M. N. Vyalyi） Lecture 1

在之前（还没更新）的课程中，主要讨论了量子计算的几种范式，并对其进行了一些形式化。从这里开始，我们将尝试对量子计算的复杂性理论做出详细的解释和说明，并表明其与经典计算复杂度类的关系。首先，有必要快速回顾一下经典复杂性理论带给我们的一些结果。