我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:六合报码室 > 多项式时间 >

Scott Aaronson在Google的新量子计算论文上发表

归档日期:05-08       文本归类:多项式时间      文章编辑:爱尚语录

  2010年,一家名为D-Wave的加拿大公司宣布,它已开始生产所谓的世界上第一台商用量子计算机,这是基于麻省理工学院的理论工作。量子计算机承诺比传统计算机更快地解决一些问题 - 至少在一种情况下,指数级更快。2013年,包括谷歌和美国宇航局在内的一个财团购买了D-Wave的一台机器。

  多年来,评论家一直认为,目前还不清楚D-Wave机器是否真正利用量子现象来执行计算,如果是,它是否比传统计算机具有任何优势。但本周,一组谷歌研究人员发表了一篇论文,声称在他们的实验中,在他们的D-Wave机器上运行的量子算法比同类经典算法快1亿倍。

  斯科特阿伦森,电气工程和计算机科学系麻省理工学院的副教授,一直跟随d波的故事多年。麻省理工学院新闻要求他帮助理解谷歌研究人员的新论文。

  问:谷歌研究人员的论文主要关注两种算法:模拟退火和量子退火。这些是什么?

  答:模拟退火是目前使用的首要优化方法之一。它是在20世纪80年代早期通过与人们退火金属时发生的事情直接类比而发明的,这是一种具有70​​00年历史的技术。你加热金属,原子都随机摇晃,当你慢慢冷却它时,原子越来越有可能去某个能减少总能量的地方。

  在算法的情况下,无论对解决方案质量如何影响,您都会有一大堆位开始在0到0之间翻转。然后当你降低“温度”时,有点变得越来越不愿意以一种会使解决方案变得更糟的方式翻转,直到最后,当温度为零时,有点只会达到保持的值解决方案直接走下坡路 - 走向更好的解决方案。

  模拟退火的主要问题,或者与任何其他局部搜索方法相关的问题是,你可能陷入局部最优。如果你想要达到一些能量场景中的最低点,你可能会陷入当地最好的缝隙中,但你没有意识到在其他地方有一个低得多的山谷,如果你只是上升和搜索。模拟退火试图解决这个问题:当温度很高时,你有时会愿意上山。但是,如果有一个非常高的山丘,即使它是一个非常非常狭窄的山丘 - 只是想象它是一个从地面伸出的大穗 - 它可能会花费你指数的时间,直到你碰巧发生这么多的事情,你发生了克服那次飙升。

  在量子力学中,我们知道粒子可以穿过障碍物。(这是物理学家使用的语言,这有点误导。)Farhi,Goldstone和Gutmann撰写了一篇重要的2002年论文,所有人都在麻省理工学院,他们所展示的是如果你的障碍确实是如此高的薄尖峰,那么量子退火可以使您获得超过经典模拟退火的指数加速。经典退火将在该尖峰的基础上陷入指数时间,并且量子退火将在其上隧穿,并在多项式时间内降至全局最小值。

  答:在目前的D-Wave芯片模型中,有大约1000个量子比特[量子比特],但它们被组织成每个八个量子比特的簇。每个群集中的量子位彼此紧密连接,群集之间只有较弱的连接。我认为这是迄今为止量子隧道行为的最佳证据,至少在8位集群的水平上。

  在这些结果中,他们比模拟退火更有优势的主要方式是利用量子隧道 - 或任何与簇内所有量子位相关的东西 - 可以同时翻转每个簇内的所有位,而模拟退火将尝试逐个翻转位,然后看到这不是一个好主意,然后将它们全部翻转,并没有意识到通过翻转它们中的所有八个,你可以得到更好的东西。

  现在已经清楚地表明,无论D-Wave设备做什么,都可以通过这个8-bit的屏障。当然,这并不意味着你做的比你经典的更快。

  答:在计算机科学中,通常我们关心的是渐近加速:我们关心的是,“作为问题大小的函数,你的运行时间是多少?它是线性增长的吗?它是否以二次方式增长?“前面的常数 - 是否需要5N步?需要10N步吗? - 我们并不在乎。我们只关心它在N中是线性的。

  在Google论文中,他们讨论了两种经典算法,这些算法与D-Wave机器的渐近性能相匹配 - 其中一种算法胜过真实世界的性能。因此,除了模拟退火之外,还有两个经典算法是这个故事中的参与者。其中一个是量子蒙特卡罗,它实际上是一种经典的优化方法,但它是受量子力学启发的方法。

  在这篇新的Google论文中,他们说尽管量子蒙特卡罗具有相同的渐近性能,但对于D-Wave机器来说,常数更好。常数大约好1亿倍。

  我有两个很大的问题。第一个问题是进行比较的问题实例基本上是模拟D-Wave机器本身的问题。为此D-Wave机器设计这种专用硬件并尽可能快地完成了1.5亿美元。因此,从某种意义上说,这种专用硬件可以在经典计算机上为模拟自身的问题获得恒定因子加速并不奇怪。

  芯片中的量子位在此特定图形拓扑中进行组织。如果要解决实际上非常重要的优化问题,则需要以某种方式将其映射到该拓扑上。当你进行映射时总会有损失。这种损失似乎完全有可能扼杀恒定因素优势。

  但另一点是舞台上还有另一种经典算法,就是塞尔比算法,我认为这是我博客上首次公布的算法。它是一种本地搜索算法,但它能够确定量子比特被组织到这些聚类中。谷歌的论文发现,塞尔比的算法在经典计算机上运行,​​在他们测试的所有实例上都完全胜过D-Wave机器。

  如果我知道这八个量子比特形成一个簇,我应该把它们看作一个巨大的变量,那么我只是找到该变量的最佳设置,我就完成了。只有256 - 2到8个案例需要检查。你可以很快做到。

  如果簇是800位,那么你将无法做到这一点。另一方面,建立800个相互通信的量子比特是一个超级难以解决的工程问题。即使你确实[构建那些量子比特集群],量子退火也不能完全解决这个问题。

  请记住,当存在高而薄的势垒时,量子退火效果最好。当你使势垒更宽时,如果你有800比特的簇会发生,那么量子退火也会有问题。

  我们终于清楚地看到了D-Wave在10年,15年前制定的设计决策的逻辑结果,即“尽快获得尽可能多的量子比特”。不要真的担心他们的一生,关于他们的连贯性。不要担心错误纠正。不要担心解决我们在理论上确信存在量子加速的问题。“

  我认为他们采取了肮脏的方法,其他大多数人都试图采取干净的方法。当然,在清洁方法之前,脏方法可能会到达某个地方。在技​​术史上有许多先例,其中肮脏的方法获胜。但它尚未获胜。

  免责声明:本网站图片,文字之类版权申明,因为网站可以由注册用户自行上传图片或文字,本网站无法鉴别所上传图片或文字的知识版权,如果侵犯,请及时通知我们,本网站将在第一时间及时删除。

  Constantinos Daskalakis采用从理论计算机科学到博弈论的技术

  罗克韦尔柯林斯的接收卡用于通过实时M代码信号导航RQ-11B乌鸦无人机

  Trover拯救了宇宙将Justin Roiland的签名喜剧带到了PSVR

  Neya Systems的VERTI系统集成到K-MAX VTOL UAS中

本文链接:http://barstaffuk.com/duoxiangshishijian/324.html