计算机基本算法有哪些公式（经典计算机的运算极限）

经典计算机的运算能力可以用CPU每秒钟所执行的指令条数来衡量，也就CPU在时钟动作电位的驱动下每秒能执行多少次基本的指令操作（比如加法的移位操作）。当然CPU的各种基本指令操作所用的时钟周期不一样，所以计算机整体上就可以用每秒执行的平均指令数来刻画，单位一般取每秒百万指令数MIPS(Million Instructions Per Second)。当然最简单直观的运算能力就是每秒运算多少次，例如我国著名的天河二号超级计算机运算速度为每秒三万万亿次。这台超级计算机是由几万个节点和每个节点有多个核的CPU架构而成。如果不断增加经典计算机的节点和不断提高CPU时钟频率，似乎计算机的运算能力就没有限制。那问题到底是不是这样，下面就来讨论这个问题：

图1 天河二号超级计算机系统（侵删）

19.什么是经典计算机的运算极限？What Are the Limits of Conventional Computing?

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

乍一看，传统计算机的运算极限似乎只是一个工程问题。传统计算机的运算极限不就决定于你能能输入多少能量而不至于把芯片融化？不就决定于你在硅存储器里翻转一个比特的最高速度? 不就决定于你在一个房间大小的空间里能把电脑系统做得有多大? 所以，传统计算机的运算极限这个问题表面上看似乎并不深奥，只要你不断提高芯片集成度、提升CPU的时钟频率，不断增加你计算系统的节点数量，经典计算系统的运算能力似乎没有极限。

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

图2 阿朗佐·丘奇和艾伦·图灵以及一个图灵机模型（侵删）

理论学家现在已经把计算问题在更为广泛的意义上分成两大类：P问题和NP问题。 一般来说，P问题是那些可以快速解决的问题，也就是能够在多项式（polynomial）时间内算出结果的问题（更严格的表述是存在多项式时间算法的问题）。例如对一个名单按字母的顺序进行排序的问题，就是典型的P问题，也就是说排序运算的时间和名单上名称的个数n（广义地称为运算规模）是多项式的关系。而 NP问题则更难解决，也就是你算出结果的时间和你的运算规模n之间不再是多项式关系，比如变成指数关系：（严格来讲NP问题是不确定有没有多项式算法的问题，英文为：Nondeterministic polynomial problems）。

图3 典型的邮递员派送NP问题

NP问题虽然难以运算但其有另外一个重要特点就是：一旦你知道了答案，检查这个答案的对错却是相对容易和快速的（即可以在多项式时间内验证其解是否正确）。NP问题的一个典型例子是旅行推销员（或者邮递员、派送员）问题，即派送员需要把货物派送到一系列地点，那么他如何在这些地点上寻找一条最短的可能路线？寻找这条最短路径的运算时间和地点个数n之间就似乎不再是一个n的多项式关系（显然遍历n个地点的所有路径有n!个）。因为目前所有已知的获得答案的算法都不是多项式时间，都是需要耗费大量计算资源才能完成的算法，即便面对一个派送规模为n的相对较小的派送问题，其运算量也能超出任何经典计算机的运算能力。

图4 克雷研究所公布的七大数学问题之一：NP=P问题

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

图4 计算复杂度问题之间的关系图，从左到右计算复杂度越来越大

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

图5 信息的传输速度和香农的信息理论

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

图6 量子计算公司及其开发的量子计算芯片

但是科学家们仍在试图弄清楚到底是什么原因让量子计算机运算能力和信息处理能力变得如此强大，并希望在更为可靠的原理上设计和制造出具有足够规模（足够量子比特数）的量子计算机来做一些具有实际应用的事情。通过认识量子世界奇异的量子特性和量子逻辑并利用它们来进行一些实际问题的计算，科学家们正在更加深入地研究亚原子量子世界的基本规律。 也许一些看似平凡的事情，比如对经典计算机运算极限的不断超越和对经典计算机运算能力的不断提升，可能最终会导致人类对量子领域更为全新的认识和理解。（CHARLES SEIFE 文）