姚期智教授给清华大学新入学研究生开的一门课，课程内容

在经典计算复杂性方面：NP完全性，多项式空间复杂性，对数空间复杂性，交互式证明系统，随机复杂性，去随机化，概率检验证明系统，电路复杂性，通信复杂性，判定树复杂性等。在量子计算复杂性方面将包括：量子计算模型，量子电路，量子Fourier变换算法，Shor算法，Grover量子搜索算法，量子纠错码，冯诺依曼墒等。

从这里可以看出理论计算机的一些主要的方向。按照姚先生的说法，这些是做理论的学生，多少都应该知道一点的东西，这样跟别人讨论的时候才不会embarrass。Researcher不应该局限于自己所专注的领域，眼界要开阔; 这也是开这门课的主要原因。

参考教材

[1] Complexity Theory: A Modern Approach, Sanjeev Arora and Boaz Barak.
[2] Quantum Computation and Quantum Information, Michael Nielsen and Isaac Chuang.
[3] Lecture nots: Quantum Computation, instructor Umesh Vazirani

这门课有I，II两个学期。这个学期主要讲量子计算和量子信息的一些东西吧。我恰好跟着写一些关于量子的东西放到这里，当然都是简单介绍性质的，目的是大家看了之后，对一些NC的东西有简单的辨别力，比如新浪科技的这篇瑞士实验显示量子信息传输速度远超光速。