MIT教授评价谷歌量子计算机：拙劣且没赢得胜利

2010年，加拿大一家名为D-Wave的公司宣布在麻省理工学院理论工作的基础上已开始生产所谓的全球首款商用量子计算机。与传统计算机相比，量子计算机能保证显著更快地解决一些问题，或者至少在一项案例下，量子计算机的速度呈指数倍提升。2013年，谷歌和美国航天局（NASA）等组成的财团购买了D-Wave的一台设备。

多年来，批评者认为，目前还不清楚D-Wave机是否真正利用量子现象进行计算。如果是，那么与比传统计算机相比，它的优势在哪里。

但本月初，谷歌研究人员小组发表了一篇论文，声称在他们的实验中，在他们的D-Wave计算机上运行的量子算法比与之做对比的经典算法快了1亿倍。

麻省理工学院电气工程和计算机科学系副教授斯科特·阿伦森已跟踪研究D-Wave计算机多年。MIT News 邀请他对谷歌研究人员的这篇新论文进行了解释。

谷歌研究人员的论文集中在两种算法上：模拟退火（simulated annealing）和量子退火（quantum annealing）。如何理解这两种算法？

模拟退火是当今使用的领先优化方法之一。它发明于20世纪80年代初，直接类比了已有7000年历史的金属退火工艺。加热金属时，原子随机扩散，而当慢慢冷却下来时，原子已错位，从而总能量减少。

在算法情况下，一大堆比特在1和0之间随机蹦跳，而不管是否对求解质量有影响。然后当“温度”降低时，比特越来越不愿意按照使求解更糟的方式蹦跳，直到最后，当温度为0时，比特只会达到使求解连续下降的值，即趋向更好的求解。

模拟退火或其他任何局部搜索方法的主要问题是，你可能会停留在局部最优。

如果你想达到某种能量景观的最低点，你可能会卡在局部最优的裂缝里，但你没有意识到，只要向上继续搜索，你会发现其他地方还有更低的山谷。

模拟退火已经试图解决上述问题：在温度高时，你有时愿意沿山坡向上移动。但是，如果山很高，即使是一座非常狭窄的山（可以想象成矗立在地上的一个尖峰），你可能需要花费指数量的时间，直到你碰巧翻动足够多的比特使你翻越该尖峰。

在量子力学中，我们知道，粒子可以通过势垒隧道（这是物理学家使用的语言，会有点误导。）来自麻省理工学院的法伊、戈德斯通和古特曼（Farhi, Goldstone, and Gutmann）2002年发表了一篇重要论文。

该论文表明，如果你的势垒确实是一个高高瘦瘦的尖峰，那么量子退火可以提供一个比经典模拟退火速度指数倍更快的速度。

经典退火会长时间陷在该尖峰底部，而量子退火可在多项式时间内越过该尖峰，然后下降到全局最小值。

D-Wave机利用了量子隧穿效应吗？

在现有的D-Wave芯片模式，有1000个左右的量子比特，但每8个形成集群。每个集群内的量子比特非常紧密地彼此连接，并且集群之间只有弱连接。

我认为，这是最好的量子隧穿行为证据，至少是在8量子比特集群的水平上。

这些研究结果显示，量子退火优于模拟退火的主要方式是利用以下事实：量子隧穿或任何与集群内所有量子比特相关的行为，可以同时翻动每个集群内的所有量子比特，而模拟退火是一个接一个地尝试翻动，然后发现这不是一个好主意，于是又把它们翻回去，并没有意识到，同时翻动8个的效果更佳。

此案例明确表明，D-Wave机所有功能的实现都要翻越这个8量子比特的势垒。当然，这仍然不意味着在任何事情上，它都比经典方式更快。

这是什么意思呢？

在计算机科学中，通常我们关心的是渐进加速：例如，“根据问题复杂度的运行时间有多长？这个时间是否是线性增长？是否是二次方地增长？”至于是否是5阶或10阶增长，我们不是很在乎，我们只关心它是N阶线性增长。

在谷歌论文里，研究人员讨论了两种经典的算法，都符合渐进性能：其中一种击败了D-Wave机的现实世界性能。

因此，除了模拟退火，还有两种比较经典的算法。其中之一是量子蒙特卡罗（quantum Monte Carlo），这实际上是一种经典的优化方法，灵感来自量子力学。

在这篇新的谷歌论文里，研究人员表示，尽管量子蒙特卡洛具有相同的渐近性能，但其常量对D-Wave而言好太多了，比模拟退火高出约1亿倍。

对此，我有两个问题。第一个问题是，做比较的问题实例基本上是为了解决D-Wave机本身的模拟问题。为使D-Wave机专用硬件的速度尽可能快，该设计花费了1.5亿美元。

因此，从某种意义上说，就模拟问题本身而言，与传统计算机相比，此专用硬件获得常数因子加速的结果是毫不奇怪的。

D-Wave机芯片里量子比特的组织形式是一个特定图形的拓扑结构。如果你想解决一个实际重要的优化问题，你需要以某种方式将该问题映射到上述拓扑结构。另外，映射时总是有丢失，而且这种丢失似乎完全有可能消灭前文提到的常数因子优势。

另一个问题是，现行的还有一种经典算法，即“塞尔比算法”（Selby’s algorithm）。

我想此算法首先是在我的博客上发布的。它是一种局部搜索算法，但能够搞清量子比特形成了集群。

谷歌论文发现，在所有测试的实例中，运行塞尔比算法的传统计算机完全优于D-Wave机。

如果我知道每8个量子比特形成一个集群，并且将其视为一个巨大的变量，那么我只需发现该变量的最佳设置即可。只有256 个案例（2到8个量子比特）需要审查，并且很快可以完成。

如果每个集群含有800个量子比特，那么你就无法做到这一点。

另一方面，创建互相联结的800个量子比特是一件超难的工作。即使你构建了这些量子比特集群，你也不清楚量子退火能否翻出势垒。

请记住，量子退火在高高瘦瘦的势垒情况下表现最好。当潜在势垒（在800量子比特集群下可能出现）变宽，那么量子退火也会遇到麻烦。

我们终于明确了D-Wave公司10-15年前所做设计决策的逻辑后果，即“尽可能快地获得尽可能多的量子比特”，而不必担心它们的寿命或一致性，不必担心错误修正，也不必担心解决一些我们在理论上坚信有量子加速存在的问题。

我把它视为拙劣的方法，而其他大多数人试图采取正统的方法。当然，拙劣的方法有可能比正统的方法更快达到目的。在科技历史上，有很多先例证明拙劣的方法更快达到目的。

但是就当前的问题而言，拙劣的方法还没赢得胜利。

扫描微信二维码关注：