罗纳德·德·沃尔夫谈量子计算

||对话

罗纳德·沃尔夫肖像画罗纳德·德沃尔夫他是CWI的高级研究员和亚博体育官网阿姆斯特丹大学的兼职全职教授。他在2001年获得了博士学位,论文的主题是量子计算和通信复杂性哈利Buhrman保罗Vitanyi.后来他在加州大学伯克利分校做博士后。他的科学兴趣包括量子计算、复杂性理论和学习理论。

他还拥有哲学硕士学位(他的论文是关于柯尔莫戈罗夫复杂性和奥卡姆剃刀),并喜欢古典音乐和文学。

路加福音Muehlhauser在我们谈到量子计算之前,让我问你一个关于哲学的问题。在其他话题中,你的硕士论文讨论计算学习理论与哲学辩论的相关性奥卡姆剃刀这一原则主张“在与事实相一致的理论、假设或解释中,我们应该选择更简单的而不是更复杂的。”

尽管许多哲学家和科学家坚持奥卡姆剃须刀原则,但“更简单”到底是什么意思,以及为什么这一原则在一开始是合理的,常常是模棱两可的。但在你的论文中,你写道,“在某些正式场合,我们或多或少,证明《奥卡姆剃刀》的某些版本的作品。”

当我为哲学家们辩护时,他们通常是持怀疑态度的K-complexity奥卡姆剃刀的版本,和你一样。例如,南加州大学的肯尼·伊斯瓦兰曾经写道,“我从来没有见过(基于k复杂度的简单性度量)是如何解决任何问题的,因为它总是取决于对通用机器的选择。”

鉴于你对奥卡姆剃刀“在某些正式场合”的合理性持乐观态度,你将如何回答?


罗纳德·德沃尔夫我更愿意把奥卡姆剃须刀当作一个经验法则,而不是一个正式的法则或定理。很明显,它是模糊的,很明显,在某些情况下,它是行不通的。尽管如此,许多科学家还是被它引导到好的效果上,经常把简单等同于美丽(例如爱因斯坦和狄拉克)。从心理学上讲,只有在存在一些共同的简单概念时,调用Occam才会有效;也许不能量化简单性,但至少可以根据简单性对理论进行排序。

您可以尝试使用Kolmogorov复杂性作为简单性的“客观”度量,在一些简化的情况下,这是非常有意义的。在我的硕士论文中,我调查了几个已知的案例,证明这一点。然而,这些案例并没有提供“现实世界”奥卡姆剃刀的令人信服的证据。它们更像是思维实验,为了更清楚地提出某个观点,你要去掉所有多余的东西。

在实践中,使用Kolmogorov复杂度来衡量简单性至少存在三个问题。首先,它要求你在一些固定的字母表上写下你的理论(或任何你要量化的简单性的理论),比如一串比特。将背景假设作为理论的一部分通常是很主观的。第二,正如Easwaran所说的,KC取决于通用图灵机w.r.t.的选择,这是它定义的。然而,我不认为这是一个大问题。如果选择某种比较高效的通用图灵机,考虑到比较长串的KC,选择通用图灵机所产生的常数差就会比较小。第三,可能也是最重要的一点,KC是不可计算的,甚至不能通过任何计算过程(即使是一个非常慢的计算过程)来逼近。这就排除了在实际设置中使用KC本身。

然而,压缩在某种程度上对应于数据中的模式检测的核心思想是完全有效的,如果您愿意将“压缩”建立在不完美但实用的程序(如gzip)的基础上,那么您可以在实践中使用它。这失去了KC所保证的理论上的最优性(您可以将其视为“最终压缩”),但它为您提供了一个用于数据挖掘和聚类的工具,在实践中通常是相当不错的。看到例如在这里.这种实用的方法就像试探法,试图接近KC的理想但无法达到的极限情况,在某种微弱的意义上。


路加福音:你认为人们可以使用类似occam的原则来选择,例如,各种各样的量子力学解释因为它们对我们应该观察到的东西做出了本质上相同的预测?


罗纳德。原则上你可以,但根据我有限的理解(我没有密切关注这场辩论),QM的主要解释都有一些看似多余的方面。标准的解释是,一个测量“使波函数崩溃”为一个概率选择的测量结果,将“观察者”视为量子物体的一个特殊类别,或将“观察/测量”视为量子过程的一个特殊类别。在你意识到之前,人们将意识带入画面,神秘主义在召唤。在我看来,把“观察者”当作一个特殊的范畴,违反了奥卡姆的剃刀原则。或者你也可以认为测量并没有什么特别之处,只是量子系统(观察者和被观察者)之间的另一种相互作用。亚博体育苹果app官方下载这有时被称为“更大希尔伯特空间的教堂”。这在数学上是令人满意的,因为现在整个宇宙只有这种平滑的,连贯的,甚至是确定性的进化。然而,现在您将拥有叠加的不同“分支”,即世界的状态向量,这将很快导致许多世界的多元宇宙视图。一种假设无限多个世界存在于叠加状态的形而上学也不太符合occam。

然后是“闭嘴,计算”的乐器派。从occam愉悦的意义上来说,这是极简主义的,但似乎在实质上削弱了科学努力,其目标不仅应该是预测,还应该是解释和给出世界的一些图片。所有对QM的解释都有其自身的问题,根据奥卡姆的剃刀在两者之间进行选择,都假设了一些关于什么是简单性的共同观点以及对科学目标的共同看法,而这些似乎是我们在这里所缺乏的。


路加福音你现在的大部分工作都是在量子计算和通信领域。量子计算是一个有趣的领域,因为它的研究人员为尚未建成的机器设计算法、纠错技术等。亚博体育官网在这个意义上,我倾向于认为量子计算是一个“勘探工程学科,类似于前苏联卫星航天、前eniac计算机科学和埃里克·德雷克斯勒的纳米系统亚博体育苹果app官方下载.你觉得这样描述公平吗?你和你在量子计算领域的同事们是否因为这样的工作“过于投机”而受到很多批评?(郑重声明,那不是我的视图)。


罗纳德。当前位置量子计算的两个主要问题是:(1)我们能否建造一台大规模的量子计算机;(2)如果我们有一台量子计算机,它能做什么。我认为你的术语“探索性工程”适用于第一个问题;十年前,在几个量子位元上的小型量子计算机已经建成,所以它不再是纯粹的理论。我本人是一个专注于第二个问题的理论计算机科学家。虽然我认为这更多的是数学而不是工程,你当然可以把它与20世纪30年代的计算机科学相比较:在那个时候,(经典的)计算机的理论模型已经由艾伦·图灵引入,但还没有大规模的计算机建成。你已经可以在纸上为图灵机设计算法,你甚至可以证明这样的计算机可以解决某些问题(就像图灵解决停机问题时所做的那样)。我们现在正在量子计算方面做这样的工作:设计量子算法和通信协议,在一些计算问题上比经典问题快得多,另一方面,证明量子计算机在许多其他问题上不能给你加速。当然,这在很大程度上的相关性取决于大型QC的最终构建。然而,有趣的是,我们正在做的一些工作对经典计算的分析具有附带意义,而这与今天构建QC的进展无关。

关于可能的“投机”:在1990年代中期,彼得·肖之后发表了开创性的量子算法考虑到大量主要因素(减免很多加密),有很多怀疑,尤其是物理学家认为这永远不会飞。他们预计,任何实现量子比特和操作的尝试都会有大量的噪音和错误,很快就会被解调到经典计算机中。当然,他们有充分的理由对此表示怀疑——操纵像电子这么小的东西是极其困难的,比在20世纪40年代和50年代操纵真空管要困难得多。对噪声和缺陷的担忧很快就被量子纠错和容错计算的开发(部分是由肖尔自己开发的)部分地解决了。量子纠错和容错计算粗略地说,如果噪声不是太大,也不是太恶意,你的量子计算机可以纠正它。要完全克服这些担忧,唯一的方法就是建立一个大规模的QC。我的印象是,实验物理学家在这方面取得了缓慢但肯定的进展,随着时间的推移,他们变得越来越乐观,认为这将在一二十年内实现。所以,这当然是一种推测性的努力(大多数长期研究都是),但也不是没有道理的。亚博体育官网


路加福音:考虑到QC的长期性和投机性,您和您在量子计算领域的同事使用了什么启发法来决定要做什么?大概你需要做出不确定的预测,哪些类型的量子计算机最有可能被建造,已知障碍的解决方案可能是什么样的,等等?(我之所以这么问,是因为MIRI的目标是进行长期研究亚博体育官网更多的比量子计算还投机。)


罗纳德。:大多数时候,我们研究量子计算机解决经典计算问题的能力,计算机科学在过去的几十年里一直在定义和研究许多有趣和有用的计算问题和模型的复杂性,我们经常从那里开始:我们采取一个现有的计算问题,并试图找到量子技巧,以改进最好的经典解决方案。在某些情况下,我们成功地设计出了超越经典计算机的量子方法,在某些情况下,我们可以证明QC不能比经典计算机做得更好。当然,很难预测哪些量子技巧(如果有的话)可能有助于解决特定的问题,但我们有一些通用的工具可供选择。例如,量子计算机擅长检测周期模式(这是肖尔算法的核心);搜索速度更快(格罗弗算法);你可以通过将信息编码到一个未知的基础(量子密码)来隐藏信息;你可以在一个n-量子位空间中封装一个双指数数量的量子态(量子指纹),等等。 A lot of work is based on skillfully combining and applying such known quantum tools, and once in a while people find new tricks to add to our toolbox. Of course, there is also work of a more specific quantum nature, which is not just throwing quantum tricks at classical problems. For example, a lot of work has been done recently on testing whether given quantum states are properly entangled (and hence can be used, for instance, in quantum cryptography).

我们通常从将实现量子计算机的具体物理系统的细节中抽象化。亚博体育苹果app官方下载相反,我们只关注数学模型,使用量子比特和一组定义良好的基本操作(“门”),我们可以对它们执行。无所谓是否实现为量子比特电子自旋,或作为光子偏振,或作为一个原子的能量水平,从模型的角度来看,它只有很重要,一个量子位定义良好的0和1的状态,我们可以形成叠加。同样,对于传统计算机来说,用C语言、Java语言或汇编语言编程并不重要;所有这些编程语言都可以有效地相互模拟。而且,您不必关心物理上用于实现位的精确电压,只要每个位具有稳定且清晰区分的0和1值。

当我们有一个大规模的量子计算机时,抽象这样的实现细节是合理的,因为不同种类的量子计算机将能够相互模拟,而只需要适当的额外的量子位和操作的开销。例如,为了设计量子算法,假设你可以交互任何一对量子位元是很方便的,即使它们相距很远;在现实的物理实验中,只允许量子位之间最近邻的相互作用要简单得多。我们可以为第一个模型设计算法,然后通过插入一些交换操作将相互作用的量子位移到一起,在最近邻模型中实现它们。然而,只要我们还没有一个大规模的量子计算机,这种“适度的开销”实际上是相当重要的。很有可能,在迈向大型QC的缓慢道路上,我们将首先拥有几十或几百个量子位的QC(目前的技术水平是几个量子位)。在这种情况下,我们不能太浪费,也许应该为特定的物理实现设计优化算法。发现一个50或100量子位的QC已经在某些显著的方面优于传统计算机的问题实际上是一个非常有趣的问题。这些问题将成为测试中型qc的基准。

关键是,一旦你有大量可用的量子位,不同的物理实现/架构之间的差异就不太重要了,因为它们都等价于小的开销(需要用另一个来模拟一种变体)。但是,当我们只有中等大小的qc可用时(比如,几十个或几百个量子位),这些开销确实会造成很大的不同,我们需要仔细优化我们的量子算法,以便在实际可用的特定物理实现上执行。在这方面,量子计算似乎与大多数未来技术截然不同:在某种程度上,我们能够更好地预测这项技术的长期威力(当我们有一个大规模的QC可用时,基本上可以忽略实现细节),而不是短期和中期(虽然我们只有带有古怪限制的小规模QC)。


路加福音我的下一个问题从量子计算跳到技术预测。你认为我们会有一台500量子位量子计算机的主观概率是多少毫无争议量子计算机,在未来20年内?对于这样的问题,你是如何推理的呢?


罗纳德。相当高,假设概率大于2/3。这是典型的计算机科学“有界错误”算法的阈值。从理论的角度来看,我认为我们不知道构建大规模QC的任何基本障碍,而容错QC的阈值定理保证我们可以处理适度数量的噪声和错误。显然,建立QC是一个极其困难的工程问题,但我的印象是,实验人员正在取得缓慢但肯定的进展。这里有三种可能的情况:

  1. 有人构建了一个大型QC
  2. 我们发现了量子力学的一个基本问题(这将是非常有趣的新物理!)
  3. 实验主义者在没有取得太大进展的情况下蒙混过关,直到他们或者资助机构失去信心并放弃。

在我看来,第一种情况似乎是最合理的。我应该说我不是一个认证的物理学家,更别说是一个认证的实验物理学家,所以这个观点是部分基于道听途说,但我确实有一些进步的信心在麻省理工学院,NIST,耶鲁,代尔夫特,……你最近的论文引用怀疑有争议的递波量子计算机,已经很多媒体在过去的几年里。出于商业原因,他们将数量(可用量子位的数量)置于质量(这些量子位的一致性和“真正的量子本质”)之上,而且他们的机器似乎太吵了,无法拥有有用的量子计算能力。


路加福音这是否意味着我们可能需要清除地球上的-可破解密码安全,并过渡到post-quantum密码学,在20年内?


罗纳德。我认为这将是一个明智的预防措施,至少对于重要或敏感的数据。至少有两种方法可以解决这个问题。我们可以坚持使用公钥密码学,但将诸如因式分解和离散日志等可突破的问题替换为即使对QC来说似乎也难以破解的问题;格点问题是经常提到的候选者。或者我们可以用量子密码学。这两种方法都不如RSA有效,但至少它们更安全。现在开始这种转变已经是有道理的,尽管还没有质量控制:安全服务(谁知道呢,也许黑手党)可能是吸收RSA-encrypted通讯暂时储存,等待质检,让他们以后对这些消息进行解密。因此,即使是今天的沟通,未来的QC也不安全。


路加福音:谢谢,罗纳德·!