🔸学习量子计算、密码学、Space等Web3前沿技术

🔸认领Bounty，赚取赏金

🔸参与Hackathon，获得资助

更多Web3精彩技术分享尽在Dōjō👇

WeChat: @HackerDojo0

量子理论

1. 加法的复杂度

简单地说，量子计算机可以解决一些经典计算机无法解决的问题。要理解其中的原因，我们首先需要考虑解决某些问题需要多少计算工作量。

首先，我们回顾一下第一节中讨论的算法:两个数相加。

  $9213$

$+$ $1854$

$=$ $???$

两个$\boldsymbol{n}$位数的和可以通过一组简单的操作来完成，每个操作只包括两个个位数的相加。为了分析这个程序的复杂度，我们可以考虑一下它需要做多少次基本的加法，以及这个次数与$\boldsymbol{n}$的关系。这个数我们记为$\boldsymbol{c(n)}$。

在最简单的情况下，我们不需要在任何地方进位1，只需要n个基本的加法。在最坏的情况下，我们将需要执行n次进位操作，每一次都需要额外的基本加法。根据这些考虑，我们可以得出结论$\boldsymbol{n≤c(n)≤2n}$.

2. 大O表示法

我们可以把这个结果总结为c(n)随n线性增长。更一般地说，我们可以说，当n很大时，可以找到一个关于n的线性函数，作为c(n)的上界。由于这是一个又长又啰嗦的句子，我们实际上不想经常这样说。相反，我们可以使用“大O表示法”更简洁地表示它。

大O表示法很有用，因为它允许我们比较算法所需的资源/运行时间如何随输入大小变化，而不受特定平台和算法实现的影响。下面是运行时间$\boldsymbol{N}$作为输入大小$\boldsymbol{n}$的函数的常见比例因子的例子;显然，对于一个足够大的问题规模，$\boldsymbol{O(a^n)}$算法的运行时间将超过$\boldsymbol{O(n^b)}$算法的运行时间，其中$\boldsymbol{a}$和$\boldsymbol{b}$是常数。

不同时间复杂度的比较。n是输入的比特数，n是需要操作的次数。

使用这种表示法，上面描述的属性可以简单地表示为$\boldsymbol{c(n)=O(n)}$。这捕捉到了线性行为，而无需纠结于细节。因此，与$\boldsymbol{c(n)=n}$还是$\boldsymbol{2n}$或其他都无关，我们可以简单地说$\boldsymbol{c(n)=O(n)}$。

到目前为止，我们所考虑的问题中有一个隐藏的假设。通过讨论数字的数量，我们已经假设使用了一个特定的数字系统。然而，数字的数量将取决于我们使用的数字系统，是十进制，二进制，还是其他。例如，表示一个数所需的位数$\boldsymbol{n_2}$与表示同一个数所需的十进制位数$\boldsymbol{n_{10}}$相关，即

因为这也是一个线性关系，所以它不会改变我们使用大O表示法表示复杂度的方式。我们同样可以说$\boldsymbol{c(n_2)=O(n_2)}$，$\boldsymbol{c(n_{10})=O(n_{10})}$，甚至$\boldsymbol{c(n_{10})=O(n_2)}$。正是由于这个原因，我们通常可以简单地说数字的数量n，而不需要指定使用什么数字系统。

3. 复杂性理论

复杂性理论研究的是运行任何算法所需的计算量。通过考虑解决给定问题的最佳算法，我们也可以研究解决该问题所固有的计算工作量。对于加法，我们已经知道了最优算法，因此我们知道这是一个$\boldsymbol{O(n)}$复杂度的问题。

乘法可没这么简单。你在学校里学过的两个n位数相乘的算法需要$\boldsymbol{O(n^2)}$个基本运算，比如个位数的加法和乘法。虽然已经发现了具有较低渐近复杂度的算法，但$\boldsymbol{O(n)}$复杂度的乘法运算被普遍认为是不可能的。

即便如此，乘法还远不是最复杂的问题。一个复杂得多的问题是因数分解:取一个n位数并找出它的质因数。在这种情况下，已知的最佳算法的复杂度高于$\boldsymbol{O(e^{n^{1/3}})}$。这里的指数意味着复杂度增长得非常快，使得因式分解成为一个很难解决的问题。

为了用实际的计算时间来证明这一点，我们可以举一个最近的例子。考虑下面的829位数。

如果你尝试使用计算机对这种大小的数字进行加法或乘法运算，你会发现它可以很快地解决此类问题。如果你将计算机的处理器数量乘以它运行的秒数得到core-seconds，你肯定会发现需要的core-seconds远远小于1。

然而，对这个数字进行因数分解需要一台超级计算机和大约2700 core-years，最终得到以下两个因子。

对于更大数字的因数分解，我们很容易达到这样的程度:一个行星大小的超级计算机需要运行整个宇宙的年龄。显然，任何这样的问题实际上都是不可能的。

到目前为止，我们只考虑了$\boldsymbol{n}$位数的数学运算，其复杂度表示为所需的简单个位数运算的次数。然而，复杂性理论可以用于分析任何类型问题的任何计算方法，如搜索数据库、渲染图像、模拟动态或穿越《塞尔达传说》中的地下城。在每种情况下，我们都能够找到一个或一组参数作为输入大小，并使用大O表示法根据输入大小表示复杂度。例如，搜索一个包含$\boldsymbol{N}$个条目的数据库，其复杂度为$\boldsymbol{O(n)}$。

形式上，定义算法的复杂性取决于我们使用的计算的精确理论模型。每个模型都有一组基本操作，称为原语操作(primitive operations)，任何算法都可以用它们来表示。对于布尔电路，如我们在第一节中所述，原语操作是逻辑门。图灵机是艾伦·图灵(Alan Turing)提出的一种假想的计算机形式，我们可以想象一个设备在磁带上执行并操作存储在磁带上的信息。RAM模型具有一组更复杂的原语操作，相当于我们每天使用的计算机的理想化形式。所有这些都是基于离散值的离散化操作的数字计算模型。尽管它们看起来可能不同，但事实证明，它们中的每一个都很容易模拟另一个。这意味着在大多数情况下，计算复杂度并不明显依赖于使用哪种模型。因此，我们可以简单地谈论数字计算机的复杂度，而不是专门描述RAM模型或图灵机的复杂度。

4. 超越数字计算

虽然数字计算机现在占主导地位，但它们并不是唯一的计算形式。模拟计算机在过去也曾被广泛研究和使用。与数字计算机的离散值不同，模拟计算机是基于对连续变化参数的精确操作。有时人们声称这样的设备可以快速解决数字计算机难以解决的问题。然而，这样的主张从未实现。模拟计算机的一个主要障碍是无法制造具有任意高精度的设备。在数字计算机中，离散化意味着误差必须相对较大才能被注意到，然后才能实施检测和纠正这种误差的方法。然而，在模拟计算机中，误差可以任意小且无法检测，但它们的影响仍然可能破坏计算。

如果有人要提出一个理想的计算模型，它可能会寻求将数字计算机的鲁棒性与模拟计算机的微妙操作相结合。要实现这一点，我们可以求助于量子力学。我们已经看到，量子比特是一个具有离散输出0和1的系统，但能够以只能由连续参数描述的状态存在。这是著名的“波粒二象性”概念的一个特例，是量子系统的典型。它们不能被完全描述为离散或连续，而是两者的结合。正如爱因斯坦所说：

量子计算机的原语操作是应用于量子比特的门，因此它既不是模拟的，也不是数字的，而是独特的。在后续章节中，我们将探讨这种独特性质的影响。我们将看到，量子计算机可以解决与数字计算机完全不同的复杂性问题。事实上，量子计算是目前已知的唯一能够在某些任务上以指数级速度超过经典计算机的技术，可能会将计算时间从几年减少到几分钟。我们还将探索量子纠错如何消除任何不完美的影响。

5. 何时使用量子计算机

有了量子比特和量子门，我们可以设计出与数字和模拟经典算法根本不同的新算法。通过这种方式，我们希望找到经典计算机难以解决的问题的解决方案。

其中一种方法是当我们想要确定某个函数的整体性质时。例如，如果我们想找到某个参数$\boldsymbol{x}$的值，使得某个函数$\boldsymbol{f(x)}$是最小值，或者是周期函数$\boldsymbol{f(x)}$的周期。数字计算机上的算法可能使用一个过程，在这个过程中，对各种不同的输入计算$\boldsymbol{f(x)}$，以便获得关于整体性质的充分信息。然而，对于量子计算机，我们可以创建叠加态的事实意味着该函数可以同时应用于许多可能的输入。这并不意味着我们可以访问所有可能的输出，因为对这种状态的测量只会给我们一个单一的结果。然而，我们可以转而寻求诱导量子干涉效应，这将揭示我们所需的整体性质。

这个一般性的描述说明了许多已经被发现的量子算法的工作原理。一个突出的例子是Grover算法，它将遍历$\boldsymbol{N}$个元素项的复杂度从$\boldsymbol{O(N)}$降低到$\boldsymbol{O(N^{1/2})}$。这种平方加速应用在许多可以表示为非结构化搜索的任务中很有用，例如优化问题和机器学习。

Shor算法获得了更令人印象深刻的加速比，该算法分析了因数分解问题的核心周期函数。这就为一个复杂度为$\boldsymbol{O(N^3)}$的$\boldsymbol{n}$位数因数分解问题提供了量子解决方案。与数字计算机高于$\boldsymbol{O(e^{n^{1/3}})}$的复杂度相比，这是一个超多项式级的加速。

另一种使用量子算法的途径是使用量子计算机解决量子问题。我们将在下一章中看到，表示一个量子态需要大量的信息，这些信息随量子比特的数量呈指数级增长。因此，随着$\boldsymbol{n}$的增加，仅写下$\boldsymbol{n}$个量子比特的状态就成为数字计算机的一项棘手任务。然而，对于量子计算机来说，我们只需要$\boldsymbol{n}$个量子比特就可以完成相同的工作。这种表达和操纵量子态的自然能力使我们能够研究和更好地理解感兴趣的量子系统，如分子和基本粒子。

因此，在不同行业中应用和调整量子算法，有希望在商业和科学中实现颠覆性的用例。 这包括药物发现、机器学习、材料发现、期权定价、蛋白质折叠和供应链方面的突破。3特别有希望的是那些经典算法面临固有的缩放限制，并且不需要加载大型经典数据集的问题。对于量子优势，给定问题的答案需要强烈依赖于具有结构的指数级多纠缠自由度，使量子力学演化为一个解决方案，而不需要经过所有路径。然而，请注意，对量子计算机来说“容易”的问题（可在多项式时间内解决）和其他复杂性理论类之间的精确关系仍然是一个开放问题。

这只是对量子算法如何以独特的方式进行计算的一个尝试。关于这些方法的更多细节可以在后面的章节中找到。但首先我们需要超越单一的量子比特，投入一些时间来理解我们将需要的全套量子门。这是下一章的重点。

6. 参考文献

1. https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html

2. Albert Einstein, Leopold Infeld (1938). The Evolution of Physics: The Growth of Ideas from Early Concepts to Relativity and Quanta. Cambridge University Press.

3. Quantum computing is coming to your business | IBM

4. https://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf

5. Image: Cmglee / CC BY-SA (Creative Commons — Attribution-ShareAlike 4.0 International — CC BY-SA 4.0)

关于Hacker Dōjō 

由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjō 会以直播/音频/文字等形式定期组织分享session, 分享主题主要覆盖L1和L2的共识算法，架构，GitHub repo相关内容，包括不限于以下话题：Scroll / Polygon zkEVM、 Eigen的混合证明系统、Starkware、azTec、 Optimism、Zecrey、Aptos、 Move、密码学(零知识证明、公钥加密、哈希函数、格密码) 、 分布式系统、 以太坊协议栈、 量子计算和量子信息、卫星通信系统和航天器系统设计等。

✨Bounty详情及认领进度详情：https://innovative-laser af4.notion.site/174922df15884848b6ac8b57cb4f2fae?v=612e13dc6b9d44dd8197f755abb9fe9c

✨加入 Dōjō 中文社区微信联系：@HackerDojo0

有关DoraHacks

DoraHacks 是一个全球范围内的极客运动，全球黑客马拉松组织者，也是全球最活跃的多链 Web3 开发者平台之一。DoraHacks.io平台使得世界各地的Hacker和开源开发者可以参与黑客马拉松、Bounty、Grant、Grant DAO，以及公共物品质押等加密原生协议和基础设施进行协作并获得资助。到目前为止，DoraHacks 社区的 4000 多个项目已经获得了来自全球行业支持者超过 3000 万美元的资助。大量开源社区、DAO 和 超过50个主要区块链生态系统正在积极使用 Dora 的基础设（DoraHacks.io）进行开源融资和社区治理。

官网：https://dorahacks.io/