从这里开始，我们要进入计算理论的世界。计算理论（theory of computation）研究的核心问题就是计算（computation）。我们需要思考的问题是：什么是计算；什么可以计算或不可以计算；如果可以计算，这个问题有多难计算；如果不可以计算，这个问题不可以计算的程度有多少。这个系列（前半部分的）主要框架来自于浙江大学计算理论课程毛宇尘老师的授课，其中插入了大量笔者个人的想法和来源于其他参考资料的结论和思路，应当完全覆盖并超越这门课程本身。这门课程事实上只部分地回答了前两个问题，对于第三个问题一带而过，而对于第四个问题几乎完全没有讨论，但是在这个系列里，我会尽可能完整地展现整个理论从新生到现代的全貌。笔者才疏学浅，如有疏漏，望指正。
这篇文章挺难读的，但是也很有意思。大概会分成四次把解读更新完，其实原文在大部分地方已经讲的很清楚了，但是一些计算过程可能需要澄清，毕竟文中的证明有些给的实在简洁。
这篇文章主要讨论的问题是 $\text{2-}\large\text{L}\small{\text{OCAL }}\large{\text{H}}\small{\text{AMILTONIAN}}$ 问题的复杂度。作为第一部分这里主要把论文的前四节的比较复杂的证明过了一遍，主要是投影引理和对 Kitaev 构造的重述，虽然还没进入正题但也并不算简单，还是很有仔细研究的价值的。
在之前（还没更新）的课程中，主要讨论了量子计算的几种范式，并对其进行了一些形式化。从这里开始，我们将尝试对量子计算的复杂性理论做出详细的解释和说明，并表明其与经典计算复杂度类的关系。首先，有必要快速回顾一下经典复杂性理论带给我们的一些结果。
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 算术复杂度就是从这个视角出发做出的形式化定义。