请选择 进入手机版 | 继续访问电脑版
专注物联网产业服务
微信二维码
威腾网服务号
游客您好
第三方账号登陆
  • 点击联系客服

    在线时间:8:00-16:00

    客服电话

    17600611919

    电子邮件

    online@weiot.net
  • 威腾网服务号

    随时掌握企业动态

  • 扫描二维码

    关注威腾小程序

柯如冰 论坛元老
未知星球 | 未知职业
  • 关注0
  • 粉丝0
  • 帖子1360
热议话题
精选帖子

量子计较机有多利害?今朝已知有一个题目是只要它能处理的

[复制链接]
 楼主| 柯如冰 发表于 2020-1-13 16:12:30 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题

量子计较机仅仅是比典范计较机强了那末一点点、快了那末一点点、效力高了一点点吗?我们都晓得,答案是“不”。

但是,为了证实量子计较机的真正气力,科学家颇费了一番功夫。在量子计较机研讨的早期,计较机科学家提出了一个题目。他们晓得,这个题目标答案会深入揭露这些未来机械的能力。但是,25年后的明天,这个题目差点还是没能处理。

现在,他们终究找到了一个只要量子计较机才能处理的题目。
量子计较机有多利害?今朝已知有一个题目是只要它能处理的-1.jpg

今年5月底在网上颁发的一篇论文中,计较机科学家冉·拉兹(Ran Raz,普林斯顿大学和魏茨曼科学学院的教授)和阿维沙伊·塔尔(Avishay Tal,斯坦福大学博士后研讨员)提出了有力的证据,证实量子计较机具有任何传统计较机都不成能到达的计较才能。

拉兹和塔尔界说了一个具体的计较题目,然后证实,量子计较机可以有用地处理这个题目,而传统计较机永久都处理不了。从1993年起头,计较机科学家就一向在寻觅这样一个题目。在那一年,计较机科学家初次界说了一类涵盖量子计较性能处理的一切题目集,统称为“BQP”。

从那时起,计较机科学家希望将BQP与被称为“PH”的一类题目停止比力。PH涵盖典范计较机可以处理的一切题目,哪怕是未来文化建造的、先辈到不成思议的典范计较机。想要停止那种比力,就必须找到一个题目,证实这个题目属于BQP,但不属于PH。现在,拉兹和塔尔做到了。

他们的研讨成果并没有使量子计较机在现实利用中超越典范计较机。理论计较机科学家已经晓得,量子计较机可以处理典范计较性能处理的任何题目。工程师们还在尽力研制实在可用的量子计较机。但拉兹和塔尔的论文证实,量子计较机和典范计较机是两回事——即使典范计较机的表示超越了一切的现实期望,量子计较机照旧会高屋建瓴。

量子级计较

理论计较机科学的一个根基使命是把题目停止复杂性归类。一个复杂性类包括在某一特定的资本预算内可以处理的一切题目。这里的资本可所以像时候大概内存这样的工具。 两个最著名的复杂性类是“P”和“NP”。P是典范计较性能敏捷处理的一切题目(“这个数字是质数吗”属于P),NP是典范计较机一定能敏捷处理的一切题目,但在给出答案的情况下,典范计较性能敏捷证实答案能否正确(“其质因数是什么”属于NP)。计较机科学家以为,P和NP是截然分歧的类,但真正证实这一点是该范畴里最困难、最重要的题目。
量子计较机有多利害?今朝已知有一个题目是只要它能处理的-2.jpg

1993年,计较机科学家伊森·伯恩斯坦(Ethan Bernstein)和乌梅什·瓦兹拉尼(Umesh Vazirani)界说了一个新的复杂性类,他们称之为BQP,即“有界误差量子多项式时候”。这个类包括量子计较机可以有用处理的一切判定性题目(答案为“是”大概“否”)。同时,他们也证实了量子计较机可以处理典范计较性能处理的一切题目,即BQP包括P中的一切题目。

但他们没法肯定BQP能否包括PH中没有的题目。PH代表“多项式条理结构”,是NP的泛化,这意味着PH包括经过度层限制语句(比如“那边有”和“一切人”)使NP题目加倍复杂的一切题目。当前的典范计较机没法处理大大都的PH题目,但假如P即是NP,PH就是典范计较机可以处理的那一类题目。换句话说,比力BQP和PH是为了肯定量子计较机能否比典范计较机更具上风,即使典范计较机今后可以(出人料想地)处理比现在更多很多的题目。
量子计较机有多利害?今朝已知有一个题目是只要它能处理的-3.jpg

“PH是最根基的典范复杂性类之一。”得克萨斯大学奥斯汀分校计较机科学家斯科特·阿伦森(Scott Aaronson)说,“是以,我们想晓得,量子计较在典范复杂性理论的天下里处于什么位置?”

区分两个复杂性类的最好方式,是找到一个可证实属于其中一类但不属于另一类的题目。但由于根本性和技术性障碍,很难找到这样一个题目。

假如想找到一个属于BQP但不属于PH的题目,必须先找到一个“典范计较机没法有用考证答案,更别说得出答案”的题目。阿伦森说:“这解除了计较机科学家想到的很多题目。”

BQP还是PH?

假定你有两个随机数天生器,每个会天生一串数字。你向计较机提出的题目是:这两串数字是相互完全自力,还是存在隐藏关联(一串数字是另一串数字的“傅里叶变更”)?阿伦森在2009年提出了这个“傅换关联”(forrelation)题目,并证实它属于BQP。然后是加倍困难的第二步——证实傅换关联题目不属于PH。
量子计较机有多利害?今朝已知有一个题目是只要它能处理的-4.jpg
普林斯顿大学理论计较机科学家冉·拉兹找到了区分两个计较类的方式



从某种意义上来说,这就是拉兹和塔尔所做的事。他们的论文实现了BQP和PH的“Oracle”(大概说“黑匣子”)分手。这是计较机科学范畴里的一种常见成果。假如研讨职员想要证实的工具超越了他们力所能及的范围之外,他们便乞助于“Oracle”。

区分BQP和PH等复杂性类的最好方式,是权衡处理题目所需的计较时候。但多伦多大学计较机科学家亨利·袁(Henry Yuen)说,计较机科学家“对实在的计较时候缺少深入的领会,也没有才能去权衡。”

是以,计较机科学家权衡其他目标,希望借此洞悉他们没法权衡的计较时候。他们算出计较机询问“Oracle”以获得答案所需的时候。Oracle就像暗示者,你不晓得祂是若何得出暗示的,但你晓得暗示是可信的。

假如你的题目是弄清楚两个随机数天生器能否存在隐藏关联,你可以问Oracle“每个天生器的第六个数字是什么?”然后,你按照每一类计较机处理这个题目所需的暗示数目,来比力它们的计较才能。计较机需要的暗示越多,速度就越慢。

“从某种意义上讲,我们更领会这类形式。它更多地是关于信息而非计较。”塔尔说。
量子计较机有多利害?今朝已知有一个题目是只要它能处理的-5.jpg
斯坦福大学理论计较机科学家阿维沙伊·塔尔操纵“Oracle”分手来区分BQP和PH



拉兹和塔尔的新论文证实,量子计较机处理傅换关联题目所需的暗示数目远远少于典范计较机。究竟上,量子计较机只需要一个暗示,而PH算法哪怕获得无数的暗示,也处理不了这个题目。“这意味着量子算法可以很是有用地处理阿谁题目,”拉兹说,“但假如只斟酌典范算法,哪怕是很是高级的典范算法也不可。”是以,傅换关联题目属于BQP,但不属于PH。

拉兹和塔尔在差不多四年前就快要得出这一成果,但他们那时没法完成其证实进程的最初一步。未几前,塔尔看到了一篇关于伪随机数列天生器的论文。他意想到,那篇论文中谈到的方式恰好可以帮助他和拉兹完成他们自己的论文。“这是缺失的一环,”塔尔说。

BQP和PH被分手的消息敏捷传布。在拉兹和塔尔颁发其论文的第二天,佐治亚理工学院计较机科学家兰斯·福特诺(Lance Fortnow)写道:“量子复杂性天下颤动了。”

这篇论文有力地证实,量子计较机存在于一个跟典范计较机分歧的计较范畴(最少在触及神谕的题目上)。拉兹和塔尔的论文证实,即即是在P即是NP的情况下,有些题目照旧只要量子计较机才能处理。

福特诺说:“即使P即是NP,哪怕有了这个强假定,也不敷以把握量子计较。”

翻译:于波

校订:李莉

编辑:漫倩

来历:Quanta Magazine

培养:剧院式的线下演讲平台,发现最有缔造力的思惟

点击蓝字“领会更多”,获得更多「培养」出色内容


        原文章作者:培养,转载或内容合作请点击 转载说明 ,违规转载法令必究。追求报道,请 点击这里
Weiot(威腾网)是一家以原创内容、高端活动与全产业渠道为核心的垂直类物联网产业媒体。
回复

使用道具 举报

精彩评论20

芰二 发表于 2020-1-13 16:14:20 | 显示全部楼层
这样说吧 量子计算机可以预测一百年后某天下午两点半的天空云彩分布情况
Weiot(威腾网)是一家以原创内容、高端活动与全产业渠道为核心的垂直类物联网产业媒体。
回复 支持 反对

使用道具 举报

癌忆筏 发表于 2020-1-13 16:17:16 | 显示全部楼层
懵逼山上懵逼树,懵逼树下,你和我
Weiot(威腾网)是一家以原创内容、高端活动与全产业渠道为核心的垂直类物联网产业媒体。
回复 支持 反对

使用道具 举报

崎溜 发表于 2020-1-13 16:19:34 | 显示全部楼层
记得可以比喻成走迷宫,像经典计算机,在破解一个迷宫,它只有一条条的去尝试,若此路不成,则重走再次尝试。而对于量子计算机,在走迷宫,可一次性解出并“分身”完成所有可能,最快时间解出,找到终点。所以说对于经典的密码,经典计算机无法破解的,量子计算机能迅速破解,因此一旦实际运用,将会引发某些技术上的革命,所有密码再怎么加密都会一键破解了,会引发某些风险与危机。
Weiot(威腾网)是一家以原创内容、高端活动与全产业渠道为核心的垂直类物联网产业媒体。
回复 支持 反对

使用道具 举报

祖饺 发表于 2020-1-13 16:21:36 | 显示全部楼层
说了一大堆感觉很牛逼的样子,那就算出来明天的双色是哪几个数我就服!
Weiot(威腾网)是一家以原创内容、高端活动与全产业渠道为核心的垂直类物联网产业媒体。
回复 支持 反对

使用道具 举报

贾丝雨 发表于 2020-1-13 16:23:57 | 显示全部楼层
幼儿园的我硬是看完了
Weiot(威腾网)是一家以原创内容、高端活动与全产业渠道为核心的垂直类物联网产业媒体。
回复 支持 反对

使用道具 举报

牝摧罔 发表于 2020-1-13 16:26:06 | 显示全部楼层
说了半天,也没说清楚到底是个啥问题
Weiot(威腾网)是一家以原创内容、高端活动与全产业渠道为核心的垂直类物联网产业媒体。
回复 支持 反对

使用道具 举报

倡膳昀 发表于 2020-1-13 16:28:13 | 显示全部楼层
看完了,然而根本不知道在说什么,
Weiot(威腾网)是一家以原创内容、高端活动与全产业渠道为核心的垂直类物联网产业媒体。
回复 支持 反对

使用道具 举报

帕昆 发表于 2020-1-13 16:31:25 | 显示全部楼层
一脸懵逼的进来,直接划拉到底看评论[捂脸]
Weiot(威腾网)是一家以原创内容、高端活动与全产业渠道为核心的垂直类物联网产业媒体。
回复 支持 反对

使用道具 举报

红茜茜 发表于 2020-1-13 16:33:32 | 显示全部楼层
字我都认识,就是组合一起我就不知道说的什么玩意儿[捂脸][捂脸][捂脸]
Weiot(威腾网)是一家以原创内容、高端活动与全产业渠道为核心的垂直类物联网产业媒体。
回复 支持 反对

使用道具 举报

Weiot(威腾网)是一家以原创内容、高端活动与全产业渠道为核心的垂直类物联网产业媒体。我们关注新兴创新的物联网领域,提供有价值的报道和服务,连接物联网创业者和各种渠道资源,助力物联网产业化升级。
15201069869
关注我们
  • 访问移动手机版
  • 官方微信公众号

© 2014-2020 Weiot.NET 威腾网 北京微物联信息技术有限公司 ( 京ICP备20000381号-1 )