量子计算与加密破解

Question

不久前，我读到Quantum计算机可以在很短的时间内破解当今使用的大多数类型的散列和加密(我相信只需要几分钟)。这怎么可能呢？我试过阅读有关它的文章，但我在a quantum bit can be 1, 0, or something else上迷路了。有人能用简单的英语解释一下这与破解这样的算法有什么关系吗？

Answer 1

前言：量子计算机是奇怪的野兽，我们真的还没有驯服到有用的程度。支撑它们的理论是抽象的和数学的，所以任何关于它们如何比经典计算机更有效的讨论都将不可避免地冗长而复杂。您至少需要对线性代数和量子力学有本科生的理解才能理解细节，但我将尝试传达我有限的理解！

量子计算的基本前提是quantum superposition。正如你所说，量子系统(例如量子比特，或量子比特，普通比特的量子模拟)不仅可以存在于0和1状态(称为系统的计算基础状态)，还可以存在于这两种状态的任意组合中(因此每个都有一个与之相关的振幅)。当有人观察到这个系统时，量子比特的状态就变成了它的一个基态(你可能听说过与此相关的Schrödinger's cat collapses实验)。

正因为如此，n量子位的寄存器有其自己的2^n基态(这些状态是您可以观察到的寄存器所处的状态；想象一个经典的n位整数)。由于寄存器可以同时存在于所有这些状态的叠加中，因此可以将计算应用于所有2^n寄存器状态，而不只是其中之一。这就是所谓的量子并行。

由于量子计算机的这一特性，它们看起来像是一颗银弹，可以比经典计算机以指数级的速度解决任何问题。但这并不简单:问题是，一旦你观察到你的计算结果，它就会崩溃(正如我上面提到的)，变成只有一次计算的结果--然后你就会失去所有其他的计算结果。

量子计算/算法的领域是试图通过操纵量子现象来解决这个问题，以比在经典计算机上可能的更少的操作提取信息。事实证明，要设计出比任何可能的经典算法都要快的“量子算法”是非常困难的。

你问的例子是量子密码分析。人们认为量子计算机可能能够“破解”某些加密算法:具体地说，就是RSA算法，它依赖于寻找非常大整数的素因数的难度。考虑到这一点的算法被称为Shor's algorithm，它可以将整数分解为多项式时间复杂度。相比之下，该问题的best classical algorithm具有(几乎)指数时间复杂度，因此该问题被认为是"intractable“。

如果你想对此有更深的理解，那就去读几本关于线性代数和量子力学的书吧。如果你需要一些澄清，我会看看我能做些什么！

抛开：为了更好地理解量子叠加的概念，请从概率的角度进行思考。想象一下，你抛出一枚硬币，然后用手接住它，盖住它，这样你就看不到它了。作为一个非常脆弱的类比，硬币可以被认为是处于正面和反面“状态”的叠加中:每个状态的概率为0.5 (自然地，由于存在两种状态，这些概率加起来为1)。当你把手拿开并直接观察硬币时，它会折叠成正面状态或反面状态，因此这种状态的概率为1，而另一种状态的概率为0。我想，思考它的一种方式是一组在观察之前是平衡的尺度，在这一点上，随着我们对系统的了解的增加，它向一侧倾斜，一种状态变成了“真实”状态。

当然，我们不认为硬币是一个量子系统:出于所有实际目的，硬币有一个确定的状态，即使我们看不见它。然而，对于真正的量子系统(如individual particle trapped in a box)，我们不能这样想。在量子力学的conventional interpretation理论下，粒子基本上没有确定的位置，而是同时存在于所有可能的位置。只有在观察时，它的位置才会在空间中受到限制(尽管仅限于有限的程度；参见。uncertainty principle)，甚至这也是纯粹随机的，并且仅由概率决定。

顺便说一句，量子系统并不局限于只有两个可观察到的状态(那些可以观察到的状态被称为two-level systems)。有些有很大但有限的数字，有些有可数的无限大的数字(例如"particle in a box"或harmonic oscillator)，有些甚至有不可计数的无限大的数字(例如free particle的位置，它不限于空间中的单个点)。

Answer 2

Wikipedia article很好地解释了这一点。

简而言之，如果你有N位，你的量子计算机可以同时处于2^N个状态。概念上类似于使用传统位的2^N CPU的处理(尽管不是完全相同)。

Answer 3

在这一点上，这是高度理论化的。量子比特可能会提供破解加密的能力，但显然还没有到那一步。

在量子层面上，管理行为的法律与宏观层面上的不同。

要回答您的问题，首先需要了解加密是如何工作的。

在基本层面上，加密是将两个极大的素数相乘的结果。这个超大的结果可以被1、本身和这两个质数整除。

破解加密的一种方法是通过做质数因式分解来暴力猜测两个质数。

这种攻击速度很慢，并且通过选择越来越大的素数来挫败。YOu听说密钥大小有40位、56位、128位，现在是256,512位甚至更高。这些大小与数字的大小相对应。

蛮力算法(简而言之)可能如下所示

for(int i = 3; i < int64.max; i++)
{
  if( key / i is integral)
  {
    //we have a prime factor
  }
}

所以你想暴力破解，尝试质数；，这在一台计算机上需要一段时间。因此，您可以尝试将一组计算机组合在一起，以分而治之。这是可行的，但对于非常大的键大小仍然很慢。

量子位如何解决这个问题，是因为它们同时是0和1。因此，假设你有3个量子比特(请记住，这不是一个小壮举)。

有了3个qbits，你的程序可以同时具有0-7的值

(000,001,010,011等)

，它同时包含质数3,5,7。

因此，使用上面的简单算法，而不是每次都将i加1，您只需除以一次，然后检查

0,1,2,3,4,5,6,7

所有这些都是同时发生的。

当然量子比特还没有到那个地步；在这个领域还有很多工作要做；但这应该会让你有一个想法，如果我们可以使用量子编程，我们将如何破解加密。