原文标题 ：When to use a quantum computer

Table of Contents

何时使用量子计算机

量子计算很奇怪

不，我不是指支配量子计算机运行的量子力学的奇怪现象。

我指的是媒体报道的差异。在流行媒体中，量子计算被吹捧为可以解决我们所有问题的神奇设备。相比之下，批判性文献怀疑量子计算是否会做任何有用的事情。

如果我们相信媒体所写的关于量子计算的所有内容，那就像患有人格障碍一样，你会在高兴和毁灭之间摇摆不定。

我也有罪。我已经在我的每周帖子中发表了这两篇文章，我已经写了将近两年了。我已经强调了量子计算机可以做的所有不可思议的事情。但我也澄清了由于对量子计算机的严重误解而导致的过高期望。

虽然我试图通过不完全依赖数学公式来使整个主题尽可能容易理解，但我会尽可能地保持基础。

因此，在我之前的帖子中，我指出了量子计算机的作用：

量子计算所做的一切就是使实现非确定性算法成为可能。

当然，如果没有进一步的澄清和解释，这个定义也无济于事。

因此，让我们看看这意味着什么及其含义，因为它是识别我们应该使用量子计算机的问题的关键。

但在我们开始之前，让我简要解释一下为什么我强调“应该”而不写“可以”。原因很简单，量子计算机可以做数字计算机可以做的所有事情。但量子计算机是昂贵的设备，其少数量子比特（qubits）易受噪声影响。

IBM 当前的 QPU（量子处理单元）Eagle 有 127 个量子位。所以它可以做 127 位 CPU 可以做的所有事情。因此，如果我们拥有数百万（一个兆比特）或数十亿（一个千兆比特）的量子比特，那么一台量子计算机就可以完成当前 CPU 所能做的所有事情。

但即使是拥有数十亿量子比特的量子计算机，也比同类经典芯片更慢、更容易出错、也更昂贵。所以我肯定会坚持使用数字计算机……除非有理由使用量子计算机。

问题不在于我们是否可以使用量子计算机。相反，问题是我们是否应该这样做。那么我们为什么还要为微型处理器、嘈杂的结果和成本而烦恼呢？

我们应该使用量子计算机来解决非确定性多项式（NP）问题。根据定义，这些是非确定性算法可以在多项式时间内解决的决策问题，而确定性算法则不能。这听起来像是重言式，但它是有意义的。

要理解这意味着什么，我们需要谈谈复杂性理论。这是关于解决问题所需的时间或步骤数量如何随着问题规模的增加而增长的理论。

让我们考虑两个问题。首先，两个数相乘，例如“三乘以七是多少？”其次，两个数的因式分解，例如，“21 的质因数是什么？”这两个问题都很容易解决。原因是问题规模很小。

这些问题怎么办：

虽然您可以用笔和纸解决第一个问题，但您可能难以解决第二个问题。顺便说一句，这些仍然是小问题，也是。

将一个 n 位数字相乘的复杂度增加了大约 n2。我们称之为多项式问题解决方案。相比之下，找到一个 n 位数的素因子的复杂度是 e^{n^{1/3}}。这意味着努力随着数字的数量呈指数增长。

重要的是不要低估多项式和指数复杂度之间的差异。虽然您的智能手机在几秒钟内将数字与 800 位相乘，但在超级计算机上对这些数字进行因式分解需要大约 2000 年。

我们认为我们可以在多项式时间内解决的问题是易于解决的，而那些具有指数增长的问题是难以解决的。对于较大的 n 值，复杂性呈指数增长的问题变得非常困难，即使是最好的超级计算机也需要很长时间才能解决它们——在某些情况下，这意味着数百万甚至数十亿年。

您是否为解决上述任务而烦恼？如果我告诉你 22523 的质因数是 101 和 223 呢？

这个解是否正确可以在多项式时间内检查，因为检查是乘法。这使得数字的因式分解成为一个非确定性多项式决策问题。

决策问题是我们可以回答是或否的问题。此外，这个答案必须通过简明的证据来验证。如果证明的复杂性呈现多项式增长，则证明是简洁的。

此外，如果我们能猜出它的解，则称该问题为非确定性多项式 (NP) 问题。这意味着我们没有可以遵循的特定规则来推断解决方案，但如果我们幸运的话，我们仍然可以在第一次尝试时找到正确的解决方案。

因此，如果一个非确定性算法可以在多项式时间内解决一个 NP 问题，这意味着它使这样的问题易于处理。

量子计算的力量源于其实现非确定性算法的能力。因此，我们可以为此类 NP 问题创建算法。

这正是我们应该使用量子计算机的时候。当面临无法用经典计算机有效解决（即多项式复杂度）的 NP 决策问题时，我们应该使用量子计算机。

以乘法为例。这是一个我们已经可以有效解决的决策问题。因此，我们不应该使用量子计算机，即使我们可以。

另一方面，因式分解是我们无法有效解决的决策问题。因此，我们应该为此使用量子计算机。

优化呢？假设您想找到一系列城市之间的最短路径。这是一个我们还不能有效解决的问题。但是，这不是决策问题，因为即使有人告诉您，您也无法验证解决方案是否是最佳的。在您考虑所有可能的路线之前，您永远不会知道是否有更好的解决方案。

但这并不意味着量子计算无法帮助优化。例如，它可以用于首先找到可能的路线。当然，有时找到一条有效的路线本身就是一个 NP 问题。但是一旦我们有了路线，我们就可以快速检查它是否正确，即使我们无法判断它是否是最优的。

在这种情况下，我们应该使用量子计算机来查找路线。然后，经典优化器可以选择最佳路线。这就是我们所知的变分量子经典算法。[0]

显然，您需要在问题领域拥有深厚的专业知识来判断是否应该使用量子计算机来解决它。

使用这些知识来确定您应该使用量子计算机解决的领域中的问题。它会让你进入杆位。

文章出处登录后可见！

已经登录？立即刷新