量子物理学——第17节-量子计算机
简介:回顾计算机发展的历史，自从第一台经典计算机问世以来，它在“大小”领域经历了巨大的变化，从一个占据几栋建筑的巨大物体到人们的手掌和口袋。在过去的20年里，计算机技术经历了一次巨大的革命性飞跃。单个芯片上三极管的数量和运行速度都在逐年呈指数级增长。
波士顿哈佛大学附近的克莱数学研究所在新的千年发布了一条信息:将提供一百万美元的奖金来寻找当时七个突出的数学问题的答案。到目前为止，12年过去了，俄罗斯数学家佩雷尔曼·格里戈里·佩雷尔曼在2006年只解决了“庞加莱猜想”中的一个问题。然而，佩雷尔曼天生对名利无动于衷，拒绝接受这个奖项。他还拒绝接受同年授予他的诺贝尔数学奖“领域”。据说这件事也给了一位数学数学家一个幕后故事。然而，这是一个题外话，这里没有显示。
七个千年奖之一是计算机算法领域中众所周知的P/NP问题。
众所周知，计算机的发明为许多需要大量数值计算的问题提供了捷径。计算机的计算能力是普通人工计算无法比拟的。一台超级计算机每秒可以连续执行数亿次运算。一般来说，需要数值计算的问题的计算量与代表问题大小的变量数n有关。变量n的数量越大，解决问题所需的计算时间t就越长。当然，计算时间T也取决于所使用的计算方法。计算机算法是对各种计算方法的研究。
所需计算量T和变量数N之间的函数关系根据问题而变化。在某些问题中，t和n是线性相关的；但在其他问题上，这是一个平方关系。指数也有可能随着n的增加而增加。
研究算法的科学家根据T随n增加的函数形式将需要大量计算的问题分成几种不同的类型。第一种类型称为P型，或多型。计算p型问题所需的时间t和n是多项式级数。多项式问题是一个可以用计算机解决的问题。只要计算机足够快，内存足够大，并且使用了正确的算法，答案今天将永远可用。然而，对于另一个NP-型问题，还没有找到成功的算法，所以当与n的关系在多项式级数中增加时，问题的答案可以在时间内得到解决。然而，这并不意味着该算法不存在。因此，这是一种不能确定t和n是否是多项式级数的问题。此外，还有一个最困难的问题，属于NP-Hard。
在NP型中，有一个子集是数学家最感兴趣的，它被称为NP完全整数。这个子集中的任何两个问题相互转换所需的时间是与n成多项式级数关系的。因此，如果我们找到一个多项式算法来解决一个NP完全问题，我们也有一个多项式算法来解决所有的NP完全问题，这叫做证明“NP=P”。另一方面，如果你能证明这个NP完全整数的多项式算法不存在，那么你就证明了“NP！=P .克莱数学学院的百万美元奖将授予那些证明了“NP=P”或“NP！=P”。
看下图，可能更容易理解生产计划/生产计划问题:
大多数数学家认为结论应该是p！=NP，但是很难严格证明这个结论。否则，答案怎么会有百万美元的奖金呢？然而，2010年8月，惠普实验室的一名研究人员声称证明了磷不是磷。然而，当时他只是在自己的网站上宣布了这件事，然后似乎就没有了追随者。因此，这应该是一个悬而未决的问题。
算法问题的本质是计算速度问题。从理论上讲，当前经典类型的计算机将永远无法处理计算中的指数增长问题。这些题目包括著名的“旅行推销员问题”，用于秘密通信的大数的素数分解问题等。，以及获胜问题，据说属于最难的NP-Hard类。我不敢说量子计算机能解决这些困难，但它们总是提供另一种完全不同于经典图灵机的选择性，并根据量子定律运行。
不幸的是，量子理论的诞生已经有大约100年的历史，而经典计算机使用的芯片制造技术已经涉及到量子理论。然而，基于数亿经典比特的计算机科学家们在半个多世纪后才知道量子计算。如果这项研究早点进行，计算机科学可能会受益匪浅。回顾计算机发展的历史，自从第一台经典计算机问世以来，它在“大小”领域经历了巨大的变化，从一个占据几栋建筑的巨大物体到人们的手掌和口袋。在过去的20年里，计算机技术经历了一次巨大的革命性飞跃。单个芯片上三极管的数量和运行速度都在逐年呈指数级增长。正是这种快速的发展将很快使经典计算机达到极限。到那时，三极管的尺寸将达到原子尺度。经典电脑的基本原理是，无论是40多年前充满整个房子的巨大物体，还是现在的移动电话电脑，一切都将保持不变。基本建设单位是比特。无论是用灯泡大小的电子管实现的一点点，还是用芯片上的三极管(微米大小)表达的一点点，都遵循牛顿力学定律。直到费曼在使用经典计算机模拟子系统时观察到“指数减速”的问题，计算机科学家和物理学家才开始携手研究“量子计算机”的物理实现和算法。
有些人还把研究“可逆计算”的IBM科学家兰道尔视为量子计算之父。人们相信他在1961年在“可逆计算”领域的发现导致了量子计算机的研究。然而，事实上，可逆计算的研究仅仅与量子计算机有关，并不直接导致量子计算的发展。此外，在他去世之前(直到1999年去世)，兰道尔本人也不遗余力地批评量子计算机的研究。他认为量子计算机“没有考虑所有可能的噪声源，也没有考虑实际生产中的误差和缺陷，这基本上是不可能的。”