量子计算与计算的基本极限

录像

第一讲:丘奇-图灵论文与物理学

2019年9月2日，星期一，下午5点。

文摘:自然可计算的吗?在表述这样一个问题时，我们到底应该意味着什么?几代人以来，将“可计算的”与“图灵机可计算的”等同起来，要么被视为一种武断的数学定义，要么被视为一种哲学或心理学主张。然而，量子计算和信息的兴起，为看待丘奇-图灵命题带来了一种富有成效的新方式:即，作为一种可证伪的关于物理宇宙的经验断言。本次演讲试图从现代的角度来审视物理定律的可计算性——这一观点充分融合了量子力学、量子场论、量子引力和宇宙学的见解。我们将批判性地评估涉及(例如)相对论性时间膨胀、黑洞、封闭的时间型曲线和奇异宇宙论的“超计算”建议，并将为物理丘奇-图灵命题(Church-Turing Thesis)在21世纪提出一个案例。

第2讲:高效计算的极限

2019年9月3日，星期二，上午9点。

文摘:计算机科学家关心的是什么是可计算的，不仅是在原理上，而且在物理宇宙的资源限制内。与此密切相关的是，哪些类型的问题是可以用一些与问题大小合理(比如多项式地)伸缩的步骤来解决的?这节课将研究臭名昭著的np完全问题，如旅行推销员问题，是否可以利用物理世界的资源有效地解决。我们将从P=?经典计算机科学的NP问题——它的意义、历史和现状。然后我们将讨论量子计算机:它们是如何工作的，它们如何有时能产生比经典计算机的指数级加速，以及为什么许多人认为，对于np完全问题，甚至它们也不会这样做。最后，我们将批判性地评估那些将使用奇异物理甚至超越量子计算机的建议，就它们将在多项式时间内呈现出可计算的内容而言。

第三讲:对量子计算霸权的追求

2019年9月3日，星期二上午10点。

文摘:有用的量子计算机能在我们的世界里被制造出来吗?本次演讲将讨论目前谷歌、IBM和许多其他地方正在进行的大规模努力的现状，这些努力旨在构建具有50-100个量子比特的噪声量子设备，至少在某些专门任务上，这种设备的性能显然可以超过经典计算机——这个里程碑被赋予了一个不幸的名字“量子霸主”。我们将调查近期的理论工作(关于玻色子采样、随机电路采样等)，目的是告诉我们:我们应该给这些设备哪些问题，我们尽可能有信心对经典计算机来说是困难的?以及我们该如何检查这些设备是否确实解决了这些问题?最后，我们将讨论一种新的协议，用于生成认证随机比特，它几乎可以在量子霸权本身实现的同时实现，因此它可能成为量子计算的第一个实现应用。