一个困扰理论计算机科学家近二十年的难题，被一套人工智能研究系统在三天之内攻克了。
11月6日，美国初创公司"物理超级智能"（简称PSI）发布消息称，其内部研发、运行着一款未公开的Anthropic模型的研究系统，找到了"阿伦森-安拜尼斯猜想"的证明。
这一猜想自2008年前后提出以来，一直是量子复杂性理论中的核心开放问题之一。
据多家科技媒体报道，系统在运行的第三天给出了完整证明，并通过了数学证明辅助软件Lean的形式化检验。
美国天体物理学家、科普作家伊森·西格尔在Big Think上撰文，解读了这一成果的意义。他的结论颇为耐人寻味：这是一个了不起的数学成就，但它对实用量子计算的影响几乎为零。
量子计算机到底快在哪里
要理解这个猜想，得先从一个根本问题说起：量子计算机究竟在什么情况下比普通计算机快？
图中展示了许多不同计算复杂度的问题类别。最内层空间所需的可写内存量最少，而较大的空间则需要更多的可写内存才能解决。从最内层到最外层的复杂度类别示例包括对数时间、多项式时间、非确定性多项式时间和指数时间等多种时间复杂度的问题。图片来源：Qef/Wikimedia Commons/公共领域
普通计算机使用比特，每个比特非0即1，再通过"与""或""非"等逻辑门进行运算。量子计算机则使用量子比特。
它可以处于0和1的叠加态，还能借助各种独特的量子门进行操作。人们期望，这些额外的能力能在某些问题上带来巨大的速度优势，这就是所谓的"量子优势"。
但有一点常被误解。根据丘奇-图灵论题，任何可计算的函数原则上都能用经典计算机算出来，没有哪个问题绝对需要量子计算机才能解决。
区别只在于效率。
分解半素数（或者更广义地说，分解大整数）的难度构成了RSA公钥密码学的基础。如果有人掌握了密钥（即某个素因子），那么分解它就变得计算起来既简单又快捷。然而，如果没有密钥，分解过程将非常耗费计算资源，因为目前还没有能够实现Shor算法的大规模容错计算机。图片来源：M. Mosca 和 SR Verschoor，科学报告，2022 年
有些问题在经典计算机上极其低效，在量子计算机上却可能非常高效。模拟量子力学系统本身，就被普遍认为属于这一类。
可对于更广泛的问题，量子计算机究竟能快多少，一直没有定论。这正是量子复杂性理论要回答的核心问题之一。
一个关于"结构"的猜想
阿伦森-安拜尼斯猜想，以美国计算机科学家斯科特·阿伦森和拉脱维亚计算机科学家安德里斯·安拜尼斯的名字命名。
目前固态存储设备的工作原理是利用衬底/栅极上带电粒子的存在与否来抑制或允许电流流动，从而编码 0 或 1。原则上，我们可以用量子比特代替带有永久电荷的栅极，从而实现从比特到量子比特的转变。量子比特在测量时只能读取 0 或 1，但在对其进行操作时可以处于叠加态。图片来源：E. Siegel/Treknology
它关注的是一种叫"查询模型"的场景：算法需要反复查看一串输入数据，才能回答一个"是或否"的问题。
如果量子算法查看输入的次数，比经典算法少到指数级别，就意味着存在巨大的量子加速；如果只是少一些、属于"多项式级别"的差距，那就谈不上真正的量子优势。
阿伦森和安拜尼斯提出，对于随机生成、没有特殊规律的输入，经典计算机只需多查询"有限的几次"，就能模仿量子算法的表现。换句话说，量子计算机想获得指数级加速，必须依赖问题本身具有某种特殊结构。
左侧图示为一个经典的“比特”：一个二态系统，其值只能是“0”或“1”。右侧图示为一个量子二态系统，即量子比特。实际上，当你进行测量时，你总是会观察到“0”或“1”，但当你对这个量子比特进行操作时，你作用的实际上是球面上箭头所代表的不确定态。在量子物理学中，我们无法预先预测不确定态、复合态或叠加态的量子态；我们只能概率性地预测一系列统计结果，而任何时刻的物理性质都需要通过测量来揭示。图片来源：Ben Gibson/Big Think
阿伦森曾这样概括：这将强调，超多项式的量子加速依赖于结构。两人在约15年前合作发表的那篇论文，标题就叫《量子加速对结构的需要》。
这个猜想被转化为一个关于低次多项式的纯数学命题：每一个有界的低次多项式中，都存在一个影响力足够大的变量。
多年来，数学家证明了它的一些特殊情形。今年8月，美国斯坦福大学的研究人员证明，如果量子算法以固定轮数并行读取输入，同样无法获得指数加速。
这张Sycamore处理器安装在超导低温恒温器中的示意图，展示了谷歌在发布Willow芯片之前，其量子计算机的雏形。尽管量子比特在计算能力上比传统计算机略胜一筹，但量子计算机能够模拟的，经典计算机也同样能够模拟。量子计算的目标是在解决实际问题时实现量子优势：量子霸权。图片来源：Forest Stearns，谷歌人工智能量子驻场艺术家
这些斯坦福研究者在评价PSI的证明时写道，这是一个巨大的成果，它解决了一个数十年的猜想，对哪些问题能获得量子加速具有重要意义。
证明汇集了布尔函数分析和概率组合学的多条研究脉络，"以一种相当神奇的方式"把一切结合在了一起。
了不起，但别过度解读
那么，这个证明对量子计算究竟意味着什么？对于那些期待量子计算机"无所不能"的人来说，答案可能有些令人失望。
西格尔的回答很直接：对实用量子计算的影响为零。
这张图表展示了问题是否有用（x轴）与经典计算机解决这些问题的难度（y轴）之间的关系。随机电路采样是经典计算机目前已知最难完成的任务，但它也可能是量子计算机所能处理的最无用的应用。图片来源：Hartmut Neven/Google
此前学界普遍认为，量子计算机要获得显著加速，需要问题具有某种特殊结构。
现在，这一判断被严格证明了。而在量子物理、量子化学和材料科学等领域，人们依然期待真正的量子加速存在。
阿伦森本人也发表了看法。他对这一证明印象深刻，但也列出了几点提醒：
尽管许多人声称量子计算的出现将使所有计算速度都比传统计算机更快，但这极不可能。相反，最好的计算机将是混合型计算机：能够在能够发挥量子优势的应用中利用量子部分，而对于所有其他（即大多数）应用则采用传统计算技术。图片来源：fotogurmespb/Adobe Stock
它没有"杀死"量子霸权；它不会改变人们建造量子计算机的方式；它只是排除了一类大多数人本来就认为不存在的量子加速。
他还自嘲说，自己已经不再是这个猜想的专家，并不确定自己真正读懂了这份证明。
阿伦森还指出，当下正是计算机科学和数学领域大量长期悬而未决的问题纷纷被攻克的时代，这个猜想被证明并不令人意外。
需要注意的是，Lean能够检验形式化证明在逻辑上是否正确，但专家仍需确认形式化的命题是否准确对应原始猜想，以及论文中Lean之外的部分是否成立。这项工作尚未经过同行评审，斯坦福的研究者正在审阅。
西格尔还提醒，迄今由AI完成的数学、计算机科学和物理学证明，都在很大程度上建立在人类此前积累的工作之上。
他抛出了两个值得深思的问题：AI是否即将触及它能够解决问题的极限？如果没有，当AI做出更高层次的发现时，还会有人类能够理解它们的意义吗？
或许，这才是这个证明留给我们最大的悬念。
