注：这学期姚期智先生在清华给了一门研究生课程《高等理论计算机I》，主要内容就是讲量子计算，我也许诺要写一些这方面的东西，现在这门课已经接近了尾声，下面开始第一篇。
准确的说，这篇不算我写的。基本上是翻译自Why the world needs quantum mechanism。而且必须得说，原文比这个翻译要详细和有趣得多，所以大家尽量去看原文吧。

理解现代物理的一个挑战...

PS: PCP可以说是理论计算机领域近20年来的最重要的结果之一，它给了NP问题一个新的刻画，并且提供了一种证明近似算法下界的方法。下面是yijia写的PCP介绍。
作者：yijia
我们可以从最基本的NP开始。一般NP的定义是基于nondeterministic Turing machine，但我们也可以用类似于Interactive Proof的系统来刻画：
一个语言是在NP内当且仅当存在一个多项式时间的算法  (i.e., prover...

姚期智教授给清华大学新入学研究生开的一门课，课程内容
在经典计算复杂性方面：NP完全性，多项式空间复杂性，对数空间复杂性，交互式证明系统，随机复杂性，去随机化，概率检验证明系统，电路复杂性，通信复杂性，判定树复杂性等。在量子计算复杂性方面将包括：量子计算模型，量子电路，量子Fourier变换算法，Shor算法，Grover量子搜索算法，量子纠错码，冯...