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

作者: [美] 斯科特·阿伦森（Scott Aaronson）

出版社: 人民邮电出版社

出版时间: 2021-07

版次: 1

ISBN: 9787115564238

定价: 119.80

装帧: 其他

开本: 其他

纸张: 胶版纸

页数: 318页

分类: 自然科学

82人买过

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

在量子计算和理论计算机领域影响力巨大的学者。2021年度ACM计算奖得主。现为得克萨斯大学奥斯汀分校讲席教授，曾任教于麻省理工学院。主要研究领域为理论计算机科学。其研究兴趣集中在探索量子计算机的能力和极限，以及更广泛的计算复杂性理论。阿伦森毕业于康奈尔大学，获得加州大学伯克利分校计算机科学博士学位。曾荣获Tomassoni Chisesi物理学奖（2018年）、Simons研究员奖（2017年）、美国国家科学基金会的Alan T. Waterman奖（2012年）等奖项。中文版序言 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
内容简介:
《量子计算公开课：从德谟克利特、计算复杂性到自由意志》由量子计算和理论计算机领域巨擘、2021年度ACM计算奖得主斯科特?阿伦森的课堂讲义整理而成。作者将量子计算置于数学、计算科学、哲学等更广阔的领域当中，谈及计算理论、集合论、图灵机、NP问题、随机性、数学逻辑、量子计算、隐变量理论、人择原理、自由意志、时间旅行和复杂性等多个话题。作者的思考深刻、发人深省，探讨了量子计算对解决相关领域难题的重大意义，并试图回答两个问题：宇宙和物理世界是如何运作的？它们为什么这样运作？
《量子计算公开课：从德谟克利特、计算复杂性到自由意志》适合爱好科普的普通大众读者，尤其适合对物理学、计算机科学、数学、哲学等内容感兴趣的读者，计算理论、计算机科学、物理学和量子物理学的从业者或专业人士也可将本书作为参考读物。
作者简介:
斯科特.阿伦森 Scott Aaronson

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