PROSAGA码农传奇-量子算法-量子计算和加密破解

序言：量子计算机是我们还没有驯服到有用性的怪兽。支撑它们的理论是抽象的和数学的，因此，关于它们如何比传统计算机更有效的任何讨论都将不可避免地涉及很多时间。您至少需要本科生对线性代数和量子力学的理解才能理解细节，但是我将尽力传达我的有限理解！

量子计算的基本前提是量子叠加。想法是，如您所说，量子系统（例如量子位或qubit，即正常位的量子类似物）不仅可以存在于0和1状态（称为系统的计算基础状态），而且可以存在也可以将两者任意组合（以使每个振幅都有关联）。当某人观察到该系统时，量子位的状态会崩溃成其基本状态之一（您可能已经听说了薛定ding的猫思维实验，与此有关）。

正因为如此，一个寄存器的n量子位有2^n其自身的基态（这些是美国，你可以观察寄存器是，想象一个经典的正整数位）。由于寄存器可以一次以所有这些状态的叠加形式存在，因此可以对所有2^n寄存器状态而不是其中之一进行计算。这称为量子并行性。

由于量子计算机的这种特性，看起来它们是灵丹妙药，它可以比传统计算机更快地成倍地解决任何问题。但这并不是那么简单：问题是，一旦您观察到计算结果，它就会崩溃（如我上面提到的那样），成为仅一种计算的结果–而您将丢失所有其他计算。

量子计算/算法领域的全部内容是通过操纵量子现象以比传统计算机上更少的操作来提取信息，从而尝试解决该问题。事实证明，要想出一种“量子算法”，它比任何可能的经典方法都快，这是非常困难的。

您询问的示例是量子密码分析。人们认为量子计算机可能能够“破解”某些加密算法：特别是RSA算法，它依赖于找到非常大的整数的素因数的困难。允许这样做的算法称为Shor算法，该算法可以分解具有多项式时间复杂度的整数。相比之下，针对该问题的最佳经典算法具有（几乎）指数的时间复杂度，因此该问题被视为“ 棘手的 ”。

如果您想对此有更深入的了解，请阅读几本有关线性代数和量子力学的书籍，并感到自在。如果您想澄清一下，我会解决的！

另外：为了更好地理解量子叠加的概念，请考虑概率。想象一下，您掷硬币并将其盖在手上，以致看不到它。作为一个非常微妙的类比，该硬币可以被认为是头和尾“状态”的叠加：每个硬币的概率为0.5（自然，因为有两个状态，所以这些概率加起来为1）。当您将手移开并直接观察硬币时，它会崩溃成正面状态或反面状态，因此该状态的概率变为1，而另一种状态变为0。我想一种思考它的方式，是一组在观察之前保持平衡的比例尺，在该比例尺上，随着我们对系统的了解的增加，一个状态变为“真实”状态，它会向一侧倾斜。

当然，我们不认为硬币是量子系统：出于所有实际目的，即使我们看不到硬币，硬币也具有确定的状态。但是，对于真正的量子系统（例如被困在盒子中的单个粒子），我们无法以这种方式考虑它。在传统的量子力学解释下，粒子从根本上没有确定的位置，而是同时存在于所有可能的位置。只有在观察时，它的位置才会在空间上受到约束（尽管只是有限的程度；参见不确定性原理），甚至这纯粹是随机的，并且仅由概率决定。

顺便说一句，量子系统并不仅限于只有两个可观察的状态（确实被称为两级系统）。有些具有大但有限的数，有些具有无数的无限数（例如“盒子中的粒子”或谐波振荡器），有些甚至具有无数的无限数（例如自由粒子的位置，即不受限于空间中的各个点）。