用 Shor 算法以量子速度进行黑客攻击 | Infinite Series

Hacking at Quantum Speed with Shor's Algorithm | Infinite Series

频道:PBS Infinite Series · 时长:16:36 · 发布:2017-04-28 · 播放:238532

在 YouTube 观看

简介

PBS Infinite Series 解释了 Shor 算法如何让量子计算机破解 RSA 加密,建立在之前关于密码学和量子计算机数学的剧集之上。它逐步推导了这个想法。

HN 为什么推荐

HN 推荐它作为对 Shor 算法的清晰、详细的解释,以建立直觉。

我认为这个 Shor 算法的例子相当不错 — HN, 2019

密码学 · 量子计算

中文字幕节选

量子计算机如何可能摧毁计算机安全? 通过利用Shor算法。 [音乐播放] 上周,我们取得了巨大进展 朝着破解加密信息的目标迈进。 记住,流行的密码学形式 通过将两个大质数相乘 并使用这些质数作为密钥来恢复信息。 所以,要破解密码,我们需要找到一个非常大数的质因数。 但这对经典计算机来说需要很长时间。 远远超过加密信息可能的有用期限。 但Shor算法允许我们快速分解大数 使用量子计算机。 要了解Shor算法的概要和整体图景, 请查看上周的剧集。 之后,回到这里,因为我们 即将深入探讨该算法的量子部分。 为此,这也将有所帮助 如果你对量子计算机的工作原理有一些背景知识。 幸运的是,我们也有一个关于这个的剧集。 有一个流行的观念,即量子计算机只是 一堆经典计算机并行工作。 这有点对也有点错。 让我们看看如何。我们将从查看一台经典计算机开始。 它找到数字N的因数的最直接方法是什么? 嗯,它可以检查。2是因数吗,3是因数吗,4是因数吗,等等。 但如果N很大,这可能需要很多步骤。 现在,如果量子计算机只是 一堆经典计算机并行工作, 那么我们可以让一台计算机检查2是否是因数, 另一台检查3是否是因数,等等。 那么它只需要两步。 我们已经将经典计算机的许多步骤 分配到量子计算机的许多并行计算中。 问题来了。当我们说量子计算机是 一堆经典计算机并行工作,我们 真正意思是量子计算机是 处于基本状态的叠加态,这些 是经典计算机可能处于的状态类型。 记住,叠加态是基本状态的组合 并且观察每个状态都有一定的概率。 要找到那个概率,你需要平方 基本状态前面的数字的振幅。 这里,我们有N个基本状态和一个1 除以N的概率处于每个状态。 所以量子计算机实际上并不处于所有这些状态。 更像是量子计算机将自己分裂成N个不同的部分。 但当你测量量子计算机时,也就是说, 询问计算结果,它不会告诉你它处于的所有N个部分。 相反,它会选择一个状态,每个概率为1除以N, 并告诉你那个状态说了什么。 你不能看到整个东西。 只是一个随机状态。这对我们来说是个问题。 只有N个状态中的两个给出真正有用的信息。 即检查的数字是N的除数。 所以绝大多数时候我们运行计算, N减2除以N的时候,结果只会告诉你某个东西不是 N的因数。这意味着我们的算法 并不比使用经典计算机检查随机数 看它们是否是除数更高效。 为了利用量子计算的能力,我们需要这些基本态中的每一个, 也就是叠加态的各个分量,协同工作。 目前,它们就像独立的计算机一样运行, 各自独立搜索,这就有问题了,因为量子 计算机无法告诉我们所有这些独立状态的信息。 但如果这些状态之间存在某种底层结构, 我们就可以利用它来放大那些包含正确答案的状态。 在这个例子中,就是那些能给出数字因子的状态。 这样,当我们测量量子态时,就有很高的概率得到 正确答案。事实上,理论计算机科学家 Scott Aaronson 写的一篇精彩

HN 上的讨论

我推荐Charles Petzold的《编码》: [LINK] 它非常出色地从比特一直构建到加法器、CPU和汇编语言(还附带历史背景)。我认为,了解量子计算及其区别的最简单方法是看一个具体例子,我觉得这个Shor算法的例子相当不错:[VIDEO] — fossuser, 2019-10
并不是说它们能在传统意义上更快地执行计算。而是你可以在某些类型的计算中(例如分解质数)利用量子行为,使答案更可能,从而在读取量子计算机状态时更可能被“观察到”,因此与传统算法相比更容易定位正确答案。PBS Infinite Series有几个关于量子计算和Shor算法的视频:1. [LINK] “量子计算机的数学” 2. [LINK] “如何破解密码学” 3. [VIDEO] “用Shor算法以量子速度黑客” — msclrhd, 2018-11
你应该看看这些视频,其中一个可能会让你理解!- [LINK] | 量子计算机解释 - [LINK] | 量子计算机的数学 - [VIDEO] | 用Shor算法以量子速度黑客 - [LINK] | 标准教科书作者的一个系列 这些是我特别喜欢的视频! — adamisntdead, 2018-04
给精明人的提示:量子计算机并不是一个神奇地翻转到正确答案的魔法比特串。一个n量子比特的量子计算机并不像2^n个幽灵计算机同时运行在某种量子叠加幽灵区中。这是流行的误解,但实际上是无知的技术胡扯。以下是真实情况。如果你有一串n量子比特,当你测量它们时,它们可能随机地最终处于2^n种可能配置中的一种。然而,如果你使用量子门对n量子比特串应用一些操作,你可以有效地偏置它们的波方程,使得某些配置的概率更可能出现。(然而,你不能有太多这样的操作,因为那会有退相干的风险。)希望你能以这样的方式做到这一点,即偏置的配置是你想要解决的问题的答案。那么,如果你有这样一个设置的量子计算机,你可以运行它很多次,如果一切顺利,经过足够多的迭代,你将能够注意到比特串某些配置的偏置。如果你能足够频繁地做到这一点以获得统计显著性,那么你就可以相当确信你找到了答案。[LINK] [VIDEO] 编辑:我相当喜欢Issa… — stcredzero, 2018-02

相关视频