原文为：arXiv:quant-ph/0406180

这篇文章挺难读的，但是也很有意思。大概会分成四次把解读更新完，其实原文在大部分地方已经讲的很清楚了，但是一些计算过程可能需要澄清，毕竟文中的证明有些给的实在简洁。

这篇文章主要讨论的问题是 $\text{2-}\large\text{L}\small{\text{OCAL }}\large{\text{H}}\small{\text{AMILTONIAN}}$ 问题的复杂度。作为第一部分这里主要把论文的前四节的比较复杂的证明过了一遍，主要是投影引理和对 Kitaev 构造的重述，虽然还没进入正题但也并不算简单，还是很有仔细研究的价值的。

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