参与:刘晓坤、李泽南

十八岁华裔天才携手「量子计算先驱」再次颠覆量子计算

量子计算再一次「被打败了」。今年 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)。专家们还指出了长期以来人们所知的量子计算机优势「项目」,例如网络搜索。在另外一些情况下——例如将大整数分解为素数(质因数分解)或模拟材料的电特性——科学家们目前认为量子计算机可能仍然具有优势,尽管这尚未在数学上得到证明。

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

原文地址:https://www.nature.com/articles/d41586-018-07801-3

理论量子计算量子计算机Nature
2
相关数据
微软机构

微软是美国一家跨国计算机科技公司,以研发、制造、授权和提供广泛的计算机软件服务为主。总部位于美国华盛顿州的雷德蒙德,最为著名和畅销的产品为Microsoft Windows操作系统和Microsoft Office办公室软件,以及Xbox的游戏业务。微软是美国《财富》杂志2015年评选的世界500强企业排行榜中的第95名。

机器之心机构

机器之心Synced创立于 2014 年,是国内首家系统性关注人工智能的科技媒体。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

重构技术

代码重构(英语:Code refactoring)指对软件代码做任何更动以增加可读性或者简化结构而不影响输出结果。 软件重构需要借助工具完成,重构工具能够修改代码同时修改所有引用该代码的地方。在极限编程的方法学中,重构需要单元测试来支持。

奇异值分解技术

类似于特征分解将矩阵分解成特征向量和特征值,奇异值分解(singular value decomposition, SVD)将矩阵分解为奇异向量(singular vector)和奇异值(singular value)。通过分解矩阵,我们可以发现矩阵表示成数组元素时不明显的函数性质。而相比较特征分解,奇异值分解有着更为广泛的应用,这是因为每个实数矩阵都有一个奇异值分解,但未必都有特征分解。例如,非方阵型矩阵没有特征分解,这时只能使用奇异值分解。

推荐系统技术

推荐系统(RS)主要是指应用协同智能(collaborative intelligence)做推荐的技术。推荐系统的两大主流类型是基于内容的推荐系统和协同过滤(Collaborative Filtering)。另外还有基于知识的推荐系统(包括基于本体和基于案例的推荐系统)是一类特殊的推荐系统,这类系统更加注重知识表征和推理。

量子机器学习技术

量子机器学习是量子物理学和机器学习交叉的一个新兴的交叉学科研究领域。人们可以区分四种不同的方式来结合这两个父类学科。量子机器学习算法可以利用量子计算的优势来改进经典的机器学习方法,例如通过在量子计算机上开发昂贵的经典算法的有效实现。 另一方面,可以应用经典的机器学习方法来分析量子系统。 一般来说,可以考虑学习装置和所研究的系统都是完全量子的情况。

推荐文章
暂无评论
暂无评论~