科学网—计算机科学里程碑式的证明波及物理与数学
精选
已有 4877 次阅读
2024-11-30 09:36
| 个人分类: 量子计算 | 系统分类: 科研笔记
计算机科学里程碑式的证明波及物理与数学
计算机科学家们在可计算式验证的知识方面拓展了新的疆域。在此过程中，他们解决了量子力学与纯数学中的重大未解难题。
Kevin Harnett 著
左 芬 译
【 译者按：在过去几年里，量子信息领域出现了两次重大突破。其一，通过对基于扩展图的经典LDPC码进行巧妙的乘积操作，得到了性能良好的量子LDPC码，并在此过程中解决了经典编码中的c 3 猜想。好的量子LDPC码的出现极有可能改变量子计算机硬件路线的当前格局，并将对量子物质相的研究产生深远影响。关于（量子）LDPC码的内容我们在前面的译文中已经陆续介绍过。
其二，在Bell实验基础上发展起来的“非定域游戏”被引入到复杂度理论的交互式证明中，并极大地拓展了多方交互式可验证问题的范围。简而言之，在量子纠缠的辅助下，我们现在甚至能验证停机问题！相信Turing若重生，也会对此惊讶不已。在此过程中，物理学中关于纠缠模型的Tsirelson论断与数学中关于算子代数的Connes嵌入猜想被否定。
这篇文章介绍了量子纠缠是如何大幅提升交互式证明的能力的。在此翻译出来，供大家参考。原文2020年4月8日刊载于QuantaMagazine，链接见文末。 】
计算机科学中的一个新证明也影响了量子力学和纯数学的研究者。
1935 年，Albert Einstein与Boris Podolsky、Nathan Rosen共同提出了由量子物理的新定律揭示的一种可能性：两个粒子无论相隔多远，也能相互纠缠或者关联。
就在第二年，Alan Turing首次表述了计算的一般性理论，并证明存在计算机永远无法解决的问题。
“这两种思想来自同一时期。它们以这种戏剧性的方式再次一同回归真的是太棒了。”
—— Henry Yuen, 多伦多大学
这两种思想革新了它们各自的领域。看起来它们彼此毫不相干。但如今一个里程碑式的证明将它们结合在一起，同时解决了计算机科学，物理与数学中的大量未解难题。
新证明证实，使用纠缠量子比特/量子位，而不是经典的1和0，进行计算的量子计算机理论上可以用于验证极其庞大的问题集合的答案。纠缠与计算之间的对应震惊了众多研究者。
“完全出人意料，”在维也纳市量子光学与量子信息研究所研究量子物理的Miguel Navascués称。
该证明的作者们最初想要确定一种方法在验证计算类问题的答案上的极限。这种方法涉及了纠缠。通过找出这一极限，他们最终还附带式地解决了另外两个问题：物理中关于如何数学建模纠缠的Tsirelson难题，以及纯数学中被称为Connes嵌入猜想的相关问题。
最终，结果像多米诺骨牌一般倾泻而下。
“这两种思想来自同一时期。它们以这种戏剧性的方式再次一同回归真的是太棒了。”证明的作者之一，多伦多大学的Henry Yuen说道。共同作者还包括悉尼科技大学的季铮锋，加州理工学院的Anand Natarajan与Thomas Vidick，以及德州大学奥斯汀分校的John Wright。五位研究者全都是计算机科学家。
不可判定问题
“你等了一百万年，程序还没终止。是不是得等到两百万年呢？这可不好说。”
—— William Slofstra, 滑铁卢大学
在计算机真正出现之前，Turing就定义了关于计算的基本框架。与此同时，他说明存在某种问题，可以证明计算机是无法处理的。这跟一个程序是否会终止有关。
通常地，计算机程序接收输入，并产生输出。但有些时候，它们陷入了无限循环，永不停歇地运行着。如果发生了这种事，就只能关机了。
“你只能手动终止程序。把它关掉，”Yuen说。
Turing 证明，不存在万能算法可以判定一个程序会终止还是会永远运行下去。你只能运行程序来查明。
计算机科学家Henry Yuen，Thomas Vidick，季铮锋，Anand Natarajan与John Wright共同完成了关于验证计算类问题答案的一个证明，并最终解决了数学和量子物理中的重大问题。
“你等了一百万年，程序还没终止。是不是得等到两百万年呢？这可不好说，”滑铁卢大学数学家Willian Slofstra说。
用术语来说，Turing证明了这一停机问题是不可判定的——哪怕用你能想象出来的最强大的计算机也无法解决它。
在Turing之后，计算机科学家开始按困难程度分类其它问题。更难的问题需要更多的计算资源去解决——更多的运行时间，更多的存储。这就是计算复杂度的研究内容。
最终，每一个难题都带来两个问题：“求解它有多难？”以及“验证一个答案是对的有多难？”
讯问式验证
当问题相对简单时，你可以自己检验答案。可当它们越来越复杂时，哪怕检验答案也变得不堪重负。不过，计算机科学家们在1985年意识到，哪怕你不能自己确认，仍可以就一个答案的正确性建立信心。
这一方法遵循了警察的讯问逻辑。
如果嫌疑人编造了一个精巧的故事，可能你无法在现实中确认每一个细节。但通过问适当的问题，你可以揪出嫌疑人的谎言，或者对故事属实建立信心。
用计算机科学术语来说，讯问中的两方分别是给出问题答案的强力计算机，也就是证明者，与想要通过问证明者问题来判定答案是否正确的不那么强大的计算机。第二台计算机被称为验证者。
举一个简单的例子，假设你是色盲，而另一个人——证明者——声称两颗弹珠具有不同颜色。你没法自己检验这一论断，但通过巧妙的讯问还是可以判定它是否是真的。
把两颗弹珠放到背后，混起来。接着拿出来让证明者告诉你是哪颗。如果它们颜色不同，证明者每次都能给出正确答案。如果弹珠其实颜色相同——意味着它们看起来完全一样——证明者有一半的时候会猜错。
“如果我发现你在远远超过一半的时候对了，我相当确定它们是不同的”颜色，Vidick说道。
通过问适当的问题，你可以验证一大类问题的答案，远远超过亲自动手的。
1988 年，计算机科学家开始考虑如果两个证明者给出同一问题的答案会发生什么。毕竟，如果你有两个嫌疑人可以讯问，查清一桩案子或者验证一个答案总归容易得多，因为你可以让他们相互对抗。
“它给予了验证者更多手段。你分别讯问，问相关联的问题，然后交叉验证答案。”Vidick说道。如果嫌疑人说的是实话，他们的回答大多数时候都会是一致的。可如果他们说谎，答案会经常相悖。
类似地，研究者证明，通过分别讯问两个证明者，你可以快速验证
更大类别问题的答案，比你只有一个证明者可以讯问时大得多。
计算复杂度可能看起来完全是理论上的，但它也跟现实世界紧密相关。计算机用来求解和验证问题的资源——时间和存储——在根本上是物理的。基于这一原因，物理学上的新发现会改变计算复杂度。
“如果你选择不同层次的物理，比如用量子的替代经典的，你会从中得出不同的复杂度理论，”Natarajan说道。
新证明正是21世纪计算机科学家们在直面20世纪物理学最奇怪的概念之一——纠缠——后的最终结果。
Connes 嵌入猜想
当两个粒子纠缠时，它们其实并不相互影响——它们没有因果关联。Einstein和他的合作者在他们1935年的文章里阐明了这一思想。之后，物理学家和数学家们试图找到一个数学方法来刻画纠缠的真实涵义。
可是这一努力带来的结果有些混乱。科学家们提出了纠缠的两种不同数学模型——并且不清楚它们是否彼此等价。
以一种迂回的方式，这一潜在的不和谐后来引发了纯数学中被称为Connes嵌入猜想的一个重要问题。最终，它也成为了五位科学家在他们的新证明中加以利用的突破口。
一种建模纠缠的方法是把粒子想象成在空间上相互远离。比如说，一个在地球上，而另一个在火星上；它们之间的距离阻止了因果性。这被称为张量积模型。
可在有些情形下，两样事物是否彼此因果性远离并不十分明显。于是数学家们想出了第二种更一般地描述因果独立性的方法。
当你执行两个操作的顺序不影响结果时，这些操作“可对易”：3×2跟2×3一样。在这第二种模型里，说两个粒子是纠缠的，如果它们的性质相互关联并且与你执行测量的顺序无关。测量粒子A来预言粒子B的动量或者反过来，无论哪种方式，结果都一样。这被称为纠缠的对易算符模型。
两种纠缠的描述都使用了排成行和列的数组，也就是矩阵。张量积模型使用了只有有限行和列的矩阵。对易算符模型使用了一种更一般的对象，运作起来像是具有无限行和列的矩阵。
随着时间的推移，数学家们开始从他们自身的兴趣出发来研究这些矩阵，完全不考虑跟物理世界的任何关联。作为这类工作的一部分，数学家Alain Connes1976年猜想应该可以用有限维矩阵来近似很多无限维矩阵。这是Connes嵌入猜想的推论之一。
在之后的十年里，一个名叫Boris Tsirelson的物理学家给出了这一问题的另一个版本，让它重新扎根于物理学之中。Tsirelson猜想纠缠的张量积和对易算符模型大体上应该是等价的。这是说得通的，因为理论上它们是描述同一种物理现象的两种不同方式。后续的工作表明出于矩阵和使用它们的物理模型之间的这种关联，Connes嵌入猜想和Tsirelson问题彼此蕴涵：解决了一个，你就解决了另一个。
然而两个问题的答案最终全都出现在了另一个地方。
游戏物理
1960 年代，一个名叫John Bell的物理学家想到了一个测试，可以用来判定纠缠到底是一种真实物理现象，还是仅仅是一个理论概念。这一测试涉及一种游戏，其输出会揭示是否有超出常规非量子物理的某种东西在起作用。
计算机科学家后来意识到这一纠缠测试也可以作为工具来验证极其复杂问题的答案。
为了看出这些游戏如何运作的，首先我们给定两个玩家，Alice和Bob，以及一个3乘3的网格。一个裁判给Alice某一行，让她在每个格子里填0或1，使得数字加和是一个奇数。Bob则被指定了某一列，并且要让填的数字加起来是一个偶数。如果他们在行和列相交的格子里填了相同的数字，则获胜。但他们不允许交流。
在通常情形下，他们最多能有89%的机会获胜。但在量子情形下，他们可以做得更好。
假定Alice和Bob分享了一对纠缠粒子。他们对各自的粒子进行测量，并用结果来确定每个格子里该填1还是0。因为粒子是纠缠的，他们的测量结果也会是关联的，这意味着他们的答案也相关——也就意味着他们能100%赢得游戏。
量子游戏