量子信息的过去、现在和未来(3)

2022年第28次物理学索尔维会议
虽然这些技术的了不起和影响力是毋庸置疑的，但它们几乎没有触碰到“量子理论如何重塑我们对宇宙中可能性的理解”这一问题的皮毛。现在，我们正在人类历史上第一次开发和完善一套工具，以创建并精确控制非常复杂的量子态。这些态因为包含许多相互作用粒子而变得非常复杂，以至于我们无法用现有最强大的计算机有效地模拟它们，也无法用目前已知的理论思想预测它们的行为。随着我们控制量子世界的能力逐渐成熟，深刻的科学发现和强大的技术必定会随之而来。
量子信息科学的快速发展使现在成为召开一次关注量子信息物理学的索尔维会议的特别合适的时机。这个话题包含四个相互交织的主题，它们将在以下分会场中集中讨论：量子计算机科学[1,2]、量子硬件[3,4]、量子物质[5,6]和量子引力[7,8]。针对每个主题，我将提供一些历史背景，然后评论现状和未来前景。
二、背景
1. 计算模型
计算的基本理论建立在由图灵于20世纪30年代奠定的基础上[9]。图灵通过操作可移动纸带上的符号这一理想化物理过程定义计算。他的模型作为界定一个函数是否原则上能在物理世界中被计算的正确方法而被广泛接受。这一断言被称作丘奇-图灵论题（Church-Turing thesis）。
一个更精确的概念，即有效计算，在20世纪70年代引起了人们的关注，引发了计算复杂性理论的出现 [10-12]。人们普遍认为，如果图灵机所需的计算步数约为问题输入规模的多项式量级，这个问题就可以被有效解决。这就是所谓的扩展的丘奇-图灵论题（extended Church-Turing thesis）。根据广泛的共识，这些是实际可解决的问题。它们被认为属于一个称为“P”的复杂性类，“P”指多项式时间。
复杂性类“NP”中的问题是指那些一旦找到解，就可以用图灵机有效验证的问题。通常认为NP包含P之外的难题。注意到存在一类问题，如组合优化问题，属于一个名为“NP完全”（NP- Complete）的类。这类问题可能被视为NP类中最难的问题 [10-12]。
我们认为NP还包含处于P之外而又不是NP完全的问题。寻找大合数的质因数就是这类问题中最有名的一个。
作为复杂性理论的一个实际应用，公钥密码系统在20世纪70年代被提出，它基于类似因式分解的那些处在P之外而又不是NP完全的问题[13,14]。这些方案在今天被大量用于保护电子通信的隐私。它们都基于这样一个假设，即破坏协议的计算过程是足够难的，不可能在实际中执行。