前沿 | 经典计算的天花板:科学家找到只有量子计算才能解决的问题

选自QuantaMagazine

作者:Kevin Hartnett

机器之心编译

参与:Huiyuan Zhuo、刘晓坤

在量子计算机研究的早期,计算机科学家提出了一个问题,他们知道这个问题的答案将会揭晓这些未来机器的强大力量背后的秘密。25 年过去了,问题仍然没有解决。在 5 月底在线发布的一篇论文中《Oracle Separation of BQP and PH》,计算机科学家 Ran Raz 和 Avishay Tal 提供了强有力的证据,证明量子计算机具有超越任何传统计算机能够达到的计算能力。Raz 是普林斯顿大学和魏茨曼科学研究员的教授,Tal 是斯坦福大学博士后,他们定义了一类特定的计算问题。他们在一定程度上证明了量子计算机能够有效解决这个问题,而传统计算机却永远无法解决。自 1993 年以来,计算机科学家一直在找寻这样一个问题,在当时他们首次定义了一类被称为「BQP」的问题,它涵盖了量子计算机可以解决的所有问题。

Oracle Separation of BQP and PH:https://eccc.weizmann.ac.il/report/2018/107/

计算机科学家希望将 BQP 与一类被称为「PH」的问题进行对比,PH 涵盖了任何可能的传统计算机(甚至是一些未来文明所设计的不可思议的先进计算机)所能解决的问题。能否进行对比取决于能否找到一个被证明是 BQP 却不是 PH 的问题。现在,Raz 和 Tal 做到了。

这一成果并没有使量子计算机在任何实际意义上超越传统计算机。比如,理论计算机科学家已经知道量子计算机可以解决传统计算机所能解决的任何问题。同时,工程师仍在努力构建有用的量子计算机。但是 Raz 和 Tal 的论文证明了量子计算机和传统计算机其实是不同的类别——即使在传统计算机超越所有现实的世界中,量子计算机仍然会超越它们。

量子类别

理论计算机科学的基本任务是将问题按复杂度等级分类。一个复杂类包含在给定资源预算内所能解决的所有问题,其中资源可能是指时间或内存。

计算机科学家已经找到了一种有效的算法,例如用于测试一个数字是否是素数。然而,他们仍没有找到一个有效的算法来计算大数的素数因子。因此,计算机科学家认为(但无法证明)这两个问题属于不同的复杂度等级。

两个最著名的复杂度等级是「P」和「NP」。P 是传统计算机可以快速解决的所有问题。(「这个数字是否是素数?」属于 P。)NP 是传统计算机不能迅速解决的所有问题,但可以快速验证一个答案。(「哪些数是这个数的素数因子?」属于 NP。)计算机科学家认为 P 和 NP 是不同的类别,但事实上证明它们的不同是该领域最难和最重要的开放性问题。

P∈NP∈PH,BQP 覆盖所有的 P 问题和部分的 NP、PH 问题(未证明);现在人们终于找到了属于 BQP 而不属于 PH 的问题。图源:Lucy Reading-Ikkanda / Quanta Magazine

1993 年计算机科学家 Ethan Bernstein 和 Umesh Vazirani 为「有界误差量子多项式时间」定义了一个新的复杂度等级,他们称之为 BQP。他们定义的类包含量子计算机可以有效解决的所有决策问题——问题的答案为是或否。同时他们也证明了量子计算机可以解决传统计算机可以解决的所有问题。也就是说,BQP 包含 P 中的所有问题。

但是他们无法确定 BQP 是否包含另一个重要的类「PH」(即「多项式分层」)中找不到的问题。PH 是 NP 的一个推广。这意味着如果你从 NP 中的一个问题出发,并通过「存在」和「任意」这样的限定语句进行分层以使其更为复杂,PH 也包含了所有你遇到的问题。现今传统计算机无法解决 PH 中的大多数问题,但如果 P 被证明等价于 NP,则可以将 PH 看作是传统计算机可以解决的所有问题的类。换言之,比较 BQP 和 PH 是为了确定是否量子计算机优于传统计算机,那么即使传统计算机能(出乎意料地)解决比现在的量子计算机更多的问题,量子计算机仍能存在。德克萨斯大学奥斯汀分校的计算机科学家 Scott Aaronson 说:「PH 是最基本的传统复杂度等级之一。所以我们想知道量子计算机如何适应传统复杂度理论?」

当谈到复杂度等级时,举个例子会很有帮助。「旅行推销员问题」询问是否存在一条途经一些城市且短于给定距离的路径。这是个 NP 问题。一个更复杂的问题是,通过这些城市的最短路径是否等于给定距离。这个问题是 PH。

区分两个复杂度等级的最好方法是找到一个问题,其能够被证明属于一个类而不属于另一个类。然而由于基础和技术上的障碍,找到这样一个问题很有挑战性。

如果你想要找到一个在 BQP 但不在 PH 中的问题,你必须确定一些东西,也就是 Aaronson 说的:「根据定义,一个传统计算机甚至无法有效验证答案,更别说找到答案了。这就排除了我们在计算机科学中考虑的许多问题。」

询问 oracle

问题是这样的。设想你有两个随机数字生成器,每个生成器产生一个数字序列。你的计算机得到的问题是这样的:这两个序列是否完全独立,还是以某种隐秘的方式相关(例如,一个序列是另一个序列的「傅立叶变换」)?Aaronson 在 2009 年介绍了这种「forrelation」问题并证明其属于 BQP。更难的第二步是证明 forrelation 不在 PH 中。

普林斯顿大学的理论计算机科学家 Ran Raz 找到一种分离两个计算类的方法。

从特定的意义上来说,这正是 Raz 和 Tal 所做的。他们的论文实现了 BQP 和 PH 之间的分离,被称为「oracle」(或「黑箱」)分离。这是计算机科学中常见的一种结果,当研究人员真正想证明的事情超出他们的理解范围时,他们会采取这种方法。

区分像 BQP 和 PH 这样的复杂度等级的最佳方法实际上是测量解决每个问题所需的计算时间。但如多伦多大学的计算机科学家 Henry Yuen 所说:「计算机科学家对实际的计算时间没有充足的理解或测量能力。」因此,计算机科学家测量了其它一些他们希望可以侧面反映无法测量的计算时间的东西:他们计算出计算机需要咨询 oracle 以便得出答案所需的次数。oracle 就像一位提示者。你不知道它的提示如何产生的,但你知道它们是可靠的。

如果你的问题是要弄清楚两个随机数字生成器是否潜在相关,那么你可以向 oracle 提问,比如说:「每个生成器的第六个数字是什么?」然后你根据每种计算机解决问题所需的提示数量比较它们的计算能力。需要更多提示的计算机速度更慢。

Tal 说:「从某种意义上来说,我们能更好地理解模型。它传递更多的是信息而不是计算。」

斯坦福大学的理论计算机科学家 Avishay 使用 oracle 分离来区分 BQP 和 PH。

Raz 和 Tal 的新论文证明了,量子计算机需要比传统计算机少得多的提示来解决 forrelation 问题。事实上,量子计算机仅需要一个提示。而即使有无穷多的提示,PH 中也没有可以解决问题的算法。Raz 说:「这意味着存在一个非常有效的量子算法可以解决这个问题。但如果你仅考虑传统算法,即使你拥有很高等级的传统算法,它们也无法解决。」这表明,对于 oracle 而言,forrelation 问题在 BQP 而不是 PH 中。

差不多 4 年以前,Raz 和 Tal 几乎达成了这一结果,但他们无法在证明中完成一个步骤。然后就在一个月前,Tal 听到一篇关于伪随机数生成器的新论文《Pseudorandom Generators from Polarizing Random Walks》,并意识到这篇论文中的技术正是他和 Raz 需要完成的。Tal 说:「这正是我们缺失的一块拼图。」

Pseudorandom Generators from Polarizing Random Walks:https://eccc.weizmann.ac.il/report/2018/015/

BQP 和 PH 分离的消息迅速传了开来。Raz 和 Tal 发表证明的第二天,乔治亚理工大学的计算机科学家,Lance Fortnow 写道:「量子复杂度的世界摇摆不定。」

这项工作提供了一个铁证,那就是相比于传统计算机(至少相对于 oracle 而言),量子计算机存在于一个不同的计算领域。甚至在 P 等价于 NP 的世界里(其中「旅行推销员问题」就像在电子表格上找到最合适的线一样简单),Raz 和 Tal 的证明仍然表明存在着只有量子计算机才能解决的问题。

Fortnow 说:「即使 P 等价于 NP,甚至做出了强有力的假设,仍然不足以掌握量子计算。」

原文链接:https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/?from=timeline

本文为机器之心编译,转载请联系本公众号获得授权。

原文发布于微信公众号 - 机器之心(almosthuman2014)

原文发表时间:2018-07-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

机器学习的必备条件不是数学而是...

编者按:2012年10月《哈佛商业周刊》上面发表了一篇专栏,文章称“数据科学家”是21世纪最最性感的工作。在美国,数据科学家的年收入已超过律师和医生,无怪乎有人...

36970
来自专栏自然语言处理

探讨自然语言处理技术学习与思考

随着人工智能的快速发展,自然语言处理和机器学习应用愈加广泛。但是对于初学者入门还是有一定难度,对于该领域整体概况不能明晰。本章主要从发展历程、研究现状、应用前景...

30610
来自专栏AI研习社

F8 2017 | 技术负责人为你解析 Facebook 神经机器翻译

编者按:该讲座主题为 Facebook 机器翻译的两代架构以及技术挑战。 在昨日的 F8 会场,该讲座吸引了众多开发者到场,主讲者是 Facebook 语言翻译...

357110
来自专栏大数据挖掘DT机器学习

订单贡献率10%,京东个性化推荐系统持续优化的奥秘

京东基于大数据和个性化推荐算法,实现了向不同用户展示不同的内容的效果,在PC端和移动端都已经为京东贡献了10%的订单。为了探索京东全品类平台“千人千面”背后的算...

35560
来自专栏编程

5本书带你走进Python与机器学习的世界

基于大数据的人工智能如今异常火爆 Python 作为最热门的编程语言之一 是实现机器学习算法的首选语言 Python与机器学习这一话题非常的宽广 5本书虽很难覆...

388100
来自专栏BestSDK

火爆的机器学习和人工智能,为何在金融业四处碰壁?

在2008年金融危机期间,银行业认识到,他们的机器学习算法是基于有缺陷的假设。 因此,金融体系监管机构决定需要额外的控制措施,并引入了对银行和保险公司进行“模式...

35660
来自专栏人工智能快报

全球人工智能行业分析

2015年9月,美国Venture Scanner公司发表了针对全球人工智能行业的分析报告,涉及很多新兴市场。该分析报告针对人工智能(AI)行业,追踪了13个人...

36250
来自专栏PPV课数据科学社区

我在面试机器学习、大数据岗位时遇到的各种问题

自己的专业方向是机器学习、数据挖掘,就业意向是互联网行业与本专业相关的工作岗位。各个企业对这类岗位的命名可能有所不同,比如数据挖掘/自然语言处理/机器学习算法工...

47260
来自专栏PPV课数据科学社区

经验谈:数据挖掘七步走

Step1.商业理解 就是商业问题的理解了,那么如何更好的理解“老大”提出的商业问题困惑呢?我觉得思维导图倒是个不错的选择,当然自己要想更好的理解“老大”的意思...

29650
来自专栏云市场·精选汇

AI学院 | 人工智能基本知识概览

人工智能(Artificial Intelligence):缩写为AI,是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。

23960

扫码关注云+社区

领取腾讯云代金券