量子计算将改变加密游戏，但尚不清楚它将改变多少。目前还不清楚，因为我们还不确定量子计算机可以解决什么样的问题。如前所述，RSA 被量子计算大大削弱了，因为素数的因式分解可以使用 Shor 算法在多项式时间内完成。然而，并不是所有的加密程序都被认为是弱于量子计算。

您可能听说过 P（多项式时间）、NP（非确定性多项式时间——给出正确答案的问题可以在多项式时间内检查）和 NP-Complete（最难的 NP 问题）。众所周知，大合数的素数分解是一个 NP 问题，并且被许多人认为不是 P 问题。这意味着传统计算机很可能¹需要超多项式时间（最好是次指数时间，如GNFS) 进行分解和 RSA 加密取决于此。NP-complete 是一类要求稍高的问题。NP 问题的任何实例都可以简化为 NP 完全问题的实例。（即使 NP 问题是另一个 NP 完全问题，也是如此。）这意味着，如果您曾经找到 NP 完全问题的多项式时间解，那么您将获得每个NP 问题的多项式时间解。如果您使用经典计算机这样做，您将证明 P = NP。

量子计算机有自己的复杂性等级。BQP 是可以由量子计算机在多项式时间内 [统计上] 解决的一类问题。众所周知，分解在 BQP 中，因为我们有 Shor 算法。尚不清楚的是 BQP 是否包含 NP-complete。目前理论上它不会，这意味着即使使用量子计算机，仍然存在 NP 完全问题仍需要指数时间，但数学家仍在努力研究该理论。

整数分解处于一个有趣的中间地带。我们知道它是 BQP 的一部分（因为我们找到了 Shor 算法）。我们也知道这是 NP 中的一个问题（它是 NP，因为只需将数字相乘就可以在多项式时间内证明分解）。我们还不知道它是 P、NP-but-not-P 还是 NP-complete。没有人能够以一种或另一种方式证明这一点。它实际上可能是一个 P 问题，可以用经典计算机在多项式时间内解决，这使得它对于加密目的非常弱。这可能是一个 NP 完全问题，鉴于我们知道它在 BQP 中，这意味着量子计算机可以在多项式时间内解决任何NP 问题，这通常对密码学来说是一个重大打击。

许多即将出现的加密算法开始使用除素数分解之外的其他问题作为其根源。特别是，一组基于晶格的问题被认为特别难以使用量子计算机解决。如果所有 NP 问题都是 BQP 的一部分，那么这将无济于事，但直到今天我们仍在弄清楚那个细节。

事实证明，AES 不受 Shor 算法的影响。 Grover 的算法允许在 O(2 ^n/2 ) 时间内暴力破解一个 n 位密钥，而不是传统计算机所需的 O(2 ^{n ) 时间。}因此，一个 128 位 AES 密钥可以在 O(2 ⁶⁴ ) 时间内被足够强大的量子计算机强制执行，该量子计算机可以使用 128+ 量子位执行 Grover 算法 2^64 时间。

¹ 下面的明智和具有挑战性的评论者正在挑选我措辞的不准确之处。从技术上讲，不知道 NP 问题是否需要指数时间。NP 类问题和 P 类问题可能是相同的。然而，大多数数学家认为 P != NP 的可能性更大，只是因为到目前为止它看起来并不像它。如果我们想用博彩术语来讨论，只需看看你能回答这个问题能赚多少钱。如果你证明 P 和 NP 是不同的，你可以获得一百万美元的克莱奖，并且可能会因为如此聪明而获得一份轻松的工作机会。如果你证明它们是相同的，我希望 NSA 愿意付出更多，让你对你的发现保持沉默，而是将你的论文交给他们的数学家。

如果您对量子计算和加密的主题非常感兴趣，我强烈建议您阅读不同的复杂性类别，例如 P 和 NP。他们值得你花时间。

破解这些算法中的任何一个都不是不可能的。问题不在于你是否可以暴力破解AES，而在于它需要多少时间以及它是否可行。

如果您想使用普通计算机暴力破解 AES，则需要搜索 2^128 个密钥，这将需要最少 2^128 次操作。

另一方面，使用量子计算机和搜索算法（如Grover算法），您将能够在 (2^128)^0.5 操作中通过相同数量的键。

这里必须注意，量子计算机可用于实现比仅使用经典计算更好的安全协议。因此，真正的问题根源在于，并非所有人都可以使用更先进的技术（在这个问题的情况下，这是量子计算变得可用的假设情况）。

不可以。AES 被认为是后量子密码学，不会被量子计算（QC 抗性）淘汰。

考虑加密强度与计算强度成反比可能会有所帮助。

加密强度通常由密钥长度来衡量。加密强度的指数增加是通过将密钥长度加倍来实现的。例如，AES-256 比 AES-128 强指数级。

目前的理解是，QC 可以代表计算强度相对于经典计算的指数级增长。这会将经典加密强度降低一半。

因此，强加密将需要双倍密钥长度来抵消 QC 计算强度。

这将是最坏的情况。如果 QC 强度只是亚指数级更强，则密钥长度的较小增加将足以抵消任何优势。

强加密的最小推荐密钥长度应从 90 位增加到 180 位。

结果：在最坏的情况下，AES-256 会从可笑的强到荒谬的强，并且 AES-128 将不再被认为是强的。

请记住，这种惊人的结果只能通过将室温经典计算 (CC) 强度与过冷 QC 强度进行比较来实现。

过冷 CC 设备也增加了计算强度。超导 QC 设备已经在接近零开尔文的条件下运行，这是通过物理方式提高计算强度的关键限制。

此外，CC 本身通过并行性支持高度可扩展性，而现存的 QC 最多仅支持受限并行性。