量子计算机可以做什么？

量子计算或许是下一代科技的核心技术之一，量子计算机也是业界期待的下一代计算机，然而，量子计算机能做什么？这个问题很大，我们现在来阐述。

研究机构希望量子计算机能够加深人们对宇宙的理解，同时解决一些经典计算机无法解决的问题。然而，这要取决于这些问题是什么，以及量子计算机能在多大程度上解决这些问题。

尽管大家对量子计算机期望很高，甚至希望它无所不能。但量子计算机并不是能够解决诸如停机问题等棘手问题的全能计算设备。

相反，它们是建立在架构上的处理器，科学家希望这种架构能够让它们做经典计算机可以做的任何事情，并为它们的量子特性带来的某些问题提供额外的功能或提高性能。

充分了解量子计算机的潜在能力，以及它们如何与经典计算机相抗衡，需要深入研究计算复杂性理论。对于研究量子或对其感兴趣的人来说，最重要的是一个量子计算机可以轻松解决的问题的理论，称为 BQP——有界误差量子多项式时间。

下面，我们汇总了复杂性类别列表，以及 BQP 适合的位置。

P——多项式时间。P 是最熟悉的复杂性类别：确定性图灵机可以使用多项式时间资源解决问题。计算机需要资源来解决问题，其中时间、精力和位数是最重要的。对于 P 中的任何类型的问题，解决或检查它所需的时间量会随着问题规模的增加而基于某些多项式而增加。所以，如果问题的大小是 x，那么它所花费的时间就是 x^ n，其中n是一个常数。你的计算机每天做的事情大多是 P ——例如乘法。

理论家认为这些类型的问题对于计算机来说“容易”解决，但这在理论上很容易，而不是在实践中。多项式n可以非常大 - 100、1,000、1,000,000 等，只要它是一个常数，这会导致 P 中的一些极难解决的问题类型。在不同的计算硬件上实现给定的算法也可以改变多项式。然而，P 旨在抽象出实现细节并作为粗粒度分类存在，以便我们可以对这些问题的本质说一些基本的东西。

NP — 非确定性多项式时间。NP 是一个复杂性类别，包括确定性图灵机可以检查解决方案在多项式时间内是否正确的问题类型。NP 包括所有 P——但也包括我们不知道是否存在多项式时间解的问题类型。此类包括诸如分解大数之类的问题类型，其中很难将大数分开，但很容易检查两个因数乘回第一个数字。NP 构成了数学中最重要的未解决问题之一的症结所在：对于每种 NP 问题类型是否存在 P 解决方案（称为 P 与 NP 的问题）尚未得到证明。解决 P 与 NP 的尝试让数学家有很多理由相信（但同样，

这里是“问题类型”，而不是“问题实例”。“因式分解”是一种问题，而“因式分解 15”是一个问题实例。可以破解难题实例的算法可能在 P 中，但对解决整个问题类型的算法更有价值，例如 Shor 的因式分解算法旨在分解任何数字。

NP-Hard —从 NP 向外扩展的是 NP-Hard 问题类型，它们至少与 NP 中最难的问题类型一样难。此类包括一部分 NP（更多内容见下文），还包括其他可能不在 NP 中的问题类型。NP-Hard 问题似乎经常表现出一种非结构化——组合行为需要转动很多旋钮，这让求解者感觉好像他们必须依靠随机性和猜测才能找到答案。

NP-Complete —在 NP 和 NP-Hard 的交集处是 NP-Complete，即本身在 NP 中的 NP-Hard 问题类型。NP-Hard（包括 NP-Complete）展示了一个有趣的对称性：您可以使用多项式资源将 NP-Hard 问题类型的求解器转换为任何 NP 问题的求解器。换句话说，为 NP-Hard 类型的问题找到一个求解器为您提供了解开 NP 中每个问题的钥匙（这也包括 P 中的每个问题）。这意味着如果您找到任何类型的 NP 完全问题的多项式时间解，您就会发现 P=NP。这没有发生，也没有预期会发生——在任何可物理实现的计算机上，对于 NP-Hard 或 NP-Complete 复杂性类别中的任何事物，都不存在多项式时间解。

NP-Complete 包括一些计算机科学家经常谈论的非常流行的问题，例如3-SAT和旅行商问题。如果您需要算法来解决任何 nxn 网格（将数独视为问题类型），则数独是 NP-Complete，但在 P 中用于解决特定大小实例的算法。

BPP— 我们还没有完全研究量子的东西，但我们已经到了那里：在 P 周围，你可以画一条代表 BPP 或有界误差概率多项式时间的模糊线。在此之前，我们只将“资源”称为计算时间，然后还有计算空间（我们稍后会谈到）。但是，如果我们添加随机性作为计算机可以使用的资源呢？随机性是普通计算机无法模拟的东西，我们必须为计算机提供数据。BPP 是一类复杂性的问题，我们可以在多项式时间内解决和检查问题，此外还可以加入随机过程来帮助解决问题——它们是有界的，这意味着算法必须返回正确的答案概率高于大于一半的设定常数。它没有被证明，但强烈假设，

如果你去掉 BPP 的界限——你只需要算法在一半以上的时间内返回答案（但它的正确率可以任意接近 1/2），那么你就有一个更强大的复杂性类，称为PP或 概率多项式时间。

BQP——最后，我们到达了具有有界误差量子多项式时间的量子世界。这些是量子计算机——即具有额外叠加、纠缠和干涉能力的计算机——可以在多项式时间内以小于设定的误差量解决的问题。而现在，对于这个博客最令人失望的部分：BQP 的边界是一条模糊的线。这条线位于 BPP 和 PP 之间，包括一些（但不清楚有多少）NP，以及一些在 NP 之外的东西。

因此，有界误差的量子计算机可以在多项式时间内解决 P 和 BPP 中的所有类型问题。它可以在多项式时间内解决一些 NP 类型的问题，其中最流行的例子是 Shor 算法的因式分解。目前尚不清楚它是否能有效地解决 NP-Complete 类中的任何问题——但研究人员怀疑它不能。关于复杂性类如何相互关联，还有很多未经证实的事情，而 BQP 是另一个没有严格定义边界的复杂性类。

然而，并非一切都是完全模糊的，我们知道 BQP 比 BPP 更强大。研究人员最近证明，BQP 包括一些在 NP 之外的问题，从技术上讲，在更大的复杂性类别 PH 之外。经典计算机很难找到或检查该类问题类型的解决方案。这意味着，即使在不太可能的情况下，有人证明 P=NP，仍然会有经典计算机无法破解的 BQP 问题类型。然而，即使这种关系也有些模糊，因为 P 是否等于包含 P、NP 和 PH 的更大复杂性类别（称为 PSPACE）尚未得到解答。

小结

研究表明，与经典计算相比，量子计算有它的核心优势。研究人员已经证明了在计算中让它们相互对抗时，使用量子比特计算与经典比特计算之间存在几种理论上的分离，例如迫使经典计算机只运行嘈杂的、恒定深度的电路。像这样的证明已经证明，量子暂存空间本质上比经典暂存空间更强大。NP 之外的问题类型仍然存在那些 BQP 解决方案。

尽管量子计算的落地应用，需要弄清楚这些算法将如何为社会提供商业价值，但目前阶段，这超出了理论计算机科学的领域。

那么，量子计算机到底能做什么呢？

目前来说还是未知的，构建量子计算机需要足够强大的硬件，但是目前还做不到。

但是已知的是，量子计算机可以有效地解决当今最好的经典算法难以解决的问题，量子计算机和经典计算机之间确实存在一些分离，并且 BQP 包含多项式解决方案，甚至可以解决 NP 之外的问题。而且，随着更多的研究和硬件开发，量子计算机将取得更多优势。