不久前我读到量子计算机可以在很短的时间内（我相信只有几分钟）破解当今使用的大多数类型的散列和加密。这怎么可能？我已经尝试阅读有关它的文章，但我迷失在a quantum bit can be 1, 0, or something else. 有人可以解释这与在没有所有花哨数学的情况下用简单的英语破解此类算法有何关系吗？
问问题
10934 次
10 回答
53
序言：量子计算机是我们还没有真正驯服到有用的地步的奇怪野兽。支撑它们的理论是抽象的和数学的，因此任何关于它们如何比经典计算机更高效的讨论都将不可避免地冗长而复杂。你至少需要对线性代数和量子力学有本科的理解才能理解细节，但我会尽量表达我有限的理解！
量子计算的基本前提是量子叠加。正如你所说，这个想法是一个量子系统（例如一个量子位，或qubit，一个普通位的量子模拟）不仅可以存在于0和1状态（称为系统的计算基态），而且也可以是两者的任意组合（因此每个都有与之相关的幅度）。当系统被某人观察到时，量子比特的状态会坍缩成它的一个基本状态（你可能听说过与此相关的薛定谔猫思想实验）。
正因为如此，一个量子比特寄存器有它自己的基本状态（这些是你可以观察到的寄存器所处的状态；想象一个经典的 n 位整数）。由于寄存器可以同时存在于所有这些状态的叠加中，因此可以将计算应用于所有寄存器状态，而不仅仅是其中一个。这称为量子并行。n2^n2^n
由于量子计算机的这一特性，它们看起来像是一颗灵丹妙药，可以比经典计算机更快地解决任何问题。但这并不是那么简单：问题在于，一旦你观察到你的计算结果，它就会崩溃（正如我上面提到的）只是其中一个计算的结果——你会失去所有其他的。
量子计算/算法领域就是试图通过操纵量子现象以比经典计算机上更少的操作来提取信息来解决这个问题。事实证明，很难设计出比任何可能的经典算法都快的“量子算法”。
你问的例子是量子密码分析。人们认为，量子计算机可能能够“破解”某些加密算法：特别是 RSA 算法，它依赖于找到非常大整数的质因数的难度。允许这种情况的算法称为 Shor 算法，它可以分解具有多项式时间复杂度的整数。相比之下，该问题的最佳经典算法具有（几乎）指数时间复杂度，因此该问题被认为是“棘手的”。
如果您想对此有更深入的了解，请阅读几本有关线性代数和量子力学的书籍，然后再适应一下。如果你想要一些澄清，我会看看我能做什么！
旁白：为了更好地理解量子叠加的概念，请考虑概率。想象一下，你掷硬币，用手接住它，盖上盖子看不到它。作为一个非常脆弱的类比，硬币可以被认为是正面和反面“状态”的叠加：每个状态都有 0.5 的概率（当然，由于有两种状态，这些概率加起来为 1）。当你把手拿开直接观察硬币时，它会塌陷为正面或反面状态，因此这种状态的概率变为 1，而另一个变为 0。我想这是一种思考方式，是一组在观察之前保持平衡的尺度，在这一点上，随着我们对系统的了解增加并且一个状态变为“真实”状态，它会向一侧倾斜。
当然，我们并不认为硬币是一个量子系统：出于所有实际目的，硬币具有确定的状态，即使我们看不到它。然而，对于真正的量子系统（例如被困在盒子中的单个粒子），我们不能这样考虑。在量子力学的常规解释下，粒子基本上没有确定的位置，而是同时存在于所有可能的位置上。只有在观察时，它的位置才会在空间中受到限制（尽管只是在有限的程度上；参见不确定性原理），甚至这也是纯粹随机的并且仅由概率决定。
顺便说一句，量子系统并不局限于只有两个可观察的状态（那些被称为两能级系统）。有的有一个大但有限的数，有的有可数的无限数（如“盒子里的粒子”或谐振子），有的甚至有不可数的无限数（如自由粒子的位置，即'不限于空间中的单个点）。
于 2010-05-04T20:56:43.370 回答
3
维基百科的文章很好地解释了这一点。
简而言之，如果你有 N 个比特，你的量子计算机可以同时处于 2^N 个状态。在概念上类似于使用传统位进行 2^N CPU 处理（尽管不完全相同）。
于 2010-05-04T20:52:43.457 回答
3
在这一点上，这是高度理论化的。Quantum Bits 可能会提供破解加密的能力，但显然还没有到那个时候。
在量子层面，支配行为的规律与宏观层面不同。
要回答您的问题，您首先需要了解加密的工作原理。
在基本层面上，加密是两个极大素数相乘的结果。这个超大的结果可以被 1、它本身和这两个素数整除。
破解加密的一种方法是通过素数分解来暴力猜测两个素数。
这种攻击速度很慢，并且会因选择越来越大的素数而受阻。您听说过 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
同时。
当然，量子比特还没有到那个地步。该领域还有很多工作要做；但这应该给你一个想法，如果我们可以使用量子编程，我们将如何破解加密。
于 2010-05-04T20:59:06.983 回答
1
量子计算机可以实现Shor 算法，该算法可以快速执行素因数分解。加密系统是建立在这样的假设之上的：在经典计算机上，大素数不能在合理的时间内被分解。
于 2010-05-04T20:53:20.723 回答
0
用最基本的术语来说，普通的非量子计算机通过使用布尔逻辑对位（开或关的状态）进行操作来工作。您可以非常快速地处理大量比特，并且可以解决一类可计算问题中的任何问题。
然而，它们是“速度限制”，即所谓的计算复杂度。这用通俗的话来说意味着对于给定的算法，您知道运行算法所需的时间（以及运行算法所需的内存空间）具有最小界限. 例如，O(n^2) 的算法意味着对于 n 的数据大小，它将需要 n^2 时间来运行。
然而，当您对可能具有“中间”值的 qbits 进行操作时，当我们拥有 qbits（量子位）时，这种情况就会消失。具有非常高计算复杂度的算法（例如分解大量数字，破解许多加密算法的关键）可以以低得多的计算复杂度完成。这就是量子计算能够比普通计算机更快地破解加密流数量级的原因。
于 2010-05-04T20:58:08.753 回答
0
首先，量子计算还勉强走出了理论阶段。大量的研究正在进行，一些实验性的量子电池和电路正在进行，但“量子计算机”还不存在。
二、阅读维基百科文章： http ://en.wikipedia.org/wiki/Quantum_computer
特别是，“一般来说，具有 n 个量子位的量子计算机可以同时处于多达 2^n 个不同状态的任意叠加（这与在任何时候只能处于这 2^n 个状态之一的普通计算机相比） ）。”
使密码学安全的是使用非常长的数字的加密密钥，这将需要非常非常长的时间来分解它们的组成素数，并且密钥足够长，以至于暴力尝试尝试每个可能的密钥值会也需要很长时间才能完成。
由于量子计算可以（理论上）代表少量量子比特单元中的许多状态，并同时对所有这些状态进行操作，因此似乎有可能使用量子计算来执行蛮力尝试所有可能的-在很短的时间内完成键值。
如果这样的事情是可能的，它可能是我们所知道的密码学的终结。
于 2010-05-04T21:04:23.510 回答
0
量子计算机等都是谎言。我不相信这些科幻杂志。 事实上 rsa 系统是基于两个素数和它们的乘法。p1,p2 是巨大的素数 p1xp2=N 模数。rsa系统就像选择一个素数..也许它的E公钥（p1-1）*（p2-1）=R找到一个D数，使E*D=1 mod（R）我们共享（E ,N) 数据作为公开密钥，我们将 (D,N) 安全地保存为私有密钥。
要解决这个 Rsa 系统破解者需要找到 N 的质因数。 *宇宙的质量更接近 10^53 公斤* 电子质量是 9.10938291 × 10^-31 公斤 如果我们将宇宙划分为电子，我们可以创造 10^84 个电子. 电子的速度比光慢。如果有人从所有宇宙质量中产生电子大小的平行 rsa 素因子探测器，它的移动频率可以是 10^26 。所有宇宙都可以处理 (10^84)*(10^26)= 10^110 个数字/每秒。
rsa 有无限位的替代素数。也许 4096 位 4096 位 rsa 有 10^600 个可能的素数来蛮力。所以你的宇宙质量量子求解器需要在 10^500 年内进行测试。
rsa vs 宇宙质量量子计算机 1 - 0
也许量子计算机可以破解 64/128 位密码。因为 128 位密码有 10^39 个可能的暴力破解节点。
于 2014-01-03T14:56:17.327 回答
0
该电路是了解量子位并行性如何工作的良好开端。2-qubits-input 在左侧。顶部量子位是 x，底部量子位是 y。y 量子位在输入处为 0，就像一个普通位一样。另一方面，x 量子比特在输入端处于叠加态。y (+) f(x) 在这里代表模2加法，只表示1+1=0, 0+1=1+0=1。但有趣的是，由于 x-qubit 处于叠加状态，f(x) 同时为 f(0) 和 f(1)，我们可以同时对所有状态执行 f 函数的评估，而无需使用任何（耗时）循环。拥有足够多的 quibits，我们可以将其分支为无限复杂的 curcuits。
于 2018-03-20T03:29:41.873 回答
0
更奇怪的是imo。是格罗弗算法。作为输入，我们在这里得到一个未排序的整数数组，arraylength = n。找到这个数组的最小值的算法的预期运行时间是多少？经典地，我们至少要检查数组的每个 1..n 元素，从而得到预期的 n 运行时间。对于量子计算机而言并非如此，在量子计算机上，我们可以在最大根（n）的预期运行时间中解决这个问题，这意味着我们甚至不必检查每个元素来找到有保证的解决方案......
于 2018-03-20T03:43:32.077 回答