十八岁华裔天才再次颠覆量子计算，引来Nature报道

选自Nature，机器之心编译，参与：刘晓坤、李泽南。

量子计算再一次「被打败了」。今年 8 月，刚刚年满 18 岁的 Ewin Tang 证明了经典算法能以和量子计算机相近的速度解决推荐问题，这位天才少女（更正：不是少年）的惊人成就引来了媒体争相报道，和人们的广泛讨论。

Ewin Tang 已经完成了在 UT Austin 的本科学位，目前正在华盛顿大学（University of Washington）攻读计算机科学博士，她近期与 András Gilyén，以及量子计算先驱 Seth Lloyd 共同完成的论文引起了 Nature 的注意。在这一研究中，科学家们再次使用经典方式重构了此前被认为量子计算占据优势的算法。

看来，量子计算方式可以带来的优势并没有人们想象的那么多。未来的超级计算机不一定是量子计算机，你觉得呢？

在某些任务中，量子计算机可能无法超越已有的系统。图源：Greg Kendall-Ball/Nature

今年 5 月，两位理论计算机科学家解决了一个长达 25 年的假设。他们证明了量子计算机在非常复杂的任务上比经典计算机更加高效，例如测试数值是否随机。换种说法即：他们定义了一类特定的计算问题。他们在一定程度上证明了量子计算机能够有效解决这个问题，而传统计算机却永远无法解决。

从计算复杂度的角度，PH 涵盖了任何可能的传统计算机所能解决的问题，他们则找到了证明是 BQP（涵盖了量子计算机可以解决的所有问题）却不是 PH 的问题。

尽管如此，这样的工作并不能证明现在围绕量子计算的期望的合理性。美国国家科学院、工程学和医学院的最新报告（由领先的谷歌和微软研究人员撰写）强调了构建实用的量子计算机的技术障碍。报告称，创建这样的机器至少需要十年时间。

报告地址：https://www.nap.edu/read/25196/chapter/1

剑桥麻省理工学院的理论物理学家 Seth Lloyd 在谈到这个领域正处于爆炸性进展期，「但是炒作也在失去控制... 整个量子计算领域现在正在走向混乱，」他说。

量子计算机是必需的吗？今年 8 月一位 18 岁的计算机科学家在一项引人注目的研究中对此提出了质疑，至少在一类特定任务中。

Ewin Tang 开发了一种非常高效的经典推荐系统算法，相比于之前的最快经典算法有指数级提高，并和量子推荐系统算法的速度 xian 相当。Tang 的算法不一定实用，因此它不会取代当前的算法，除非它在目前的形式中得到实质性的改进，它只对真正巨大规模的数据集有用。但是，在它有机会在实际机器上运行之前，针对同一任务的量子算法现在已经没有实际意义了。

上个月，现在已经位于西雅图华盛顿大学的 Tang 对量子机器学习算法实现了二次冲击。她和两位同事证明了在另一项机器学习任务上，量子优势也不复存在。德克萨斯大学的另一个团队也独立地取得了相同的结论。计算机科学家用比喻回应了这个消息。例如，将 Tang 比作屠杀量子社区的希望和梦想的角斗士。对于 Tang 的合著者 Seth Lloyd 来说，这是一个苦乐参半的时刻，他写了一个被打败的量子算法。

论文：Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension

论文地址：https://arxiv.org/abs/1811.04909

摘要：我们为低秩矩阵构造了量子矩阵求逆算法（HHL）的有效经典变体。受 Tang 最近工作的启发，我们假设对输入数据进行长度平方的采样，实现了低秩矩阵的伪逆，并使用快速采样技术从解决方案到问题 Ax = b 进行采样。我们通过找到 Avia 子采样的近似奇异值分解，然后利用奇异值的倒数来实现伪逆。原则上，该方法还可用于将任何所需的「平滑」函数应用于奇异值。由于许多量子算法可以表示为奇异值变换问题，我们的结果表明，更多的低秩量子算法可以有效地「去量化」为经典的长度平方采样算法。

另一篇：Quantum-inspired sublinear classical algorithms for solving low-rank linear systems

论文地址：https://arxiv.org/abs/1811.04852

该领域的一些研究者认为，经典计算机在这方面的使用实际上是量子计算的成功，因为它们表明了量子思维方式如何产生影响——即使是在量子计算机出现之前的今天（毕竟这些算法也是 Quantum-inspired）。专家们还指出了长期以来人们所知的量子计算机优势「项目」，例如网络搜索。在另外一些情况下——例如将大整数分解为素数（质因数分解）或模拟材料的电特性——科学家们目前认为量子计算机可能仍然具有优势，尽管这尚未在数学上得到证明。

量子计算机是一种尚未存在的技术，它可以解决的问题还有待人们的发现。同时，研究者们也正在寻找使用经典策略可以解决的问题。两者都是有前途的研究方向。量子计算设备仍然是一个有价值的目标，但它并不是通往未来的唯一途径。