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

在上一次讲座中，简单地介绍了量子电路的基本概念和量子编程的方法。这一次课将分析几个量子电路的例子和代码实现，包括：

• 2 位半加器
• 量子近似优化算法（Quantum Approximation Optimization Algorithm, QAOA），以 Ising 问题为例
• Grover 搜索

在近二十年间，出现了两种量子计算的主要范式。一种是量子门编程模型（gate-based model of quantum computing），也叫通用量子计算（universal quantum computing）；另一种是量子退火方法（quantum annealing），也叫绝热量子计算（adiabatic quantum computing）。从数学角度上看，这两种模型具备同等的计算能力，但在实践上，两者有显著的不同。

前两次讲座主要介绍量子门编程模型，第一次讲座的内容包括量子比特（quantum bits, qubits）和量子门（quantum gates）、以及量子电路（quantum circuits）。