量子计算机可以做令人惊奇的事情：可惜它们还不存在。但这并没有阻止物理学家为这些设备设计新的算法，这些设备比普通计算机的计算速度快得多——实际上是指数级的快，在非常字面的意义上。一旦量子计算机投入使用，这些算法可能成为需要大量数字运算的应用的关键部分，从工程到视频游戏。
最新的量子算法正在物理学家中引起轰动。它处理线性方程：诸如 3x + 2y = 7 之类的表达式，通常将未知数写在一侧，常数写在另一侧。许多高中生学习通过一次消除一个未知数来求解此类方程组的机械方法。当系统包含数十亿个变量和数十亿个方程时，速度变得至关重要，这在现代应用中（例如天气和其他物理现象的模拟）中并不少见。高效的算法可以通过计算机求解大型“N 乘 N”系统（具有 N 个线性方程和 N 个未知数的系统）。尽管如此，计算时间至少与 N 成正比增长：如果 N 增大 1,000 倍，则解决问题的时间将至少延长 1,000 倍，通常更长。
英格兰布里斯托大学的 Aram W. Harrow 以及麻省理工学院的 Avinatan Hassidim 和 Seth Lloyd 现在提出的量子算法采用了一个巧妙的捷径。它可以返回关于解的最相关信息，而无需完全计算解本身，从而用产生的数据量换取速度。（例如，在天气预报的情况下，它可以返回一个城镇的平均温度，而不是按街区预测的温度。）
关于支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您正在帮助确保关于塑造我们今天世界的发现和想法的具有影响力的故事的未来。
像所有量子算法一样，他们的方法（在 10 月 9 日的《物理评论快报》中描述）将关于系统的所有相关信息编码到量子比特中。与普通的或“经典的”比特相反，量子比特可以同时以 0 和 1 存在——或者，正如物理学家所说，处于状态的叠加态。该算法将这些比特转换为一种状态，该状态基本上编码了系统所有可能解的叠加态，这意味着对于方程右侧常数的所有可能值。从这个“通用解”中，人们可以提取关于特定解的相关信息，而无需完全计算它们。
速度的提升是巨大的：产生通用解所需的时间仅随 N 的位数增长。因此，如果 N 增大 1,000 倍，算法花费的时间仅延长三倍（因为 N 增加了三位数），而不是延长 1,000 倍。即使写下所有变量的结果，在经典情况下也需要 1,000 倍以上的步骤。“解决问题所花费的时间比读取解决方案的时间呈指数级减少，”Lloyd 半开玩笑地说。
新加坡国立大学的 Artur Ekert 说：“与经典类似物相比，每个显示出明显加速的量子算法仍然是一件大事。” 只有少数量子算法可以夸耀这一成就——例如 1990 年代发明的用于将大数分解为素数或用于搜索数据库的算法。
到目前为止，只存在实验性量子计算机，其中仅包含少量比特。但德国乌尔姆大学的 Martin Plenio 说，在不久的将来，对新算法的小型演示应该是可行的。“但是，要建造一台足够大的量子计算机来解决经典设备无法解决的问题，还需要很多年，”他补充道。
Lloyd 说，如果某些应用利用光子的内在量子特性，则可能更快实现。例如，他提出，该算法可以体现在“超成像设备”中，该设备可以消除望远镜中的光学畸变。望远镜测量的每个光子都将扮演方程常数项的角色，而畸变将对应于线性方程组。找到解意味着逆转畸变，从而提高图像质量。