量子计算和加密打破

Question

我读过一段时间后,昆腾计算机可以在很短的时间内打破大多数类型的散列和加密(我相信这只是几分钟).这怎么可能？我试过阅读有关它的文章,但我迷失了a quantum bit can be 1, 0, or something else.有人可以解释这是如何与普通英语破解这些算法没有所有花哨的数学？

Answer 1

序言:量子计算机是奇怪的野兽,我们真的还没有驯服到有用的地步.支撑它们的理论是抽象的和数学的,因此任何关于它们如何比传统计算机更有效的讨论都将不可避免地涉及很长时间.你需要至少一个大学生对线性代数和量子力学的理解来理解细节,但我会试着传达我有限的理解!

量子计算的基本前提是量子叠加.这个想法是,量子系统(如量子位,或量子位,正常位的量子模拟)可以,正如你所说,不仅存在于0和1状态(称为系统的计算基础状态),也可以是两者的任意组合(以便每个都具有与之相关的振幅).当系统被某人观察时,量子比特的状态会崩溃到其基本状态之一(您可能听说过薛定谔猫的思想实验,这与此有关).

正因为如此,一个寄存器的n量子位有2^n其自身的基态(这些都是你可以观察到寄存器是在美国;想象一个经典的正整数位).由于寄存器可以同时存在于所有这些状态的叠加中,因此可以将计算应用于所有2^n寄存器状态而不仅仅是其中之一.这称为量子并行.

由于量子计算机的这种特性,它看起来像是一颗银弹,可以比传统计算机指数级地快速解决任何问题.但事情并非如此简单:问题在于,一旦你观察到你的计算结果,它就会崩溃(如上所述)到一个计算的结果中 - 你就会失去所有其他的计算结果.

量子计算/算法领域就是通过操纵量子现象以比在经典计算机上更少的操作中提取信息来尝试解决这个问题.事实证明,设计比任何可能的经典对应物更快的"量子算法"是非常困难的.

你问的例子是量子密码分析.据认为,量子计算机可能能够"破坏"某些加密算法:特别是RSA算法,它依赖于找到非常大整数的素因子的难度.允许这种情况的算法称为Shor算法,它可以将整数与多项式时间复杂度进行因子分解.相比之下,该问题的最佳经典算法具有(几乎)指数时间复杂度,因此该问题被认为是" 难以处理的 ".

如果你想更深入地了解这一点,可以阅读一些关于线性代数和量子力学的书籍并获得舒适.如果你想澄清一下,我会看到我能做些什么!

旁白:为了更好地理解量子叠加的概念,请考虑概率.想象一下,你翻转一枚硬币并将它抓在手上,盖上盖子以便你看不到它.作为一个非常脆弱的类比,硬币可以被认为是头尾的"状态"的叠加:每个人的概率为0.5(当然,因为有两种状态,这些概率加起来为1 ).当你把手拿开并直接观察硬币时,它会折叠成头状态或尾状态,因此这种状态的概率变为1,而另一种变为0.我猜想,有一种方法可以考虑它.是一组在观察之前保持平衡的尺度,此时它向一侧倾斜,因为我们对系统的了解增加,一个状态变为"真实"状态.

当然,我们不认为硬币是一个量子系统:对于所有实际目的,即使我们看不到,硬币也有一定的状态.然而,对于真正的量子系统(例如被困在盒子中的单个粒子),我们不能以这种方式考虑它.在量子力学的传统解释下,粒子基本上没有明确的位置,但同时存在于所有可能的位置.只有观察它的位置才会受到空间的限制(虽然只是在有限的程度上;参见不确定性原理),甚至这只是随机的,只能通过概率来确定.

顺便说一句,量子系统不仅限于只有两个可观察状态(那些被称为两级系统).有些有一个很大但有限的数字,有些有一个可数无限的数字(例如"盒子中的粒子"或谐波振荡器),有些甚至有一个无数的无限数(例如自由粒子的位置,这是不受空间中各个点的限制.