题记：这是涉及物理、数学和计算机领域的一个令人激动的综合性问题，其实该问题的价值不在于问题的答案本身，而在于人类在不断提升经典计算机运算能力过程中所产生的数学问题和物理结果。

What Are the Limits of Conventional Computing?

https://www.science.org/doi/10.1126/science.309.5731.96

什么是经典计算机的运算极限？

 乍一看，传统计算机的运算极限似乎只是一个工程问题。传统计算机的运算极限不就决定于你能输入多少能量而不至于把芯片融化？不就决定于你在硅存储器里翻转一个比特的最高速度? 不就决定于你在一个房间大小的空间里能把电脑做得多大? 所以，传统计算机的运算极限这个问题表面上看似乎并不深奥。  

 然而事实上，运算(computation)的概念远比怎样更好地制造一台计算机更加地抽象和基础。早在 20世纪30年代中期，普林斯顿数学家阿朗佐·丘奇(Alonzo Church)和艾伦·图灵(Alan Turing)就已经证明，任何涉及比特和字节的计算都可以在一个被称为图灵机(Turing machine)的理想化计算机上完成，也就是任何传统计算都能在图灵机的框架下进行。 这个结果表明所有的经典计算机本质上都等价为图灵机，这一发现使科学家和数学家能够提出关于计算的更为基本的问题而不必纠缠于计算机架构的细枝末节。

 例如，理论学家现在已经把计算问题在更为广泛的意义上分成两大类：P问题和NP问题。 一般来说，P问题是那些可以快速解决的问题，也就是能够在多项式（Polynomial）时间内算出结果的问题（更严格的表述是存在多项式时间算法的问题）。例如对一个名单按字母的顺序进行排序的问题，就是典型的P问题，也就是说排序运算的时间和名单上名称的个数n（广义地称为运算规模）是多项式的关系。而 NP问题则更难解决，也就是你算出结果的时间和你的运算规模n之间不再是多项式关系，比如变成指数关系：2ⁿ（严格来讲NP问题是不确定有没有多项式算法的问题，英文为：Nondeterministic polynomial problems）。NP问题虽然难以运算但其有另外一个重要特点就是：一旦你知道了答案，检查这个答案的对错却是相对容易和快速的（可以在多项式时间内验证其解是否正确）。NP问题的一个典型例子是旅行推销员（或者邮递员、派送员）问题，即派送员需要把货物派送到一系列地点，那么他如何在这些地点上寻找一条最短的可能路线？寻找这条最短路径的运算时间和地点个数n之间就似乎不再是多项式关系（显然遍历n个地点的所有路径有n!个）。因为目前所有已知的获得答案的算法都不是多项式时间，都是需要耗费大量计算资源才能完成的算法，即便面对一个派送规模n相对较小的派送问题，其运算量也能超出任何经典计算机的运算能力。  

 然而数学家们已经证明，如果你能找到一个快速而简单的捷径来解决任何一类NP问题中最难的那个NP问题，那么你就能解决所有这类NP问题。 所以从这个意义上，NP问题就会转化为P问题， 但我们不确定是否存在这样的捷径和算法，也就是：是否P = NP。更为清楚的表述就是：那些在多项式时间内能被验证答案的NP问题是否就是能在多项式时间内找到答案的P问题？然而科学家们并不认为P = NP，而数学家们要想证明这一点却并不那么容易。目前这个问题已经成为数学中最大的一个未解之谜，被美国著名克雷数学研究所(Clay Mathematics Institute, 简称CMI)列为千禧年七大数学问题之一。

   然而事情还远不如此。20世纪40年代，贝尔实验室的科学家克劳德·香农(Claude Shannon)证明：比特不仅适用于计算机，它还是描述从一个物体流向另一个物体的信息的基本单位。 有一些物理的规律决定了一个比特从一个地方传递到另一个地方的速度，决定了有多少信息可以在一个给定的通信信道上来回传输，以及从内存中删除一个比特需要多少能量。 香农发现所有处理经典信息的机器都必须遵守这些物理法则（香农法则）。显然对我们人脑来说，由于信息在我们的大脑中的确也是来回不断传输和跳动的，那么这个信息法则是否意味着我们人类的思想也最终可以简化为比特和字节? 难道我们人类这么复杂精密的大脑也只不过是一台运行的经典计算机? 显然这是一个令人不安的想法。 

  但是在经典计算机之外还有一个领域超越了上面对运算速度和信息传输的限制，那就是量子。 量子理论的概率属性允许原子或其他量子单元能存储和处理和经典二进制不同的信息，这些信息不仅可以是二进制里的0或1，也可以同时是0和1（0和1的叠加态）。目前，世界各地的物理学家们正在各地的实验室里制造着最原始的量子计算机并取得了一些阶段性的进展，他们希望利用量子计算机独特的量子效应来完成传统经典计算机无法完成的任务，比如通过更少的访问在数据库中快速找到目标记录（Grover的量子搜索算法），利用量子特性快速地进行大数分解（Shor的大数分解算法）（需要说明的是在量子算法下NP问题变成了P问题）。 但是科学家们仍在试图弄清楚到底是什么原因让量子计算机运算能力和信息处理能力变得如此强大，并希望在更为可靠的原理上设计和制造出具有足够规模（足够量子比特数）的量子计算机来做一些具有实际应用的事情。 

  通过认识量子世界奇异的量子特性和量子逻辑并利用它们来进行一些实际问题的计算，科学家们正在更加深入地研究亚原子量子世界的基本规律。 也许一些看似平凡的事情，比如对经典计算机运算极限的不断超越和对经典计算机运算能力的不断提升，可能最终会导致人类对量子领域更为全新的认识和理解。

                                                                            ——CHARLES SEIFE 撰文，张林 编译