encryption - 量子计算和加密破解

Question

不久前我读到，量子计算机可以在很短的时间内破解当今使用的大多数类型的散列和加密(我相信只有几分钟)。这怎么可能？我曾尝试阅读有关它的文章，但在 a quantum bit can be 1, 0, or something else 中迷失了方向。 .有人可以解释这与在没有所有花哨数学的情况下用简单的英语破解此类算法有何关系吗？

Answer 1

序言:量子计算机是一种奇怪的野兽，我们还没有真正驯服到有用的地步。支撑它们的理论是抽象的和数学的，因此任何关于它们如何比经典计算机更有效的讨论都将不可避免地冗长而复杂。你至少需要对线性代数和量子力学有本科的了解才能理解细节，但我会尽量传达我有限的理解!

量子计算的基本前提是quantum superposition .这个想法是一个量子系统(例如一个量子位，或量子位，普通位的量子模拟)，如你所说，不仅可以存在于 0 中。和 1状态(称为系统的计算基础状态)，但也可以是两者的任意组合(因此每个状态都有与之相关的幅度)。当有人观察系统时，量子位的状态collapses进入其基本状态之一(您可能听说过 Schrödinger's cat 思想实验，与此相关)。

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

由于量子计算机的这一特性，它们似乎是一颗银弹，可以比经典计算机以指数级的速度解决任何问题。但这并没有那么简单:问题在于，一旦您观察到计算结果，它就会崩溃(正如我上面提到的那样)成为其中一个计算的结果——而您失去了所有其他计算结果。

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

你问的例子是量子密码分析。人们认为量子计算机可能能够“破解”某些加密算法:特别是 RSA 算法，它依赖于很难找到非常大的整数的质因数。允许这样做的算法称为 Shor's algorithm ，它可以分解具有多项式时间复杂度的整数。相比之下best classical algorithm因为该问题具有(几乎)指数时间复杂度，因此该问题被视为“intractable”。

如果你想更深入地理解这一点，找几本关于线性代数和量子力学的书，然后舒服一点。如果你想澄清一些，我会看看我能做些什么!

旁白 :为了更好地理解量子叠加的思想，请从概率的角度思考。想象一下，你抛一枚硬币，用手捕获它，盖住它，这样你就看不到它了。 作为一个非常微妙的比喻 ，硬币可以被认为是处于正面和反面“状态”的叠加:每个都有 0.5 的概率(当然，因为有两个状态，这些概率加起来为 1)。当你 Handlebars 拿开直接观察硬币时，它会坍塌成正面或反面状态，因此这种状态的概率变为1，而另一个变为0。我想，一种思考方式，是一组在观察之前平衡的尺度，此时随着我们对系统的了解增加并且一个状态变成“真实”状态，它会向一侧倾斜。

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

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