Path: blob/main/translations/zh-CN/intro/why-quantum-computing.ipynb
3855 views
我们为什么需要量子计算？
什么是计算机？
既然你已经成功访问了这个网页，你应该已经知道什么是计算机了吧。今天的计算机有许多种形式：从笔记本电脑或智能手机到控制交通信号灯的系统，计算机似乎可以做任何事情！这些系统可能非常复杂和专业，但它们都有一个共同点：计算机根据一些输入信息执行一组指令，来为我们提供一些新的（输出）信息。
我们给计算机的指令需要非常具体和明确。我们称这些指令为*算法，*并且许多关于计算机的研究都是针对不同算法的行为。在本课程中，我们将只考虑最简单的计算机：没有键盘、鼠标或屏幕——只有信息和算法。
对计算机算法归类
要了解量子计算机在现代传统计算机中的作用，我们首先需要了解如何衡量不同算法的性能。
在计算机科学中，我们根据算法使用的资源如何随着输入的大小而增长对算法进行分类。我们称之为算法的复杂度（包括时间复杂度与空间复杂度，我们以下讨论的均为时间复杂度）。例如，确定一个数字是否为偶数的算法只需要检查该数字中的最后一位数字。在这种情况下，“输入”是一个数字，输出是“偶数”或“奇数”。我们将这种算法称其为恒定时间算法，因为算法完成所需的时间不取决于输入数字的大小。不同的计算机可能需要不同的时间才能得到这个结果，但这是由于其他因素而不是输入的长度。
让我们再看一个不同的例子。这一次，输入的是两个等长的数，而问题是把它们加在一起。在这种情况下，输出将是一个新数字。当对两个多位数进行求和时，你在学校大概率学到的一种常见算法是从每个数字中最右边的数字开始，然后将它们加在一起。然后我们向左移动一位数（如果结果大于 9，则进位“1”）并重复该过程。计算机重复此操作直到没有更多数字要添加，算法即结束。
加法的复杂度是怎样的？
此加法算法完成所需的时间...
...随着输入数字的长度线性（成比例地）增长（线性时间）。
...不受输入数字长度的影响（恒定时间）。
...随着输入数字长度的平方增长（二次时间）。
同样，不同的计算机将以不同的速度执行该算法；笔记本电脑可以比人类快数百万倍地执行加法。但是，无论你可以在一秒钟内进行一百万次操作还是只能一次操作，其增长率都是一样的。
最后有一个对我们来说非常特别有趣的例子。假设我有一个秘密号码（例如 PIN），问题是猜对它。在这种情况下，问题的大小是数字的长度。
让我们假设检查答案是否正确的唯一方法是将其输入数字键盘。由于我们没有关于这个号码的信息，寻找这个秘密号码的最佳算法是使用“穷举”方法：这意味着算法没有做任何聪明的事情，只是简单地尝试每个可能的数字。
这需要多长时间？现在，理论上我们可以幸运地一口气猜出答案，但这不太可能。平均而言，我们必须尝试大约一半的可能输入，因此我们算法的运行时间与可能组合的数量成正比。现在的问题变成了：可能组合的数量如何随着秘密号码的长度而增长？
我们在密码中每添加一个位数都会使可能的情况增加到原来的 10 倍。例如，具有 1 位数字的密码有 10 个可能的值（0、1、2、3、4、5、6、7、8 和 9），一个 2 位的密码有 100 个可能的值。假设猜测每个数字所花费的时间相同（无论长度如何），我们可以这样在数学上表示：
ParseError: KaTeX parse error: Undefined control sequence: \cssId at position 1: \̲c̲s̲s̲I̲d̲{T}{T} \cssId{p…你会注意到位数（d）是该等式中的指数，因此我们说这是一个指数时间算法，即运行时间随着输入的长度呈指数增长。
我们为什么这样度量算法？
不同的电脑有不同的长处；在一台计算机上的某些操作可能比另一台计算机更快。通过研究算法运行时间与输入大小的增长关系，我们可以忽略特定设备的细节并实际度量算法，而不是算法和计算机的特定组合。更重要的是，了解算法如何随输入大小扩展也可以告诉我们该算法是否会在可控范围内增长。
让我们考虑一下我们在上面看到的线性时间加法算法。如果我们可以在一秒钟内对两个 10 位数字求和，由于线性增长率，我们应该能够在两秒钟内对两个 20 位数字求和。每多出 10 位数字，我们的计算时间就会增加大约一秒。
相比之下，假设你可以使用上面的指数时间搜索算法在 1 秒内找到一个 10 位数的 PIN。这意味着你的计算机速度足以每秒尝试约 5,000,000,000 次组合。我们预计同样的计算机大约需要 5,000,000,000 秒（约 150 年）才能找到 20 位数的 PIN。再增加 10 位数字会将其增加到大约 150,000,000,000 年（大约是宇宙年龄的 120 倍）。即使是中等大小的输入（在这个例子中约为30位数字），指数时间算法甚至都不能说很困难，而是根本无法执行。
虽然为了尽量简单地讲清楚问题，我们人为构造了一个 PIN 查找的例子，但计算机科学中有许多实际问题，对于这些问题我们目前只有低效的算法。尽管今天计算机的速度是非常震撼的，但即使是最大的超级计算机，这些棘手的问题也可能太难了。
但是，如果我们能找到更高效的算法，哪怕使用相对较慢或不可靠的计算机，这些棘手的问题可能会突然变得在我们掌控能力范围内。这就是量子计算的用武之地。
量子计算如何帮助我们？
到目前为止，我们都在以一种非常抽象的方式来考虑算法，但是执行这些算法的计算机必须存在于现实世界中。无论这些计算机是高性能的微芯片，还是带有纸笔的人类，所有的计算机最终都受物理定律的支配。它们可以执行的操作限制了我们可以创建的算法。
物理学试图找出宇宙中所有事物都遵循的一套规则。大约在 20 世纪初，通过实验室的精密实验，物理学家看到了他们当时的物理学无法解释的奇怪现象。这意味着原有的规则不太准确，因此他们开发了更完整的“量子”物理学以更好地描述这类现象。
物理学家创造了量子物理学来解释他们以前从未见过的现象，而计算机科学家发现他们可以（理论上）利用这种新发现的现象来创建更高效的算法。因此，一些我们认为对于传统计算机来说棘手的问题，对于利用这类新现象的“量子”计算机而言是在掌控范围内的。其中一个问题是因数分解。
假设我们有一个整数 ''。因数分解算法的目标是找到整数 和 使得 。有时这很简单：例如你一眼就能看出 。但是如果 是两个大素数的乘积，这个问题就变得非常困难了。当我们谈论因数分解时，我们将假设最困难（最坏情况）的情景。在下面的代码单元格中，我们为变量 x 指定了一个 250 位数字：
2020 年，研究人员使用经典的超级计算机并花费了约 2700 核年的算力对这个数字进行了因数分解。这是一项巨大的努力，并且至今依然保持世界纪录。我们可以在下面的代码单元中验证他们的结果（万幸，乘法算法是高效的！）：
显示的输出是代码单元最后一行的值。在这种情况下，我们可以看到 p*q == x 的计算结果为 True。虽然没有经过数学证明，但我们很确定传统计算机没有高效的算法来分解这些数字。事实上，互联网的大部分加密原理都依赖这样一个假设：因数分解问题是棘手的，因而经典计算机不可能分解 617 位的 RSA 数字。相比之下，我们知道量子计算机的高效因数分解算法。一旦我们拥有足够大的量子计算机，我们估计可以在一天内分解这些数字。
我们现在处于什么阶段？
现在我们知道量子计算机可以执行更高效的算法。但我们目前拥有的量子计算机体量太小且不够稳定，无法提供相对传统计算机的计算优势。
在一个非常简单的层面上，有两个因素限制了我们的量子计算机可以解决的问题的大小。首先是他们可以存储和处理的数据量，这个我们通常以 量子比特 来衡量。如果我们没有足够的量子比特，我们根本无法存储和处理超过一定规模的问题。第二个是量子计算机的错误率。由于我们只能在精密的实验室实验中看到量子行为，制造量子计算机也是一个复杂的过程。我们现在拥有的量子计算机还很嘈杂，这意味着它经常会出错并在最终结果中引入“噪声”。如果噪声太大，我们从中得到结果将没有任何意义！
目前，我们拥有的量子计算机是实验性的。量子计算机受到量子比特数和错误率的限制，因此其目前可以解决的问题对于传统计算机来说依然可以轻松解决。
但在未来的某个时候，这种情况或许将会改变。我们将达到“量子优势”，这意味着使用量子计算机解决问题比传统计算机更具有实际经济意义。为什么我们有这样的自信？*因为我们通过算法的增长率来度量算法！*我们知道，只要量子计算机继续稳步发展，其最终会取代经典计算机。
如果想在一天内分解一个 617 位 RSA 数字，我们估计需要大约 2000 万个有噪声的量子比特。在撰写本文时，IBM 目前拥有一台 65 量子比特的量子计算机，并计划到 2023 年之前创造一个拥有超过 1000 个量子比特的系统。我们相信还有许多其他算法将在这个里程碑到来之前为我们带来量子优势，但我们依然还有很长的路要走。
我们应该提醒一下自己传统计算机的来历。下图是世界上第一个晶体管，创造于 1947 年。晶体管是现代计算机处理器的组成部分。
Image credit: Federal employee Link, Public Domain.
70 年后的今天，我们的现代计算机芯片可以包含数十亿个晶体管。
在本课程剩下的部分，我们将探索能帮助我们创建更高效算法的量子效应。在本课程结束时，你将能够使用软件库 Qiskit 对量子计算机进行编程以运行其中一种算法。
课后小测
量子计算机最终将...
...计算对传统计算机来说太难的问题。
...替代传统计算机。
...提高传统计算机的速度。