研究人员认为，量子计算机很快就能比经典计算机更有效地解决某些问题。为了衡量和分类这些效率增益，我们依靠计算复杂性理论，这是计算机科学的一个分支，其核心是衡量和比较解决不同类型问题的计算工作量。复杂性理论为我们描述计算中遇到的各种加速和问题类提供了有用的简写，但它的意义远不止于此。事实上，至少有一位权威专家认为，如果没有复杂性理论，我们就不会有量子计算。

Scott Aaronson 是德克萨斯大学奥斯汀分校计算机科学教授和量子信息中心主任，也是量子计算和计算复杂性理论领域的世界级顶尖专家之一。Aaronson 的研究帮助定义了量子计算机的一些基本功能和局限性，他作为科学传播者的工作帮助普及了量子，并通过Complexity Zoo wiki和他的Shtetl-Optimized 博客等项目吸引了更多人加入量子社区。在一次采访中，Aaronson谈到了计算复杂性理论在量子计算历史上发挥的基础作用。

Aaronson 说：“我认为复杂性理论在这门学科中的中心地位从一开始就存在，”“你需要复杂性理论——即使只是为了阐明为什么量子计算机会比经典计算机更好。”

计算复杂性的简要概述

为了更好地理解 Aaronson 的观点，让我们简要了解一下Shor 的算法。我们经常说，运行 Shor 算法的量子计算机理论上可以比任何已知的经典技术更快地找到大整数的因子，但这很模糊。复杂性理论帮助我们更详细地描述这种差异：我们可以说“Shor 算法在多项式时间内找到大整数的因数，而所有已知的经典算法都需要指数时间。”

这两个概念——多项式时间和指数时间——是“时间复杂性”的例子，它限制了解决不同类型问题所需的基本计算步骤的数量。时间复杂度使我们能够看到，随着问题规模的增长，所需步骤的数量是如何增加的。

例如，多项式时间算法可能有一个时间复杂度描述的函数，如$n^{2}n²$ 。如果我们为该算法提供一个大小为$n=5n=5$ 的问题，我们知道我们只需$2525$ 步（$5^2=255²=25$ ）即可完成该问题。如果$n=10n=10$ ，我们需要$100100$ 步。另一方面，指数时间算法可能具有像$2^{n}2ⁿ$ 这样的时间复杂度。这意味着如果$n=5n=5$ ，我们将需要$3232$ 个步骤（$2^5=322⁵=32$ ），但如果$n=10n=10$ ，那么我们已经需要$1,0241,024$ 个计算步骤来解决问题。这就是为什么多项式时间算法比指数时间算法更受欢迎的原因:它们所需的步骤数量比指数时间算法要少得多。

我们利用时间复杂性将我们可以用计算机解决的不同类型的问题——从基本的乘法到我们几乎无法想象的理论问题——组织成“复杂性类”。

有无数种复杂性类，其中许多是重叠的。其中最著名的包括P，这是经典计算机可以在多项式时间内解决的所有问题的类别，以及NP，NP是所有问题的类别，其解决方案可以在多项式时间内由经典计算机检查，即使它们不能在多项式时间内求解。量子复杂性理论是与量子计算相关的复杂性理论的一个分支——也为我们提供了BQP，这是量子计算机可以在多项式时间内以小于设定的误差量解决的所有问题的类别。BQP包括所有P，以及一些特殊问题，如整数分解，研究人员目前认为这些问题属于BQP和NP，但不属于 P。

像这样的复杂课程是所有计算机科学中最有趣的谜题的基础。例如，上图表明P只是NP的一小部分。例如，上图表明P只是NP的一小部分。大多数理论家认为确实如此，但也有可能P和NP相同，这意味着有多项式时间的算法来解决任何问题，其解决方案可以在多项式时间内检查;只是我们还没有找到它们。

这个问题被称为P 与 NP，Scott Aaronson说这是第一次吸引他研究复杂性理论的原因之一。

他说:“当我十四五岁的时候，我学习了P和NP的问题，它完全迷住了我。”“我可能不是第一个，也不是最后一个了解P和NP的青少年，并幻想自己能解决这个问题。”Aaronson 说没过多久，他就放弃了这个想法。

复杂性理论为我们提供了一个框架，用于系统地思考哪些计算问题属于哪些复杂性类，以及研究这些类之间的关系。但Aaronson表示复杂性理论不仅仅影响我们思考计算问题的方式;它也会影响我们对计算本身的思考方式。当谈到量子计算时，他认为复杂性理论提供了关键的见解，导致理论学家首先建立了一个正式的量子计算理论。

弥合量子理论和量子计算之间的鸿沟

量子计算机是由物理学家理查德·费曼在40多年前首次正式提出的，当时他建议用量子计算机来模拟物理系统。有些人可能会对研究人员很久以前就在考虑量子计算感到印象深刻，但 Aaronson 认为量子计算理论的诞生早就应该出现了。

这是因为量子力学——量子计算的支柱——早在费曼的提议之前就已经存在了50多年，起源于20世纪20年代中期。经典可计算性理论在 1930 年之后不久出现，1936年，Alan Turing首次描述了他的图灵机。

“那么……为什么过了这么久才有人提出量子计算的想法呢?”Aaronson说。“为什么直到20世纪80年代初，才有人想到这一点?”

这种差距出现的部分原因可能是Turing和John Von Neumann等思想家的早逝造成的，John Von Neumann对于开发一个全面的量子力学数学框架发挥了至关重要的作用。这两个人物都在 1960 年之前去世，Turing只活了41岁。Aaronson 说：如果他们活得更久一些，也许他们会转而研究量子计算。”

但是Aaronson认为，在20世纪80年代之前没有人提出量子计算的概念还有另一个原因。

“我认为这个问题的答案的一个关键部分是，直到 60 年代和 70 年代，人们对​​复杂性理论没有明确的概念，”Aaronson 说。“在多项式时间内可解决的问题和需要指数时间的问题之间的区别是一个非常基本的区别——至少与可计算和不可计算之间的区别一样基本……在你提出量子力学如何帮助计算这个问题之前，你真的需要把它作为第二天性。”

最基础的计算机

多项式和指数时间复杂度之间的区别并不是研究人员开发量子计算理论所需的唯一概念。Aaronson 说，他们还需要解决一个关于复杂性理论与现实本身之间关系的基本问题。量子计算利用量子力学定律来执行计算，但它需要在复杂性理论中进行关键的洞察，才能明白为什么量子力学应该与计算有任何关系。

作为这种分歧的证据，Aaronson 指出了 2011 年《纽约客》物理学家 David Deutsch 的简介，David Deutsch与 Richard Feynman被广泛认为是量子计算理论的创始人之一。

Deutsch在接受《纽约客》采访时回忆起与 IBM 研究员 Charlie Bennett 的一次交流，那次交流在帮助他建立量子计算的正式理论方面发挥了关键作用。当时，Deutsch 认为当时新兴的计算复杂性领域几乎没有价值。他认为，复杂性理论只能描述一个问题相对于特定计算机系统的复杂性，而不是以任何基本的、普遍的方式。

换句话说，“Deutsch 对复杂性理论嗤之以鼻，并说这一切都取决于你的计算模型，”Aaronson 说。

Bennett 反驳说，复杂性理论可以描述一种基本的通用计算机：物理学。毕竟，计算机是物理系统，它们的能力受物理定律的支配。这表明复杂性理论不仅限于描述特定计算机系统的基本属性，还可以用于描述宇宙和计算本身的最基本属性。

这使 Deutsch 得出了一个重要的见解：复杂性理论的问题不在于它仅限于描述特定的计算机系统；只是还没有人用最基本的术语来描述它。Alan Turing 曾打算将图灵机用作计算的“通用”模型——一个描述所有可能的计算设备的模型，并且可以作为复杂性理论等学科的基础。然而，事实上，他只得出了基于经典物理定律的通用计算的近似值。一个真正通用的计算模型应该是基于自然界最基本的定律——量子力学。

这一见解启发了 Deutsch 开发量子图灵机，这是他在1985 年的一篇有影响力的论文中概述的量子计算的形式化模型。通过建立一个真正通用的计算模型，Deutsch 帮助证明了复杂性理论具有比任何人都意识到的更深层次的含义和更广泛的应用。

“Deutsch 将与 Bennett的谈话作为他发明量子图灵机的起点，”Aaronson 说。“那么为什么复杂性理论对量子计算很重要？我的意思是，它从一开始就是其中不可分割的一部分。”

复杂性理论和量子算法的未来

Deutsch 的量子图灵机是物理量子计算机的第一个精确数学模型。他的工作在1993 年由计算机科学家 Ethan Bernstein 和 Umesh Vazirani 撰写的具有里程碑意义的论文“量子复杂性理论”中发挥了基础性作用，该论文定义了 BQP 等量子复杂性类别，以及我们今天仍在使用的其他几个关键量子计算概念。

Bernstein-Vazirani 的论文帮助将量子复杂性理论形式化为计算复杂性的一个分支，就像 Deutsch 的工作帮助将量子计算形式化为计算机科学的一个分支一样。这为第一个量子算法奠定了基础——包括 Shor 的算法，该算法于 1994 年发表，距 Bernstein 和 Vazirani 的量子复杂性理论论文仅一年。

Aaronson 说：“Shor 的算法建立在早期的称为 Simon 算法的量子算法的基础上，而 Simon 反过来又建立在 Bernstein 和 Vazirani 的论文之上……所以，Shor的算法是在人们将量子多项式时间定义为一个复杂性类并开始真正系统地思考这个问题的一年后出现的。”

量子计算在 1997 年开始了通往实际应用的漫长道路，当时IBM-Almaden 的研究人员成为第一批在真正的量子硬件上运行 Shor 算法的简化版本的人。从那时起，量子计算技术取得了巨大进步，基于云的可访问量子计算的出现使研究人员能够超越纯粹的理论，开始在量子硬件上进行有趣的实验。

然而，即使量子社区越来越多地将注意力转移到寻找量子计算机的实际应用上，Aaronson 表示，量子复杂性理论仍然对该领域有很大贡献。它可以帮助我们更好地了解在获得实际量子优势之前我们需要做多少工作。

“对于目前已知的方案来说，要在容错量子计算机上运行任何东西，你都将付出巨大的开销，”Aaronson 说。“所以无论你获得什么量子加速，它都必须足够大，以抵消你为运行全功率量子计算而付出的开销。”

复杂性理论帮助我们了解我们需要在纠错和其他协议开销方面实现什么，以实现不同类型的量子加速。“量子计算的最终目标是将其用于有价值的现实世界应用，”Aaronson 说。“但是随着围绕这个领域的所有炒作，我们需要复杂性理论来让我们诚实地知道，在我们实现这个目标之前，我们还有多少工作要做。”

原文链接：https://medium.com/qiskit/scott-aaronson-says-complexity-theory-is-inextricable-from-quantum-computing-18369d0bd05d

---煤油灯科技victorlamp.com翻译整理---