量子计算公开课：从德谟克利特、计算复杂性到自由意志

　　中文版序言 v
　　致中国读者 ix
　　引言 xi
　　第 1章 原子和虚空 1
　　第 2章 集合 6
　　一阶逻辑规则 7
　　关于非负整数的皮亚诺公理 7
　　集合论的公理 9
　　第3章 哥德尔、图灵和他们的小伙伴 15
　　图灵机 16
　查看完整　　

　　斯科特.阿伦森 Scott Aaronson在量子计算和理论计算机领域影响力巨大的学者。2021年度ACM计算奖得主。现为得克萨斯大学奥斯汀分校讲席教授，曾任教于麻省理工学院。主要研究领域为理论计算机科学。其研究兴趣集中在探索量子计算机的能力和极限，以及更广泛的计算复杂性理论。阿伦森毕业于康奈尔大学，获得加州大学伯克利分校计算机科学博士学位。曾荣获Tomassoni Chisesi物理学奖（2018年）、Simons研究员奖（2017年）、美国国家科学基金会的Alan T. Waterman奖（2012年）等奖项。

　　《量子计算公开课：从德谟克利特、计算复杂性到自由意志》由量子计算和理论计算机领域巨擘、2021年度ACM计算奖得主斯科特?阿伦森的课堂讲义整理而成。作者将量子计算置于数学、计算科学、哲学等更广阔的领域当中，谈及计算理论、集合论、图灵机、NP问题、随机性、数学逻辑、量子计算、隐变量理论、人择原理、自由意志、时间旅行和复杂性等多个话题。作者的思考深刻、发人深省，探讨了量子计算对解决相关领域难题的重大意义，并试图回答两个问题：宇宙和物理世界是如何运作的？它们为什么这样运作？
　　《量子计算公开课：从德谟克利特、计算复杂性到自由意志》适合爱好科普的普通大众读者，尤其适合对物理学、计算机科学、数学、哲学等内容感兴趣的读者，计算理论、计算机科学、物理学和量子物理学的从业者或专业人士也可将本书作为参考读物。

　　中文版序言 v
　　致中国读者 ix
　　引言 xi
　　第 1章 原子和虚空 1
　　第 2章 集合 6
　　一阶逻辑规则 7
　　关于非负整数的皮亚诺公理 7
　　集合论的公理 9
　　第3章 哥德尔、图灵和他们的小伙伴 15
　　图灵机 16
　　额外补充 23
　　第4章 心智和机器 25
　　第5章 古复杂性 38
　　第6章 P、NP和它们的小伙伴 47
　　第7章 随机性 62
　　第8章 密码学 80
　　密码学 81
　　伪随机数发生器 83
　　单向函数 86
　　公钥密码学 87
　　第9章 量子力学 93
　　小于0%的可能性？ 95
　　混合态 99
　　平方规则 100
　　实数与复数 102
　　线性 106
　　第 10章 量子计算 113
　　反算 117
　　与经典复杂性类的关系 118
　　量子计算和NP完全性问题 124
　　量子计算和多世界 126
　　第 11章 彭罗斯 128
　　打开黑盒子 130
　　冒险说些显然的事 133
　　所有人都瞄着这一整块量子“肥肉” 133
　　第 12章 退相干和隐变量 137
　　进坑 138
　　故事一 退相干 140
　　退相干和热力学第二定律 142
　　故事二 隐变量 145
　　“行不通”定理大荟萃 148
　　隐变量的例子 153
　　第 13章 证明 160
　　何为一个证明？ 160
　　概率证明 162
　　零知识证明 163
　　PCP 166
　　模拟隐变量理论的复杂性 167
　　第 14章 量子态有多大？ 171
　　第 15章 量子计算十一诘 185
　　第 16章 学习 194
　　第 17章 交互式证明、电路下界及其他 207
　　交互式证明 208
　　新进展 218
　　量子交互式证明 221
　　第 18章 人择原理趣谈 224
　　第 19章 自由意志 244
　　第 20章 时间旅行 258
　　第 21章 宇宙学和复杂度 273
　　第 22章 问我什么都行 289
　　注释 306
　　致谢 317
^ 收 起　　

　　斯科特.阿伦森 Scott Aaronson在量子计算和理论计算机领域影响力巨大的学者。2021年度ACM计算奖得主。现为得克萨斯大学奥斯汀分校讲席教授，曾任教于麻省理工学院。主要研究领域为理论计算机科学。其研究兴趣集中在探索量子计算机的能力和极限，以及更广泛的计算复杂性理论。阿伦森毕业于康奈尔大学，获得加州大学伯克利分校计算机科学博士学位。曾荣获Tomassoni Chisesi物理学奖（2018年）、Simons研究员奖（2017年）、美国国家科学基金会的Alan T. Waterman奖（2012年）等奖项。

　　《量子计算公开课：从德谟克利特、计算复杂性到自由意志》由量子计算和理论计算机领域巨擘、2021年度ACM计算奖得主斯科特?阿伦森的课堂讲义整理而成。作者将量子计算置于数学、计算科学、哲学等更广阔的领域当中，谈及计算理论、集合论、图灵机、NP问题、随机性、数学逻辑、量子计算、隐变量理论、人择原理、自由意志、时间旅行和复杂性等多个话题。作者的思考深刻、发人深省，探讨了量子计算对解决相关领域难题的重大意义，并试图回答两个问题：宇宙和物理世界是如何运作的？它们为什么这样运作？
　　《量子计算公开课：从德谟克利特、计算复杂性到自由意志》适合爱好科普的普通大众读者，尤其适合对物理学、计算机科学、数学、哲学等内容感兴趣的读者，计算理论、计算机科学、物理学和量子物理学的从业者或专业人士也可将本书作为参考读物。