Transcription
许多科普类媒体对量子计算的总结，我几乎可以肯定地说，这会导致误解。总结大致是这样的。在经典计算机中，数据以比特的形式存储，即一串零和一。但在量子计算机中，你能够一次性地在一个被称为“叠加”的大整体中表示出固定长度的所有可能的比特序列。而这些总结有时暗示，量子计算机之所以能更快，是因为它们基本上能以并行的方式执行经典计算机所做的任何事情。
现在，这确实触及了某些真实之处。但请允许我尝试向你证明，为什么我认为这会导致误解。我将通过一个测验来证明。为了铺垫，我想让你想象我有一个神秘函数，我告诉你，在从0到n-1的所有数字中，有一个特定的秘密数字，如果你将这个值代入我的函数，它会返回真。但如果你代入任何其他值，它都会返回假。而且，假设你无法查看函数的内部来了解任何信息。你唯一能做的就是用数字来测试它。
热身问题是，平均而言，你需要调用这个神秘函数多少次才能找到秘密密钥？好吧，如果是在普通的经典计算机上设置，你确实没有比猜测和检查更好的方法了。你遍历所有数字，也许你运气好，早早就找到了。也许你运气不好，直到后面才找到。但平均而言，对于一个包含n个可能性的列表，找到密钥需要n/2次尝试。
在计算机科学中，人们关心运行时间的扩展性。如果列表大10倍，需要多长时间？计算机科学家有一种方法来对运行时间进行分类。他们会称之为O(N)，其中大O表示可能存在一些常数，比如1/2，或者一些增长速度慢于N的因子。但N这个因子解释了随着N的增长，它会如何快速扩展。如果N增加了10倍，运行时间也增加10倍。
现在，这是给你的测验：对于经典计算机设置的等价情况，但在量子计算机中，找到秘密密钥的最佳运行时间是多少？在我多年来给出的某个讲座中，我问过这个测验的一个变体很多次。我通常提供的选项是O(√N)、O(log N)、O(log log N)和O(1)，其中O(1)表示运行时间只是一个不随N增长的常数。
现在，公平地说，我还没有定义量子计算。事实上，从头开始定义它将是本视频的目标。所以，在不向你展示这个神秘函数在那种设置下会是什么样子的情况下，这个问题有点不连贯，但它并不是真的 meant to be 一个我正在评分的测验，或者别的什么。它只是 meant to be 在我们深入之前，对直觉进行一次“腹部检查”。原则上，这是相同的任务，就像在干草堆里找一根针一样，你想在众多选项中找出哪个值能唯一地触发某个函数。
上个月我把这个问题作为一个YouTube帖子发出去，有10万人 kindly 回答了。我最近一次现场提问是在一个斯坦福大学的学生群体中。我还把它问给了参加国际数学奥林匹克竞赛的人。在所有这些以及许多其他场合，答案的分布看起来非常相似。最常见的答案总是O(1)。这是错误的。而且我相当确定，这源于那个误导性的总结。那个总结暗示你会把所有你需要搜索的N个值放入这个神秘的叠加态中。然后你会并行处理它们，然后某种方式答案就会被揭示出来。
第二个最常见的答案通常是O(log N)。这同样是错误的。你会称之为指数级加速。例如，如果你将列表的大小增加10倍，O(log N)的运行时间每次只会增加相同的加法增量。现在，我怀疑这个错误的答案源于对量子计算机总体上有多大优势的误解。在某些非常特殊的问题上，你可以实现指数级加速。最著名的例子可能是Shor的算法，用于分解大数，但大多数问题并非如此。
在这种情况下，正确的答案是O(√N)。这更能代表你用量子计算机获得的典型加速。1994年，人们证明了量子计算机在这个任务上不可能做得比O(√N)更好。然后两年后，Lov Grover找到了一个实际达到该运行时间的特定过程。因此，搜索一百万个选项需要大约一千步。搜索一万亿个选项需要大约一百万步。
这个大O实际上隐藏了一些非常有趣的东西，那就是精确运行时间中的π/4常数。而这个π本身也有一个完整有趣的故事要讲，我稍后会讲到。你可能会认为，这个由一个特定值触发的神秘函数的谜题是极其牵强的，但我希望你记住，这 meant to be 是一个通用的替代品，适用于任何你知道如何快速验证一个解，即使你一开始不知道如何找到那个解的问题。这描述了计算机科学中一个庞大的问题类别，称为NP问题。因此，虽然平方根加速坦率地说不如指数级加速那样具有颠覆性，而且大O运行时间通常比其他实际考虑因素不那么重要，但像Grover算法这样能够为任何NP问题提供这种通用加速方法的东西，本身就引人深思。
我本课的目标是逐步讲解那个算法是如何工作的。它实际上非常几何化，也非常优美，但我们需要积累大量的背景知识才能达到那里。视频的前2/3左右将用于建立量子计算的基础。不是用一套类比，正如我们所见，类比可能导致误解，而是作为数学的一部分，我认为它为你提供了一副眼镜，让你能更诚实地看待整个领域。这是那些有一些前提的课题之一，这些前提一开始会让你觉得有点奇怪，我应该警告你，它们需要一点时间来适应。我目前的计划是，在本课之后再讲一个关于一些底层物理学的课程，希望能帮助解释你在这里看到的一些奇怪规则。但今天，目标是提供一个最小可行路径，让你看到一个真正合法的量子算法。
让我们再次对比经典计算和量子计算，看看我们是否能建立一个更具代表性的心智模型。当然，经典计算机中的数据看起来是一系列的零和一，在更高层次的抽象中，这可能代表一个实际的数据类型，如整数或文本，而在更低层次的抽象中，这些零和一代表物理世界中的实际事物，如电容器上的电压或类似的东西。
现在，这些相同的抽象层次在讨论量子计算时也提供了非常有用的框架。在那里，也有一些底层的物理测量，同样，你用一系列零和一来表示测量的结果。同样，这可能实现了你关心的某个实际数据类型，比如一个数字。顺便说一句，我展示的这个符号叫做“ket”。我会在几分钟内正确解释它，但现在你只需认为它传达了某种东西来自量子计算机。
让我们从中间抽象层面的角度来描述量子计算。也就是说，我们暂时推迟所有底层物理学，这有点像在不讨论硬件的情况下教授计算机科学。在经典计算机中，没有必要区分内存的状态和你从内存中读取的内容。它们看起来都是相同的比特序列。但在量子计算机中，情况完全不同。我们今天的主要任务将是理解所谓的“状态向量”，它是连续的。这是计算机实际操作的东西。但它与你实际读取的离散比特序列有着非常不寻常的关系。
在我能定义这个状态向量之前，你需要知道与经典计算机的另一个关键区别，那就是你读取的这个值，它看起来仍然是一串零和一，是随机的。或者更准确地说，我应该说它通常是随机的。你可以这样想：如果你在量子计算机上运行一个程序，那个程序不一定会确定一个特定的输出。相反，它会确定一个跨越所有可能输出的概率分布。所以，对于我在屏幕上展示的例子，这将是一个非常小的量子计算机，你读取的东西有四位，这意味着有2的4次方或16种可能的输出。而你运行的特定程序决定了所有这些可能输出的某种分布。有些程序可能会设法将更多的概率集中在一个输出上，但其他程序可能会在所有输出之间提供更均匀的分布。
顺便说一句，这个你读取的东西有四位的例子将被称为4QIT量子计算机。更一般地说，如果你有一个kQIT量子计算机，这意味着有2的k次方个不同的可能输出，任何程序都会提供一个跨越所有这些输出的分布，而你读取的东西有k位。顺便说一句，这个词“qubit”是我将在几分钟内更精确地定义的另一件事。
我确实想强调，这个分布是隐含的。你永远无法直接看到它。你而是根据你运行的程序来推断它必须是什么。你永远不会同时看到所有比特串以某种方式共存。你只会看到一个根据这个分布随机抽取出来的比特串。
在更低的抽象层面上，我所描述的从内存中读取就像物理测量。而随机性源于量子力学的定律。如果你对物理学感兴趣，那个更低的抽象层面，那正是下一个视频的内容。在这个层面之上，你只需考虑所有可能比特串的概率分布。
现在，这里还有一个有趣的规则，它确实源于底层的量子力学，那就是在你从内存中读取并看到某个特定值之后，计算机的底层状态会发生变化，以至于现在所有的概率都集中在你读取的那个值上。所以，如果你一遍又一遍地从内存中读取，你只会看到相同的值。你可以想象这些程序创建了一个非常微妙和敏感的概率分布，当你查看它，从该分布中采样时，整个东西就会崩溃成一个值。
现在你可能会想，这个分布从何而来？这是最重要也是最令人困惑的部分。你认为计算机的状态是由一个大向量描述的。现在我说“向量”这个词时，你只需将其视为一个大数字列表。尽管正如你稍后将看到的，将其视为超高维空间中的一个方向可能很有帮助。这个向量的每个分量都对应于你可能读取的每个可能值，那些不同的比特串。所以，在这个例子中，你读取的东西有四位，状态向量将有16个不同的分量。
状态向量与所有可能输出的概率分布不是同一回事，但它们非常密切相关。基本规则是，我承认一开始会看起来非常奇怪，那就是如果你取状态向量中每个分量的模长并将其平方，你就会得到看到相应输出、相应比特串的概率。我先说清楚，很多学习量子计算的人觉得这个状态向量有点奇怪。它到底是什么？为什么我们要平方来得到概率？
就目前而言，为了简单起见，我忽略了一个重要的细节，直到视频的最后。我只想提醒你，对大多数人来说，这需要一点时间来适应。为了非常清楚地说明我在这里的基本规则的意思，假设在这个程序处理完这个向量之后，也许与某个特定比特串相关的分量，比如我不知道的0011，碰巧是0.5。那么当你平方这个值0.5的平方是0.25。因此，可观察到的影响是，当你从内存中读取时，你有25%的机会看到那个比特串0011。
我将强调的一点是，状态向量中的值可以是负数，这是完全有效的。起初你可能会认为这没有实际影响，因为改变符号不会改变平方值，因此所有概率都保持不变。确实，概率保持不变，但我们绝对认为这是一个不同的状态。而且正如你将看到的，改变符号的想法在Grover算法中起着核心作用。
这个包含四个量子比特的例子屏幕上信息量很大，但可视化支持却不多。所以让我们缩小到最小的情况，即计算机只有两个可能的输出，用0和1表示。在这种最简单的情况下，状态向量将是二维的。所以我们可以将其几何地表示为二维空间中的一个箭头。在这种情况下，x坐标对应于0这个结果，因为该坐标的平方告诉你，当你从计算机读取时，你读到0的概率。这里，也许加上一个小条来表示这个概率会很有帮助。你会注意到，当向量更多地指向水平方向时，更多的概率集中在0上。同样，y坐标也以相同的方式对应于1。一个更垂直的状态向量意味着当你从计算机读取时，你更有可能看到1。
现在请注意，因为两个概率加起来应该等于1。毕竟，总会发生什么。X^2 + Y^2 应该等于1。从几何上看，这意味着状态向量的长度是1。所以你可以认为它被限制在一个单位圆上。更一般地说，量子计算机的状态向量的长度总是1。你可以认为它存在于某个非常高维的单位球体上。
这个二维例子有一个特殊的名字，我已经提过了。它叫做Qubit，是量子比特的缩写。与经典比特的类比是，当你从计算机读取时，你看到的是0或1。但除此之外，它是一个完全不同的东西。在数学上，一个量子比特是二维空间中的一个单位向量，以及一个坐标系，其中这两个垂直的x和y方向对应于你测量时可能读取的两个值。你应该知道，我推迟了那个额外的复杂性，但这已经是90%的正确想法了。同样，你也有这个有趣的规则，当你测量量子比特，看到0或1时，向量就会坍缩到那个相应的方向。所以，除非采取措施将那个量子比特准备成一个对角方向，否则你之后做的任何观察都将总是显示相同的结果。
此时你很可能在想：“好吧，承认吧，你要求我接受的是一套非常奇怪的前提。”如果你是这样想的，你并不孤单。正如你可能已经猜到的，我所描述的基本上是量子力学的公设。物理学中有许多系统，如电子的自旋或光子的偏振，都具有这种性质，即测量的结果是随机的，而我们最好的物理定律让我们用一个向量来模拟该系统的状态，就像我在这里描述的那样，向量分量的模长平方给出看到各种可能结果的概率。这实际上有一个特殊的名字。它被称为玻恩定则。
这个量子比特的概念基本上是为了抽象许多这样的系统，就像比特是为了抽象许多可以切换两个方向的物理系统一样。顺便说一句，我一直在展示的符号在任何带有“量子”一词的学科中都用来指代状态空间中的单位向量。而你放在ket里面的东西通常会给出某种可读的含义，说明该向量代表什么。所以，在我们量子比特的例子中，右边的单位向量通常用ket中的零来表示，因为如果那是状态向量，就意味着你从计算机中确定性地读取了一个零。同样，垂直方向的单位向量用包含一的ket来表示。如果你继续阅读，你会经常看到，与其像我一直展示的那样用列向量写下一个通用的量子比特，很多人喜欢将其写成这两个单位向量在两个坐标方向上的显式加权和。这是一种非常物理学的约定。
现在，经典计算有逻辑门的概念。像AND、OR和NOT这样的基本操作，你可以用它们来处理比特，并将它们串联起来创建任意复杂的函数。类似地，我们有所谓的量子门，它们是一些基本操作，你可以将其应用于一个量子比特或多个量子比特的系统。它们总是看起来像是以某种方式翻转或旋转状态向量。
我不会深入探讨所有不同量子门的细节，但如果你好奇，我将向你展示其中一个的样子。这是一个非常标准的，称为Hadamard门。它的作用是将水平零方向的单位向量映射到对角的东北方向，并将垂直一方向的单位向量映射到东南方向的对角方向。你通常会用它来将一个确定性状态，即0或1，变成一个50/50的均等平衡状态，反之亦然。这只是一个例子，还有许多其他例子构成了量子计算的基础。而在这个设置中编写算法的艺术在于，如何将一堆不同的量子门组合起来，逐步操纵、翻转和调整这个向量，直到它几乎完全指向某个特定的坐标方向。大概是那个能回答你关心的问题的方向。
现在，在最简单的量子比特例子中，你只有两个坐标方向可以工作。所以你将被限制回答简单的“是/否”问题。虽然我无法用超过三维来展示几何向量，但原则上，一个包含k个量子比特的系统将有2的k次方个不同的坐标方向，每个方向对应一个比特串。所以，如果你能以某种方式将这个向量强制指向其中一个方向，你就有可能回答一些更复杂的问题，承载更多信息。也许其中一个代表你试图分解的一个非常大的数字的素数因子。或者其中一个代表本视频开头谜题中的那个秘密密钥值。
尽管量子计算机的潜在能力有着悠久的被大大夸大的传统，因为确实可能存在更多的能力，但一个关键原因是状态向量的大小呈指数级增长。仅仅100个量子比特就已经意味着一个令人难以置信的庞大数据向量。但关键在于，你无法直接访问这个向量中的值。它对你来说基本上是不可见的。它唯一有用的方式是，如果你有一种方法可以操纵它，使得所有概率，或者至少大部分概率，都集中在一个单一的分量上，并且那个分量对应于你关心的问题的答案。
Grover算法提供了一个很好的例子，让我们实际看看它是如何实现的。现在是时候了。让我给你一个非常高层次的预览。我保证会详细解释这一切，但这是鸟瞰图。它初始化状态向量，使得所有可能输出的概率都处于均等平衡状态。其中一个输出将是你正在寻找的秘密密钥。而你将拥有的工具，我保证稍后会解释其原理，就是翻转该坐标处状态向量的符号。现在这不会立即影响概率。但当你将其与另一个操作交错进行，并且你来回进行这两者时，发生的事情是，概率质量开始缓慢地集中在那个秘密密钥值上，在某个点上几乎全部在那里。所以当你从计算机读取时，你几乎肯定会看到你正在寻找的秘密密钥。
好的，这是高层次的概述，但让我们更详细地探讨一下。首先要解决的是翻转与秘密密钥相关的分量的符号这个想法。这可能感觉有点奇怪。为什么我们要假设这个操作对我们可用？回想一下，Grover算法 meant to be 应用于任何你可以快速验证解的问题，即使找到解本身很困难。这里的例子包括解数独，找到地图的一个有效着色，其中没有两个相邻区域共享颜色，或者密码学中的无数任务，其安全性通常取决于某个值难以找到，尽管出于实用性，它必须易于验证。
我们从一个通用的替代品开始，代表所有这些问题，你想象一个函数，它接受从0到n-1的任何数字，并只在一个数字上返回真。原则上，我们将这种函数视为由一堆经典逻辑门构成。这些逻辑门作用于输入的某种二进制表示，最终输出是0或1。现在，关键点来了。Grover知道，给定任何一组这样的逻辑门，你可以将其翻译成一套量子门。因此，在经典情况下，函数接受某种二进制输入并返回1表示真，那么在量子情况下，所有这些门的效果就是翻转与相同比特串相关的状态的符号。然后类似地，如果在经典情况下，函数将某种二进制输入映射到0表示假，那么在这个量子翻译中，对相应状态的效果就是保持不变。然后更一般地说，因为所有这些量子操作都是线性的，如果状态是多个纯坐标方向的组合，那么效果就是简单地翻转与触发该经典函数的任何比特串相关的分量的符号。这意味着，如果你有任何NP问题，任何你可以快速验证解的问题，你就能在量子计算机上创建一个操作，翻转与该问题解对应的位置的状态向量的符号。
这起初可能感觉有点无用。毕竟，翻转符号不会影响概率。但Grover意识到，这可以与另一个步骤结合使用，该步骤会缓慢地放大该密钥值的概率。而且有一个非常好的方法可以可视化他的算法。为了铺垫，让我们假设我们的状态向量只有三个维度。显然，原则上，它会大得多，但这让我可以画出第一张图。这里的三个方向将对应于值0、1和2。而整个问题陈述是，其中一个值将是我们正在寻找的秘密密钥。
许多不同的量子算法将以将状态向量置于一种均等平衡状态开始，其中所有分量都具有相同的值。我想给这个均等平衡向量起个名字。我们称之为B。我希望你不要太介意我只是声明这是可能的，而不纠结于实现它的底层量子门。在这种情况下，它基本上看起来像一大堆Hadamard门。但你只需要知道，这个均等平衡方向是极其容易获得的。
所以，从这里开始，目标是某种方式将这个向量强制改为指向秘密密钥方向。而对于可视化来说，非常有用的是，在整个Grover算法中，向量只在由这两个向量张成的二维平面内移动。所以我要把所有东西都画在这个二维切片上。这将为我们提供一个忠实的表示，即使当维度太高以至于我无法实际绘制时也是如此。我将使用的约定是，将秘密密钥方向（无论它是什么）放在这个y轴上。然后x轴将代表一个所有其他状态（非密钥状态）的均等平衡。所以，在我们非常小的三维例子中，如果秘密密钥是z方向上的状态2，那么这意味着垂直方向是0和1的均等平衡，它位于垂直于z轴的xy平面上。
请注意，完全均等平衡状态B在秘密密钥方向上具有一定的分量，因为根据定义，它包含一点秘密密钥。与其从三维绘制这个切片，不如看看如果它取自某个更大的维度会是什么样子。它几乎相同，但主要区别在于，那个均等平衡状态向量越来越接近于垂直于秘密密钥方向。然而，关键是，这个角度永远不会是90°，因为平衡状态总是包含一点秘密密钥值。事实上，计算这个角度对于理解Grover算法的运行时间至关重要。这是你必须做的主要数学。你可以通过计算平衡状态和密钥方向之间的点积来找到这个角度。
这个平衡状态向量的分量看起来都是1/√N。因为记住，当你将所有这些分量的平方相加时，它应该等于1。由于密钥向量几乎处处为零，但在一个分量上为1，这意味着这两个向量的点积是1/√N。如果你对点积有点了解，你会知道这也就是这两个向量之间夹角的余弦值。我将稍微翻译一下这个事实，使其对我们以后的目的更有用。这与说下面这个补角的正弦值，我称之为θ，是1/√N是相同的。而对于非常小的角度，sin(θ)和θ近似相等。所以，如果N非常大，我们可以安全地说，只要以弧度为单位，这个角度大约是1/√N。这个θ值最终将是运行时间中平方根的来源。所以让我们记住它。我把它放在角落里。
好的，花了不少时间设置好实际的图景，让我来展示一下这个过程。它非常简单。还记得我们之前看过的那个密钥操作吗？那个你将要解决的任何NP问题的验证函数，并将其翻译成一些量子门，效果是翻转与那个密钥值相关的符号。那么，在我们的图表中它看起来是什么样的？在这个图表中，如果你翻转与密钥值相关的分量的符号，而所有其他分量保持不变，它看起来就像是关于x轴的翻转。而你需要知道的最后一个要素是，也可以围绕这个均等平衡方向翻转这个状态向量。我承认，我不断声明某些操作可用可能会让人觉得有点不满意。但有一点要知道的是，一般来说，如果你能清楚地描述并访问其中一个状态向量，那么围绕它进行反射也是完全可能的。有一些量子门。它们允许你围绕这个平衡方向进行翻转。但相信我，纠结于它们具体外观的细节并不会给整个算法增加多少清晰度或直觉。洞察力真的只来自几何。
请注意，如果你先绕x轴翻转，然后绕这个非对角方向翻转，状态现在稍微更指向垂直方向。如果你现在从内存中读取，你看到秘密密钥值的几率会比其他值稍大一些。这里，也许加上实际坐标会很有帮助，以n=100为例，以及基于坐标平方的一些概率条。请注意，每次我绕x轴翻转，然后绕这个非对角轴翻转时，与秘密密钥相关的分量都会稍微变大一些。
所以，Grover算法非常简单。你所做的就是一遍又一遍地重复这个过程，直到向量指向尽可能接近秘密密钥方向。最后一步推理是弄清楚需要重复多少次。几何学中一个奇妙的事实是，如果你连续绕两条不同的直线翻转，总效果就相当于一次旋转。更具体地说，是绕两条线之间角度的两倍的旋转。所以，在我们这个例子中，一个接一个地应用我们可用的两个操作。净效果是将状态向量旋转2*θ，其中θ是我们之前计算过的那个小角度，大约是1/√N。
最终目标是将我们的初始状态旋转不到90°，或者大约π/2弧度。这意味着最佳重复次数看起来是π/2 / 2θ，即π/4 * 1/θ。关键是，因为θ大约是1/√N。这意味着总步数看起来是π/4 * √N。所以Grover算法说的是，首先找到最接近这个值的整数，然后重复你的两个可用翻转，这个特定的次数。作为一个具体的例子，假设n是2^20，这意味着你在寻找大约一百万个选项中的一个秘密密钥。你将使用至少20个量子比特的计算机来运行它。算法会说，首先计算π/4 * √N，大约是804。这意味着你现在重复你可用的两个操作：翻转密钥状态的符号的操作，以及围绕平衡方向翻转的操作，重复804次。
现在请记住，这个状态向量对你是不可见的。你无法做任何事情来读取它所拥有的值。你必须通过推理来推断它必须在哪里。在这种情况下，通过所有的几何推理，你可以得出结论，在特定的次数之后，向量应该几乎完全指向那个秘密密钥方向。所以当你从计算机读取时，你几乎可以肯定会看到那个秘密密钥值。
现在要说清楚，你并不保证能看到它。读取后看到不是秘密密钥的某个东西的可能性仍然存在。所以为了确保，你总是可以快速验证答案，毕竟，这种情况的前提是你有一种快速验证答案的方法。你可以在经典计算机上做到这一点。最坏的情况是，如果你运气不好，抽样了一个不同的数字，你重新运行整个过程，而你只需要运行几次就变得极不可能了。
最后，我想坦白我一直告诉你的一个谎言，并稍微反思一下加速从何而来，然后强调一个令人惊讶的类比。在此之前，现在可能是说声感谢Patreon频道支持者社区的好时机。制作像这样的可视化课程需要大量的时间。正如你可能知道的，大多数YouTuber通过视频内赞助来货币化他们的内容，但多年来，我一直选择拒绝。我认为这让视频更好，而它不是一个极其昂贵的决定，只是因为足够多的同意这一点的观众通过Patreon直接支持频道。作为交换，我为支持者提供新内容的早期观看，这对于开发它非常有帮助。而且里面还有其他好处。总的来说，如果你喜欢这个内容，考虑加入将意义重大。没有压力。
其中一个重要价值是内容不能免费。总之，回到那三个结束点。谎言是遗漏的谎言。我一直在展示这些带有正负实数值的状态向量，但更一般地说，这些分量可以是复数。现在，我希望在关于物理学的后续视频中解释为什么会这样。总体的想法是，任何时候你处理波，你都会关心幅度和相位，而复数是编码幅度和相位的优雅方式。所以，如果你看状态向量中的一个分量，更完整的图景是它有一个幅度和一个相位。幅度是你平方得到概率的东西。而相位本质上是我们在这里围绕正负值讨论的更一般的版本。改变相位不会立即影响概率，但它会影响状态，而状态又会影响它如何被处理以及它如何与世界互动。
Needless to say，加入一堆复数会给一个已经很复杂的话题增加很多潜在的混乱。这就是我避免它的原因。但对于Grover算法来说，我们可以安全地忽略复数值，因为非常幸运的是，在该算法中，你只会看到正负值。我想让你知道的是，复数值的可用性在其他量子算法中起着至关重要的作用，比如Shor的分解数字算法。
接下来，即使你理解了我描述的关于这个算法的所有内容，也很难总结出加速的确切来源。你开始对这个均等平衡状态应用某个操作的事实，使得说加速来自于并行化对所有输入的运算非常诱人。但正如我在开头提到的，对我来说，那个总结真的感觉不对。而且它肯定会导致误解。正如你现在所知，仅凭那一步并不能揭示密钥值。我将把它留给你解释，无论你是否觉得将第一步描述为并行地对多个输入应用函数是恰当的，或者你是否觉得说平衡状态只是它自己的新事物，而我们拥有的函数总是单独应用于输入，从不一次应用于多个输入，这感觉更好。只是那些输入现在是一种新的东西。
在我看来，对于这个算法，如果你想要一个词的总结，说明加速从何而来，我认为一个更好的选择是毕达哥拉斯。作为一个松散的类比，如果你想从一个单位正方形的一个角走到对角，如果你只能在x和y方向上移动，你需要走2个单位。但如果你可以斜着走，你可以用√2到达。更一般地说，如果你在n维空间中，如果你只能沿着边移动，你必须走n个单位才能从一个立方体的角走到对角。但如果你可以斜着走，你可以用√n到达。
在量子力学的世界观中，不同的可观测状态都代表着某个状态空间中的垂直方向。所以从这个框架来看，经典确定性世界看起来是这样的：你只能接触到这些纯粹的坐标方向。如果你仔细想想，任何时候你进行计算，你的计算机都在某种程度上穿梭于它可用的各种状态之间。算法运行时间就是理解你必须在所有可能状态的空间中走多少步。所以，从这个量子世界观来看，经典状态看起来像纯粹的坐标方向。与量子计算的关键区别在于，你现在还可以使用各种额外的对角方向。
现在要说清楚，这个类比并不太字面化。你应该带着一点点盐来理解它。运行时间不一定看起来像是这个特定状态空间中的旅行距离。但确实，如果你在Grover算法中跟踪状态向量，它所做的是从初始条件缓慢地沿着四分之一圆弧走到目标条件，描绘了一条如果你只能在纯粹的坐标方向上移动将完全无法获得的路径。其效果是提供这个平方根大小的捷径。
作为我让你离开之前的最后一点，常规观众会知道我覆盖这个主题的原因之一是，因为它与我们上期视频中关于两个碰撞的块可以计算π的类比有关。在那期视频中，我们也研究了一个在某个二维状态空间中围绕圆周反弹的点。事实上，它所经历的一系列反弹与我们在这里看到的Grover算法几乎相同。
这里的故事是，当我的物理学家朋友Adam Brown看到那个视频的第一个版本时，他最近一直在研究Grover算法，并立即意识到这两个过程是相同的。现在，我为这个视频有一个完整的计划，我将解释量子计算和Grover算法的背景，以及那个类比。但事实证明，这只是一个糟糕的主意。整个事情只有在你已经理解Grover算法的情况下才真正说得通。所以，现在你已经分别看到了这两个主题，我将留下一个粗略的轮廓，说明这个类比是什么样的。把它想象成一个开放式的家庭作业谜题，任务是自己找出联系。作为一种答案键，我将链接到Adam Brown一篇非常精彩的论文，其中详细说明了那个类比是什么样的。
如果你想了解更多量子计算的基础知识，几年前，我的两位非常聪明的朋友Andy Matusek和Michael Nielsen一起整理了一个很好的学习资源，提供了非常独特的方法来确保你长期记住它。要学习一些基础的量子力学，来自Looking Glass Universe频道的Mathan Yoga Nathan一直在制作一个非常适合初学者的课程。她实际上是很多年前教我Grover算法如何工作的人。而且，坦率地说，本视频的许多内容都归功于她与我的许多有益的谈话。
最后一点，我与Scott Aronson进行了一次谈话，他是一位备受尊敬的研究者，也是该主题的绝对令人愉快的作者。我录制了Zoom通话作为笔记。其中有一小段我想与你分享。
>> 你知道，我有一个写科幻小说的梦想，你知道，我知道高潮场景会是什么，好吧？英雄们将，你知道，运行Grover算法来尝试找到这个加密密钥，对吧？整个世界的命运将取决于他们是否能找到它。好吧，坏人已经包围了他们的基地。你知道，他们正在，他们正在，他们正在砸开墙壁，但Grover算法仍在运行，如果你测量，它只有大约30%的概率给你解决方案。所以，问题是，你现在测量还是让它再运行一分钟，对吧？如果你现在测量，你就知道了，你没有得到它，那么你就失去了一切，你必须从头开始。对吧？所以，这不是一个你可以用任何经典算法来构思的情节。对吧？
>> 对。