当前位置
主页 > 产品中心 > 产品一类 >
‘华体会体育’这篇长达165页的论文,同时解决了量子物理学和理论数学的难题
2021-11-09 01:56
本文摘要:选自Quanta Magzine作者:Kevin Hartnett机械之心编译到场:Panda、蛋酱盘算机科学、数学、物理学,这三个学科各自的一些重浩劫题在克日公布的一篇标题简练的论文《MIP*=RE》中同时获得相识答。在该论文中,五位盘算机科学家为可通过盘算方式验证的知识确立了一个新的界限。 基于此,他们又为量子物理学和纯数学领域仍未获得解决的重浩劫题带去了谜底。

华体会体育

选自Quanta Magzine作者:Kevin Hartnett机械之心编译到场:Panda、蛋酱盘算机科学、数学、物理学,这三个学科各自的一些重浩劫题在克日公布的一篇标题简练的论文《MIP*=RE》中同时获得相识答。在该论文中,五位盘算机科学家为可通过盘算方式验证的知识确立了一个新的界限。

基于此,他们又为量子物理学和纯数学领域仍未获得解决的重浩劫题带去了谜底。这篇长达 165 页的论文所展现的研究结果,一经公布,就在学界引发了广泛的关注,《Nature》杂志也对此举行了先容。

原论文可会见:https://arxiv.org/abs/2001.04383。本文编译自 Quanta Magazine,以下内容是对该证明的详细解读:故事要从 80 多年前说起。1935 年,阿尔伯特·爱因斯坦与鲍里斯·波多尔斯基(Boris Podolsky)和纳森·罗森(Nathan Rosen)互助展现了一种可能性:纵然距离很远,两个粒子也可以发生纠缠或关联。就在接下来的一年里,阿兰·图灵(Alan Turing)提出了第一个通用盘算理论,他证明晰一件事:存在盘算机永远无法解决的问题。

这两个想法都为各自的学科领域带来了革命,而且它们看起来似乎并不相关。但现在,一个具有里程碑意义的证明泛起了,它将这两种想法联系在了一起,同时解决了盘算机科学、物理学和数学领域许多尚未解决的问题。

这个新证明就是:理论上,使用纠缠态量子比特(qubit)而非经典的 1 和 0 举行盘算的量子盘算机可用于验证很是多的问题的谜底。纠缠与盘算之间的这种对应关系震惊了许多研究者。这个证明的作者们原本是想确定一种用于验证盘算问题的谜底的方法局限性,这种方法涉及纠缠。找到谁人局限性之后,顺带解决了另外两个问题:物理学中的 Tsirelson 问题(关于如何用数学建模纠缠)以及纯数学领域的一个相关问题(科纳嵌入料想)。

最终,这些效果像多米诺骨牌一样级联到了一起。「这些思想都是同一时间泛起的。它们能以如此戏剧性的方式再次聚首,真是很不错。」该证明的作者之一多伦多大学的 Henry Yuen 说。

此外,该证明的作者另有悉尼科技大学的季铮锋(Zhengfeng Ji)、加州理工学院的 Anand Natarajan 和 Thomas Vidick 以及德克萨斯州大学奥斯汀分校的 John Wright。这五位研究者都是盘算机科学家。

不行定的问题在盘算机降生之前,图灵就已经为盘算方面的思考界说了一个基本框架。险些在同时,他也讲明始终存在某些盘算机无法解决的特定问题。这就是常说的「图灵停机问题」。

经典设计中,盘算机法式可以吸收输入并发生输出。但有时候,法式会进入无限的循环之中,不停地重复事情。如果你遇到了这种情况,那只能手动终止这个法式。

图灵证明晰,并不存在一个通用算法,可以确定一个盘算机法式将停止还是永远运行。谜底必须在运行这个法式后才气知道。

盘算机科学家 Henry Yuen、Thomas Vidick、Zhengfeng Ji、Anand Natarajan 和 John Wright 互助证明晰一个验证盘算问题的谜底的问题,却最终为数学和量子物理学领域的重大问题提供相识答。「如果你已经等候了 100 万年而一个法式还未停止,你需要等候 200 万年吗?没措施知道谜底。

」滑铁卢大学数学家 William Slofstra 说。用技术术语来说,图灵证明这个停止问题是不行定的(undecidable)——甚至可想象的最强大的盘算机也无力解决。图灵之后,盘算机科学家开始凭据难度来对其它问题举行分类。

要解决更难的问题,所需的盘算资源也更多,也就是说需要更多运行时间、更多内存。这些属于盘算庞大性问题。

最终而言,每个问题的求解都涉及到两个重大问题:「这个问题的解决难度有多大?」和「验证谜底正确的难度有多大?」审问式验证当问题相对简朴时,判断谜底正确与否也很简朴。但问题变得越发庞大时,就很难直接判断了。但就算无法确认,你也能知道谜底到底对差池。

此处就要提到「审问式验证」了。这个方法跟警员审问的逻辑差不多:如果一个嫌犯讲的故事是经心编造的,那你可能没措施去验证每一处细节。

但只需要针对这个故事提出一些问题,你就可以知道嫌犯是在说谎,还是在如实陈述。套用到盘算机科学术语上说,「审问」的双方划分是一台强大的盘算机和一台更弱的盘算机。其中强大的盘算机(证明者)给出了一个解,较弱的盘算机(验证者)则希望通过提问来确定该解是否正确。

举个简朴的例子,假设你是一个色盲,另一小我私家(证明者)称两颗弹珠颜色差别。你要怎么验证他说的是不是真的呢?你可以把这两颗弹珠拿到身后混在一起,再拿出来让证明者区分它们。如果它们颜色真的差别,那么证明者应该每一次都能给出正确的谜底。

如果这两颗弹珠实际上颜色一样,那么证明者有一半的可能会猜错(就算凌驾半数的时间能说对,那也能肯定颜色纷歧样了)。这种方法还可以验证大量差别种别问题的解。以此推之,当两个证明者针对同一个问题都给出解时,验证速度会变得更快。就好比,你要审问的嫌犯如果有两个,解决一个犯罪案件就会越发轻松,因为你可以交织磨练他们的谜底。

如果这些嫌犯讲的是实话,那么他们所说的大多都对得上。如果他们在说谎,那么更多时候会泛起相互矛盾的谜底。

盘算庞大性可能看起来完全是理论方面的问题,但其实也与真实世界联系很精密。在求解和验证问题的历程中,盘算机需要时间和内存资源,本质上这是物理问题。

因此物理学领域的新发现会影响到盘算庞大性。Natarajan 说:「如果你选择了量子物理学而不是经典物理学,那么你会获得差别的庞大性理论。」这是 21 世纪的盘算机科学家们,面临 20 世纪物理学中最离奇的纠缠思想,获得的最终效果。突破口:科纳嵌入料想当两个粒子相互纠缠时,实际上并不会相互影响——它们之间不存在因果关系。

爱因斯坦与其互助者在 1935 年的论文中论述了这一思想。在那之后,物理学家和数学家都在努力想要通过数学的方式来形貌纠缠的真正寄义。可是努力的效果却有点杂乱,科学家们为纠缠构想出了两个差别的数学模型——而且之前并不清楚它们是否等效。

这种潜在的反面谐,最终给纯数学领域带来了一个重要问题,即科纳嵌入料想。最终,这成为了这五位盘算机科学家新证明中的突破口。第一种建模纠缠的方法将粒子视为在空间上是相互隔离的,好比一个在地球上,一个在火星上;故障两者之间因果关系的是它们之间的距离。

这被称为张量积模型,但在某些情况下,两个事物在因果关系上是否相互独立却并不很是显着。因此,数学家想出了另一种更通用的形貌因果独立性的方法。

当执行两个运算的顺序不影响效果时,则这两个运算满足交流律:3×2 和 2×3 是一样的。在第二种模型中,只要粒子的属性相互关联,则这些粒子即是相互纠缠的,但你执行观察的顺序无关紧要:观察粒子 A 来预测粒子 B 的动量或反过来,不管选用哪种顺序,获得的谜底都一样。这被称为交流算子式纠缠模型。这两种对纠缠的形貌都要用到按行列形式组织的数字阵列,即矩阵。

第一种张量积模型使用了行数和列数有限的矩阵,第二种交流算子模型使用一个更通用的工具,其事情方式就像是一个行数和列数无限的矩阵。随着时间的推移,数学家开始以研究这些矩阵为目的,完全与物理学世界脱离了联系。

除了这项研究之外,数学家 Alain Connes 在 1976 年提出了一个料想:有可能使用有限维矩阵来近似许多无限维矩阵。这是科纳嵌入料想暗含的效果之一。下一个十年,物理学家 Boris Tsirelson 提出了该问题的一个版本,再次将这个问题纳入了物理学研究中。

Tsirelson 料想张量积纠缠模型和交流算子式纠缠模型是大致等价的。这固然是合理的,因为是对同一物理现象的两种差别的理论形貌。后续的研究讲明,由于矩阵以及使用这些矩阵的物理模型之间所存在的关联性,科纳嵌入料想与 Tsirelson 问题实际上是相互暗含的。

解决了其中一个,你也就解决了另一个。然而,这两个问题的解最终都源自另外一个完全纷歧样的位置。博弈所体现的物理学1960 年月,物理学家约翰·贝尔(John Bell)提出了一种测试方法,可以确定纠缠究竟是真实的物理现象或只是一个理论观点。这种测试涉及到一种博弈,其效果可说明是否存在某种差别寻常的非量子物理学的工具。

厥后,盘算机科学家又意识到,这种测试纠缠的方法也可用于验证很是庞大的问题的谜底。为了相识这种博弈的事情方式,我们先假设有两个玩家 Alice 和 Bob 以及一个 3×3 的网格。裁判为 Alice 分配了一行,并告诉她在每个空格中输入一个 0 和 1,并使得数字之和为一个奇数。

Bob 则获得一列,他的填充方式要使得该列之和为一个偶数。如果他们在列与行的重叠区放的数字一样,则他们就获胜。同时不允许他们相互交流。在经典设置中,他们的最佳体现为 89% 的胜率。

但在量子设置中,他们可以做得更好。假设为 Alice 和 Bob 分配了一对相互纠缠的粒子。他们观察各自的粒子,然后使用观察效果来引导每个格子的数字填充。

由于这些粒子相互纠缠,所以他们的观察效果是相互关联的,也就意味着他们填入的谜底是相互关联的——进一步意味着他们的胜率可达 100%。图片来自:Lucy Reading-Ikkanda/Quanta Magazine所以如果两个玩家获胜的概率横跨预期,可以得出结论:他们使用了某种超出经典物理学之外的工具。这样的贝尔式实验现在被称为「非局部博弈(nonlocal game)」,因为玩家之间是离开的。物理学家在实验室中真正地执行了这样的实验。

hth华体会

Yuen 说:「多年来做实验的人已经讲明这样这种鬼魅般的事情确实存在。」在分析任何博弈时,你可能都想知道玩家如果竭尽全力地玩,在一场非局部博弈中的胜率是几多。

但在 2016 年时,William Slofstra 证明不存在用于盘算所有非局部博弈简直切最大胜率的通用算法。所以研究者就想:能不能至少做到近似求取最大获胜百分比?使用两个形貌纠缠的模型,盘算机科学家锁定了谜底。

在近似所有非局部博弈的最大胜率时,使用张量积模型的算法可确立一个下限,即最小值。另一个使用交流算子模型的算法可确立一个上限。

运行这些算法的时间越长,获得的谜底就会越精准。如果 Tsirelson 的预测是对的,这两个模型确实等价,那么这个上限与下限之间应当相距很近,最终收缩为单个值,这个值就是近似获得的最大胜率。

但如果 Tsirelon 的预测差池,那么这两个模型就不等价。Yuen 说:「那么上限和下限就一直相隔很远。」那么也就没有措施盘算非局部博弈的近似最大胜率了。

这五位研究者在他们的新研究中使用了这一问题:上限和下限能否收敛以及 Tsirelson 问题是否为真?目的是解决另一个问题:是否有可能验证一个盘算问题的谜底。纠缠所提供的资助2000 年月早期,盘算机科学家开始思考:如果审问两个共享了纠缠粒子对的证明者,可验证问题的规模又将如何变化?大多数人都料想纠缠倒霉于验证。

究竟如果两个嫌犯之间存在某种勾通谜底的方式,那么他们就更容易编造出一致连贯的口供。但最近几年,盘算机科学家已经意识到事实恰恰相反。通过审问共享了纠缠粒子的证明者,可验证问题的规模比没有纠缠时更广。

Vidick 说:「纠缠可以发生关联,你可能认为这能资助他们说谎或欺骗,但事实上你能把它酿成自己的优势。」怎么会这样?要明白这一点,你首先需要相识你可以通过这个交互式流程验证的大量问题。假设有一个图,由一组点(极点)和毗连这些点的线(边)组成,能否使用三种颜色给其中的极点涂色,使得任何一条边所毗连的两个极点的颜色都纷歧样?如果可以,那么这个图就是「三色可分的(three-colorable)」。

如果你交给一对纠缠的证明者一张很是大的图,而他们陈诉说这张图是三色可分的,那么你会疑问:是否存在验证他们谜底的方法?如果图很是大,那么直接检查效果是不行行的。可是,你可以向每个证明者提问,让他们告诉你两个相连极点中划分一个极点的颜色。如果他们陈诉的颜色纷歧致,而且每次提问的效果都是如此,那么你就能越来越相信这种三色涂色方案是可行的。但当图很是大时,这样的审问计谋也会失效,好比当边和极点的数量凌驾宇宙的原子数量时。

甚至称述一个详细问题(「告诉我 XYZ 极点的颜色」)的任务就超出你这个验证者的能力规模,因为用于命名各个极点所需的数据量凌驾了你事情内存所能容纳的极限。但纠缠可以让证明者自己想需要提出的问题。Wright 说:「验证者不必去盘算问题。验证者可以迫使证明者为其盘算问题。

」验证者想要证明者陈诉相连极点的颜色。如果这些极点不是相连的,那么这些问题的谜底与该图是否三色可分无关。换句话说,验证者想要证明者给出的问题是相关的。

一个证明者问的是有关极点 ABC 的情况,另一个证明者则问的是有关极点 XYZ 的情况。希望是这两个极点是相连的,不外这两个证明者都不知道相互想的是哪个极点。(就像 Alice 和 Bob 都希望在同一个方格中填入同样的数字,即便他们都不知道对方被要求填哪一列或行。)如果两个证明者完全靠自己想出了这些问题,那么就不行能迫使他们选择相连或相关的极点,也就没法让验证者验证他们的谜底。

但纠缠能提供这样的相关性。我们险些可以把所有任务都交给证明者,让它们自行选择问题。到该流程竣事时,每个证明者都陈诉一种颜色。

验证者检查它们是否一样。如果这个图是真正三色可分的,那么证明者永远不应陈诉同一种颜色。Yuen 说:「如果存在三种颜色,证明者可以说服你只有一种。

」事实证明,这个验证流程不外是非局部博弈的又一案例而已。如果证明者能说服你相信他们的解是正确的,那么该证明者便「获胜」。2012 年,Vidick 和 Tsuyoshi Ito 证明,有可能使用纠缠的证明者来执行种类广泛的非局部博弈,以验证问题的谜底,而且这些问题的数量至少与可通过审问两台经典盘算机验证谜底的问题数量一样多。

也就是说,使用纠缠的证明器与验证不冲突。去年,Natarajan 和 Wright 证明:与纠缠的证明者交互实际上可以扩展可以验证的问题的种别。

但那时盘算机科学家尚不清楚可用这种方式验证的所有问题种别。而现在,情况发生了变化。

一连串的结果这五位盘算机科学家在他们的新论文中证明,通过审问纠缠的证明者,可以验证无法求解的问题的谜底,包罗停机问题。Yuen 说:「这种模型的验证能力真的是超出了想象。」但停机问题是无法解决的。事实上,正是这种新提出的思想,有望为这一断言带来最终证明。

设想你将一个法式提供应了一对纠缠的证明者,想要它们告诉你这个法式是否会停止。你已经准备好通过一种非局部博弈来验证它们的谜底:这些证明者会生成问题,然后会凭据这些问题的谜底的协调性来「获胜」。如果该法式事实上会停止,则证明器的胜率应为 100%——类似于一个图确实三色可分的情况,纠缠的证明者不应该陈诉两个相连的节点的颜色一样。如果该法式不会停止,则证明者只能靠运气获胜——胜率为 50%。

这意味着如果某人要求你确定这个非局部博弈问题的一个详细实例的近似最大胜率,你首先需要解决这个停机问题。而解决这个停机问题是不行能的。这意味着为非局部博弈盘算近似最大胜率的问题是不行定的,就像停机问题一样。这又进一步意味着 Tsirelson 问题的谜底是「否」——这两个纠缠模型并不等价。

因为如果它们是等价的,那么你可以把上限和下限压到一起,盘算获得一个近似最大胜率。马德里康普顿斯大学的 David Pérez-García 说:「不行能存在这样一个算法,所以这两个模型肯定差别。」这篇新论文证明:通过与纠缠的量子证明者交互所能验证的问题种别(称为 MIP* 种别)其实就即是不难于停机问题的问题种别(称为 RE 种别)。

该论文的标题就简练明晰地说明晰这一点:「MIP* = RE」在证明这两个庞大性种别相等的历程中,盘算机科学家证明 Tsirelson 问题为假,而且由于之前的研究事情,也意味着科纳嵌入料想也为假。对于这些领域的研究者而言,回覆这些大问题的谜底竟然来自于盘算机科学领域一个看似不相关的证明,这着实让人惊讶。「如果我看到一篇论文说 MIP* = RE,我认为这和我的研究没关系。

」之前实验证明 Tsirelson 问题和科纳嵌入料想的研究者之一 Navascués 说,「对我来说,这完全就是一个惊喜。」量子物理学家和数学家刚开始消化吸收这个证明。

在这个新研究结果之前,数学家已经在思考能否用大型的有限维度矩阵来近似无限维度的矩阵。现在,由于科纳嵌入料想为假,他们知道这无法做到了。Slofstra 说:「他们的效果讲明这是不行能的。

」这些盘算机科学家并没有以回覆科纳嵌入料想为目的,因此,他们并不是解释他们最终解决的一个问题的最美人选。Natarajan 说:「我小我私家并不是一个数学家,我不是很是明白科纳嵌入料想的原始形式。」他与其互助者预测数学家将会把这个新效果转化成数学领域的语言。

在宣布这个证明的一篇博客文章中,Vidick 写道:「我怀疑最终不需要庞大性理论来获得纯数学的效果。」然而,现在研究者可以使用这个证明晰,探究之路就可以到此为止了。在凌驾 30 年的时间里,盘算机科学家一直想搞清楚交互式验证能让他们前进多远。现在,以一篇标题简朴的长论文,他们给出了谜底,也映照了图灵的思想。

「已往长时间的研究都想要知道使用两个纠缠的量子证明者的验证流程有多强大,」Natarajan 说,「现在我们知道它有多强大了。故事也就到此为止。」参考链接:https://www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/https://www.nature.com/articles/d41586-020-00120-6。


本文关键词:hth华体会,‘,华,体会,体育,’,这篇,长达,165页,的,论文

本文来源:华体会体育-www.zcdkj.com

联系方式

电话:067-534628942

传真:0480-307581252

邮箱:admin@zcdkj.com

地址:江苏省扬州市祁门县化复大楼1467号