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

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

Per Martin-Löf, The Definition of Random Sequences, Information and Control, 9, 602-619(1966)

考虑一个在有限字母表中所有字符串的集合。记字符串 $x = \xi_1\xi_2\dots\xi_n$ 的长度 $l(x) = n$。接下来我们需要考虑的问题是，这个序列有多复杂？

很显然，直观地讲，一个“随机”（我们很快会回到这一点上来）字符串要比一个有规律的字符串复杂地多。同样很直观地，我们可以把一个字符串的复杂度定义为某种“最简单的描述方法的长度”，Kolmogorov 算术复杂度就是从这个视角出发做出的形式化定义。