罗纳德德沃尔夫在量子计算上

卢克·穆罕沃斯：在我们到达量子计算之前，让我问你哲学。在其他主题中，你的硕士论点讨论计算学习理论与哲学辩论的相关性奥卡姆剃刀，这是倡导“与事实一致的理论，假设或解释中的原则，我们更喜欢更简单的更复杂。”

虽然许多哲学家和科学家都坚持春天的原则，但它往往是暧昧的“更简单”的意思，以及为什么这一原则首先是合理的。但在您的论文中，您可以在某些正式设置中写下“我们可以，或多或少地，证明某些版本的潮流的工作。“

当我争辩时，哲学家通常是持怀疑态度的k复杂性当你这样做时，偶尔的剃刀版本。例如，USC的Kenny Easwaran一旦写道“我实际上从未见过如何[A-Complexity的简单测量]应该解决任何东西，因为它总是取决于普遍机器的选择。”

鉴于您对optimence的剃须刀“在某些正式的环境中”的乐观态度，您将如何回复？

罗纳德德沃尔夫：我会像经过拇指一样对待冬季的剃刀，而不是作为正式规则或定理。显然它是模糊的，显然存在它不起作用的情况。尽管如此，许多科学家们仍然是以良好的影响为指导，往往与美容（例如爱因斯坦和Dirac）等同于简单。心理上，如果有一些共同概念的简单概念，调用偶尔将是有效的;也许不是为了量化简单性，但至少能够根据自己的简单来排名理论。

您可以尝试使用Kolmogorov复杂性作为您的“客观”衡量的简单性，并且在一些简化的情况下，这是完美的意义。在我的MSC论文中，我调查了一些已知的案例，在那里它可被淘汰。然而，这种情况不会在“真实世界”中不提供令人信服的剃刀“证明”。他们更像是思想的实验，在那里你剥离了一切都是多余的，以便更清楚地带来一定程度。

在实践中，使用Kolmogorov复杂度来衡量简单性至少存在三个问题。首先，它要求你将你的理论(或任何你正在量化的简单性的理论)写在一些固定的字母上，比如一串比特。通常情况下，背景假设是你理论的一部分是很主观的。第二，正如伊斯瓦兰所说，KC取决于通用图灵机的选择。然而，我不认为这是一个大问题。如果您选择一些比较有效的通用图灵机，并考虑比较长的字符串的KC，那么选择通用图灵机所引起的常量差异将相对较小。第三，可能也是最重要的，KC是不可计算的，甚至不能通过任何具有近似保证的计算过程(即使是非常慢的计算过程)来近似。这排除了在实际设置中使用KC本身。

然而，压缩以某种方式的核心思想对应于您的数据中的模式的检测是一个完全有效的模式，如果您愿意在不完美的情况下基于“压缩”但是像GZIP这样的实用程序，则可以在实践中使用它。这损失了KC保证的理论最优性（您可以将其视为“终极压缩”），但它为您提供了一种数据挖掘和聚类的工具，通常在实践中常常很好。见图这里。这种实用方法就像试图接近的启发式，在一些弱道的意义上，理想但无法到达的kc案例。

卢基：您认为可以使用类似偶像的原则选择，例如各种各样的量子力学的解释，因为他们似乎与我们应该观察到的基本相同的预测？

罗纳德：原则上，你可以，但要对我有限的理解（我没有紧密遵循这场辩论），QM的主要解释都遭受了一些看似多余的方面。测量“将波浪函数塌陷”到概率中所选择的测量结果的标准解释将“观察者”视为量子物体的特殊类别，或“观察/测量”作为量子过程的特殊类别。在你知道之前，人们会把意识带入图片和神秘主义的招手。在我看来，将“观察者”视为特殊类别违反了冬季的剃刀。或者，您可以采取测量的位置是没有特殊的，而只是量子系统（观察者和观察系统）之间的另一个交互。金宝博官方这有时被称为“较大的Hilbert空间教会”。它在数学上令人愉悦，因为现在只有整个宇宙的这种平滑，连贯，甚至确定性演变。然而，现在您将拥有卓越的“分支机构”，这是世界州的州向量，这很快就会导致许多世界的多层视图。一系列无数世界的形而上学，其中存在于叠加中的许多世界也不会让我符合符合偶变的。

然后有乐器“闭嘴和计算”学校。这在偶然令人愉悦的感觉中是简约的，但似乎大大侵略了科学的努力，其目的不仅仅是预测，而且还要解释并给出世界的一些照片。所有对QM的解释都是有问题的，并根据orcom的剃刀选择它们之间的选择假设一些简单的共同看法以及科学目标的共同看法，我们似乎缺乏。

卢基：这些天的大多数工作都是量子计算和沟通。Quantum Computing是一个有趣的领域，因为它的研究人员设计算法，纠错技术等即可用于无法构建的金宝博娱乐机器。在这个意义上，我倾向于认为量子计算为“探索工程“纪律，类似于Pre-Pre-Putnik航天，eniacal计算机科学和Eric Drexler的纳米系统金宝博官方。你认为这是一个公平的特征吗？你或你的同事在量子计算中得到了很多批评，这些工作是“太投机”？（对于记录，那不是我的看法。）

罗纳德：量子计算中的两个主要问题是（1）我们可以建立一个大规模的量子计算机，（2）如果我们有一个，它可以做些什么。我认为你的一词“探索工程”符合第一个问题的工作;几十年前已经建造了少数额度的小量子计算机，所以它不再纯粹理论。我自己是一个重点关注第二个问题的理论计算机科学家。虽然我认为这更像是数学而不是工程，但您当然可以将其与20世纪30年代的计算机科学进行比较：此时（古典）计算机的理论模型已经被Alan TINGE引入，但没有大规模的计算机尚未建造。您可以在纸上设计用于制定机器的算法，您甚至可以证明这些计算机可以不是解决某些问题(就像图灵在停止问题上的著名做法)。我们现在正在量子计算上做这样的工作:为一些计算问题设计比经典问题快得多的量子算法和通信协议，另一方面证明量子计算机不能给你很多其他问题的加速。当然，这在很大程度上取决于最终能否建立一个大型QC。然而，有趣的是，我们正在做的一些工作有经典计算分析的副产品，这与今天建立QC的进展无关。

关于“过于投机”的可能指控：在20世纪90年代中期，彼得·赫尔发表了他的突破性量子算法，以将大量分解为他们的主要因素（这突破了很多加密），有很多怀疑论，特别是认为这绝不会飞的物理学家之间。他们期望任何实施量子位和操作的尝试都有如此多的噪音和错误，即它将迅速欺骗经典计算机。当然，他们有很好的理由 - 持怀疑态度 - 操纵一小块电子的东西非常艰难，比操纵真空管在20世纪40年代和20世纪50年代更难。在Quantum纠错和容错计算的开发（部分地通过Shor Himself）之后，噪音和缺陷的担忧很快就会很快回答，这粗略地说，如果噪音不是太大并且不会太恶意，您的量子计算机可以纠正它。这些担忧可以完全克服的唯一方法是实际建立一个大规模的QC。我的印象是，实验物理学家正在缓慢但肯定会在这方面取得进展，并且随着时间的推移变得更加乐观，这实际上将在一天或二十年内实现。因此，确定这是一个投机性努力（最长期的研究是），但不合理的是。金宝博娱乐

卢基：您和Quantum Computing Computing的HeuRistics在Quotum Computing的同事中，以QC的长期和某种投机性质为准据推测，您需要做出关于最有可能构建的量子计算机类型的不确定预测，所知障碍物的解决方案可能如上所述等？（我问，因为Miri旨在进行长期研究金宝博娱乐更多的投机比量子计算。）

罗纳德：大多数时间我们研究量子计算机如何解决古典计算问题，经典输入问题（如大数字N）和经典输出（如N的主要因素）。计算机科学已经多十年来定义和研究许多有趣和有用的计算问题和模型的复杂性，并且我们往往从那里开始：我们采取现有的计算问题，并尝试找到超过最佳经典解决方案的量子技巧。在某些情况下，我们成功地设计了夸大古典计算机的量子方式，在某些情况下，我们可以证明QC不能比经典计算机更好。当然，很难预测量子技巧（如果有的话）可能有助于特定的问题，但我们可以随意使用一些普通工具。例如，量子计算机擅长检测周期性模式（这是Shor算法的核心）;他们可以搜索更快（格罗弗的算法）;您可以通过以未知的基础（量子密码学）编码它来隐藏信息;您可以在n QUBBit空间（量子指纹识别）中包装双指数数量的量子状态。很多工作是基于巧妙地组合和应用这种已知的量子工具，并遍布人们找到新技巧添加到我们的工具箱。当然，还有更具体的量子性质的工作，这不仅仅是在古典问题上抛出量子技巧。 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).

我们通常摘要远离将实现量子计算机的特定物理系统的细节。金宝博官方相反，我们只是专注于数学模型，具有量子位和明确定义的基本操作集（“门”），我们可以在它们上执行。It doesn’t really matter whether the qubits will be implemented as electron spins, or as photon polarizations, or as energy levels of an atom — from the perspective of the model, it only matters that a qubit has well-defined 0 and 1 states and that we can form superpositions thereof. Similarly, for classical computers it doesn’t really matter whether you program in C or Java or assembler; all such programming languages can efficiently simulate each other. And you don’t care about the precise voltages used to implement bits physically, as long as each bit has stable and clearly distinguished 0 and 1 values.

在我们拥有大规模量子计算机时，摘要远离此类实施细节是合理的，因为不同品种的量子计算机将能够在额外的贵族贵族和操作方面彼此模拟。例如，出于设计量子算法的目的，即使它们相距甚远，也可以互动地互动。在物理实验的现实中，允许只能在Qubits之间的最近邻居的相互作用更简单。我们可以通过插入几个交换操作来设计第一模型的算法，然后在最近的邻居模型中实现它们，以便将交互Qubits靠近。然而，这种“中等开销”实际上是非常重要的，只要我们还没有大规模的量子计算机。很可能在朝大型QC的慢速道路上，我们将首先拥有几十几个或几百夸张（最新的艺术状态是几个Qubits）。在这种情况下，我们不能太浪费，可能应该设计针对特定物理实现优化的算法。实际上是一个非常有趣的问题，可以找到一个50或100个Qubit QC可以以某种明显的方式表达古典计算机的问题。这些问题是可以测试中间QCS的基准。

重点是，一旦您有大量的Qubits可用，不同的物理实现/架构之间的差异就无关紧要，因为它们都相当于小开销（所需的使用另一个变体）。但是，当我们只有中间大小的QCS（比如说，几十几个或几百QCBits），那么这些开销确实会产生很大的差异，我们需要仔细优化我们的量子算法以执行特定的物理实现that’s actually available. In this respect quantum computing seems quite different from most other future technologies: somehow we’re better able to predict the power of this technology for the long term (when we’ll hopefully have a large-scale QC available and can essentially ignore implementation details) than for the short and medium term (while we only have small-scale QCs with quirky limitations).

卢基：我的下一个问题从量子计算到技术预测。您将拥有500态量子计算机的主观概率是什么？无论是无关紧要的一个量子计算机，在未来20年内？而且，你如何推理这样的问题？

罗纳德：非常高，让我们说概率大于2/3。这是“界限错误”算法的典型计算机科学阈值。从理论的角度来看，我不认为我们知道建立大规模QC的任何根本障碍，以及来自容错QC的阈值定理向我们保证我们可以处理适量的噪音和错误。显然建立QC是一个非常艰难的工程问题，但我的印象是实验主义者正在缓慢而肯定的进展。这里基本上有三种可能的场景：

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

第一个情景似乎是我最合理的。我应该通过说我不是经过认证的物理学家来限定这一点，更不用说认证实验physicist, so this opinion is partly based on hearsay — but I do have some confidence in the progress that’s happening in places like MIT, NIST, Yale, Delft,… The recent paper you refer to casts doubt upon the controversial D-Wave quantum computer, which has gotten a lot of press in the last few years. For commercial reasons they prioritize quantity (=number of available qubits) over quality (=the coherence and “true quantum nature” of those qubits), and their machines seem too noisy to have useful quantum computing power.

卢基：这是否意味着我们可能需要吹扫地球怪物- 可用于密码安全性，并转换到后量子密码学，在〜20年内？

罗纳德：我认为这将是一个明智的预防措施，至少是重要的或敏感的数据。至少有两种方法可以处理这个。我们可以坚持公钥密码学，但是通过似乎难以破解的问题，替换因子和离散日志等狂暴的问题。格子问题是一个提到的候选人。或者我们可以使用量子密码术。既不是RSA也不高效，但至少他们更安全。It makes sense to start this transition already now, even though there’s no QC yet: the security services (and, who knows, maybe the mafia too) are probably hoovering up RSA-encrypted communications that they store for the time being, waiting for the QC that will allow them to decrypt these messages later. So even today’s communication is not safe from a future QC.

卢基：谢谢，罗纳德！