“九章”问世：量子计算机究竟有多快（二）

量子计算机到底有多快？

　　那么，当我发现因数分解算法后记者会问：量子计算机比经典计算机快多少呢？答案就是：这个问题无法回答。就像问船要比火车快多少的问题，这不仅仅是取决于船和火车，还取决于目的地在哪里。所以对量子计算机和经典计算机来说，问题在于经过希尔伯特空间的捷径能否有一个从输入到输出。因此要考虑到许多因素， 而事实上这样的误解非常普遍， 这也说明了公众普遍接受了量化邱奇图灵论点， 即认为计算机中最重要的是足够的空间以及计算速度。然而量子计算机中的一步操作要比经典计算机中的一步操作长。但是量子计算机可以通过走希尔伯特空间的捷径来加速计算，而经典计算机无法这样做，这就大大减少了操作数。

　　去哪里寻找定量丘奇图灵论题的反例呢？可能会在难以模拟的物理系统中。那什么样的物理系统是难以模拟的呢？一个明显的答案就是湍流问题，它跟纳维尔-斯托克斯问题相关，是七个千禧年难题之一。陶哲轩思考过这个问题， 认为它和一些系统的偏微分方程组很相似。

　　湍流就是这样一类很难去模拟的物理系统，而量子力学是另外一种很难模拟的系统，这首先是由Poplavskii和费曼提出的。用数字计算机来模拟量子力学是指数级低效的， 费曼曾指出， 量子计算机的态空间大小是指数级增长的。你把量子系统的状态存储到经典计算机中，然后去精确追踪它们，这需要天文级的时间，但是量子计算机也许能解决这个问题。

　　在量子算法领域的早期， 1985年， David Deutsch提出问题：量子计算机是否可以加速非量子力学问题的计算？并且他提出了一个非常新颖的例子。七年后，它和Jozsa合作提出了另外一个算法，然后有了更多的人找到新的算法。量子计算机可以加速这些计算，当然，这些算法是为一些问题特定构造的，量子计算机确实可以更快的解决这些问题， 然后呢？

　　量子算法

　　量子计算机擅长哪些事情呢？第一个擅长的事情是： 量子计算机可以更有效的模拟量子力学系统。这是Feynman和Manin首先提出的想法。也可以用量子计算机来寻找周期性，这就是Simon问题。还有用量子计算机来分解大数和求离散对数，还有Pell方程和一些其他数学问题也是寻找周期性，Grover则提出可以用量子计算机来有效进行更大空间的搜索。现在来看下什么是因数分解。

　　假设你有一个整数33，你想要找到两个整数相乘等于33，用3乘以11即可，两个数字相乘对经典计算机来说非常简单。但是如果我们有一个非常大的数字，想要找到它是由哪两个质数相乘得到，这就是一个非常困难的问题了。如果我们想要分解一个L位的数字， 最好的经典方法是数域筛法， 它需要指数级的时间， 而量子计算机只需要平方级的时间。

　　用已知算法来进行大数分解的资源消耗估计，需要的经典指令数目上升的非常快， 而需要的量子门操作数上升的很缓慢， 这是因为要分解更多位的数，需要的经典指令数目会指数倍的增加。这个发现对计算机科学家来说是令人兴奋的，但对密码学家来说，互联网的安全基于公钥加密，比如RSA加密系统是基于以下事实：很容易将两个因数相乘，但很难将一个大数进行因数分解。

　　这意味着我们可以这样使用它：取两个质数并把它们相乘就得到一个密钥， 然后把它们分开，这样其他人就无法分解这个密钥， 别人也就无法破解你的信息。但是如果有量子计算机就可以破解信息，这意味着你可以监听计算机之间的信息交流，比如在互联网上购买东西时的信息交流。这就是为什么这个算法在1994年提出后就像病毒一样迅速传播。

来源：新浪科技