如何评价谷歌在12月10日在发布会上称发现了一个比传统算法快一亿倍的量子算法？ Summer Clover 2013 年谷歌和美国宇航局共同研发了 D-Wave X2 计算系统，这个 D-Wave 应该是世界上第一个功能正常的量子计算机，尽管公司内外的专家从未总结性的证明这台机器真正进行了量子计算，而现在这已经成为过去式。 D-wave 是世界上第一种商用的利用量子效应进行计算的机器。它最准确的称呼是量子退火机（Quantum Annealing Machine），只能运行量子退火算法。量子退火算法是用来解决最优化问题的。 新闻里还有一些谬误。D-wave System 是加拿大公司 D-wave Inc. 研发的，Google 和 NASA 花了一千万美元买了一台。 最优化（Optimization）是机器学习 / 人工智能中必不可少又十分消耗计算的一步，所以 Google 对量子退火非常上心。与 Google 联合建立量子人工智能实验室（Quantum AI Lab）的 NASA 也很倾心 D-wave，也是因为宇宙飞船的远距离航线是非常复杂的最优化问题。亚马逊的创始人贝佐斯和 CIA 是 D-wave 这家公司的两大股东。亚马逊可以用退火机来优化物流运输线。CIA 的目的我就猜不到了。 由于 D-wave 不能运行其他量子算法，不能进行量子逻辑门（Quantum Gate）操作，不是通用型量子计算机，相当一部分科学家不认为 D-wave 是真正的量子计算机。 但是，D-wave 毫无疑问是具有一台具有量子计算功能的机器（Machine）。因为 D-wave 可运行绝热量子计算，而且绝热量子计算在理论上等价于基于逻辑门的标准量子计算。 绝热量子计算和量子退火的关系有一些模糊。但是量子退火算法的提出者西森教授认为绝热量子计算是量子退火的子集。更多情况下，这两者的原理和目的非常接近，以至于很多 paper 都没做特别的区分。 目前实验上最主要的关注点在组合优化上，尤其是对二进制变量函数的优化。一方面是，经典计算机解决凸优化（Convex Optimization）问题相当高效，一方面是 D-wave 的芯片本身还很初级，目前还表示不了太复杂的函数。D-wave 的量子比特是由通电流的超导环制成的，电流逆时针即表示逻辑 0，顺时针则表示逻辑 1。所以 D-wave 表示二进制变量非常容易。 在谷歌这次实验之前，一直有相当多的人怀疑 D-wave 是否可以比经典计算机更快的解决组合优化问题。D-wave 也一直没有给出确凿的实验证据。这次 Google 的实验算是一个显著的支持证据。不管 D-wave 能不能叫量子计算机，D-wave 都比一个单核的经典计算机更快（快 1 亿倍）地解决了这个组合优化问题。 几位回答者都提到了一个问题，为什么实验结果是快一个常数倍？对于不了解量子退火的人来说不太容易理解。主要原因是因为量子退火算法的时间复杂度和基于门操作的算法的时间复杂度很难比较。基于逻辑门的算法，无论是经典的还是量子的都会写成类似于 的形式。像 Shor 算法虽然从来没有在量子计算机上运行过，但没人质疑它是不是真的更快，因为它是基于逻辑门的算法，时间复杂度就是逻辑门操作的次数。 经典算法解决谷歌实验组这个二进制变量函数优化问题的时间复杂度就是 。搜索空间会以 2 的指数倍增长。而量子退火算法的时间复杂度是 。这个是基态和第一激发态的能量差，这个比较正式的说法叫谱隙（Spectral Gap）。 （等等，为什么机器学习、优化问题会有量子力学里的基态？最后解释。） 也就是说，无论这个优化问题有多么复杂，哪怕搜索空间比整个宇宙的粒子数目还多得多，量子退火的速度都可能很快。现在是 的搜索空间，量子退火已经快一亿倍了。如果 2000 个变量呢？那么，最完美的情况（Spectral Gap 还是同一个量级）是比普通的单核电脑快一亿亿倍左右。 就算 2000 个变量不够，那 10000 个变量总够了吧？D-wave 最新型号是 1024 比特（实际上是 1097 比特）。每一代 D-wave 的比特数都会翻倍，每两年就能推出新型号。几年之内，D-wave 比特数就能达到万的量级。处理组合优化问题上，D-wave 胜过天河二号是迟早的事。现在乐观的估计是一个十年（decade）。 量子退火 / 量子优化 / 绝热量子计算为什么备受关注？因为标准量子计算以十年为单位规划蓝图，而量子退火以月为单位向前迈进。 为什么机器学习、最优化会有基态？是这样的。一个机器学习问题总会被转化为求解一个最优化问题。而一个最优化问题的 cost function 和一个量子系统的能量有类似的数学结构。理论上来讲，总是存在一个量子系统对应一个机器学习系统（但我们未必能构造这个量子系统）。这个量子系统的能量就是我们要优化的 cost function。D-wave 就是一种可以表示一大类机器学习（比如 clustering）和最优化问题（比如组合优化）的量子系统。 Spectral Gap 和 n 有什么关系？ 仍然没有答案。只能简单地想象一下，n 增加，量子系统变复杂，复杂的量子系统一般有更小 Spectral Gap，但是变小的幅度肯定不会快到 倍。想一下原子的能谱结构和最简单的旅行商问题就明白。Spectral Gap 和 n 关系，比较糟糕的一点是，最近一篇 Nature 说，一般情形下的 Spectral Gap 是不可判定(Undecidability)的。（这里有个简单的介绍Nature 和 Science 上有哪些非常有趣而又脑洞大开的文章？ - Climber.pi 的回答）或许，除了不停地实验以外，我们永远都不知道 D-wave 的极限在哪里。 这次的实验的确可以算是一个里程碑。512 比特的 D-wave 没办到的，1024 比特 D-wave 办到了，第一次超越一台电子计算机一亿倍。这一系列的实验还会继续下去，在解决问题的速度上和表示问题的广度（更广义的组合优化问题，甚至是连续变量的非凸优化问题）上要继续前进。 现在最想做的就是早点把自己设计的算法实现了。 查看知乎原文
